### NALP's blog

By NALP, 8 years ago, translation, ,

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.ru/blog/entry/4124

UPD: Congratulations to the winners!

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

• +118

 » 8 years ago, # |   0 All the best to all of us. :)
 » 8 years ago, # |   -11 The score per problems?
 » 8 years ago, # |   +4 Blog about match with A, B and C explanationsThis was a fun problem set, thanks.
 » 8 years ago, # |   +8 What is this message? -> "Judge protocol is inaccessible." (I got this message when I tried to hack.)
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 have u locked ur submission?
•  » » » 8 years ago, # ^ | ← Rev. 5 →   0 yes. HackID : #36282 Vertect : Unknown verdict:OTHER Message : Judge protocol is inaccessible.
•  » » » » 8 years ago, # ^ |   0 Maybe someone hacked that solution before you.
 » 8 years ago, # |   -7 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.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +12 long long ans=bits.size()*(bits.size()+1)/2; type of bits.size is int.
•  » » » 8 years ago, # ^ |   +8 Actually it is std::size_t.
•  » » » » 8 years ago, # ^ |   0 thanks guys :D doh. silly me -_-
•  » » » » 8 years ago, # ^ |   +5 Louise Françoise Le Blanc de La Vallière? Is that you?
 » 8 years ago, # |   0 Any hint on problem D?
•  » » 8 years ago, # ^ |   +9 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.
•  » » » 8 years ago, # ^ |   0 Fenwick's tree (or another tree) should be OK for this problem.We have root (vertex with largest degree) and some paths from root.
•  » » » » 8 years ago, # ^ |   0 I used Fenwick's tree and got Accepted in less than 1000ms. What you should do is just to maintain some paths from root.
•  » » » » » 8 years ago, # ^ | ← Rev. 3 →   0 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?
•  » » » » » » 8 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 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
•  » » 8 years ago, # ^ |   0 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.
 » 8 years ago, # |   +2 As it seems E has surprisingly short solution.
•  » » 8 years ago, # ^ |   0 Does anyone know where could I read about the method used in solving E?
•  » » » 8 years ago, # ^ |   0 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
•  » » » » 8 years ago, # ^ |   +8 Most probably it will time out, as the DFS is not guaranteed to stop very soon.
•  » » » 8 years ago, # ^ |   +4 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.
 » 8 years ago, # |   +8 use long long, instead of int... shouldn't make such a trivial mistake! :(
•  » » 8 years ago, # ^ |   0 Yes，you are right. I would be wrong in problem D. My way to solve it may bigger than int...
 » 8 years ago, # |   +3 Thanks for contest. I like the problems, B and C are good for hacks, but unfortunately I stucked on C :-(
 » 8 years ago, # |   +6 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
•  » » 8 years ago, # ^ |   0 hello! Could you tell me where the problem Query on a tree is? Thank you!
•  » » » 8 years ago, # ^ |   +5
 » 8 years ago, # |   +1 Editorial??
 » 8 years ago, # |   +4 Waiting for the editorial eagerly. Hope it will be published soon.
•  » » 8 years ago, # ^ |   0 Editorial in Russian: http://codeforces.ru/blog/entry/4124 Maybe you are in need of google translate.
•  » » » 8 years ago, # ^ |   0 thanks...:)
•  » » » 8 years ago, # ^ |   +6 It would be nice to have the editorial in english too, just saying...
 » 8 years ago, # | ← Rev. 2 →   -6 sorry
•  » » 8 years ago, # ^ |   0 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; } 
•  » » » 8 years ago, # ^ |   0 thanks sir but now i never believe on ideone because there my code is giving correct answer inspite of the fact that my code is wrong......