I_love_Hoang_Yen's blog

My story at ACM ICPC World Final 2016
By I_love_Hoang_Yen, history, 9 years ago, In English

My team (me + flashmt + nguyenhungtam) was probably never noticed by anyone, but we were actually aiming for medal. And I think we performed ok in the final, ending up at #15, still need some more luck & brain to win a medal. Anw, I decided to share my story. Btw if you are Vietnamese, you can also read this.

Back story

In the ACM history, a Vietnamese team has never won any WF medal. 5 years ago, team of ktuan (only Vietnamese red target on Topcoder) had high hope, but ended up at #17. 4 years ago, team of ConanKudo also had high hope, but messed up in the first 3 hours and ended up at #17.

So I really wanted to win medal. And I've been planning for this World Final for several years..

Team formation

I've chosen flashmt as teammates for several years, but were not able to choose any third member. Since I only want to select Vietnamese, we have only few good options (darknstd, infrmtcs — both IOI silver medalist). After the WF 2015, I read this comment by fhlasek about the story of his team, and decided to pick an IMO guy instead. Thus, I picked nguyenhungtam who was IMO medalist but has very few experience with programming / algorithm and I trained him from that. It was a good choice, I had a lot of fun watching/trying to understand problem solving from Math people perspective, and we did much better with better mathematical imagination.

Regionals

At regionals, nguyenhungtam has few experience, so I was really afraid of losing ticket to WF. Anw, we won in Jakarta regional which guaranteed a ticket. We were #3 at Singapore regional, but I always believe we can do much better as nguyenhungtam improved very fast towards WF.

Strategy

Our strategy is flashmt will code mostly all problems while nguyenhungtam and I solve all the problems on paper. This is mainly because I usually fail to code simple things in important competitions (anw during this WF I implemented B & K, both had 1 wrong submission, but I think it is ok considering my current standard). And we also believe that the WF problemset requires more thinking, so 2/3 team time thinking is good.

And indeed, there are many positive side on this strategy:

  • I think I had much more time solving problems.
  • The algorithm needs to be very clear before we start implementing them.
  • Since flashmt's coding skill is very good, leaving him the only one coding is definitely good enough.

My take on the WF problemset

I think the easier problems are ok, but maybe too many of them (8 easy problems..). I liked K. The judge solution for B is nice, but I think they are not very familiar with Divide & conquer DP optimization, thus this problem became copy-paste divide & conquer DP from our notebook. (I publicized our notebook here — you can use it at your own risk)

There were 5 hard problems F H I J M. I think H I J are too hard, M is hard to implement, so my team only had one choice of solving F: either we solve F and get medal or we don't solve F and don't get medal. I think the choice is very limited this year. Maybe if there was 1 medium problem instead of easy problem, there would be some choice for teams after solving easy problems.

Anw, my team strategy worked well. We always have something to code until we finished the 8th problem. And flashmt did not have too hard-to-debug bugs, so we were solving problems quite fast considering our level.

After this WF, probably I'll partially retired (probably still participate in CF rounds & big contests but mostly no training). If you have questions for me in comments, I'll gladly answer.

UPD: Special thanks to my girlfriend, ktuan, ConanKudo and ngfam_kongu. I inherited the spirit from ktuan by hearing stories about him, and ConanKudo and ngfam_kongu trained me to this level :)

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

Comments Comments (41)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

I want to Vietnam have a medal. :)

→ Reply
»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

how much time it will take to become red on codeforces? given that you will start from nothing

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    It depends on you. A few months, a few years or maybe never (sorry, but it's true)

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +74 Vote: I do not like it 
    100 / (your smartness * percentage of time you spent)

    e.g. your smartness = 100 and you spend 100% --> 1 year. Your smartness = 0 or percentage of time you spent = 0 --> infinite time.

    → Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Since you have planned this World Final several years ago, the choice of your university is it related? Will you participate again? Congratulations.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    This is the last time I can participate due to age limit / number of regionals / number of world finals.

    I planned to go to NUS and participate with flashmt several years ago, (obviously since he was in NUS).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      How many times can I attend acm icpc regional in one year?

      → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

  1. How should we start the contest to win gold medal? //Maybe some tips that you can use before(like eating a chocolate or smth like that)

  2. Should we always start with most easiest problem?

3.After which time should we stop solving some difficult problem? Maybe, you always get WA on test 5, do not give up, but time decreases too.

4.How much time do you spend for training per day?

Thanks for posts like that, it gives us a motivation!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
    1. I don't know
    2. Yes
    3. If you are talking about training, just stop when you feel too frustrated.
    4. I spend as much time as possible (in high school / university that means > 12 hours on many days).
    → Reply
»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

You gave us green light so you'll probably get a lot of noob questions that you don't want and that everyone's tired of. :P
Like: how does one become red? (not asking)

Or this one:
Do you suggest I spend time learning things that I don't know (like FFT, Max-flow, dp optimizations, etc.) or just hunting problems?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    I have lots of free time now that I don't need to train for ACM =)

    If you are doing ACM, yes (all 3 of these have appeared in ACM WF before). Otherwise no.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Wow, you couldn't have been more right :).

    → Reply
