NALP's blog

Codeforces Round #112 (Div. 2)
By NALP, 13 years ago, translation, In English

Dear friends!

The next competition — Codeforces Round 112 for participants Div. 2 will take place through a pair of hours, but the others can traditionally participate out of competition. It has been prepared by a small command of authors: me (NALP), Artem Rakhov (RAD) and Pavel Holkin (HolkinPV). There were Gerald Agapov (Gerald), Maria Belova (Delinur) and Michael Mirzayanov (MikeMirzayanov) with us as always.

Especially I would like to wish good luck to my teammates Artem Rakhov and Max Ivanov (e-maxx) who recently flew to the U.S. to participate in Onsite Round Facebook HackerCup.

We hope that this problems will be pleasant to all participants and everyone will take the deserved high place in the standings :)

UPD: The contest is over, thanks to all for taking part :) We hope you have fun.

UPD: You can find the tutorial here http://codeforces.me/blog/entry/4124

UPD: Congratulations to the winners!

  1. Doriam30

  2. woshisb

  3. Senjougahara_Hitagi

  4. LiWenHaoTianXiaDiYi

  5. pqxdcel

  6. UranusX

  7. QDkAc

You can see the full standings here: http://codeforces.me/contest/165/standings

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

Comments Comments (37)
| Write comment?
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

All the best to all of us. :)

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

Blog about match with A, B and C explanations

This was a fun problem set, thanks.

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

What is this message? -> "Judge protocol is inaccessible." (I got this message when I tried to hack.)

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

    have u locked ur submission?

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

      yes.
      HackID : #36282
      Vertect : Unknown verdict:OTHER
      Message : Judge protocol is inaccessible.

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

During the contest today, I kept getting WA on pretest 11, during the last 5 minutes (in desperation :P) I spammed a bunch of (long long) (I used C++) wherever i had calculations going on and then i got pretests passed. All my variables were already long longs anyway, can someone please explain what might have happened? much thanks.

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

Any hint on problem D?

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

    I tried using Fenwick's tree. I couldn't finish it in time so I don't know whether that method would have been successful.

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

      Fenwick's tree (or another tree) should be OK for this problem.

      We have root (vertex with largest degree) and some paths from root.

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

        I used Fenwick's tree and got Accepted in less than 1000ms. What you should do is just to maintain some paths from root.

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

          I run a DFS from the root through the paths and give each node a unique ID. For example, root node has ID 1, then first path has IDs 2, 3, 4, 5, 6, 7, second path has IDs 8, 9, 10, 11, third path 12, 13, 14 etc.

          Also, for each node I calculated the distance between it and the root node.

          When an edge is colored white, I call fwt_update(x, 1) where x is the ID of the node right after this edge. When the egde is colored black, I call fwt_update(x, -1).

          When asked to tell about the SP between nodes X and Y, there are two cases. Lets assume that Y is further from root than X.

          If both X and Y are on the same path, I can express the number of white edges between them as fwt_read(Y) — fwt_read(X — 1).

          If X and Y are on different paths, I similarly check if there are any white edges between root and X as well as between root and Y.

          Am I right about the idea?

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

            Yeah, your solution is very perfect and convenient,thank you! I got a Accepted that I delete the root and for each chain build a Fenwick tree.Also my code is very long.

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

      Can anyone please explain why beard graph has to be a tree. 1->2->3->1 satisfies as a beard graph but is not a tree. Please correct me if I am wrong

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

    Let the vertex who has the maximum degree be root,if we delete the root,there will be several chains.For each chain,build a segment tree to maintain it.

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

As it seems E has surprisingly short solution.

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

    Does anyone know where could I read about the method used in solving E?

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

      I couldn't solve problem E in time but had a solution in mind. It involved converting each element of the array to its binary form->reverse it and then create a trie type DS (binary tree in this case). the height of this would at max be 20. Along this trie I also store information of when an element of the array ends in a particular node(call this val A). As well as a information at each node which tells any one of the numbers whioch would be discoverable in the path following(call this val B). Then for each number in the array I travel the Trie. Convert the number to binary and reverse it and then travel it from the front. For each 1 I take the 0 path. For a 0 I search in both path's. DFS in this process should work. If the search string ends at a particular node I return the val B else if any val A is found first before the search string ends I return the val A

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

        Most probably it will time out, as the DFS is not guaranteed to stop very soon.

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

      To solve the problem E, you may can just use the dynamic programming. dp[i] = dp[j], if j is sub-state of i and dp[j] != 0 ( 1100(2), 0110(2), 1010(2), 1000(2), 0100(2), 0010(2) are all sub-state of 1110(2), but you can just use 1100(2), 0110(2), 1010(2) to transfer dp).In the beginning， you just let dp[a[i]] = a[i], the others equal to 0. Finally, you can get answer from dp[(1 << 22) — 1 — a[i]], because (1 << 22) — 1 — a[i] is sub-state of ~a[i] and if (1 << 22) — 1 — a[i] has none-zero's sub-state, dp[(1 << 22) — 1 — a[i]] must not equal to 0.

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

use long long, instead of int... shouldn't make such a trivial mistake! :(

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

    Yes，you are right. I would be wrong in problem D. My way to solve it may bigger than int...

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

Thanks for contest. I like the problems, B and C are good for hacks, but unfortunately I stucked on C :-(

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

Thanks for contest,E is a good problem, I think for a long time，very happy finally solved。And problem D with problem ——Query on a tree is very similar。：-D

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

Editorial??

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

Waiting for the editorial eagerly. Hope it will be published soon.

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

sorry

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

    I think it's because of pow(), never use it if you work with integer numbers.

    This gets Accepted:

    long long int p = k;
while(total1 != 0){
    total1 = mid / p;
    total = total + total1;
    p = p * k;
}
    → Reply