Thank you for participating in this round! Problems I are authored by [user:orzdevinwang,2025-01-20] and the rest by me.↵
↵
Sorry for the weak pretest in problem B.↵
↵
hints and code are WIP.↵
↵
[problem:2061A]↵
↵
<spoiler summary="Hint 1">↵
What is the parity of $s$ after an operation?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061A]↵
</spoiler>↵
↵
[problem:2061B]↵
↵
<spoiler summary="Hint 1">↵
What is the condition for four edges to form an isosceles trapezoid?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
How do you find two bases after fixing the length of the legs?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
How do you choose two legs?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061B]↵
</spoiler>↵
↵
[problem:2061C]↵
↵
<spoiler summary="Hint 1">↵
How can you solve the problem in $O(n^2)$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
**No two liars can stand next to each other** is important.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061C]↵
</spoiler>↵
↵
[problem:2061D]↵
↵
<spoiler summary="Hint 1">↵
Thinking outside the box.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
How is a number $x$ merged from?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Approach the problem in reverse.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061D]↵
</spoiler>↵
↵
[problem: 2061E]↵
↵
<spoiler summary="Hint 1">↵
Consider the minimum number that can be obtained by operating $0, 1, 2, \dots, m$ times on a number $x$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Do these numbers have any other properties?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Consider the cost of each operation and each number independently.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061E]↵
</spoiler>↵
↵
[problem: 2061F1]↵
↵
[problem: 2061F2]↵
↵
<spoiler summary="Hint 1">↵
What is the property for the final string?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider the immovable blocks.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
For the easy version, fix the immovable blocks greedily.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
For the hard version, use dynamic programming to determine the immovable blocks.↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
Use a data structure to speed up dynamic programming.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061F2]↵
</spoiler>↵
↵
[problem: 2061G]↵
↵
<spoiler summary="Hint 1">↵
What is the size of the maximum possible matching? What can be the "most dense" graph with maximum matching $k$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Mixed-color triplet($u, v$ with edge $0$ and $v, w$ with edge $1$) is a flexible structure to find a matching for both types.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Add vertices one by one. Try to get a "mixed-color triple" or a larger set of the same color.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061G]↵
</spoiler>↵
↵
[problem: 2061H1]↵
↵
[problem: 2061H2]↵
↵
<spoiler summary="Solution">↵
[tutorial:2061H2]↵
</spoiler>↵
↵
[problem: 2061I]↵
↵
<spoiler summary="Solution">↵
[tutorial:2061I]↵
</spoiler>↵
↵
↵
Sorry for the weak pretest in problem B.↵
↵
hints and code are WIP.↵
↵
[problem:2061A]↵
↵
<spoiler summary="Hint 1">↵
What is the parity of $s$ after an operation?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061A]↵
</spoiler>↵
↵
[problem:2061B]↵
↵
<spoiler summary="Hint 1">↵
What is the condition for four edges to form an isosceles trapezoid?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
How do you find two bases after fixing the length of the legs?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
How do you choose two legs?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061B]↵
</spoiler>↵
↵
[problem:2061C]↵
↵
<spoiler summary="Hint 1">↵
How can you solve the problem in $O(n^2)$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
**No two liars can stand next to each other** is important.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061C]↵
</spoiler>↵
↵
[problem:2061D]↵
↵
<spoiler summary="Hint 1">↵
Thinking outside the box.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
How is a number $x$ merged from?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Approach the problem in reverse.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061D]↵
</spoiler>↵
↵
[problem: 2061E]↵
↵
<spoiler summary="Hint 1">↵
Consider the minimum number that can be obtained by operating $0, 1, 2, \dots, m$ times on a number $x$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Do these numbers have any other properties?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Consider the cost of each operation and each number independently.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061E]↵
</spoiler>↵
↵
[problem: 2061F1]↵
↵
[problem: 2061F2]↵
↵
<spoiler summary="Hint 1">↵
What is the property for the final string?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider the immovable blocks.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
For the easy version, fix the immovable blocks greedily.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
For the hard version, use dynamic programming to determine the immovable blocks.↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
Use a data structure to speed up dynamic programming.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061F2]↵
</spoiler>↵
↵
[problem: 2061G]↵
↵
<spoiler summary="Hint 1">↵
What is the size of the maximum possible matching? What can be the "most dense" graph with maximum matching $k$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Mixed-color triplet($u, v$ with edge $0$ and $v, w$ with edge $1$) is a flexible structure to find a matching for both types.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Add vertices one by one. Try to get a "mixed-color triple" or a larger set of the same color.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2061G]↵
</spoiler>↵
↵
[problem: 2061H1]↵
↵
[problem: 2061H2]↵
↵
<spoiler summary="Solution">↵
[tutorial:2061H2]↵
</spoiler>↵
↵
[problem: 2061I]↵
↵
<spoiler summary="Solution">↵
[tutorial:2061I]↵
</spoiler>↵
↵
