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

Разбор задач Технокубок 2018 — Отборочный Раунд 1 (и открытые раунды Codeforces Round 434 Div.1+Div.2)
Автор vovuh, история, 7 лет назад, По-русски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div 2 B http://codeforces.net/contest/861/submission/30468001

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

Can authors share the generator of testcase #36 in problem E?

It seems heavy-light decomposition and some other solutions perform really bad on this testcase.

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

    It is just full binary tree with n = 500000.

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

      Thanks.

      I tested this case (pi = i / 2) during the contest. And my solution finished in ~1.2s. But I found the solution is 3 times slower if I shuffled the labels of vertices.

      It is so strange because I think the total operations in segment tree/Fenwick tree are same.

      UPD: If I visited the vertices in order, two consecutive operations will share many positions in Fenwick tree. These positions will be fetched in the cache. So it could be much faster than visiting the vertices randomly.

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

    Well, I've got an OK-submission with HLD which performs in 1.3 seconds on this case: 30478628.

    Or you can check out cdkrot's HLD submission 30469620 which does it in 1.152 s.

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

      Thanks. I will try to learn from your codes.

      I try to random shuffle array "by_h" in your code (like what my solution did during the contest). This submission got TLE. I think this result is surprising to me.

      So It's really important to make your solution cache-friendly :D

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

Can someone please provide a more detailed explanation of Div2 D and their C++ code for reference? I know a Trie is to be used but I'm not able to implement it correctly.

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

    You can store each prefix in the trie first and then for each substring you remove the contribution of the present string and then see if the trie has any such substring. You just print the smallest substring which is not in the trie. My solution: http://codeforces.net/contest/861/submission/30489173
    Hope this helps :D

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

      Can you explain me this part please "and then for each substring you remove the contribution of the present string and then see if the trie has any such substring" i will be highly thankful to you.

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

        In my code, take a look at the last loop. The outermost loop traverses the strings one by one. For each string, I first remove all its substrings from the trie(If they were present then I will be taking them into consideration too, but I wanna check if any OTHER string other than my current string contains the substring or not). So, I remove all substrings of the current string, see if a substring is present in the trie and then again insert all the substrings of my current string. In case its still unclear, "current string" refers to the ith string I took, i.e, v[i].

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

I didn't get why in Div2 B problem the quantity of the flats on each floor is in [1,100], may someone explain please?

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

    Because in worst case maximum flat number will not be greater than 100. Then maximum floor quantity will not exceed 100.

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

      OK, but what about this sentence in the statement "Polycarp don't remember the total number of flats in the building, so you can consider the building to be infinitely high (i.e. there are infinitely many floors)"?

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

        Oh, sorry, there was a mistake. I wanted to say "Then maximum flat quantity on each floor will not exceed 100."

        The condition about infinitely high building is no matter for you, because even if there is only one flat on each floor, maximum floor index we are interested in is not greater than 100 (and, of course, it is not getting greater with more flats on each floor).

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

          I approximately got it. My mind closes some times :), so I'll back to this problem later.. Thank you very much.

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

Here's a solution for div1e with just "brute force".

The first step is to make the first observation in the tutorial. Let's consider a naive way to compute the value.

We'll process all nodes with the same depth simultaneously.

For each previous depth's nodes, let's suppose we have computed the number of children at the current depth that we are considering (I will show how to keep track of this later).

For each node, we can naively iterate through its parents and add this stored value.

To update the values, we can also do this naively. More specifically, for each node and ancestor pair, we will update the ancestor's value by adding number of children of node and subtract 1 (we subtract 1 since we no longer want to consider the current node, and we add number of children of this node to represent children at next depth).

Of course, this solution is n^2. We can speed it up to pass with just two optimizations.

  1. If a node ever has 1 child, we delete this node, and connect the child directly to the parent.
  2. If a node has zero children, we'll delete this node (and recursively delete the parent if it now has 0 children).

With these two simple optimizations, the running time becomes O(n sqrt n)!

short justification

Here's a sample implementation with those two optimizations: http://codeforces.net/contest/860/submission/30449695 You can note that it's basically brute force but with these line added in various places:

while (par[cur] != -1 && child[par[cur]] == 1)
	par[cur] = par[par[cur]];
→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

could someone help me with problem D : my submission id is 35750991, it is showing runtime error, but dont know why.

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

    I think in the set called val in your code sometimes it could exceed it's initial size which is 70707 in this instruction val[mp[d]].insert(i); like if we have zeros in the the given numbers more than 70707

    → Ответить