matthew99's blog

By matthew99, history, 3 weeks ago, In English,

If you were a Chinese high school student, what would you need to do to become a member of Chinese IOI Team?

As you know, China is a hugely populated country, and we have our own special system of contests.

The following is only a brief introduction to our system. Details information in Chinese can be found here.

NOIP(联赛)

NOIP, namely National Olympiad of Informatics in Provinces, is an annual nationwide contest that nearly everybody can participate in. As the name suggests, it's held in provinces---in each province there's a site where this contest is held.

Provincial Selection Contests(省选)

This contest is held annually in every province. Members of the Provincial Teams(省队) are selected based on their performances on this contest combined with those on NOIP.

NOI(SC)(全国赛)

NOI(SC), or CNOI, namely (Chinese) National Olympiad of Informatics (Summer Camp), is an annual nationwide contest held in different cities every year. 50 members of the National Training Team(国家集训队) are selected based solely on their performances on this contest. Moreover, every member of this team receives the chance to get admitted(保送) by top universities in China.

Tsinghua University Training(清华集训)

Every winter, all members in the NTT are gathered in Tsinghua University(清华大学, abbr. THU) to have a 4-day long competition, which is called Tsinghua University Training.

(NOI)WC(冬令营)

(NOI)WC, namely (National Olympiad of Informatics) Winter Camp, in an annually contest where 15 candidates for the Chinese National Team(国家集训队候选队员) are selected based on their performances on this contest combined with those on THU training and their scores on assignments. WC is usually held in the same place where NOI was held the same year.

CTSC(中国国家队选拔赛)

CTSC, namely Chinese Team Selection Contest, is, as its name suggests, a contest where 4 members of Chinese National Team are selected based on their performances on this contest combined with their scores on THU training, WC and all kinds of assignments. Although 6 top-scorers have the chance to enter the final English Interview, most of the time 4 top-scorers are selected regardless of their performances in the interview. CTSC is always held somewhere in Beijing.

So, that's all you would have to do:

Travel to the capital of your province and do NOIP

Travel to the capital of your province and do the provincial selection contest in your province

If you are lucky enough to enter the provincial team, travel to a new city and do NOI

If you are lucky enough to enter the NTT, travel to Beijing and do THU training and in the meantime do all the assignments

Travel to a new city and do WC

If you are lucky enough to be a candidate, travel to Beijing and do CTSC.

All these processes together take more than a year. So if you want to participate in IOI2017, start your NOIP in 2015.

Finally, if you enjoy reading it, don't forget to click the like button.

Read more »

 
 
 
 
  • Vote: I like it  
  • +463
  • Vote: I do not like it  

By matthew99, history, 3 weeks ago, In English,

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.

UPDATE

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.

UPDATE

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +689
  • Vote: I do not like it  

By matthew99, history, 2 months ago, In English,

Well, sometimes our code sucks. We may end up spending much more time coding and getting rejected much more times on our submissions. During your debugging, your bugs seem to appear ceaselessly and you code starts to become messed up. Finally, when you see the lovely "Accepted" verdict, you find your code filled with patches and temporary variables, and you never wanna read it anymore. This is what I've been doing over and over again, especially when my code is lengthy and complicated. And I guess some of you may have similar experiences. So, what is the reason behind it?

First, I suck at naming my variables. I don't like lengthy names like "SumOfAllPrimeNumbers" or meaningless names along the lines of "a1", "a2", "a3". When the variable is related to a value, I name it "val". When related to, say, the set of all prime numbers, it is named "all". If I can't find a way to name it, "tmp" will already be the thing I'd turn to. Obviously, the awkward thing is that I often end up having two variables with the same name. Consequent names will be like "val1", "all1", "tmp1", which are ridiculous. Therefore, I tried using names like "foo", "bar" to make my code great again, but to no much avail. Also, when I change the name of a variable in my code, like changing "all" to "All", I always have the temptation to use "all" instead of "All", which eventually makes the situation worse.

Second, I am always confused at whether I should replace some codes with a new function. Well, an obvious method is when two parts are similar, replace them with one function. However, awkwardness comes when two parts are partly similar. For example, in one part we calculate the sum of all numbers, while in the other part will calculate both the sum and the product of all numbers. If we replace them with one function, we end up either not calculating the product or calculating it when it is not required. Also, if we need to add some new codes to somewhere which you have already replaced the codes with a function, we'll have a hard row to hoe. Besides, expressions like "", "" are annoying, and I always hesitate at whether I should replace them with a new constant.

So, have you ever encountered any similar predicaments? What's your solution to them? Also, can you list more kinds of awkwardness in coding? Be free to leave comments down below.

Read more »

 
 
 
 
  • Vote: I like it  
  • +189
  • Vote: I do not like it  

By matthew99, history, 14 months ago, In English,

Life is like this.

Read more »

 
 
 
 
  • Vote: I like it  
  • +250
  • Vote: I do not like it