Блог пользователя hossainzarif

A problem(inspired from round 707 div1-A)
Автор hossainzarif, история, 3 года назад, По-английски

In 1500A - Going Home, how can we construct a sequence of $$$n$$$ integers such that the answer is NO.

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

We can construct an increasing sequence such that each element is strictly greater than sum of previous numbers . But that will increase exponentially.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -15 Проголосовать: не нравится

    Well, that won't fulfill the constraint as $$$a_i <= 2.5*10^6$$$ needs to satisfy

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
3 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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

    → Ответить
»
3 года назад, # |
← Rev. 4   Проголосовать: нравится -54 Проголосовать: не нравится

The sequence of alternate prime nos. (2, 5, 11, 17...) works! Edit: Changed 19 to 17

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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:

  1. http://www.cs.toronto.edu/~apostol/golomb/presentation-en-combinatorics.pdf
  2. https://www.researchgate.net/publication/239285940_A_review_of_the_available_construction_methods_for_Golomb_rulers
→ Ответить
»
3 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

n = 4. a = {1, 10, 100, 1000} Clearly works.

→ Ответить