codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2061.md (3621B)


      1 Source: https://codeforces.com/blog/entry/138620
      2 
      3 Thank you for participating in this round! Problems I are authored by [zhoukangyang](/profile/zhoukangyang "Legendary Grandmaster zhoukangyang") and the rest by me.
      4 
      5 Sorry for the weak pretest in problem B.
      6 
      7 [2061A - Kevin and Arithmetic](/contest/2061/problem/A)
      8 
      9 **Hint 1**
     10 
     11 What is the parity of $s$ after an operation?
     12 
     13 **Solution**
     14 
     15 Tutorial is loading...
     16 
     17 [2061B - Kevin and Geometry](/contest/2061/problem/B)
     18 
     19 **Hint 1**
     20 
     21 What is the condition for four edges to form an isosceles trapezoid?
     22 
     23 **Hint 2**
     24 
     25 How do you find two bases after fixing the length of the legs?
     26 
     27 **Hint 3**
     28 
     29 How do you choose two legs?
     30 
     31 **Solution**
     32 
     33 Tutorial is loading...
     34 
     35 [2061C - Kevin and Puzzle](/contest/2061/problem/C)
     36 
     37 **Hint 1**
     38 
     39 How can you solve the problem in $O(n^2)$?
     40 
     41 **Hint 2**
     42 
     43 **No two liars can stand next to each other** is important.
     44 
     45 **Solution**
     46 
     47 Tutorial is loading...
     48 
     49 [2061D - Kevin and Numbers](/contest/2061/problem/D)
     50 
     51 **Hint 1**
     52 
     53 Thinking outside the box.
     54 
     55 **Hint 2**
     56 
     57 How is a number $x$ merged from?
     58 
     59 **Hint 3**
     60 
     61 Approach the problem in reverse.
     62 
     63 **Solution**
     64 
     65 Tutorial is loading...
     66 
     67 [2061E - Kevin and And](/contest/2061/problem/E)
     68 
     69 **Hint 1**
     70 
     71 Consider the minimum number that can be obtained by operating $0, 1, 2, \dots, m$ times on a number $x$.
     72 
     73 **Hint 2**
     74 
     75 Do these numbers have any other properties?
     76 
     77 **Hint 3**
     78 
     79 Consider the cost of each operation and each number independently.
     80 
     81 **Solution**
     82 
     83 Tutorial is loading...
     84 
     85 [2061F1 - Kevin and Binary String (Easy Version)](/contest/2061/problem/F1)
     86 
     87 [2061F2 - Kevin and Binary String (Hard Version)](/contest/2061/problem/F2)
     88 
     89 **Hint 1**
     90 
     91 What is the property for the final string?
     92 
     93 **Hint 2**
     94 
     95 Consider the immovable blocks.
     96 
     97 **Hint 3**
     98 
     99 For the easy version, fix the immovable blocks greedily.
    100 
    101 **Hint 4**
    102 
    103 For the hard version, use dynamic programming to determine the immovable blocks.
    104 
    105 **Hint 5**
    106 
    107 Use a data structure to speed up dynamic programming.
    108 
    109 **Solution**
    110 
    111 Tutorial is loading...
    112 
    113 [2061G - Kevin and Teams](/contest/2061/problem/G)
    114 
    115 **Hint 1**
    116 
    117 What is the size of the maximum possible matching? What can be the "most dense" graph with maximum matching $k$?
    118 
    119 **Hint 2**
    120 
    121 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.
    122 
    123 **Hint 3**
    124 
    125 Add vertices one by one. Try to get a "mixed-color triple" or a larger set of the same color.
    126 
    127 **Solution**
    128 
    129 Tutorial is loading...
    130 
    131 [2061H1 - Kevin and Stones (Easy Version)](/contest/2061/problem/H1)
    132 
    133 [2061H2 - Kevin and Stones (Hard Version)](/contest/2061/problem/H2)
    134 
    135 **Hint 1**
    136 
    137 Think about the necessary conditions.
    138 
    139 **Hint 2**
    140 
    141 Simplify the graph while keeping the conditions.
    142 
    143 **Hint 3**
    144 
    145 Try to move the stones one bye one.
    146 
    147 **Solution**
    148 
    149 Thanks to [zhoukangyang](/profile/zhoukangyang "Legendary Grandmaster zhoukangyang") and [JohnVictor](/profile/JohnVictor "Master JohnVictor") for their discussions. A large part of the following approach comes from discussion with them.
    150 
    151 Tutorial is loading...
    152 
    153 [Draft in Chinese](https://drive.google.com/file/d/1-NMKUs6uyWNztU_221VkGyLfQJ-CnBCt/view?usp=sharing)
    154 
    155 [2061I - Kevin and Nivek](/contest/2061/problem/I)
    156 
    157 **Hint 1**
    158 
    159 Can you compute $dp(r, *)$ from $dp(l, *)$ efficiently?
    160 
    161 **Hint 2**
    162 
    163 If the difference between the number of victories is large, he will either always win or always lose for type 2 matches.
    164 
    165 **Hint 3**
    166 
    167 We can speed up this part to $O(n \log n)$.
    168 
    169 **Hint 4**
    170 
    171 For the part that the difference between the number of victories is not large, solve it recursively.
    172 
    173 **Solution**
    174 
    175 Tutorial is loading...