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.com/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.

Auto comment: topic has been updated by intptr (previous revision, new revision, compare).Auto comment: topic has been updated by intptr (previous revision, new revision, compare).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).

By total length i mean total count of current dots.

I understand now, he saves the data in index i + 1 in order not to access -1 element when i = 0.