Blocks

Ivan_Metelsky 2004-12-12 22:06:26 UTC #1

It is written in problem statement, that "there are no more than 2 blocks of each color".

But in sample input there is a color matrix

1 2 3
1 1 1
1 1 1

where there are 7 blocks with color 1.

Is everything correct?

Adrian_Kosowski 2004-12-12 22:53:55 UTC #2

The example indeed didn't comply to the restrictions in the description. Thanks, I've fixed it.

kfas 2005-01-20 22:32:31 UTC #3

I can see that Tomek Czajka solved the problem first.
Congratulations!

I have a question:
Can there be a simpler version of the problem put on SPOJ, where the colors are all different. I think I can solve it then and It could be an easier start for BLOCKS if I could test my ideas on the simpler version.

Best regards,
Adam

tomek_sof 2005-01-20 23:02:22 UTC #4

Thanks!

Test your ideas theoretically!

This was a great problem to spend hours thinking about, thanks problemsetters!

Adrian_Kosowski 2005-01-21 00:18:34 UTC #5

Our pleasure , glad you enjoyed solving it.

Perhaps it will be done one day. But there really isn't much to test in the simpler version - if you know you can solve it, then you can .
If you are in doubt, I think that a very simple random test case generator is enough to verify your ideas (I used this code for some of the test data). Run with e.g.: echo "20 400 10 0 1 100 " | ./blockgen to obtain a test case for the simpler version of the problem.

Guest 2005-01-21 05:31:06 UTC #6

Please, tomek, can you tell me something about your idea?

tomek_sof 2005-01-21 23:45:24 UTC #7

My solution is described in the topic "Problemset 5".