alwcod_nn's blog

By alwcod_nn, history, 4 weeks ago, In English,

http://codeforces.com/contest/1206/problem/C

I found a challenge in the editorial (http://codeforces.com/blog/entry/69158) :

Challenge:

For which pairs of (n,k) (n>k≥1) is there an arrangement of numbers from 1 to n on a circle such that the sums of each k consecutive numbers differ by not more than 1 ? ( The problem above is a specify case where n=2*k)

My solution is: — if k is even, there are no n satisfied the condition. — if k is odd, only n=2*k satisfied the condition.

Can someone verify this for me?

Thank you very much....

 
 
 
 
  • Vote: I like it
  • -20
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Proof?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Does the sentence "Proof?" proof that i'm true? I'm just guessing.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And of course i have reasons then to guessing: First, i found that the solution can be found only if n=x*k. Then i try to link the original problem with this one. if there is such a solution, then we can divide the array A ( the solution) into x group with the same number of elements (k elements). for every (A[i%k] % x) i see they're always a permutation of {0,1,2,...,x-1} ( If not, there will be 2 same numbers in A, the thing we're avoiding). Then we only need to fill A'[i]=m such that 0<=m<=x-1 have A', finding A is just taking a candy from a baby. The problem is, idk how to find a x satisfied the condition, but i fell that there will be a solution only if x=2. Then the problem back to the the original one.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe you guy press downvote because the title right? :) It's because i have the same question 2 days ago, but no one care, obivously no one care, so i decided to repost it :)