»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

"I inherited the spirit from ktuan by hearing stories about him"

If possible, why don't you tell us these inspiring story too?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    If I tell you here in few words, it will most likely be very boring.

    Anw, in my generation, ktuan is well known as the best Vietnamese competitive programmer: only red target on Topcoder, 2 times Google Code Jam finalist, #2 Facebook Hackercup. He also aimed for ACM WF medal (but failed).

    During that time, there was no one of same level as him to help him train (actually nowadays we have at least some other people around my level, so for me it was much easier). He reached that level because of constantly forcing himself to move forward: strict rules for himself / constantly finding new methods / very serious attitude towards training. One example is always debug by printout + eyes in team training (instead of debugging on computer). He also remembers + link problems very well and sometimes solved problems after couple of years after reading the statement.

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

You ended up in 15th. That's still very very amazing, considering the fact that only the best coders from around the world participated in the contest.

→ Reply
»
9 years ago, # |
  Vote: I like it +17 Vote: I do not like it

First of all, congratulations!

We usually talk about mathematicians, who do really well in competitive programming, but, can't a competitive programmer learn mathematics till the level of IMO medal?, do you think is worth spending some time learning mathematics (e.g. trying to solve IMO problems) to improve in competitive programming?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think that, unless you are going to spend significant amount of time solving IMO problems, you probably are not going to gain much. And in Vietnam the way we teach Math is usually very different from programming (e.g. no proof), so Vietnamese IOIers are very weak in Math topics or when Math imagination is required to solve problems. (This is changing though, after 2 Math major students ll931110 and I_love_tigersugar won 2 gold medals for VN after many years).

    → Reply
»
9 years ago, # |
  Vote: I like it +17 Vote: I do not like it

I assume you're studying CS, so now that you're not going to solve problems as much are you planning to just chillax or start a new field maybe something in AI or whatever?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Well, past year was extremely stressful for me: I always do not have enough sleep and always behind my own training schedule. So probably I'll spend some time relaxing & taking care of myself.

    Anw, I always wanted to study some Machine Learning (and participate in Kaggle contests for example), and study some other things not related to programming / CS.

    → Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

After spending those > 12 hours of training per day, what's a real-world benefits you got/will get ?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +34 Vote: I do not like it

    I practiced much because I like it, so I don't really think about cost / benefit.

    Anw, probably you already heard people saying things like you no longer need to worry about interviews @ big companies / amazing debugging skills.. (it is true btw). So I want to say about some things that people don't usually talk about:

    • After training for contests, I handle pressure much better. Several years ago I always did very terrible in contests. This year I was quite relaxed in big competitions.
    • I became quite famous amongst the Vietnamese competitive programming community. I know a lot of interesting people, some completely changed my life.
    • Our teamwork is quite good this year. Most of the time when I am not coding, I try to figure out what we can improve as a team, which helped our coordination a lot, and also applicable in real life :)
    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

"I inherited the spirit from ktuan by hearing stories about him". Is ktuan a boy? :P

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What would you do hypothetically if you want to participate in ICPC but you're going to a university that has never participated yet and that university is in the same region as Harvard and MIT?

