matthew99's blog

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

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

»
3 weeks ago, # |
  Vote: I like it +85 Vote: I do not like it

Could you make a prediction of China team members this year?

»
3 weeks ago, # |
  Vote: I like it +54 Vote: I do not like it

I wish there was an online mirror.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    There is indeed an online mirror for NOI, tasks in Chinese, but none for CTSC.

»
3 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

Good luck & have fun

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it +71 Vote: I do not like it

Could you make a prediction of the problem setters?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +62 Vote: I do not like it

    I have no idea. But definitely not me :)

    C'mon man. I'm not Nostradamus. I am poor at prophesying.

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
3 weeks ago, # |
Rev. 2   Vote: I like it +51 Vote: I do not like it

It turned out that [20000, 30000] was a "segment of horror" to me.

You reminded me that sad memory from CF406D. Every moment with that problem was a big surprise for me.

  • When I read the statements, I never thought O(nq) won't pass. I couldn't believe such simple implementation problem is in Div1D, so I read it again and again.
  • I didn't find any flaw with my understanding, so I tried to find a flaw in my algorithm. I failed to do so, so I started coding. And it turned my algorithm was not WA, but TLE.
  • I tried to find a flaw in my complexity analysis, but it was a trivial dfs — so I failed. I never thought the model complexity was o(nq), so I thought constant optimization was a bottleneck. It was weird, but whatever I did.
  • The model solution was O((n+q)lg^3(n)) — with tons of complex algorithm which have no good constant factors (in my experience). And the author claims that is faster than O(nq) simple dfs under given constraints (WHAT?)
  • And when we compare their time, it really is. (WHAAAAAAAAAAT?)

I actually still can't believe how point 4/5 can happen....

»
3 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

Quick question. Are you not allowed to get on team twice in china? Or is it mostly so, because it's hard to get on team?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Good question.

    Years ago there was no restriction, so some participants like Yifei Zhang won IOI gold medal twice.

    Now, the restriction is there that if you win an IOI gold medal, you are not allowed to enter the National Training Team.

    Furthermore, non-high school students are not allowed to get pre-admitted nor enter NTT, which postponed my entering by two years. (Actually were I one year older I could have entered the National Team in 2015, instead of failing it in 2016, who knows?)

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
3 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Man, just reminding :) Keep it up matthew99

»
2 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
2 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

What was the second problem on 8th April?

»
2 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
2 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

The remaining players:Dylans and Altria-PenDragon

»
13 days ago, # |
  Vote: I like it +29 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
12 days ago, # |
  Vote: I like it +106 Vote: I do not like it

It seems my last effort to squeeze my solution gave rise to a boner.

This is 1st time I see the word "boner" used in such way @_@.

»
11 days ago, # |
  Vote: I like it +16 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
10 days ago, # |
  Vote: I like it +46 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
7 days ago, # |
  Vote: I like it +34 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
7 days ago, # |
  Vote: I like it +40 Vote: I do not like it

Cool blogs, can you describe more about your research paper? How you started it? How long it takes to write it? What is the theme? Why do you started to write it?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    It's part of the assignments. 15 research papers of the 15 candidates will be published in the future.

»
6 days ago, # |
  Vote: I like it +19 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
6 days ago, # |
  Vote: I like it +22 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
31 hour(s) ago, # |
  Vote: I like it +24 Vote: I do not like it

Auto comment: topic has been updated by matthew99 (previous revision, new revision, compare).

»
10 hours ago, # |
  Vote: I like it +15 Vote: I do not like it

What was wrong with random_shuffle?

  • »
    »
    9 hours ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    changing random_shuffle into REP(i, 0, n) swap(a[i], a[Rand() % (i + 1)]) got me accepted(Rand is rand() in linux and rand() << 15 | rand() in windows).