February Long 2021 - Final Comments

I usually coordinate the odd long challenges. But for some notorious coincidences, I ended up admining February Long.

A bit of the action on the other side of the board.

HDIVISR , MEET: Just do what the problem says :slight_smile:

MAXFUN : The first div3 problems are prepared internally by a codechef team. This time I decided to take this one also for div2. I liked that the algebraic problem is actually solved without algebra by interpreting the absolute value as distance between points on a line.

FROGS : Sometimes I play with frogs

I still have some frog-problems that I can’t solve! Sorting problems in different kinds of situations/operations are usually interesting.

TEAMNAME : Some brute force + string operations. I think it is good for the first problem in div1.

PRIGAME : Game problems are always welcome! we’ll have more problems written by Divyam in future contests.

(Not Used) CHEPLANT : I planned to have 10 problems in div1, however we had many issues with this problem. It requires a non-trivial test generation, and the author is new to problem setting plus there was little time to prepare it. The problem is good, maybe we’ll use it in a future contest.

MULGAME : In order to hide a bit the winning condition, the setter initially proposed that we could say that all the integers have the same most significant bit. I was a bit afraid that since the range of the integers is small, it could be hard to prepare test data. In the expected solution, the way of processing the queries was more elaborate, however the setter found that the naive way of processing queries is good enough. At the end Milos decided to use just sorted sequences with steps of size at most A1.

SUMXOR2 : The problem is a bit standard, think bit by bit and then convolutions. I feel it is easier than MULGAME, however it requires to know NTT, so it ended up with less ACs. Initially it had a “strict” time limit. We setted a time limit of 2s to let slower NTT implementations AC.

ATWNT : I liked the problem, it may have applications in other situations. Some months ago I received another proposal a bit similar where water flows on the edges of the tree (maybe we’ll use it in a contest if the setter finds a solution!).

BASH : In the initial proposal, there were no weights and it asked to construct any matrix. I suggested asking for the matrix with minimum cost, with arbitrary weights per cell, but we couldn’t solve it. Sayantan found that if there are only 4 different costs (one for each direction), then it is possible to solve it with weighted bipartite matching and minimum spanning tree. During the review we focused more on the vertices of the cycles, we tried to solve it for larger constraints and forgot about the other vertices. Fortunately during testing Felipe found that actually Directed MST is required, it took some time to fix the issue, so the insertion of the problem was delayed a bit.

MEOW1234 :
I like the problem, it requires a couple of interesting observations and is not too hard to implement the solution. The combinatorics part helps to prevent many greedies. We’ll have some interesting problems written by Yuriy in upcoming contests (probably March Long)!

DRE3HGF : I also think that the universe can be represented as a graph :slight_smile: My first impression during the review was that it is a standard problem. My first idea was to perform the queries offline (Mo trick), and preprocess the additional edges as non-overlapping intervals, however all the approaches I tried TLE, moreover the initial constraint was N \leq 5e5 which looks too high for the given time complexity. Um_nik also tried the problem and according to his comments he struggled to find the proper transitions, not to say how to solve the whole problem. During the contest the setter was afraid that non-optimal solution AC, and decreased the time limit to 2s (without an approval of the admin or tester). After considering the opinion of Radoslav, I decided to increase the time limit to let other slower approaches/implementations AC.

CUTCAKE: The initial problem was about cutting a rectangular cake with slices (lines) that connects points from the perimeter of the rectangle. Alexey suggested using integer coordinates to have an integer score, however I had troubles finding a good test plan generation. Then I came up with the idea of creating the portions by connecting points in a plane, the easiest way I thought for generating test data was using triangulations. (Unfortunately?) I used very small constraints N<=1024 that allowed rns_cus solve it optimally! After his submission, the relative score of all the other contestants became 0/S, and rns_cus got an undetermined relative score 0/0. So we decided to tweak the scoring formula to eliminate indeterminate.