In 1500A - Поеду домой, how can we construct a sequence of $$$n$$$ integers such that the answer is NO.
In 1500A - Поеду домой, how can we construct a sequence of $$$n$$$ integers such that the answer is NO.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3390 |
| 6 | Um_nik | 3387 |
| 7 | tourist | 3384 |
| 8 | heuristica | 3322 |
| 9 | turmax | 3319 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 142 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | maroonrk | 133 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
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 \lt = 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 \lt = 2.5*10^6$$$)is needed