Hello,
While we are in talks with the organizers over detailed editorials for the round, I’d like to share the brief setter’s notes we received from them, so that you guys can start upsolving and practicing them :). I tried my best to make the notes reader-friendly as well, and added a couple of alternate explanations/hints etc. Let me know if they can be improved, and dont forget to share your approaches for discussion!!
#1. Pizza Cutting
Ans- The answer is easy to guess if you think in terms of GCD(a2 - a1,a3-a2, ..., an - a1). Alternatively, you can try all angles and rotations and brute force.
Reference Solution : Here
#2 Subtract Leading Digit
Hint- Binary Search
**Ans-**Binary search on answer. Notice that you can entirely skip groups (of numbers) with the same leading digit and length.
Some more Explanation-
Click to view
Notice that you can find answer for a group easily. Lets say leading digit is K. We will do this step until we get a new number N which has 1 digits less. If our original number was, say P, then we can see that P-x*K=D. Repeat this for all groups.
#3 Antimatching
Hint: 1 Corner case + Trivial observation.
Ans- The answer is either the largest degree (trivial to prove) , or 3 if there is a triangle (corner case).
#4 Inverse LIS:
Ans- Place small numbers after i[k - 1] in decreasing order, then i[1], ..., i[n], then all other positions in decreasing order.
Corner cases- k = 1 and k=2 are special cases.
#5 TREEMEX
Ans- TBA. Please share your approaches for now.
#6 Grid Flippers
Ans-
O(n log n log C) (not intended to pass): Binary search on answer d. Tracks with midpoints at manhattan distance at most d have to have the same orientation (implication of kind 1), also tracks with midpoints on the same horizontal line at distance at most 2d can not be both horizontal (same for vertical, implication of kind 1). The implication graph for 2SAT can be made of size O(n log n) with persistent treap.
O(n log n) with small constant: note that only edges of manhattan MST can be left for implications of kind 1, one can find them in O(n log n) with sorting in four diagonal directions. There are now O(n) edges for 2SAT in total, hence O(n log C) in total.