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.↵
↵
↵
↵
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
↵
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.↵