Master0fPuppets's blog

By Master0fPuppets, history, 5 weeks ago, In English

I have been trying to solve this problem and I did with just observation but when I read the solution I didn't understand the proof behind why there is no answer for an even number.

https://codeforces.com/contest/304/problem/C.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

In this problem, we need to find permutations $$$A$$$, $$$B$$$ and $$$C$$$ such that $$$A_i + B_i = C_i$$$ $$$mod$$$ $$$n$$$.

Note that this implies that $$$\sum A_i + \sum B_i = \sum C_i$$$ $$$mod$$$ $$$n$$$. However, for an even value of $$$n$$$, the left side of this equation is different from the right side, meaning that no permutation triple ($$$A$$$, $$$B$$$, $$$C$$$) can satisfy the problem's conditions.

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

    "for an even value of n, the left side of this equation is different from the right side"

    I am sorry but could you elaborate on this part more.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      $$$\sum A_i = \sum B_i = \sum C_i = \frac{n \cdot (n - 1)}{2}$$$

      For odd values of $$$n$$$:

      $$$\frac{n \cdot (n - 1)}{2} = \left[\frac{n - 1}{2} \cdot n\right] = 0 \; mod \; n$$$

      Therefore, in this case, $$$\sum A_i + \sum B_i = \sum C_i \; mod \; n$$$

      For even values of $$$n$$$:

      $$$\frac{n \cdot (n - 1)}{2} = \left[\frac{n}{2} \cdot (n - 1)\right] = \left[\frac{n}{2} \cdot (-1)\right] = \frac{-n}{2} = n - \frac{n}{2} = \frac{n}{2} \; mod \; n$$$

      Therefore, in this case, $$$\sum A_i + \sum B_i = 2 \cdot \frac{n}{2} = 0 \; mod \; n$$$, while $$$\sum C_i = \frac{n}{2} \; mod \; n$$$