Do you quit? Train your own generation of competitors? Transfer?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I'd avoid myself to enter such situation.

    It's very hard to build up a generation of competitors. The most heavy obstacle is that, not many people will share your vision and put much effort into it. Usually such things take many years and good personal skills to achieve (time to figure out how to find people with same interest, time to start clubs or such activities, time to convince other people to fund you, time to train some people and show good results...). And I think it is only feasible if you're a univ professor and people actually have reasons to hear you.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

  1. Did training improve your implicit thinking ability, or did it give you better tools and the knowledge to efficiently use those tools? If both, then is which one happened more?

  2. How did you find an IMO medalist's thinking process different from a programmers?

  3. After you've taken a break and relaxed, what are you going to study? I don't mean just CS related subjects, but anything that interests you.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it
    1. It's hard to answer, since I don't usually think much about this when I do things. Anw I think it improved my thinking ability.
    2. Math people tends to be much better in reducing a complicated problem to simpler ones, better at dividing complex problems in to smaller cases, and usually more imaginative.
    3. Most likely Machine learning + Psychology.
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      Donald Trump: we will build a yuge wall of text!

      Protip: psychology as a science is complete crap. Statistically, over half of the reported results are falsified upon replication attempts (source; the sample size isn't big, but even the bottom end of the  ± 3σ range gives 1/3, which is an equally alarming result for prestigious journals) and far more are found to be overestimates. That article gives more examples, which show that all science reports results that were falsified upon attempted replication too often. This has an impact on taught psychology: it has to be founded on prior reported results, and if those are crap, then it's just propagating crap.

      While the problems could be fixed with hard science, how do you expect psychology to be done? Can any man objectively look into people's minds? Can you listen to people and hear anything else than a (modified) echo of your own thoughts? No. The most we can do is interact with each other and form our own views of people — often interesting, yet likely always wrong in some way. That's not what psychology does and it's even harmful to give it a special name and position, since it leads to a form of elitism and unwarranted legal power.

      <offtopic>

      The root of the problem with modern science is this: everyone needs to eat and most people have a family that also needs to eat. How does ongoing research feed you? Answer: it doesn't, only finished research does. Some forms of research feed you better than other ones, some (that go against the current political narrative) don't at all. If you (note: a general "you", not necessarily you specifically) publish negative results, or positive results in an undesired direction, you're less likely to get further funding. That creates fraud and subconscious bias. With the volume of research being published and the sorry state of review (for the same reasons plus laziness), you get compromised science.

      I submitted my bachelor's thesis yesterday. It's quite clear what it does and under which assumptions, and it's just modelling, so it can be checked quite easily. Still, it's about something which is known very little: subsurface oceans on moons of Jupiter/Saturn and other space objects which one would expect to be fully frozen (as far as water is concerned, not liquid hydrocarbons, nitrogen etc.). We really have only photos and some long-distance measurements like magnetic response — apparently, there's water under ice cover, but we don't even know how deep it is. There are some guesses as to why it's not frozen, but all we can do is make as many hypotheses as possible and hope for a new space probe with better technology that gives us more data to check the hypotheses against. It's even hard to model when not considering the lack of data (how to deal with two interacting systems — water and ice?). So I made one fairly simple model, a program which can be modified to support other ones, ran it and reported the results I got. Nevertheless, I don't expect it to be even a step in the right direction — only a step in a direction.

      One thing that gets talked about a lot is global warming. Oh wait, the term is rather "climate change" now after real data says there's been no global warming in the recent years. What did the "scientists" do? Modify the data. http://lmgtfy.com/?q=noaa+fiddles+with+climate+data In the end, when we look at global temperatures for the past centuries and extrapolated even longer, we find out that climate changes all the time and by all accounts, it should be getting warmer now (http://lmgtfy.com/?q=little+ice+age). There really is no indication of human actions having a worrying effect on climate, so it's all just a big scam — getting funding for research to prevent a fictional global threat.

      Here's something fun: http://lmgtfy.com/?q=global+cooling. I have a bunch of articles from newspapers going as old as the 19th century trying the same boogeymen of "we're destroying Earth, we're all gonna die!", with something different everytime. Science lol!

      </offtopic>

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Thanks for the wall of text, it was really interesting and helpful :)

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Let's make codeforces nerdy again

        → Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

"And we also believe that the WF problemset requires more thinking," — I guess you got disappointed xD

→ Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Thanks for the story ! It's really inspiring. I'd like to ask some things if you don't mind.

My team is currently training regularly for ACM, but every time we did an ICPC virtual contests, we did not do that good (only solve 3-5 problems), we feel that the other problems too hard / still impossible even if we have an infinite amount of time to do it. I'm thinking that we as individuals are not good enough as our team only consists of 1 blue and 2 cyan coder. What do you suggest for our training (to practice more individually or training as a team) and what kind of problems do you usually use to train ? Thanks in advance. :D

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    When I was in high school it is usually the case that I can only solve 1 or 2 problems out of 10. Usually you should try problemset that you can only solve 40-50% of problems.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      (I am just a bit curious and suspicious, forgive me if I say something wrong)

      When you were in high school, you was the highest rated coder in VNOI. You were also an IOI medalist plus many extra things. According to the old rating, you became red after only five contests. Even tourist could not do that.

      Was you really only able to solve 1 or 2 out of 10? Were those problem set normal or all IOI, ACM problems :))?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +31 Vote: I do not like it

        There are so many things wrong in your comment..

        1. tourist's first contest was 6 years ago, when the rating system is completely different (currently it is much more inflated)
        2. I did not go to IOI
        3. Russian training camps problems can be very hard.
        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it +30 Vote: I do not like it

          Sorry :)) As you are very famous in Vietnam, there are too many rumours about you. A friend of me even told me that you got a gold at IOI. :)) But anyway, you are still a great Vietnamese coder, IOI medal or not, you are still famous now.

          But you know that knowing this has a great impact on me, as I always thought that only IOI medalist could make it so far. Now I know that hard work will definitely bring me to somewhere I have never been to. Thank you for your inspiring story and comment. :D

          → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    The green coder wrote ...our team only consists of 1 blue and 2 cyan coder.

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In your opinion , What is the best strategy to use in contests that have easy and medium problems ?

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Ohh, please let me ask another question :D

What method do you think is the best (or what method did you use) to train an IMO competitor, if he already knows how to code, but not so many things about competitive programming?

→ Reply