11194 - Stone Grid

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
JL
New poster
Posts: 1
Joined: Sun Mar 04, 2007 12:51 pm

11194 - Stone Grid

Post by 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
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by 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
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel »

A small hint on a problem please.
thanks

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by 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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by 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
New poster
Posts: 11
Joined: Sun Feb 25, 2007 3:14 pm
Location: Kyoto, Japan

Post by LayCurse »

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

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

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

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

Post Reply

Return to “Volume 111 (11100-11199)”