Looking at the algorithm for the problem C in contest 316 I couldn't figure out how it works so I decided it could be a good idea to ask for an explanation here.
Reference to the solution is here : http://codeforces.me/contest/570/submission/12523751
Let's assume an input of ".b..bz...."
After precomputation the array named 'ok' looks like this
[0,1,0,1,1,0,0,1,1,1] num = 7; group = 3
Now we start queries :
1st one is [1,h] :
We evaluate a = ok(1) ( True ) and b ( False )
thus (a != b) = ( True )
Then num-- => num = 6
How does decreasing the total length by one make sense here?
In general could someone give a good explanation for this implementation? I understand what must happen to solve the problem but my solutions end up being too long/convoluted.
There is no total length in the solution. num is current number of dots, group is current number of dot groups. a == is the old value dot? b == is the new value dot? num is recomputed in an obvious way; to recompute group, we need to know whether the neighbour letters are dots (draw a picture for each possible case to understand better).