Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя soul_voyage

Cannot see others solutions of educational round 2
Автор soul_voyage, история, 6 лет назад, По-английски

Title of blog

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Yes, me too, because solutions for this round is private. If this is useful for you, link on my solutions of problems A-E on github.

  • 600A.cpp: Strings analysis, integer conversion, implementation, O(n)
  • 600B.cpp: Sort + Binary search, O(n log(n))
  • 600C.cpp: Sort by counting, palindrome, greedy, O(n)
  • 600D.cpp: Geometry, area of the circle segment, circles intersection in O(1).
  • 600E.cpp: Euler tour over tree + Mo algorithm, O(n sqrt(n))
→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Thank you :). Do you have code for pE using merging small to large technique?

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Solution to E using merging small to large technique.

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thank you :). Can you explain a bit?

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Do you tried to read this article about dsu on tree from Arpa? I'm too stupid to understand this, but other people successfully understand this and use it in practice, maybe this article will come in handy for you, it has very good feedback.

          P.S. For "not easy" problem 375D in this article I used euler tour on tree + Mo algorithm too. Code.

          → Ответить
          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Hi.

            Which part is not clear? I'll explain more. Anyway, my code for problem E using dsu on tree is here.

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              I am not ready yet, thanks for your reply. To implement this, I need to understand the recursive functions very well, but at the current time I can write only simple dfs. I understand the idea of "merging small to large" and why it is O(nlog(n)), but when I start writing code, I'm lost in recursive calls. I will train and return to your article again.

              → Ответить