AlexLorintz's blog

By AlexLorintz, 4 months 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

»
4 months 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/

  • »
    »
    4 months 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!