11194 - Stone Grid

[JL]

This last sample case outputs 4:

Code: Select all

3 2 4
1 1
-1 -1
1 1

Which 2 of these are not a solution and why?

Code: Select all

0 0
-1 -1
0 0

0 0
-1 -1
1 1

0 0
-1 -1
2 2

1 1
-1 -1
0 0

2 2
-1 -1
0 0

1 1
-1 -1
1 1

[Erik]

Hi,

I got the same question and sent a clarification request, which is not answered yet.
Anyway I solved it now. It's about the interpretation of

For the same reason, they do not want the final arrangement to have more stones than the initial grid configuration does.

It means that in the end no cell may contain more marbles than it had initially. Hence, solutions

Code: Select all

2 2
-1 -1
0 0 

0 0
-1 -1
2 2 

would be considered wrong.
I got Accepted this way.

Cu, Erik

[sclo]

It turns out that I have badly misintepreted this problem during the contest, and that's why I keep getting WA. They should rewrite the problem statements to make it a little more clear.

So L is the maximum total number of stones allowed in an arrangement, and each cell can't have more stones than what it has in the initial configuration.

I'll have to rewrite much of my program to fix this.

[rushel]

A small hint on a problem please.
thanks

[sclo]

A small hint:
Each cell is either odd or even. A cell (i,j) is odd(even) iff (i+j)%2 is odd(even).

A bigger hint:
Think about connected components.
There exists a sequence of moves to move any stone on odd(even) cell to any other odd(even) cell in the same component, leaving the number of stones on all other cells unchanged.

Another hint:
If we remove any stones from an odd(even) cell, we must remove an equal number of stones from an adjacent even(odd) cell.

My hints are enough to solve this problem.

[rio]

Could someone verify my IO ? Thanks in advance.
Input:

Code: Select all

5

1 2 0
-1 1

3 2 4
 1  1
-1  1
 1  0

4 4 20
 8  9  0 -1
-1  2  1  9
 9  2  3  6
 5 -1 -1 -1

4 4 10
 3  9  0 -1
-1 -1 -1  9
 0  2  3  6
 5 -1  2 -1

4 4 14
 9  9  0 -1
-1 -1 -1  9
 7  2 -1  6
 5 -1  2 -1

Output:

Code: Select all

0
4
2784
18
65

[LayCurse]

>rio
My AC program gives the same output as yours.

[rio]

Thanks LayCurse. I found the bug and got AC. My code was overflowting with big test cases.

----
ところで十号館の住人だったりする？