kpw29's blog

[ICPC blog series #0] My last ACM experience
By kpw29, 3 years ago, In English

Disclaimer

This isn't really a first tutorial in the series. If you are interested in reading what participating in ICPC World Finals feels like, you can enjoy my pathetic behind-the-scenes story of the Cambridge silver-medal performance in WF2020. I tried to write a spoiler--free blog so that it contains minimum information about the problems.

Motivation

In 2016 I have written a blogpost My first ACM experience. It made sense to me to also close some chapter of the book by writing up about how my last serious contest went. I advise not to take the blog too seriously, it is just an honest stream of consciousness (some facts may not even be 100% accurate, though I will fix things people point me). Feel free to comment, praise, or hate. For a different perspective, check out IBaloff's blog.

The hero and heroine of the story other than me are David (_h_) and Maja (zdolna_kaczka) to whom I am very grateful for allowing me to share our experiences.

The contest

It's waaay too long so I hid it in a spoiler

Thanksgiving

Attending ICPC finals was a fulfillment of my childhood dreams. I have met so many Codeforces friends and legends of the competitive programming world. I would like to thank:

  • Maja, David, and our coach Andrej, for a beautiful trip to Moscow together

  • Uni of Bucharest: freak93, livlivi, bicsi, theodor.moroianu for hanging out together when my teammates were too tired of me, and for not being able to use long longs properly.

  • The legends: Petr, MikeMirzayanov, Benq and andrewzta for agreeing to have a picture taken with them.

  • Other contestants whom I talked to and can recognize their CF handles: Monogon, awoo, TheOneYouWant, SecondThread, yarek, Anadi, w0nsh, znirzej, tabasz, kobus, Devil and probably many more I don't remember.

  • Last but not least, MikeMirzayanov Bill Poucher for an awesome platform of Codeforces event, and everyone from the hosts who helped to make it possible.

Some pictures

My team
ICPC Venues
Famous
  • Vote: I like it
  • +348
  • Vote: I do not like it

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

I had a great time too and I'm glad I could meet you. Congrats to your team on the silver medal!

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

Great job! Btw how do you solve D? I did it in-contest by greedily applying GOOF but I don't know why it works ...

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

    The question: ‘Can we obtain $$$[l..r]$$$ as a subsequence via foldings?’ turs out to be independent on prefix and suffix (i.e. equivalent to obtaining $$$[l..n]$$$ and $$$[1..r]$$$). Then, the greedy strategy for obtaining a given prefix/suffix can be easily proved to be correct.

    PS: Perhaps ironically, I was one of the authors of a harder version of this same problem about 4 years ago for one of the romanian selection contests for IOI. (one of my favorite problems)

    https://infoarena.ro/problema/origami2

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

      Could you elaborate on both of these?

      independent on prefix and suffix

      Then, the greedy strategy for obtaining a given prefix/suffix can be easily proved to be correct.

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

        Let's start with the easy one:

        Then, the greedy strategy for obtaining a given prefix/suffix can be easily proved to be correct. — Suppose you are only allowed to fold from the left hand side and you want to obtain some suffix $$$s[l..n]$$$. Suppose you can fold at position $$$i$$$. Because of the perfect overlaps, folding after position $$$i$$$ essentially means erasing prefix $$$[1..i]$$$. After folding you have the subproblem on string $$$s[i+1..n]$$$, which only has more available folding positions (no position that was available before for folding can now be unavailable). So it's always good to fold when you can (it doesn't matter if you fold on smallest $$$i$$$, but it makes the implementation a lot easier).

        independent on prefix and suffix — Let's suppose our goal is to reduce the string $$$s$$$ to some subsequence $$$s[l..r]$$$ (and let's suppose it's actually doable). Let's consider such a solution and unfold it. To make it more clear, imagine $$$s$$$ is a piece of paper that was folded in-place by overlapping pieces, and you literally unfold it in your head. Let's now look at the creases on the unfolded paper. You will notice that you will always be able to re-fold the prefix at each of the creases from left to right, and the pieces will never overflow onto the right part (if they were to overflow, there would have been another crease at the overflowing part). Same with the left part.

        So, in actuality, you can always fold as much as you can from both parts, and you'll end up with the best solution.

        I know it's not too formal, but I hope it makes it a little more clear nonetheless.

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

    I solved the problem on Kattis and my solution is to check if each index can be the left end (and right end) of the final string. It can be done in linear time using Manacher's algorithm.

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

Happy for ya, that's a great achievement and also the reward for your hard work in recent times!

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

I’m glad we made it to the memorial! We’re really happy that we met and hung out. Maybe we’ll meet again some day. Good luck in the next parts of your story!

→ Reply