Russian Code Cup — Third Qualification Round
By RussianCodeCup, history, 8 years ago, translation, In English

Hi, all!

The last possibility to get to the Elimination Round of Russian Code Cup this year is the Third Qualification Round, that will take place on Sunday, June 5, 16:00. Everyone who has not yet qualified is welcome to participate. Good luck, and see you at Russian Code Cup 2016!

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

»
8 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Do you can check system faster? In the previous round we were waited about two minutes to know the results.

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

    Yes, making judging faster would be highly appreciated.

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

Curiously, did they fix the bug with problemset presentation? Or when the contest starts, we will see 1st-qualifiication's problems again?

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

Can someone who is not Russian participate ?? if yes Link to the contest website please .

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

    http://www.russiancodecup.ru/en/

    The problems are quite interesting, but mail.ru reinvented the wheel developing their own system, which turned out to be the worst Online Judge ever, so expect huge bugs and slow testing during the contest. If you don't want a t-shirt from them, you'd better just wait for the problems to appear on the CF Gym.

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

How can I submit solutions ? I am not seeing any submit button option.

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

Is there some problem with the judge?

My code runs fine offline and on ideone, but gets runtime error on test case 1 in problem D. I asked the jury, and they confirmed that Case #1 is indeed sample case..

→ Reply
»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

For D we needed this, right? http://e-maxx.ru/algo/tree_painting Found it 5 minutes before the end :/

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

    lca + segment tree

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

    I used sqrt-decomposition: new DFS+LCA every 400 queries.

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

      Sorry if this is a dumb question but how did you check if some deleted edge was part of the path from u-v quickly?

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

        Let vertex W = LCA(U, V) so X (a deleted vertex) is a part of the path U-V if and only if X is an ancestor of U or V, but not W (i.e. X is ancestor of exactly one of the path ends).

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

          Thanks. I didn't think enough about it, this is quite easy to using dfs entry/exit times. Sorry.

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

      I came up same solution but failed in coding this idea. Can you share with your code ?

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

        Sure: code

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

        As mentioned in the editorial, it is not necessary to delete the vertex explicitly — we may just assume that the corresponding edge has length 0. So, we may use a significantly simpler dfs — just calculating heights, without the tree rebuilding.

        Code mk.II

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

    You need just this:
    a) LCA
    b) sum on path.

    Both are standard.

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

    I solved it with BIT on tree preorder. BIT holds current dept of the nodes.For update operation i updated corresponding segment of the BIT. And using LCA we can answer the other query.

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

What's wrong with this solution for D?

Keep a BIT on the DFS order for prefix sums from root to the node. For updates, subtract 1 from those which lie in the subtree of the current node, and to answer query use formula val[a] + val[b] - 2 * val[LCA(a, b)]. Only corner case is that both nodes are children of same node that has already been deleted where answer is 2. I kept getting WA on case 7.

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

    There is no corner case. You just have to subtract 1 from everyone in the deleted node's subtree, including the node itself.

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

      Shit, I was doing exactly that initially, but had some bug so rewrote large part of it, and messed that up and came up with new logic :/

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

To D I copy-pasted both LCA and HLD summing on paths. But what is funny is that I didn't copy it from my library but from problem E from RCC week ago :P (however I could as well copy-pasted from library, but second round was closer in directory tree than library :P).

Week ago 120 minutes weren't sufficient for me to get a result sufficient for qualification. Today 8 minutes were enough :P.

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

    i think HLD is too hard solution to D You can use euler tour and segment tree with min and range substraction

    code: http://pastebin.com/PApcfyiw

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

      As long as I can copy-paste prewritten code I don't care whether it is complicated or not. What I care about is what I need to write specifically for that problem and here it was everything I needed: http://ideone.com/WGc7Uj Not too complicated, right?

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

The contest in Gym: 2016 Russian Code Cup (RCC 16), 3-й квалификационный раунд.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

What's wrong with my solution? I used the same idea with the editorial, but instead of using a segment tree with lazy propagation, I used a trick with BIT that allow me to do range update, single node query (the same trick with this editorial, problem C div 1).

My solution

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

when will the editorial be out??

→ Reply