MikeMirzayanov's blog

Kotlin Heroes: Episode 2 Editorial
By MikeMirzayanov, 5 years ago, In English

Hello Codeforces!

I hope you enjoyed the problems. I forgot to mention the contribution of testers to the preparation of problems in the round announcement. I apologize and correct myself. Many thanks to the testers: elizarov, ashmelev, KAN, arsijo, adedalic and Roms. Also many thanks to my co-authors: 300iq and geranazavr555. Special thanks to cannor147 who helped with translations.

1211A - Три задачи

Problem writer: MikeMirzayanov

Tutorial

1211B - Путешествие по Золотому кольцу Берляндии

Problem writer: MikeMirzayanov

Tutorial

1211C - Мороженое

Problem writers: MikeMirzayanov, geranazavr555

Tutorial

1211D - Команды

Problem writer: MikeMirzayanov

Tutorial

1211E - Double Permutation Inc.

Problem writers: MikeMirzayanov, geranazavr555

Tutorial

1211F - kotlinkotlinkotlinkotlin...

Problem writer: MikeMirzayanov

Tutorial

1211G - Путь короля

Problem writer: MikeMirzayanov

Tutorial

1211H - Ремонт дорог в Древляндии

Problem writer: MikeMirzayanov

Tutorial

1211I - Необычный граф

Problem writer: 300iq

Tutorial
  • Vote: I like it
  • +29
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 8   Vote: I like it +8 Vote: I do not like it

My solution to E: Double Permutation Inc. was similar to the reference solution (except I used sets rather than maps), but it turns out that calling .size on TreeSet.tailSet() is slow ($$$O(n \log n)$$$) and caused TLE. I submitted that in the last minute and would've got the T-shirt if it passed. Oh well...

After contest time, I submitted a solution using BIT instead and it passed easily, but good to know there is a solution that doesn't require non-STL data structures.

For F: kotlinkotlinkotlinkotlin..., isn't Fleury's algorithm too slow ($$$O(n^2)$$$)? I spent too much contest time implementing Hierholzer's algorithm from scratch as I never used it before. Handling linked-list-nodes is just so error-prone. However, after the contest time, I discovered that a mere ArrayDeque can also implement Hierholzer's by "rotating" the deque whenever you get stuck. (The deque then may need to be rotated again after the path is complete, so that it starts with vertex 0. It can be shown that you'd never need more than $$$n$$$ rotations in total.) Example code: #60237987. Great learning experience though.

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

    Fleury's algorithm works in $$$O(n+m)$$$, where $$$n$$$ is the number of vertices and $$$m$$$ is the number of edges in case of careful implementation.

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

      Is Wikipedia incorrect or outdated on this matter then? How do you efficiently find bridges during traversal?

      https://cs.stackexchange.com/questions/90068/optimizing-fleurys-algorithm-to-work-in-ove

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

        I think you are right about Fleury's algorithm. Probably Mike's implementation is also the typical Euler tour algorithm (apparently known as Hierholzer).

        For the implementation, just maintain a global pointer for each adjacency list (so you have pointer for every 6 nodes). It shouldn't have to be real pointer but just an integer index. And implement edge removal by incrementing the pointer.

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

        Oh, sorry. I agree with ko_osaga — it seems the popular Eulerian tour's algorithm is not Fleury's algorithm.

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

I think the should be a small correction in editorial of D. It should be a>=b and not the other way round

→ Reply