intptr's blog

By intptr, history, 4 years ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by intptr (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by intptr (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By total length i mean total count of current dots.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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