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.net/blog/entry/4124
UPD: Congratulations to the winners!
You can see the full standings here: http://codeforces.net/contest/165/standings
All the best to all of us. :)
Blog about match with A, B and C explanations
This was a fun problem set, thanks.
What is this message? -> "Judge protocol is inaccessible." (I got this message when I tried to hack.)
have u locked ur submission?
yes.
HackID : #36282
Vertect : Unknown verdict:OTHER
Message : Judge protocol is inaccessible.
Maybe someone hacked that solution before you.
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.
type of bits.size is int.
Actually it is
std::size_t
.thanks guys :D doh. silly me -_-
Louise Françoise Le Blanc de La Vallière? Is that you?
Any hint on problem D?
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.
Fenwick's tree (or another tree) should be OK for this problem.
We have root (vertex with largest degree) and some paths from root.
I used Fenwick's tree and got Accepted in less than 1000ms. What you should do is just to maintain some paths from root.
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?
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.
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
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.
As it seems E has surprisingly short solution.
Does anyone know where could I read about the method used in solving E?
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
Most probably it will time out, as the DFS is not guaranteed to stop very soon.
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.
use long long, instead of int... shouldn't make such a trivial mistake! :(
Yes,you are right. I would be wrong in problem D. My way to solve it may bigger than int...
Thanks for contest. I like the problems, B and C are good for hacks, but unfortunately I stucked on C :-(
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
hello! Could you tell me where the problem Query on a tree is? Thank you!
http://www.spoj.pl/problems/QTREE/
Editorial??
Waiting for the editorial eagerly. Hope it will be published soon.
Editorial in Russian: http://codeforces.net/blog/entry/4124 Maybe you are in need of google translate.
thanks...:)
It would be nice to have the editorial in english too, just saying...
sorry
I think it's because of
pow()
, never use it if you work with integer numbers.This gets Accepted: