We were trying to solve this problem using divide And conquer approach but could not solve it. Any clue on how to do it?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
We were trying to solve this problem using divide And conquer approach but could not solve it. Any clue on how to do 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
Any hints for AMR16I ?
You can see the comments in this blog
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.
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.
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.
This link contains a formal proof for the greedy algorithm.
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 :)