10411 - Another Game of Tetris

Moderator: Board moderators

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

10411 - Another Game of Tetris

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
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
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

10411 Another Game of Tetris.

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).

Andrey.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10411 - Another Game of Tetris

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.
Check input and AC output for thousands of problems on uDebug!