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.

# | User | Rating |
---|---|---|

1 | tourist | 3822 |

2 | Benq | 3745 |

3 | ksun48 | 3560 |

4 | Radewoosh | 3538 |

5 | peehs_moorhsum | 3532 |

6 | Um_nik | 3489 |

7 | maroonrk | 3424 |

8 | Petr | 3380 |

9 | sunset | 3338 |

10 | ecnerwala | 3336 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 207 |

2 | Errichto | 181 |

2 | awoo | 181 |

4 | Um_nik | 180 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 172 |

7 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

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.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/31/2021 16:21:29 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

"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.

$$$\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$$$