sensibilityness's blog

Pick elements from an array so that their sum lies within an interval
By sensibilityness, history, 5 years ago, In English

Update: My coach got back to me and sent me the constraints! $$$w_1, w_2, \ldots$$$ are the elements.

Subtask 1: $$$n \leq 20; w_i \leq 10^9; l, r \leq 10^{15}$$$

Subtask 2: $$$n \leq 40; w_i \leq 10^9; l, r \leq 10^{15}$$$

Subtask 3: $$$n \leq 80; w_i, l, r \leq 10^5$$$

Subtask 4: $$$n \leq 200000; w_1 = w_2 = \ldots = w_n \leq 10^9; l, r \leq 10^{15}$$$

Subtask 5: $$$n \leq 200000; w_i = i; l, r \leq 10^{15}$$$

Subtask 6: $$$n \leq 200000; w_i, l, r \leq 10^{15}; r - l \geq \max w_i - \min w_i$$$

Update: A helpful user has sent me an online judge link. I can start researching from here. Thanks a lot! Unfortunately, the trollish attitude of downvoters is something I have to put up with. It's a permanent aspect of Codeforces.

Edit: The constraints weren't included in the original problem statement! My coach and I failed to solve this problem. I have two RAR archives of test cases for you to judge the validity of your solution. Any suggestions are welcome.

Given an array of $$$n$$$ positive integers and an interval $$$[l, r]$$$, you need to pick some elements from this array so that their sum lies within the interval $$$[l, r]$$$.

Input:
The first line contains three positive integers $$$n$$$, $$$l$$$ and $$$r$$$. The second line contains the elements of the array.

Output:
Print one line containing an integer denoting the number of elements chosen and another line containing a space-delimited list of elements sorted in ascending order.

Note: If there are multiple solutions, print any of them.

Sample test case:

Input:

7 80 100
10 20 30 40 50 60 70

Output:

3
20 30 40

Edit (to address this comment): This output is valid as well:

2
40 60
  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Why the downvotes? Is the problem too easy for you? It was a homework problem and my teacher didn't even know how to solve it. I have taken the time to translate the problem statement into English and flesh out the problem statement with more details. I detest such unhelpful behavior. I don't care about imaginary internet points, they are pointless. I am still a green hand when it comes to competitive programming. Do you have some "sensibilityness"? Why are you invalidating such a genuine and honest attempt at asking a question? Everyone has to start somewhere, right?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

BTW What are the CONSTRAINTS for the problem??

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

You can do dp similar to knapsack.

dp[i][j] = true/false if there exists or not a subset having the sum i, with the first j elements

Also, you could post some constraints too on n, l, r.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it -16 Vote: I do not like it

    Update: This comment is outdated! Downvote this comment to your heart's content!

    Thanks for your helpful comment. I'll implement your idea and keep you posted. The constraints weren't included in the problem statement. In fact, I had to refine the problem statement so that it is somewhat acceptable to read.

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

      The problem with knapsack is that it works only if the maximum value for an element is small enough to consider O(maxval^2). You might need something else if this isn't the case.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you sure that "pick some elements" is the right term and it isn't "pick a sub-array"?

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

This problem is NP-hard. In the subcase where L = R, the problem becomes precisely the NP-complete subset sum problem.

This is why everyone is asking about constraints on the problem. If you don't have any constraints to help make it easier (e.g., the numbers aren't very large, or N isn't very large, or the test data are somehow weak), then your only option to solve the problem is to prove that P = NP.

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

Subtask 1: just look at all the possibilities.

Subtask 2: use meet in the middle: find the smallest sum greater or equal to $$$l$$$ by looking at all the possibilities of the first and second half of the array, sort them and then you can use 2 pointers or binary search.

Subtask 3: knapsack, already described in another comment.

Subtask 4: just check if $$$n*w_1 \geq l$$$ and at least one of $$$r-l \geq w_1-1$$$ and $$$r$$$ $$$mod$$$ $$$w_1<l$$$ $$$mod$$$ $$$w_1$$$ is true.

Subtask 5: you can get any number between $$$1$$$ and $$$\frac{n*(n+1)}{2}$$$ by just taking greedily from largest to smallest.

Subtask 6: identical to IOI 2016 Molecules. You can sort the array and then you can prove that if there is an answer a continuous subarray is an answer.

→ Reply