In this post, I'll record my life from now on all the way till the end of CTSC(Chinese Team Selection Contest). This post works like a diary, so during this time period, I'll try my best to keep it updated. Although there'll be some contents of complaints, there'll also be some good suggestions about how to improve myself, which might be helpful to you as well. If you enjoy reading it, don't forget to click the like button. If you want to keep watching my performance in coming Codeforce contests, you can add me as a friend on my profile page. Leave your comments down below and I'll try to read as many as I can.
Before you read this post, it's suggested to have some basic knowledge about CNOI contests. If you don't, click here.
CTSC will be held from May 7 to May 11 in Beijing. The candidates are matthew99 jiaqiyang yyt16384 eds467 xumingkuan immortalCO Dylans JOHNKRAM Philipsweng fateice Altria-PenDragon YJQQQAQ ShineRain jzzhu SkyDec
Happy to get 500 likes! You guys are really amazing!
Tomorrow will be the first day I record. See you guys tomorrow!
April 7th, 2017
I spent nearly two hours on upsolving GCJ2016 final #A, which is obviously too long and I feel very sad about it.
The solution is easy to find, while I did poorly at coding.
I think the following things are culpable of it.
Writing before thinking: I thought poorly before I started to construct the NFA, which turned out to be not as easy as I had thought. I even wrote a futile DSU. Also when I wrote the DP on bits, I didn't even see that leading zeros aren't allowed. Writing code without much thinking or with over confidence is really hazardous, and in fact, it made me change my code over and over again, by which many bugs were incurred.
Trying too hard while coding: While writing the NFA I tried to squeeze the index of the nodes of the NFA into 32 so that I could use 32-bit integers as bitmasks instead of 64-bit ones. In retrospect, as I have said, my algorithm of constructing the NFA was wrong, this notion was obviously ridiculous.
Awkwardness in naming: First I named an array 'mask', then I changed it into 'mask_go' because I found a better candidate for the name. Same thing recurred on 'maxdigit'---I first gave this name to something denoting 'the total number of digits', while later I found the base was a better candidate and called what had been called 'maxdigit' 'maxndigit'. Later I found the base should be called 'Base' instead of mouthful 'maxdigit'.
Next time, I should think more before coding. Also, I should avoid premature optimizing, and only optimize when I've got my algorithm correct. I'll be more careful on naming and I'll try to make my names final in the very beginning.
Tomorrow there'll be a contest among the 15 candidates(called 集训队互测), which doesn't count as part of the selection but I still hope I can win it. Wish me good luck!
April 8th, 2017
This afternoon I was overwhelmed by the contest I mentioned yesterday.
At first, I read the first task and soon found it undoable, because it seemed to me that it required gargantuan coding. So I shifted my focus to the second one and found that n ≤ 20000, and although there were multiple cases, the sum of n in one test didn't exceed 70000. Moreover, the time limit was 8s, and the based on my recognition, the Judge ran very fast. I was determined that an algorithm with O(n2) could pass easily. The third task turned out to be an answer-submitting task, a task that I was given inputs and asked to submit your outputs according to the inputs, which was not my cup of tea.
Therefore, every piece of me became focused on the second task, believing it would crack soon. However, my algorithm was always incorrect, and I wasted a huge amount of time revising it. When I finally got rid of Wrong Answers, more than 2 hours elapsed.
However, my algorithm didn't manage to fit into the time limit, and I spent another one hour squeezing it, to not much avail. Frustrated, I used the rest poor amount of time implementing some trivial subtasks, which of course gave me little score.
Obviously I got a poor result, whereas ShineRain won the contest by squeezing his solution into the time limit and also getting a decent score on the answer-submitting problem to boot. Congratulations!
In retrospect, it was obvious that had the problem setter set the limit stricter, I would have known that my algorithm wouldn't pass and try to find a better one. Ironically, only in the past one month, I was cheated by limits three times. The first time was in JOI when n was 30000 and the O(n2) algorithm could pass and I spent lots of time implementing an o(n2) one. The second time was Codeforces Round #406 when n was 20000 and O(n2) couldn't pass while I thought it could. Needless to say, the third time was today. I never had a right intuition whether my O(n2) algorithm could pass when n was within [20000, 30000]. It turned out that [20000, 30000] is a "segment of horror" to me.
Another bad thing happens when there is an answer-submitting task in a contest. when to embark on it and how long to spend on it has always baffled me, because I can't have a basic understanding of how hard this task really is at my first sight since I need to read the inputs. To be honest, I really hate contests with this kind of tasks, while they are ubiquitous in CNOI contests, including CTSC.
I think the basic solution is to improve my efficiency on coding. Had I coded faster, I would have found that my solution wouldn't pass faster, so I would have more time to respond. Also, when there's an answer-submitting task, I can have more than on it if I am more efficient on other ones.
Another thing I should do is that, when in doubt whether my algorithm can pass and I still have enough time, try to find out some more efficient algorithms first. If I succeed in finding them, I can have a better plot what to do next: first, write a naive solution which is pretty close to the improved one, and if it won't pass, change it into the improved one. This can prevent me both from wasting time on implementing complicated over efficient algorithms and becoming frustrated when my simple but less efficient algorithms won't pass.
Tactics are very important in CNOI contests, especially in those with answer-submitting tasks. I have been doing these contests for years but still, don't know how to deal with these tasks properly. If you have some good suggestions for me, leave your comments down below.
Late at night I did the qualification round of Codejam, and had the same lackluster performance. I did poorly in the last task, where I changed my algorithm multiple times and even got a wrong try.
It seems I had pretty much enthusiasm in the first two days, while in the next couple of days there won't be many contests so I may just write a few words. Please stay tuned, though.
April 9th, 2017
A normal Sunday, nothing happened. I was busy whole day and didn't do any coding. Good news is that all my large outputs in the qualification round passed.
April 10th, 2017
Sorry for the delay.
I continued to solve problems of GCJ 2016 final.
In problem B I did something really awkward. First I came up with the correct conclusion, but then I debunked it by giving out a plausible counter-example. Then I had no idea and was like thinking desperately for a long time until Reyna told me the conclusion was correct and my counter-example was somehow wrong. The issue of the example was quite hard to find. When I see no hope finding the solution, I should just re-think what I have disproved or re-read the statements.
Also, I got a wrong try despite the small amount of coding, which as you know was quite common to me.
Then I solved problem C quite easily, as I was spoiled by Petr in his blog once upon a time.
April 11th, 2017
Tried to solve problem D. Got small correct now.
April 12th, 2017
Proved my algorithm to SRM 583 hard by algebraic methods. It seemed that I just read moejy0viiiiiv's code in the first place and didn't care much about precise proofs.
Still working on problem D. Hoped I wouldn't need to read the solution this time. However, as I've spent so much time on it, I don't think I would solve it in CTSC should it appear that time, which would be quite fatal for me.
April 13th, 2017
I finally solved problem D. I'll show you my thinking route.
The statement can be found here.
First I was in an utterly wrong path. I tried thinking on shrinking the path, like changing zigzags into strange lines. When you have a 'C' shaped route, its length can be decreased by 2 moving it one step inside.
However, it didn't turn out to be as simple as I thought, as moving it one step inside wasn't an easy job. If we just delete every block in the corresponding column or row, we may accidentally create a much shorter path.
Frustrated, I had to try to find a brand new idea. I found that although shrinking C wasn't viable, decreasing length by 2 was, so I hypothesized that if the length isn't minimal, we can always decrease the length by exactly 2 someway.
Note that the parity of the length can't be changed. Thus, my hypothesis is equivalent to that it's possible to decrease the length to anything not less than the direct distance disregarding all blocks.
Thus, I wrote a program that for every block, if deleting it doesn't decrease the distance to less than D, delete it. This can be done in O((RC)2) for each case. I passed small this way.
However, I wasn't able to solve large for a long time until today it suddenly dawned on me that I should consider 4-connected components of blocks.
I found that as long as deleting a block doesn't create a new component, the distance can be decreased at most by 2, and proving it needs all the conditions listed in the statements, which was a good harbinger of my route being correct.
However not until tens of minutes later did I really have a solution---binary search. First, find a sequence of deleting blocks so that no new components are created at any moment of the process. Then binary search the time when the distance is exactly D, and voila, we solve the task in time, which is acceptable.
It is quite exciting when I finally found out the solution, but it is still obvious that I would have little chance to solve it during the contest. I still need to improve myself a lot!
After reading the solution to problem E, I don't really like it, and I still have some assignments for all candidates including a research paper to do, so I'll just skip it. While some algorithms mentioned in the solution look fascinating, I'll study them some day.
April 14th, 2017
Tomorrow and the day after there will be four contests---2 provincial selection contests(HNOI) and two contests between candidates(集训队互测, which is mentioned above and you can use search box to locate it), all of which doesn't affect the selection but I still hope I can win as many of them as I can.
Today jiaqiyang and Philipsweng came to Changsha to participant in HNOI in the next two days! As they are part of the candidates they will participate the other two as well. I was very excited to meet them. Wish all of us good luck the next two days!
April 14th & 15th, 2017
Sorry that I have no time today due to intense competition. This blog will be updated tomorrow, so stay tuned.
HNOI proved to be a disaster for me.
In the first contest, I was generally doing great but was tricked by the judges.
The first two tasks turned out to be about data structures, which were not my cups of tea, while the third one a math problem. So I stuck to the third task and spent a considerable amount of time, with no results.
Then it suddenly dawned on me that that task was actually a pretty easy task about FFT. Without any hesitation I implemented my algorithm and did all the stress testing, not much time passed.
Then I focused on the first task, and I soon had an idea. I implemented it slowly and steadily---first used brute-force, passed the samples, and then changed the slowest parts into a segment tree, stress tested it with brute-force.
Finally, I tried to solve the second one. First I thought it must be the most difficult one based one my usual easy-first sequence of solving tasks. However, I eventually found it to be the easiest one and solved it with ease.
Then I did some checking and found both my brute-force and final solution on task one have one small but critical issues. I fixed it within seconds, but it was totally horrible.
However, the final results turned out tragic. While both jiaqiyang and Philipsweng got the full score, I did not. My solution to task one fitted the time limit narrowly in my computer, which was faster than the
UPD: My solution to task E seems to be unable to pass it