This is the first problem that we coded. I didn't read this problem at all. Shi-jie explained this problem to Rais then Rais started coding. If I remember correctly, we had several bugs so we got this AC at 11 minutes.
This is the first problem that I read. Since the problem description was extremely long, I just read the problem and tried to figure out what's the problem about from the samples. It turned out that we just had to simulate something in the problem description. After Rais finished coding F, I told him to code this problem. We wanted to use bruteforce initially but we realized that we could just use greedy to solve it.
Shi-jie read this problem and explained it to Rais and me. The problem is very simple so Shi-jie asked Rais to code this using greedy. But before submitting, I was suspicious about the approach since many teams didn't get AC in by looking at the scoreboard and the fact that N <= 3000. To be safe, I told Rais to code an N2 DP.
I read this problem while Rais was coding J. The problem was simple but again, the problem description was very long. I was thinking about many weird solutions since the time limit was very weird, 7s. After explaining the problem to Rais, it turned out that we can just use disjoint set data structure and keep track of every set's size. After Rais finished coding J and still got WA, he switched to this problem. After coding this problem, I realized that we need revert operation on disjoint set, therefore, I coded the disjoint set reverting part since I just coded something similar earlier before the contest. After submitting, we got a very disappointing TLE which surprised me since the time limit was 7s. Finally, after adding size heuristic optimization to the disjoint set we got AC. I still don't get why it could make such a huge difference.
Shi-jie was the one who explained this problem to Rais, and he got the solution right away. After that, He started coding after finishing problem G. After coding, he just submitted and unfortunately got WA. After fixing a few bugs, he submitted it again but the verdict changed to RTE. After that, he switched to ppoblem C. After getting AC at problem C, Rais realized another bug in the program and then submitted again and got AC.
Shi-jie explained this problem to me and Rais at the beginning of the contest, but, we decided to work on the other problems first. When Rais was coding problem A, I spent some time to think about this problem. I got an idea after asking Shi-jie about the case where there are only 2 fruits which was surprisingly simple. Then I verified my idea with Shi-jie. After being sure that the idea is correct and Rais got WA on problem A, I coded this problem and fortunately got AC in one attempt.
Shi-jie explained this problem to Rais. Shi-jie suggested to run the instruction until we get 24 million states, which might be too slow. Then he changed the constant to 16 million states only. After Rais coding that approach, it got WA once before solving I. Rais realized that it could not handle the cases where the cycle length is large. After solving I, Shi-jie suggested another solution which involved traversing the states once to get which vertex was surely in the cycle then traversing it once again to get the whole cycle. After verifying the idea with Rais, Rais spent a few minutes thinking about the implementation details, then he coded it and we finally got AC.
Shi-jie was the one who came up with the idea for this problem. Initially, Shi-Jie did some summation of sequences and figured out that we need to consider displacement vectors in which the absolute value of the coordinates of the vectors are bounded by approximately 400. Then, we can shift a point using the displacement vectors in decreasing gradient to generate a convex polygon. However, this idea was not good enough to generate a polygon with 400,000 sides. We then tried to consider displacement vectors in which the norm is bounded by 500. Upon trying different bounds, we were finally able to generate a convex polygon with 400,000 sides. We submitted the code without double checking that the polygon is indeed convex, and luckily it got accepted.
I had read this problem at the start, the problem was simple but complicated. Shi-jie told me that we could just use log of the numbers and find subset sum instead of subset multiplication. I found a meet in the middle solution but quite different from the intended solution. Then I told Rais to code. Unfortunately, this approach still got TLE. There were 2 functions that we used, one to find all subsets, and another to backtrack to find the solution which had similar complexity. We tried commenting the backtrack function and got WA. Therefore, we were sure that if the time limit were twice of what it was, this solution could get AC. Unfortunately, we failed in optimizing our program before the contest ended.
I spent some time thinking about this problem and got the solution for N <= 5000, but I got no idea for K <= 20. After thinking for a while, I decided to give up and switched to other problems.
I didn't read this problem at all. :D
Bye!
Translated by Rais
Written by Me, Rais, and Shi-jie in my point of view :|