Hint
Hint
Hint
Solution
Hint
Hint
Hint
Solution
Hint
Hint
Hint
Solution
Hint
Hint
Hint
Solution
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Codeforces Round #728 Editorial
The parity (whether $$$n$$$ is odd or even) matters.
Swapping two adjacent cats keeps both of them close to their original location and changes both of their locations.
If $$$n$$$ is even, the optimal distance is $$$n$$$, and if $$$n$$$ is odd the optimal distance is $$$n+1$$$.
$$$i+j \leq 2 \cdot n$$$
The number of pairs $$$(a, b)$$$ such that $$$a \cdot b \leq x$$$ is $$$O(x log x)$$$.
If $$$n$$$ is even, the optimal distance is $$$n$$$, and if $$$n$$$ is odd the optimal distance is $$$n+1$$$.
What's the minimum value that an edge from $$$a$$$ to $$$b$$$ can be?
Use edges with negative value whenever you can.
The sum of the values of edges with positive weight must be $$$\geq$$$ the maximum value in the array.
The answer is always unique.
Try to figure out what the location of the $$$i$$$-th element would be if you only looked at the first $$$i$$$ elements, then the first $$$i+1$$$, etc. to find an $$$O(nq)$$$ solution.
Use sqrt decomposition to optimize it.
Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|
en10 | ijxjdjd | 2021-06-25 21:37:30 | 0 | (published) | ||
en9 | ijxjdjd | 2021-06-25 21:34:05 | 0 | Tiny change: 'oblem:1540E]\n\nAuthor: ' -> 'oblem:1540\nAuthor: ' (saved to drafts) | ||
en8 | PurpleCrayon | 2021-06-25 21:21:31 | 138 | |||
en7 | PurpleCrayon | 2021-06-25 21:19:22 | 278 | Tiny change: '1541A]\n\n<spoi' -> '1541A]\n\nAuthor: [user:PurpleCrayon]\n\n<spoi' | ||
en6 | PurpleCrayon | 2021-06-25 21:16:16 | 0 | (published) | ||
en5 | ijxjdjd | 2021-06-25 21:12:49 | 133 | |||
en4 | ijxjdjd | 2021-06-25 21:08:12 | 379 | |||
en3 | ijxjdjd | 2021-06-25 21:05:16 | 1319 | Tiny change: 'oiler>\n\n' -> 'oiler>\n\n[problem:1540E]\n\n' | ||
en2 | PurpleCrayon | 2021-06-25 20:55:31 | 1705 | |||
en1 | PurpleCrayon | 2021-06-25 20:44:46 | 32 | Initial revision (saved to drafts) |
Name |
---|