AlexLorintz's blog

About problem "Missing Coin Sum Queries" from CSES
By AlexLorintz, 3 years ago, In English

Hi, I recently came across this problem on CSES: https://cses.fi/problemset/task/2184 and the best solution I found is something like O((N + Q) * sqrt(N) * log(N)), but I'm pretty sure there should be a better solution, because this would probably not fit in 1 second.

We know the greedy way of solving it from its easier version: https://cses.fi/problemset/task/2183/ : we need to sort the array and keep a current answer meaning the smallest sum that can't be produced with the elements 1...i(if we are at the ith element in sorted order), which is of course initialized with 1. When we move from i to i+1, if array[i+1] <= currentAnswer, then currentAnswer gets increased by array[i+1](using 1...i we can get every sum from 1...currentAnswer-1 so adding i+1 helps us get all sums from 1...currentAnswer+array[i+1]-1), else we stop and print currentAnswer as the answer to the problem(we will not be able to obtain currentAnswer further on because all elements in the remaining suffix are already too big).

My idea to solve it for queries was to use MO algorithm with a segment tree on normalized values from the array. The problem gets reduced to something similar with: "Find the first index i such that array[i]-preffixSum[i-1] > 1", so it's easy to keep this information in a segment tree for the current useful elements(from the current query interval) using lazy updates and in order to solve the query the answer can be "binary searched" directly in the segment tree in logarithmic time. I'm eager to hear any solution that would fit in the time limit or any observations about my solution if it's wrong.

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

»
3 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Let’s solve the easier version of the problem (the problem without queries) using a different approach.

Consider all integers in interval [2^i .. 2^(i+1) — 1]. Suppose all integers below 2^i can be formed from the sum of numbers from the given array.

Let C be the sum of all numbers below 2^i. If C >= 2^(i+1) — 1, every number in this interval may be represented as a sum of given numbers. Otherwise we could check if interval [2^i .. C + 1] contains any number from given array. And if there is no such number, C + 1 is our answer. (I took this from a stack overflow post)

How do we answer queries fast:

1) We can use prefix sums to efficiently get sums of numbers less than some 2^i for any interval

2) To tell if there exists a number in [2^i .. C + 1] we can check the smallest number in interval [2^i .. 2^(i+1) — 1]. We can create a segment tree where every node stores the smallest number in [2^i .. 2^(i+1) — 1] for all i in [1 .. 30].

Accepted submission: https://cses.fi/paste/2735dacf1865596d32a4df/

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Indeed, a very nice and smart idea of splitting in these buckets, thank you!

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

    Not able to understand how if all numbers from 0 till 2^i — 1 be achieved using array elements less than 2^i, then all numbers from 2^i till C can also be achieved using array elements less than 2^i (C is the sum of all array elements less than 2^i)..... can this be proved mathematically?

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the easy problem , why this code is working 

Arrays.sort(arr);
long ans = 1;
for(int x: arr ) {
    if(x > ans) break;
    ans += x;
}
out.println(ans);
→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    if you have the current answer ans, and a number you didn't use yet x that is not larger that it, you can generate all numbers from 1 to ans+x-1 because you can use x with 1 to ans-1 from before to generate x+1 to ans+x-1 and just used 1 to x from before for the rest. so ans += x.

    If all the numbers are larger than ans, you're stuck. and the cleanest way to check that is to sort the elements and loop from the smallest to the largest

    → Reply
»
20 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I think there is another solution

It's obvious that for evey time we do the “add operation” ,The new answer is at least twice as large as $$$a_i$$$ 's

So if we use the Persistable segment trees to maintain the value , for every question ,we binary search the max value that is small than now ans, next add another value to the ans

This solution has the same time complexity

→ Reply