PikMike's blog

By PikMike, history, 12 days ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +55
  • Vote: I do not like it  

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

Can't understand C's explanation.

»
12 days ago, # |
  Vote: I like it +29 Vote: I do not like it

Alternately F can be solved with Divide and Conquer Optimisation as well.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I seem to get TLE with Divide and Conquer Optimization , was any pruning required to pass the time limit ?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's Complexity O(n^2logn)?

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem E can also be solved offline with an O(n) memory complexity, by sorting the queries w.r.t k and solving all queries with the same k together using dynamic programming.

Intuitions about the time complexity:

  1. If all queries have the same k, time complexity will be O(n)
  2. If all queries have different k (from 1 to 1e5), then first query will do n/2 iterations, second one n/3 iterations and so on. Overall complexity will be n * (1/2 + 1/3 + ... + 1/100000) = constant

I don't know exactly how to calculate a generalized upper bound for the time complexity, but I had the intuition that it would fit in time using this approach

Implementation: 26497630

  • »
    »
    8 days ago, # ^ |
    Rev. 4   Vote: I like it +6 Vote: I do not like it

    (1/2 + 1/3 + 1/4 + ... + 1/n) = logn

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh yes you're right, it's logn. I got confused about it. Thanks.