### intptr's blog

By intptr, history, 4 years ago, ,

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.

• 0

 » 4 years ago, # |   0 Auto comment: topic has been updated by intptr (previous revision, new revision, compare).
 » 4 years ago, # |   0 Auto comment: topic has been updated by intptr (previous revision, new revision, compare).
 » 4 years ago, # |   0 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).
•  » » 4 years ago, # ^ |   0 By total length i mean total count of current dots.
•  » » 4 years ago, # ^ |   0 I understand now, he saves the data in index i + 1 in order not to access -1 element when i = 0.