Last month, I participated CodeChef November Challenge 2016 and win 2nd prize as a high school student, which makes me delighted. Thanks to CodeChef for giving me a chance to share my thoughts on this contest.
Before the contest, actually, I was not confident in my ability to solve difficult problems, I just wanted to try my best and get a relatively high score. In my last participation, September Challenge, I only had solved 6 problems, so in this month, I wanted to make a difference.
As soon as the contest started, I entered into the contest page. It was not difficult to solve ALEXTASK, CHSQR, CPERM and GIFTCHEF. FRIEMEET and URBANDEV were also two classic problems, but a bit hard to code. It took me about 3 hours to solve the problems above. When I met KIRMEME, I knew I had to code for a long time – divide and conquer on a tree and something else. I finished my first version at about 22:00 (UTC+8), but got a WA, which made me sad and tired. In the following day, I got up early because I kept thinking of my WA program. It took me about half an hour to fix it and finally passed.
However, I found it difficult to solve any of the remaining 3 problems. SEAWCU was a challenge problem, BIKE seemed closely related to the matrix and SEAPERM3 was likely to be a hard counting problem. After submitting 2 brute force programs, I decided to think about SEAWCU and SEAPERM3. For SEAWCU, first I submitted a naive program, which cost less than 0.01 pts. Thus I spent the whole afternoon to think about how to optimize and came up with an idea of DP. When I submitted again, it was surprising that there were still really low points. Ah, there was a fatal mistake in the program! Finally I got 1 pts after fixing it (but now only 0.52 pts >_<, for ceilks' solution was really great).
During the night, I used brute force to find the clue of SEAPERM3. After observing lots of data, I felt that there was some magic relations between i and pi and code for over 3 hours to pass it. I had to say it really required patience and concentration to solve it, it was a great problem indeed.
For BIKE, I had no any thoughts on it at all for almost a week. One day afternoon, when I learned a paper about 2-dimensional DFT, I remembered BIKE. The 2-dimensional DFT method fits this problem very well! Thinking of some details about the problem, I spent about 3 hours on the program and got Accepted eventually.
This contest meant a lot to me. It is my first time that I have solved all the problems (except the challenge problem), which builds up my confidence a lot. I also feels excited to meet all these algorithm problems, they shows me bright ideas and brings more fun to my life. Anyway, I will keep learning and study much harder in the future. At the end of this blog, I want to express my thanks to CodeChef Teams for providing us with a fantastic problem and contest platform.
Dec. 6, 2016