In 1500A - Going Home, how can we construct a sequence of $$$n$$$ integers such that the answer is NO.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | djm03178 | 153 |
In 1500A - Going Home, 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