Ishan.nitj's blog

Need help with Icpc regional problem
By Ishan.nitj, history, 7 years ago, In English

We were trying to solve this problem using divide And conquer approach but could not solve it. Any clue on how to do it?

https://www.codechef.com/AMR16MOS/problems/AMR16B

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

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

Hint : in the second round divide the array into quarters and swap the 2nd and 4th quarters. Similarly do for eighths in the next round and so on for \ceil{\log(n)} rounds

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

Any hints for AMR16I ?

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

    You can see the comments in this blog

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

    it can be easily seen that the ith pile has coins in the order of power of 2. thus it is not required to create all N piles. just create piles till the last pile is lesser than or equals to X.

    the query follows this simple rule = move from the larger pile till you reach a pile Pi such that Pi<=X. take this pile and reduce X (X = X-Pi） keep on performing this.

    if you're able to reach X=0. then the sum is formed.

    The proof for such a technique lies in the fact that Pi is always greater than sum of all piles till i-1.

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

    I am the setter of this problem. :) The given sequence is superincreasing. The subset sum problem on such a sequence can be solved in a greedy manner. Move from largest to smallest value of the sequence. Let X be the required sum. If the largest value <= X, then you HAVE to take it (think why? Hint: each element in a superincreasing sequence is greater than sum of all previous elements). After you traverse the entire array in this manner, if X == 0, then answer is YES else NO.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Are we allowed to use the same pile more than once . For example sequence 1, 2, 5, 12 and 22 . X = 10. What's the answer in this case.

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

    This link contains a formal proof for the greedy algorithm.

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

Think about N=2^x, where X is a positive integer, for example x=3, therefore N=8

1 2 3 4 | 5 6 7 8

the numbers from 1 to 4 are no longer related to 5 through 8, and viceversa, which means you can now solve the problem for [1,4] and for [5,8], so it's the same as having N=4 (two times).

Now think about cases where N is not a power of 2 :)

→ Reply