Thank you for participating in our contest! We hope you enjoyed it.
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.
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.
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.
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.
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.
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?
Idea: BlazingDragon
Preparation: Pew_Pew.
Editorial: Swap-nil
Think simple.
If $$$a$$$ and $$$b$$$ both are divisible by $$$c$$$ then, $$$a + b$$$ will also be divisible by $$$c$$$.
Idea: Swap-nil
Preparation: Swap-nil
Editorial: Swap-nil
$$$1 + 2 \equiv 0 \pmod{3}$$$.
Can you notice something that does not change, an invariant?
1983C - Have Your Cake and Eat It Too
Idea: DC17
Preparation: Swap-nil
Editorial: BlazingDragon
Idea: MrSavageVS
Preparation: MrSavageVS
Editorial: MrSavageVS
Can we convert this complicated operation to something simpler?
We can convert the operation to basically swapping adjacent elements and it still works. Try to prove why?
Swapping adjacent elements in a distinct array is basically trying to equate two permutations using adjacent swaps. When is it possible?
Inversions in a permutation
Idea: DC17
Preparation: BlazingDragon
Editorial: BlazingDragon
Idea: TimeWarp101
Preparation: MrSavageVS
Editorial: MrSavageVS
Can we fix an upper bound to count the number of subarrays having xor-pair less than that?
We can use binary search to fix an upper bound and calculate all subarrays with xor-pair less than the given value.
In order to count the number of subarrays we can use a popular data-structure used for a lot of xor-operations.
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.
Idea: AwakeAnay,TimeWarp101
Preparation: ShivanshJ, Swap-nil, Pew_Pew.
Editorial: Swap-nil
Try looking at the problem bit by bit.
What does the contribution of a particular bit over a path look like?
Can you think of some simpler queries you can easily solve the problem for?
Root the tree.
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.
Let $$$dp[u][k]$$$ be the contribution of bit $$$k$$$ to the query from $$$u$$$ to the root.
Keep track of a few additional nodes for each query. Read hint 5 again.
