JawbreakerProblem code: LX |
All submissions for this problem are available.
Jawbreaker is a one-person game. You start with a square of dimension n*n, composed of small colored stones. One move consists of indicating one stone. Then, the maximal possible connected group of stones the of the same color, containing the indicated stone, is destroyed. The destroyed rocks disappear, and all rocks which have empty space below them drop to a lower row. If any column is left empty, rocks that are to the right of it are shifted accordingly to the left. When a group of k stones is destroyed, you score k2points. Your task is to maximize the total score.
Input
First, 50 <= n <= 100, the size of the starting board. Then, n lines follow, n characters long each, containing a description of the board, with up, down, left, right oriented just as we see it on a computer screen (upper rows first, left columns first). The color of each stone is described by one character, from '0' to '9'.
Output
First, output t, the length of answer. The following t pairs of integers are a sequence of moves. Each pair i,j defines one move, i being the 0-based number of a column (column 0 is the one most to the left), and j being the 0-based number of a row (row 0 is the lowest one).
Example
Input: 3 202 202 110 Output: 3 0 0 2 0 1 1 Moves: 202 202 110 ..2 202 200 ... 22. 22. Score: 22+32+42
Tests
The size of the tests will be chosen uniformly between 50 and 100, and then the number of colors will be chosen uniformly between 4 and 10. The colors of the rocks are chosen independently at random.
| Date: | 2009-12-30 |
| Time limit: | 1s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
1 second is too tight for the
1 second is too tight for the tiebreaker isnt it ?
I thought all future tiebreakers would have >= 5 secs.
I really feel that I'm
I really feel that I'm justified - input data are really small.
is there no option to delete
is there no option to delete a commnt ??? :(
Sumit, you are not supposed
Sumit, you are not supposed to post ur code in the comments section. Read FAQ section for any complier issues. Admins, please remove the code from above comment.
Are the stones with same
Are the stones with same color that have one common point (diagonally positioned) considered "connected group of stones"???
The example does not explain that either.
My solution which only prints
My solution which only prints 0 0 - It does only this move. This takes 2.36 seconds. Any reason for this behavior.
Admin, What does wrong answer
Admin,
What does wrong answer mean in the context of this problem.
Wrong answer means your
Wrong answer means your output is invalid.
sorry - squares are connected
sorry - squares are connected if they share edge
@admin i read the faq and
@admin
i read the faq and then tried to delete but there was no delete option.
Thanks fror deleting it
can you please tell me what is wrong with my piece of code???
No, this is a contest. You
No, this is a contest. You won't be given hints as to what you have done wrong until perhaps after the contest.
Is there an optimum solution
Is there an optimum solution for each and every test case possible,
and hence there should be same score of all the solutions?
What is to be done to get my solution accepted?
The aim of a challenge
The aim of a challenge problem is to score as highly as possible; achieving the optimal solution shouldn't be possible. All you need to do to get accepted is to output a value sequence of moves. Wrong answer means you are choosing a square that does not have a stone in it.
Hey...i'v a doubt. when some
Hey...i'v a doubt.
when some rocks dissapear and some rocks have some empty space beneath them then they fall to a "lower" level or the "lowest" level possible...
like in the case below
0 0 0
0 1 1
0 0 1
0 1 1
1 1 1
the output will be...
.......
0 0 0
0
0 0
0
or...
.......
0
0
0 0
0 0 0
and I hav a similar doubt about the column shift...
plz help me....
They drop as far as possible.
They drop as far as possible.
thanx....and what about the
thanx....and what about the sideway shift...do the shift to the leftmost position possible or just to one left position...
1 0 1 0 1
0 0 0 0 0
the output will be
.........
1 1...1
or
.........
1 1 1...
thanx in advance...
Same thing, All empty columns
Same thing, All empty columns are removed.
in that case the table
in that case the table shown(in the example in given question) after first move is wrong....
No it isn't. There aren't any
No it isn't. There aren't any empty columns, so nothing moves left.
The sample moves don't look
The sample moves don't look right in a non-monospace font. After the first move, the "2" in the top row is still all the way on the right:
anyone know html tag for
anyone know html tag for fixed-size font?
Use <code> (with br tags in
Use <code> (with br tags in it).
..2202
200
can any stone be connected
can any stone be connected diagonally , basically is it 8 point connection or 4 point connection ?
That has already been
That has already been answered.
ok ! got it , thanks !!
ok ! got it , thanks !!
The relative scores displayed
The relative scores displayed in the My/All submissions page appear to be incorrect (eg it is saying 0.999 rather than 0.98, etc).
my score at score board is
my score at score board is .961, but in my submission page it is 0.99. can you explain what is the problem?
I just mentioned that in the
I just mentioned that in the comment above yours :P The scoreboard is correct, the submission page is incorrect.
you = admin :P i did not
you = admin :P i did not refer to you, i just wanted to strengthen ur comment :)
can anybody explain me the
can anybody explain me the output in the above example plz?????
Nice, Pratik.
Nice, Pratik.
pieguy: a) Congrats. b) How
pieguy:
a) Congrats.
b) How on EARTH did you do that in 0.21 seconds?
Yes, I'm wondering about that
Yes, I'm wondering about that too. And he made only 6 submissions which means any test data based optimizations were not done. Just Brilliant work!
I think pieguy is a person
I think pieguy is a person from the future ;-) Seriously, amazing work pieguy!
And Ajay, Stephen, Pratik, Josh, s.max, and Tomasz and all other algorithmic overlords did pretty well too!
Performing hundreds of
Performing hundreds of submissions is no substitute for writing a better algorithm. And although I know I could get better results by tailoring my solution to the server's specific test data, I think that defeats the purpose of the competition. As for the 0.21 seconds, I suppose that was a bit of showboating, as I did have a algorithm that took advantage of the extra time for a 1-2% increase in score.
My algorithm:
Call A the most abundant colour and B the next most abundant (in my code I relabel them 0 and 1, respectively).
Step 1: remove some of colour B in such a way that all of colour A will be connected in step 3
Step 2: remove all colours except for A and B
Step 3: all of colour A is connected, remove colour A
Step 4: only colour B remains, remove it
Hm, nothing completely
Hm, nothing completely extraordinary then. I did something similar, though spent a lot of extra time maximising the score before only colours A + B left. Just couldn't work out a work a way of connecting A without removing too many Bs. I guess my problem was that I swapped step 1 and 2, which perhaps meant too many Bs were removed later.
I swapped step 1 and 2 as
I swapped step 1 and 2 as well.
My algorithm to connect A when only A,B were left: In each iteration I mark all components of color A, and remove the component of B which has neighbors in most number of different components of A. I break the ties by choosing the smallest component of B if there are multiple options.