soul_voyage's blog

Cannot see others solutions of educational round 2
By soul_voyage, history, 6 years ago, In English

Title of blog

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

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

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))
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

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

      Solution to E using merging small to large technique.

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

        Thank you :). Can you explain a bit?

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

          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.

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

            Hi.

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

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

              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.

              → Reply