I had the same problem and my mistake was treating n as always a power of 2, thus doing some extra work in the last step. Revise your code for that. Hope this helps.

Sample is correct, find the mistake in your logic.

6 10
ababaabaab
ababbbbbbb
baaaaababb
bbaaabbaba
bbbbabbabb
abbbaaaaaa
answer: 14
Good luck!

lual.ru

Edited by author 08.09.2013 18:45

Maximum matchings in bipartite graph is almost enough to solve it + some "magic" :)
Maybe maximum flow algos' works better here...
My complexity was O(V*E), 0.3sec

Just gredy.

There was incorrect checker, it checked with precision 10^-4.
It fixed now, all solutions were rejudged, 7 authors lost their AC.

Consider that the sum of swim,bike and run is a const number,so we can let the total s=1,then we can solve it for 2D convex hull alogrithm rather than 3D.

You should use reciprocals of speeds (preferably multiplied by some constant) as coordinates, but not just the speeds. After applying such an "inversion" to the points in your example, the last one jumps out of the convex hull formed by others.

use float instead of int for s and you will get AC

Try this test:
azqhazqhazqhazqhazqhazqhazqhazqhazqhazqhazqhazqh

My answer:
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++.<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.

I rewrote my solution - got time limit on 10th test - good, but I think it's may be bug (or feature?) in 3 test (because i changed only 1 feature in input/output code).
Can anyone give me this (3) test?

Edited by author 30.08.2011 06:23

Edited by author 30.08.2011 06:26

cannot get it....

BTW, you also need that if you have only one row or column, you can only take half of the stones

Interesting. But I also can't proove it! How to get this idea more formally? Let's talk about this.

Thank you

I still can't get it,especially for your graph,I hope you can explain it more clear.
Thanks.

Here comes the proof of why you can't remove all stones but one if M or N is divisible by 3.
Let us paint all the grid nodes for which the sum of their coordinates is divisible by 3 ((x + y) mod 3 = 0) in red, all ones meeting the (x + y) mod 3 = 1 condition in green, and the rest in blue. Let us also denote the amount of stones placed in red, green and blue nodes as R, G and B respectively.
Obviously, each turn two stones lying on nodes of different colors turn into one stone lying on the third color. So, two of the R, G and B values get decreased by 1, and the third one gets increased by 1.
This process has an invariant: parities of (R - G), (R - B) and (G - B) don't change! At the start of the game with M or N being divisible by 3 R, G and B are equal. So all the three differences listed above stay even till the very end, and it's impossible to get the (1,0,0), (0,1,0) and (0,0,1) combinations of R,G,B, therefore the game can't be finished with only one stone. Q.E.D.
P.S. My English could have some flaws, i know.