Behind the scenes - January Long

Usually the information of what happens during the preparation of the contest is lost (or at least not made public). I recorded some of the important facts during January Long so you can have a feeling of what happened in the other side of the board, and maybe encourage you to set problems for future contests.

FAIRELECT
Initially it had higher constraints, we reduced it to let the quadratic solution AC. The problem was intended to be the cakewalk.

WIPL
It is a bit harder for the second slot, but since it is a long contest I thought there is a lot of time to learn the concept. It is kind of educational, there is a greedy part (sorting) and a dp part (knapsack). The first solution of the setter was to sort the elements and then take the even elements for one tower and the odd for the other, which is obviously incorrect. To make data stronger we added more test files (and rejudged) in the second or third day.

ANTSCHEF
The problem for a line is well known, I remember a similar old topcoder problem. Adding many lines makes it a bit more difficult.

RCTEXSCC
The first version was a bit standard and required fft, so the setter came up with the idea of strongly connected components in a grid, during testing phase Radoslav found a nicer solution based on the euler formula for planar graphs.

TILESQRS
The first version was very straightforward, it asked to find the expected number of squares in a grid containing slashes and anti-slashes. After half-rejecting some of the variants proposed by Jay he came up with the harder final version.

BLKJK
I approved the problem almost immediately after reading it, because it solves a real world problem i.e how to win blackjack by swapping cards. I think it is a nice problem, but the solution is a bit standard dp + bitsets.

ORAND
I also liked this problem, It is FWHT but requires an observation on the number of necessary convolutions.

COOLSBST
The problem was in the queue for a long time (sorry Nishant). The number theory part is googleable and I felt that the required pre computations were a bit standard. Radoslav predicted that most of the 6 and 7 stars coders could solve it.

ARCRT
The first version of the problem asked only for the longest possible prefix. I suggested changing it to find the longest subarray to prevent some binary-search + matching solutions, however during testing Radoslav squeezed an incremental matching solution! and it is hard to generate test data against it. Fortunately I came up with the combinatorial problem that kills such solutions (and makes the problem a bit harder), the intended solution is to use two-pointers and dynamic connectivity to keep a pseudoforest. However the setter was not familiar with LCT, and it requires to know the data structure to keep the size of each connected component. Conceptually the problem is not hard, but is kind of technical. The final implementation was written by Radoslav and test data prepared by Aman, he ran a quadratic DSU for a couple of hours. Nishant found that it is not necessary to use LCT, just dsu with rollback.

CURMAT
I like problems that require a graph model. The first definition of a curious matrix was given as a matrix of rank 1, but I felt some contestants may not know what is a rank, so Sayantan changed the definition to require only knowledge about determinants. I feel I’ve seen that definition in some books, but probably the change of definition made it a bit harder. I didn’t want to use both CURMAT and ARCRT In the same contest because both are about dynamic connectivity, however since the intended solution of ARCRT was link-cut trees I thought it was ok to use both of them to have a more complete study on connectivity. The intended difficulty agreed by the setter is medium-hard, however it got fewer ACs, and the tester also felt it was hard.

GRDSTD
The initial version was a more direct application of finding the k-th longest/shortest path in a DAG, especifically dyck-paths. I suggested setting it in a geometrical situation. After some brainstorming (I stormed and the setter brained), Sabbir came up with the nice final version. It turned out that the geometric problem was in the literature, however the papers about it provide a slower solution (second subtask).

SQSORT
This is one of the first problems I created and couldn’t solve. I remember I even sent an easier version (just stacks and no weights) to Errichto, 4 or 5 years ago!

55 Likes

This kind of BTS really shows the work Problem setters and testers put in to make the long contest fun and challenging. Great work from all the coordinators!!

9 Likes

I always like reading such contest preparation notes, keep it up! I was surprised to see my name though :smiley: I coordinated Codechef contests a very long time ago.

21 Likes

Nice work .

1 Like