How does the algorithm for Contest 316 C problem work?

Revision en5, by intptr, 2015-08-16 16:57:23

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.

#### History

Revisions

Rev. Lang. By When Δ Comment
en5 intptr 2015-08-16 16:57:23 89
en4 intptr 2015-08-16 16:56:35 8 Tiny change: 'ate a = ok[one] ( True ) ' -> 'ate a = ok(1) ( True ) '
en3 intptr 2015-08-16 16:55:51 6 Tiny change: 'te a = ok['1'] ( True )' -> 'te a = ok[one] ( True )'
en2 intptr 2015-08-16 16:55:27 2 Tiny change: 'te a = ok[1] ( True )' -> 'te a = ok['1'] ( True )'
en1 intptr 2015-08-16 16:54:26 787 Initial revision (published)