10411 - Another Game of Tetris

[Ghost77 dimen]

The request is stated below:

Find a solution with no more than 10,000 operations to achieve the goal, i.e clean up the whole board.

What kind of searching stategy can have it done well???

By the way, the problem 197 is also complicated like this or even harder.

I guess the main ideas of them are similar.

Would anyone like give me some clues?Thanks.

[Larry]

There's a simple filtering that makes this problem computationally a lot simpler. If a column is really tall, think about how you would get rid of it..

[Ghost77 dimen]

Filter some situations can reduce the judge time and the operations.

But I have no idea how to generate a program to solve this problem.

That is, I don't know how to search in this complicated problem.

[Larry]

Alright, another hint then:


There's a condition that holds for a column that has height over 4. How would you reduce it to lower than height 4?

[Yarin]

Problem 197 and this problem is completely different. 197 is a brute force search over all possible states, which is feasible. In this problem, no such search is necessary since you don't need the optimal solution.

I made a greedy solution - find the lowest column, try placing all pieces in all rotations so this column is filled (and no holes appear). Select the combination which flattens all the columns most (sum of the squares of neighbouring column differences). In case of a tie, choose at random (important, didn't work otherwise). Maybe not the best solution, but it worked (and I'm pretty sure it will always work under the problem constraints).

[Ghost77 dimen]

I also use greedy method to approach a solution.

But I got OLE.

My strategy is :

1. Find the lowest column, and search for i <- 1 to 19 operation

2. If the operation can fill in this column without further spaces, goto 3

3. Set some attribute of the situaction.

One is the rate of eveness 1 2 1 0 --> 4 ; 1 1 1 1 --> 0

;another is the difference of height between the highest column

and lowest one.

4. Finally, choose the best one operation ,according to the attributes,

to fill in.

Hmmm~~, how about the stategy above?

Where can be improved or any algorithm is better?

[Larry]

There is a filter that basically lowers all the columns so that the end result will be n columns, each with less than 4 in height, which is probably optimal in what it suppose to do. PM me if you want more..

[Andrey Mokhov]

Hi, everyone!

I'm trying to solve this problem, but I can't understand this phrase

For each column, the occupied blocks should be successive starting from bottom at ANY TIME, so the board can be represented by an array of n integers indicating the 'height'(number of occupied blocks) of each column.

What will happen if I will make a 'hole' with my move, i.e. I'll put such a piece that under one of its squares there will be an empty square? Will that empty square be considered to be filled or I just can't do such a move?

And another question. What if a puzzle has no solution? I mean for exapmle such an input:

Code: Select all

2
0 1

We can't here clean up all the board as all the pieces have even number of squares in it (four).

Thank you in advance.
Andrey.

[brianfry713]

You can't make a move that will create a hole.

All puzzles have a solution. I used an algorithm similar to Yarin's and got AC in 0.02 sec. I also checked that there is never a case where n is even and the sum of the heights is odd. There is also never a case where n is divisible by 4 and the sum of the heights modulo 4 is 2.