In 1500A - Поеду домой, how can we construct a sequence of $$$n$$$ integers such that the answer is NO.
# | User | Rating |
---|---|---|
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 |
# | User | Contrib. |
---|---|---|
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 |
In 1500A - Поеду домой, how can we construct a sequence of $$$n$$$ integers such that the answer is NO.
Name |
---|
We can construct an increasing sequence such that each element is strictly greater than sum of previous numbers . But that will increase exponentially.
Well, that won't fulfill the constraint as $$$a_i <= 2.5*10^6$$$ needs to satisfy
largest $$$n$$$ value test case in problem with answer "NO" was $$$1572$$$ . $$$n$$$ in worst case could be $$$2*10^5$$$ . So at an average numbers are around $$$12.5$$$ distance apart (for worst case $$$n$$$) which increases difficulty of finding such sequence satisfying the constraint.
Not completely sure but I don't think we can, it is guaranteed to have an answer if n is greater than some limit (you can calculate that), because of the pigeon hole principle.
Yeah, I know. But, for N <= 1572, we can have NO. And we need to find a sequence having the answer No for those N
The sequence of alternate prime nos. (2, 5, 11, 17...) works! Edit: Changed 19 to 17
You're looking for a Golomb ruler. There are many ways of constructing such a ruler (apart from the one mentioned in the link I just gave), for instance:
n = 4. a = {1, 10, 100, 1000} Clearly works.
I mean, satisfying the problem constraints($$$a_i <= 2.5*10^6$$$)is needed