sliviu's blog

By sliviu, history, 4 months ago, In English

Could someone please help me with this problem? I've been thinking about it for over a week but I still have no idea how to solve it. Thank you

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

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm not sure what the official solution is, but here's a sketch for a O(q log^2 n log 1e9) solution.

  • We need to find the smallest x such that x > 1 + the sum of all coins < x . (where the sum is taken over all coins in the query subarray) (See https://cses.fi/problemset/task/2183 for a related problem )

  • We can use a tree similar to merge sort tree to calculate the sum of all coins < x in a subarray [l,r] and also get next coin value which is greater than x.

  • Now we initially let x = 1. Then we keep setting x to to the smallest coin value greater than 1 + (sum of all coins <= x) until we satisfy x > 1 + the sum of all coins < x . Note that each time our value of x at least doubles, and so this finishes in a logarithmic number of steps. Then our answer is the 1+(sum of all coins < x)

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    TLE. I've tried optimising it (in vain).

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

    Could you elaborate and how the tree similar to merge sort tree would work? I dont see a way of retrieving the values fast enough

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Offline processing only needs Fenwick tree and $$$O(n\log n+q\log n\log10^9)$$$.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      this is my online solution with $$$ O (Q log N * 31 ) $$$ time complexity using normal segment tree for finding range minimum and also prefix sum, in ith bit bucket but it's still tle on two test cases.

      So i guess offline solution is the only option for solving this. or might be optimisation will be possible using dp with segment tree to store the range query as we only need is range minimum, so we could avoid recalculation.

      Also thanks for your solution.

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

    You can also optimize this solution to get O(nlogn + q*(logn)*log(1e9)) with online query.

    You have to replace the merge sort tree with a Persistent Segment Tree. You might need to compress the values in order to fit the values in the segtree.

»
4 months ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

You can split numbers, According to highest powers of 2 or highest set bit and then you know that if you could add two numbers from that particular power set, you could get another next power of 2, so in total you can use set to maintain this, total complexity will be n logn log a_i.
It's just speed up of normal missing coin, here we don't need to process all coins that we do in sorted order.
Will explain in detail later.