In this post, I'll record my life from now on all the way till the end of CTSC(China 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 judges.
But it was just one of these days. The second day turned out to be a total failure.
After reading the first two tasks, one of which made no sense to me and the other of which a geometry task, I decided to go for task three.
Task three happened to be a math problem, which wasn't such an obstacle, but solving it took me quite a long time due to all the tiny mistakes I had made. It was 2 hours since the match started then.
Task one seemed to me a complicated task with two separate parts, the first of them quite simple and the other kind of hard. Nonetheless, after writing a small program and did some testing, I found out that a simple dfs can do the second part efficiently. The rest of the task was trivial, and I solved it before 11:30, with 1.5 hours left.
I soon found out a plausible solution to the second task and coded it out happily in the illusion that I should get a full score. I managed to pass all the samples before 12:30.
The rest is history---of course, I didn't get a full score. My solution to the first task was wrong and got only 40% of the score, and the more staggering fact was that my solution to the second task didn't get any score. After some meditation, I debunked my solution and was quite surprised at the absurdity of my solution and my gleeful reaction to an imaginary accomplishment.
That is my sad story these days.
Obviously, the biggest bane of my woe was my ostensibly correct algorithm to the second task in the second contest. It should be an axiom that no idea is better than bad ideas. Having no idea makes you frustrated, while you still have a decent control of the contest, because you know what you are doing and what you should do, either write subtasks or try other problems. However, having a bad idea means you are misled to an abyss of passiveness, as you no longer control the contest, and are fully unconscious of what you are actually doing, let alone what you should do, and, most severely, never change the way of doing until you notice the issue of your idea hours later or even after the contest.
There will soon be another Codeforces round. Wish me good luck!
Because I was really sleepy, I just did the first four simple tasks and didn't find the solution to the fifth task, which was actually not difficult.
It seems the truth is not quite what I purported above.
The third task in the first contest, purported TLE, was actually wrong. I, not the judges, am to blame. It seems my last effort to squeeze my solution gave rise to a boner, which somehow, I didn't find during the contest although I did some stress testing about it. I am now quite sure that it was because my generator was too weak. It was actually a fluke that the solution got 70/100, giving me the illusion that it was because of slowness instead of incorrectness.
Also, I still haven't mentioned one of the tasks yet---the third task of the second contest, which was because the data was modified and when I updated the post last night, I didn't know the final results. However, it seems the data is not the only thing to blame. I made another blunder in my solution---I didn't take the remainder in one sneaky place, and it proved furtive. The modulus was quite small, and the range of the data I did stress testing on was small as well, so all these efforts have no avail to fixing this issue.
My mistake on the first task of the second contest is also a somewhat algorithmic one. One essential speed up in my dfs is wrong. However, simply swapping two lines can make my solution great again.
The second task to the second contest turned out to be the most difficult one. After some thinking, I found out a solution. However, I don't think I could have made it during the contest as it is quite tricky.
April 18th, 2017
Spent time on Codeforces #409 E. Despite all the rejected submissions, I actually managed to solved it with little debugging but instead finding every mistake with naked eyes(Can eyes with glasses be called "naked"?). I was exhilarated by the fact that by the time I couldn't manage to find any other mistake, my program had really got Accepted.
Well...Obviously, I should have made fewer mistakes, but at least it's been ages since I can find all mistakes with naked eyes.
Apparently, I am more sanguine than before now. Everybody experiences boom and bust during his competitive programming career, but no bust lasts forever. I never feel contented with my coding skill, but I feel relatively fine with my thinking skill. I crave having a coding skill as strong as my thinking skill. I have thought about doing a full-scale revolution on my coding habits, but no sooner than my enthusiasm waned. However, several years ago I had the exact same feeling on my thinking skill. Unfortunately, if I had a time machine and traveled back to the past and met my past self, I would have no good way to enlighten him, because the natural accrual of thinking abilities has benefited me the most. I think it's the same with coding skill.
April 19th, 2017
Worked on my research paper, which is about recursions of a given sequence.
Because it's part of assignments for the candidates so I have to use Chinese, which of course I'm fluent in, but after spending so much time on English recently I actually sometimes came up with English and had to do the translation. For example, I would like to use "blah blah blah, which is blah blah", which can't be translated into Chinese easily(Like this sentence). Actually, I think writing in English can be more precise than writing in Chinese because it's easy to make my sentence equivocal in this language(Prepare for this: "爱上一个人" has 4 interpretations, which are "Love someone", "Love to roast the broomstick with someone", "Love the previous person", "Love to be alone").
April 20th, 21th, 2017
Kept revising my research paper, and doing other parts of the assignments.
April 22th, 2017
I continued to do the assignments and did google Codejam R1B. Although no wrong try in smalls, I was too slow. However, I don't mind it because I purposely spent more time to be more steady. Hope all three larges can pass with this steadiness. (update: they passed)
April 23th, 2017
Got all my assignments done and submitted. Hope I can get a decent score on them. At least I can't bear if I can't stay No.1 before CTSC has even started.
By the way, since some of you asked, my research paper was on Berlekamp-Massey algorithm.
They will be a Codeforces round later. Wish everybody good luck.
April 24th, 2017
My performance on this Codeforces round was a flop.
My B, C and D got staggering 8 failed attempts in total. 2 hacks were to no avail.
To add insult to injury, I didn't pass the first sample of problem G during the contest. Instead, I passed it minutes after the contest after some tiny modifications. Actually, I'd rather it has more mistakes than these. The biggest pity is that you don't get your solution right during the contest, but get it correct right after it.
Upsolved E, F and G during the day.
April 25th, 2017
Upsolved 798E. It needs an algorithm that I didn't know before.
April 26th, 2017
Solved a task from CTSC2015. I was pretty sad that every mistake I made was still the most primitive ones, and the most irritating thing was that no matter how tiny changes of my code, many mistakes would come out.
It should be simple for everybody to at least get the names of the variables you used in the code right, but this seems to be a tough thing for me. I think around half of the mistakes and also compile errors come from this issue. If this issue isn't fixed during CTSC, I'll pay hard for it.
April 27th, 2017
Upsolved a task from CTSC2016. It's the very task I failed last year. It seems pretty simple to me now. I don't know why I didn't manage to solve it back then.
April 28th, 2017
Today I tried to upsolve what is said to be the most challenging tasks from CTSC in history---CTSC 2011 infinite(无穷图的桥, bridges on an infinite graph). Although this task has been a nightmare for many people for many years, it is actually not so challenging to me. Still, I think it's one of the most interesting tasks from CTSC(I hope they will make more tasks like this one this year. This kind of tasks are much more intriguing than squeezing, complicated data structures, or boring answer-submitting tasks).
Besides, what made me happy was that I made fewer mistakes today and passed all the test data upon passing the samples.
By the way, the algorithm introduced here really helped me a lot.
Good news is that with 134 contributions, I am one of the top contributors now. I sincerely thank you for your supports. Now I am finally a man that has been to both top rated list (for a long time, #4) and top contributors list.
April 29th, 2017
Today I got angry about RCC qualification round.
My problem D got TLE twice because of memset. I memset all the array, and there is a total of 100000 cases per data. What I did on the second attempt was to do some input optimizations, which really seemed necessary to me that time. I was surprised it wasn't the cause of TLE.
The most irritating thing is on problem E, on which I write a randomized solution, but the use of random_shuffle would lead to WA. I was at my wit's end when I finally decided to probe whether it was due to some environmental differences, and surprisingly it paid off.
However, I spent around 20min on that issue, and I didn't manage to fix the last tiny issues of my solution. Had I had more time I would have at least more (much more I think) chances to get it passed.
Lesson learned, never use random_shuffle on RCC contests.
Update: my solution seems too bad to get accepted.
April 30th, 2017
Preparing the presentation of my research paper on CTSC.
May 1st, 2017
Did a preparatory exam for CTSC at my school. I only managed to solve 1 out of 3 tasks. The rest 2 seemed really hard to me. One of them requires Minkowski difference, which I am not familiar with, and the other requires some mathematical insight, on which I struggled a lot even after reading the solution. It's like another SRM582 hard for me, which I did have a hard time on.
May 2nd, 2017
Did a preparatory exam for CTSC at my school again. It was quite reminiscent of HNOI. The first task got RE because the array saving all the edges required 2 times the number of edges as the graph was undirected. My algorithm on the second task was bullshit again. I made some annoying tiny mistakes coding all my solutions as well. To add insult to injury, I spent a huge amount of time coming up with a solution to the third task, which was not extremely difficult.
May 3rd, 2017
A one-day hiatus. Leaving Changsha to Beijing tomorrow. To train two days there. Then to begin the climatic battle---CTSC.
I still need to perfect my presentation, and I hasn't begun writing my English speech for the final 6 to 4 phrase yet(Although if I am not lucky enough to get into top 6, this speech will be unnecessary, and if hopefully, I am top 4, were I not to be too hilarious on stage, I would be quite easy to enter the team).
Solved 803E. The only bad thing was that I made several mistakes during the compiling phase, but once it passed the compilation it passed all data, no debugging needed.
I should keep the pressure on coding these days. I shouldn't try to solve something challenging now because it's a question whether I can make it before CTSC.
May 4th, 2017
Arrived in Beijing.
There will be a Codeforces round soon. Everybody good luck and have fun.
May 5h, 2017
I hacked four people during the Codeforces match, while didn't manage to solve E, so the result was just normal.
I shouldn't have been so excited when I got rank 3 in the middle of the contest, which reduced my motivation to solve another task. Also, I shouldn't have spent so much time deciding whether to hack, to solve E or to read F, on which I ended up doing all, none succeeded.
Had an exam in the morning. Rehearsed the presentation in the afternoon.
May 6th, 2017
Rehearsed English speech in the interview.
It's kind of like another TOEFL speaking test for me. I still stammer a lot and make a lot of hilarious mistakes.
May 7th, 2017
The first day in the CTSC event. We registered and tested the machine, during which I learned that there would be no answer-submitting tasks, great news for me.
Tomorrow there will be the first contest of CTSC. If I don't want this post to be a farewell post to my OI career, I have to try my best. Wish me BEST luck!
May 8th, 2017
The first contest in CTSC.
After reading all three tasks, I found every task pretty simple.
The first task had a neat solution which was not too hard to find. I finished it and stress tested it before the one-hour mark.
With a smart insight, the second task was nearly identical to a task in IOI2016, which I knew the solution to. I finished everything before the two and a half hours mark.
The third task seemed to me something that could be maintained by a segment tree. However I struggled a lot to get it correct. The worse thing was that my solution outputted 'nan' on generated data and I tried to get rid of it, only to have my solution too slow to fit into the time limit. Thus, my solution was wandering between outputting 'nan' and being too inefficient, which was the case until the very end moment.
Under the thought that everyone except me could get the third task correct, I was kind of sad after the contest. However, it happened that many people either didn't have the insight on the second task or forgot the solution to the IOI one, and many people had the same situation as me on the third task.
The most dramatic thing happened after I read my results this afternoon---perfect score!
How can that be? My solution to the third task actually got accepted.
After some communication, the reason turned out to be that my generator was actually in some aspect stronger than the setter's.
Ironically, this was the same person who set the simple task I didn't solve last year. C'est la vie!
So I have a very decent preponderance of score now, with 50 points more than rank2 today and 7 points under the scoring system of CTSC(100 in total).
Tomorrow everybody will give his presentation, and the second contest will be on the day after.
May 9th, 2017
Presentation day. Everything went well in the morning. However, when the scores came out this afternoon, they were really surprising. What we had expected to be good didn't necessarily get a decent score. Good thing is that the differences between our scores are tiny.
May 10th, 2017
The second day of CTSC.
The first task seemed to be pretty simple, but the second one seemed intriguing, and the third a little unsolvable.
Thus, I decided to spend time on the second one. However, I was in the total state of mess, and after a long time of thinking still had no idea.
I shifted my focus to the first task, hoping that after refreshing my mind by doing something else, I would be able to find something new on the second task.
Then I found the first task not as easy as I had thought, but I re-found a solution within minutes and implemented it pretty quickly.
Still, I had no much idea on the second task. I kept on thinking about extreme cases. To add insult to injury, it seemed that even extreme cases didn't crack easily. The full solution seemed to be as far as Mars. I kind of wanted to just write some subtasks to ensure that I shouldn't fail too hard.
After some calculation, as long as I could get around 200 points in this contest, I would still maintain my championship even if everyone else were to get 300. However, it seemed the gamut of subtasks I could solve waned badly. I had thought I could get 70 on task 2, but after testing my solution I found I could merely get 45.
What was worse, there was little time left. My 30-point solution on task 3 turned out to be not so correct as well. Knowing that the data was generated randomly, I decided to implement a heuristic solution with a magic number and finished it before the very end.
However, after the contest ended, it first came to me that the data to the first subtask of task 3 were not generated randomly, while those of the other two were. Great, 30 points gone.
Also, it turned out that I could have gotten a more decent score on task 2. I found some better solutions during the contest, but I was aiming for a full solution that time and didn't pay too much attention to them. When I gave up, it was too late and everything was done just in a hurry. Therefore, it's normal that I thoroughly forgot these better solutions after beginning to solve subtasks.
A ridiculous thing was that the solution to the first task was even easier than I had thought. I thought the problem setter didn't find out the easier solution, but it turned out that it was the harder one that he didn't find, ergo the strange restriction that enabled the easier solution.
After knowing that, as a case of deja vu, my solution to the first subtask of task 3 managed to pass it again, and that I got all 175, it's obvious that I had no problem maintaining my national team membership. Actually, I got rank 1 with a decent margin---11 points higher than the second highest score by the 100-point system of CTSC.
All is well that ends well. CTSC has ended, so let's meet the other three members.
xumingkuan, who, despite the failure in the first contest, managed to solved the third task in the second contest, which catapulted him from rank 12 to rank 2. This and its counterpart, falling from top to bottom, are actually common phenomena in CTSC. He also ranked 5th in NOI2016.
jiaqiyang, another IGM in China. He got 195 in the first contest, and 155 on the second. Despite the normal performance on CTSC, his epic performance on WC2017 made him ranked 2nd before CTSC and eventually made him prevail.
eds467, the only 11th-grade student who entered the team. He got 225 in the first contest, and 135 on the second. Despite the lackluster performance on the second day, his advantage accumulated when in the course of THU training and WC2017 combined with his fair performance on the first contest make him ranked 2nd during the hiatus of the two contests, and prevented him from failing. He currently had the 2nd highest rating on UOJ, where his post including record of CTSC(in Chinese) can be found.
Congratulations to all of them!
Tomorrow is the farewell day of CTSC, and I will leave Beijing and go back to my hometown. Therefore, this is the end of the post. Peace!