parth015's blog

Help needed in following problem

By parth015, history, 8 years ago, In English

Hello everyone, I needed help in following problem. From editorial it is not clear. Link of problem is(http://mirror.codeforces.com/contest/165/problem/C)

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
  • Let Si be the amount of ones in the prefix 1..i, so for a substring l..r to contain exactly k ones, we have Sr - Sl - 1 = k. For this problem, we are interested for every position i in how many positions p we have Sp = Si + k.
  • We can precalculate Lx and Rx, the first position i with Si = x and the last position i with Si = x.
  • So now for every position i we must simply do the subtraction RSi + k - max(LSi + k, i + 1) + 1.

Check code for further clarity: String Problem

→ Reply