How does the algorithm for Contest 316 C problem work?
Difference between en3 and en4, changed 8 character(s)
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.↵
↵
↵
↵
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[one](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 English intptr 2015-08-16 16:57:23 89
en4 English intptr 2015-08-16 16:56:35 8 Tiny change: 'ate a = ok[one] ( True ) ' -> 'ate a = ok(1) ( True ) '
en3 English intptr 2015-08-16 16:55:51 6 Tiny change: 'te a = ok['1'] ( True )' -> 'te a = ok[one] ( True )'
en2 English intptr 2015-08-16 16:55:27 2 Tiny change: 'te a = ok[1] ( True )' -> 'te a = ok['1'] ( True )'
en1 English intptr 2015-08-16 16:54:26 787 Initial revision (published)