codeforces-scrape

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

1983.md (8583B)


      1 Source: https://codeforces.com/blog/entry/131268
      2 
      3 Thank you for participating in our contest! We hope you enjoyed it.
      4 
      5 **On a personal note (contains spoilers)**
      6 
      7 This is the first time some of us are problemsetting. I apologise in case some of you did not have a good experience with the contest. I realise B was probably too hard for its position, we had a 2 hour 15 minutes contest and I expected the extra time to compensate for that. I believe some people did not like B being easily guessable. We were actually in a position where we could punish guessers who submit without proof. A lot of testers had submitted the sum over the entire grid modulo 3 to be equal as an initial guess (the samples were weak back then). I added a lot of samples to B (and, for that matter, to C, too) to make the problem easier instead of going the other way and punishing guessers. I really do not know if going the other way would have been appreciated, either.
      8 
      9 I really like observation-based problems, like the format we have on CF nowadays. I did not realise all these constructives might cause a bad experience. I've never prepared for math olympiads or related stuff, and it has been CF that introduced me to all these sorts of problems, so I have no idea what would count as math-heavy and what would not.
     10 
     11 For D I'm very surprised people managed to guess permutation parity without proving. We wanted to introduce new and uncommon problems, like the usage of permutation parity here would have been for a div2D. D and G are my personal favourites from this round. For G, too, it is possible to solve it without any heavy data structures, just plain observations.
     12 
     13 It had been a complaint in last year's ByteRace round that the problems in the Div1 range were not hard or interesting enough. This time, we did try to ensure that, hopefully. I really like problem G, as said before. Actually, we were planning to have a 3-hour long 8 problem round, but we had to get down to this.
     14 
     15 We ended up overlooking some mistakes in the statement of E. I'm sorry about that, too. Many of us preparing the contest have been busy interning, and sometimes it gets hard to manage time.
     16 
     17 I believe the observations required for B and D make them really good and unique problems. We just did not put them in ways that would, like, prevent guessing. Are we supposed to? E was one math-heavy problem, is that a lot? I'm genuinely curious, can any experienced problemsetter (and not random greys echoing each other) explain what did not go well with this contest, if anything?
     18 
     19 [1983A - Array Divisibility](/contest/1983/problem/A "Codeforces Round 956 (Div. 2) and ByteRace 2024")
     20 
     21 Idea: [BlazingDragon](/profile/BlazingDragon "Expert BlazingDragon")  
     22  Preparation: [Pew_Pew.](/profile/Pew_Pew. "Expert Pew_Pew.")  
     23  Editorial: [Swap-nil](/profile/Swap-nil "Expert Swap-nil")
     24 
     25 **Hints**
     26 
     27 **Hint 1**
     28 
     29 Think simple.
     30 
     31 **Hint 2**
     32 
     33 If $a$ and $b$ both are divisible by $c$ then, $a + b$ will also be divisible by $c$.
     34 
     35 **Solution**
     36 
     37 Tutorial is loading...
     38 
     39 **Implementation (C++)**
     40 
     41 [269328935](/contest/1983/submission/269328935 "Submission 269328935 by Swap-nil")
     42 
     43 **Implementation (Python)**
     44 
     45 [269329008](/contest/1983/submission/269329008 "Submission 269329008 by Swap-nil")
     46 
     47 **Feedback**
     48 
     49 * Good problem
     50 * Average problem
     51 * Bad problem
     52 * Did not solve
     53 
     54 [1983B - Corner Twist](/contest/1983/problem/B "Codeforces Round 956 (Div. 2) and ByteRace 2024")
     55 
     56 Idea: [Swap-nil](/profile/Swap-nil "Expert Swap-nil")  
     57  Preparation: [Swap-nil](/profile/Swap-nil "Expert Swap-nil")  
     58  Editorial: [Swap-nil](/profile/Swap-nil "Expert Swap-nil")
     59 
     60 **Hint**
     61 
     62 **Hint 1**
     63 
     64 $1 + 2 \equiv 0 \pmod{3}$.
     65 
     66 **Hint 2**
     67 
     68 Can you notice something that does not change, an invariant?
     69 
     70 **Solution**
     71 
     72 Tutorial is loading...
     73 
     74 **Implementation (C++)**
     75 
     76 [269329137](/contest/1983/submission/269329137 "Submission 269329137 by Swap-nil")
     77 
     78 **Implementation (Python)**
     79 
     80 [269329083](/contest/1983/submission/269329083 "Submission 269329083 by Swap-nil")
     81 
     82 **Feedback**
     83 
     84 * Good problem
     85 * Average problem
     86 * Bad problem
     87 * Did not solve
     88 
     89 [1983C - Have Your Cake and Eat It Too](/contest/1983/problem/C "Codeforces Round 956 (Div. 2) and ByteRace 2024")
     90 
     91 Idea: [DC17](/profile/DC17 "Candidate Master DC17")  
     92  Preparation: [Swap-nil](/profile/Swap-nil "Expert Swap-nil")  
     93  Editorial: [BlazingDragon](/profile/BlazingDragon "Expert BlazingDragon")
     94 
     95 **Solution**
     96 
     97 Tutorial is loading...
     98 
     99 **Implementation (C++)**
    100 
    101 [269329204](/contest/1983/submission/269329204 "Submission 269329204 by Swap-nil")
    102 
    103 **Implementation (Python)**
    104 
    105 [269329258](/contest/1983/submission/269329258 "Submission 269329258 by Swap-nil")
    106 
    107 **Feedback**
    108 
    109 * Good problem
    110 * Average problem
    111 * Bad problem
    112 * Did not solve
    113 
    114 [1983D - Swap Dilemma](/contest/1983/problem/D "Codeforces Round 956 (Div. 2) and ByteRace 2024")
    115 
    116 Idea: [MrSavageVS](/profile/MrSavageVS "Expert MrSavageVS")  
    117  Preparation: [MrSavageVS](/profile/MrSavageVS "Expert MrSavageVS")  
    118  Editorial: [MrSavageVS](/profile/MrSavageVS "Expert MrSavageVS")
    119 
    120 **Hint**
    121 
    122 **Hint 1**
    123 
    124 Can we convert this complicated operation to something simpler?
    125 
    126 **Hint 2**
    127 
    128 We can convert the operation to basically swapping adjacent elements and it still works. Try to prove why?
    129 
    130 **Hint 3**
    131 
    132 Swapping adjacent elements in a distinct array is basically trying to equate two permutations using adjacent swaps. When is it possible?
    133 
    134 **Hint 4**
    135 
    136 Inversions in a permutation
    137 
    138 **Solution**
    139 
    140 Tutorial is loading...
    141 
    142 **Implementation (C++)**
    143 
    144 [269303026](/contest/1983/submission/269303026 "Submission 269303026 by MrSavageVS")
    145 
    146 **Feedback**
    147 
    148 * Good problem
    149 * Average problem
    150 * Bad problem
    151 * Did not solve
    152 
    153 [1983E - I Love Balls](/contest/1983/problem/E "Codeforces Round 956 (Div. 2) and ByteRace 2024")
    154 
    155 Idea: [DC17](/profile/DC17 "Candidate Master DC17")  
    156  Preparation: [BlazingDragon](/profile/BlazingDragon "Expert BlazingDragon")  
    157  Editorial: [BlazingDragon](/profile/BlazingDragon "Expert BlazingDragon")
    158 
    159 **Solution**
    160 
    161 Tutorial is loading...
    162 
    163 **Implementation (C++)**
    164 
    165 [269329340](/contest/1983/submission/269329340 "Submission 269329340 by Swap-nil")
    166 
    167 **Feedback**
    168 
    169 * Good problem
    170 * Average problem
    171 * Bad problem
    172 * Did not solve
    173 
    174 [1983F - array-value](/contest/1983/problem/F "Codeforces Round 956 (Div. 2) and ByteRace 2024")
    175 
    176 Idea: [TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101")  
    177  Preparation: [MrSavageVS](/profile/MrSavageVS "Expert MrSavageVS")  
    178  Editorial: [MrSavageVS](/profile/MrSavageVS "Expert MrSavageVS")
    179 
    180 **Hint**
    181 
    182 **Hint 1**
    183 
    184 Can we fix an upper bound to count the number of subarrays having xor-pair less than that?
    185 
    186 **Hint 2**
    187 
    188 We can use binary search to fix an upper bound and calculate all subarrays with xor-pair less than the given value.
    189 
    190 **Hint 3**
    191 
    192 In order to count the number of subarrays we can use a popular data-structure used for a lot of xor-operations.
    193 
    194 **Hint 4**
    195 
    196 We can binary search on the upper bound and use tries to count the number of subarrays with xor-pair less than given value. This way we can find the kth-smallest value.
    197 
    198 **Solution**
    199 
    200 Tutorial is loading...
    201 
    202 **Implementation (C++)**
    203 
    204 [269305957](/contest/1983/submission/269305957 "Submission 269305957 by MrSavageVS")
    205 
    206 **Feedback**
    207 
    208 * Good problem
    209 * Average problem
    210 * Bad problem
    211 * Did not solve
    212 
    213 [1983G - Your Loss](/contest/1983/problem/G "Codeforces Round 956 (Div. 2) and ByteRace 2024")
    214 
    215 Idea: [AwakeAnay](/profile/AwakeAnay "Grandmaster AwakeAnay"),[TimeWarp101](/profile/TimeWarp101 "Candidate Master TimeWarp101")  
    216  Preparation: [ShivanshJ](/profile/ShivanshJ "Master ShivanshJ"), [Swap-nil](/profile/Swap-nil "Expert Swap-nil"), [Pew_Pew.](/profile/Pew_Pew. "Expert Pew_Pew.")  
    217  Editorial: [Swap-nil](/profile/Swap-nil "Expert Swap-nil")
    218 
    219 **Hints**
    220 
    221 **Hint 1**
    222 
    223 Try looking at the problem bit by bit.
    224 
    225 **Hint 2**
    226 
    227 What does the contribution of a particular bit over a path look like?
    228 
    229 **Hint 3**
    230 
    231 Can you think of some simpler queries you can easily solve the problem for?
    232 
    233 **Hint 4**
    234 
    235 Root the tree.
    236 
    237 **Hint 5**
    238 
    239 For a query from a node $u$ to its ancestor $v$, the countribution from the counting term $(0,1,2,3, \ldots)$ changes for the first time at an ancestor at a jump of a power of two.
    240 
    241 **Hint 6**
    242 
    243 Let $dp[u][k]$ be the contribution of bit $k$ to the query from $u$ to the root.
    244 
    245 **Hint 7**
    246 
    247 Keep track of a few additional nodes for each query. Read hint 5 again.
    248 
    249 **Solution**
    250 
    251 Tutorial is loading...
    252 
    253 **Implementation (C++)**
    254 
    255 [269315826](/contest/1983/submission/269315826 "Submission 269315826 by Swap-nil")
    256 
    257 **Feedback**
    258 
    259 * Good problem
    260 * Average problem
    261 * Bad problem
    262 * Did not solve