hossainzarif's blog

A problem(inspired from round 707 div1-A)
By hossainzarif, history, 3 years ago, In English

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

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
  Vote: I like it -28 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it -54 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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
→ Reply
»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I mean, satisfying the problem constraints($$$a_i <= 2.5*10^6$$$)is needed

    → Reply