problem-solved's blog

why does this soution works so fast for problem 246E(cf 151 div2 E) ?
By problem-solved, 12 years ago, In English

kawatea's solution http://codeforces.net/contest/246/submission/2621642 i think it's brute force because this solution uesd a "for" loop to find distinct names of k sons

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

»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

It caches every query. It seems that there could not be many distinct large queries.

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

for (i = p; i < q; i++) { if (f[w[z][i].second] == 0) { sum++; f[w[z][i].second] = 1; } }

In the worst case this part works (summary) in .

Sample:

K+M -> K+M-1 -> K+M-2 -> .... K

K -> 1,2,3, ..., K-1

K+1 -> some chain of length 1

K+2 -> some chain of length 2

...

K+M -> some chain of length M

Prove:

Each w[z][i] will be viewed at most times. To view it k times, we should ask about layer z from k different ancestors of w[z][i]. How to get k different pairs <p,q>? For each of these k ancestors we have to add a chain from it to layer z. Lengths of these chains will be at least 1,2, ... k. Sum is at most n. So k is at most .

→ Reply