### Zlobober's blog

By Zlobober, 5 years ago,

Hi everybody!

I'm glad to invite you to the Yandex Algorithm Round 2 that will happen tomorrow at 21:00 Moscow Time. This round is prepared by me with a great help of GlebsHP. I want to say thanks to Chmel_Tolstiy, snarknews and Gassa for their support during the preparation and to all of the Yandex developers that tested this round.

Good luck and have fun!

Link to the contest will be posted here as soon as I manage to find it by myself :)

UPD: the link to the contest is located here: https://contest.yandex.com/algorithm2016/contest/2540/enter/

UPD2: Thanks everybody for the participation, I hope you enjoyed the round! Results will be available shortly. I'd like to publish an editorial, but it fails to compile on Codeforces and I'm trying to fix this issue.

UPD3: Congratulations to winners:

The preliminary pdf-version of an editorial is posted: http://codeforces.com/blog/entry/45354. Continuing the nice tradition of providing an editorial with questions related to the problems, I invite you to think about them/

• +188

 » 5 years ago, # |   0 There is no way to participate for those who didn't took part in previous rounds, am I right?:(
•  » » 5 years ago, # ^ |   +11 Unfortunately there is no way to participate during the contest for those who didn't qualified. Though after each round is held, it becomes available for participation on http://contest.yandex.ru. We will also, most probably, publish archives containing test data and all materials of all rounds in the nearest future.
•  » » » 5 years ago, # ^ |   -40 Why is there no mirrors on CF? I don't know how difficult to make mirror but think it should be simpler than make new round from scratch (in this case CF get all problems for free).
 » 5 years ago, # |   +25 Darn, it overlaps with first match of Euro : /.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +122 Yep, I'm choosing a nice bar with live football to conduct the contest from there right now :)Sorry for that, I couldn't do anything with the time of round.I can send you messages about goals via testing system :D
•  » » » 5 years ago, # ^ |   +12 At least we will be able to watch second half. What is worse is that DCJ overlaps with first match of Poland ;__; (also first half)!
•  » » » » 5 years ago, # ^ |   +117 Easy, just quickly solve all problems.
•  » » » » » 5 years ago, # ^ |   -44 Easy, when you know how.
•  » » » 5 years ago, # ^ |   +3 Thank for sending me notifications about all of the goals ;).
•  » » » » 5 years ago, # ^ |   +5 I had an opened tab with text footage of the match but they didn't give me an option :)
 » 5 years ago, # |   +13 Don't forget to participate!
 » 5 years ago, # | ← Rev. 2 →   0 Была ли регистрация к раунду ? Было бы лучше если её открыли во время контеста.
•  » » 5 years ago, # ^ |   +1 Её не было и не будет. Регистрация была на участие в квалификационных раундах, которые уже прошли.
 » 5 years ago, # |   +9 Thanks for making the system fast and stable this time. :)How to solve C?
•  » » 5 years ago, # ^ |   0 I used bruteforce. Code.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +3 Notice that for integer a number of used banknotes is (all divisions are done in integers).It can be rewritten asSo we need to maximize the subtrahendThis can be done with DP.Code.
•  » » 5 years ago, # ^ |   +41 Well... it is kind of the backwards sieve of Eratosthenes, isn't it?  for (int i = MAX; i >= 1; --i) { for (int j = 0; j < N; ++j) dp[i] += A[j] / i; // i is the highest denomination for (int k = 2 * i; k <= MAX; k += i) { // k is the next denomination int tmp = dp[k]; REP(j, N) tmp += (A[j] % k) / i; if (tmp < dp[i]) dp[i] = tmp; } } printf("%d\n", dp[1]); 
•  » » 5 years ago, # ^ |   +18 An N log N DP solution:We'll pick coins from smaller to bigger. Suppose we already picked some coins and the biggest of them is A. We used coins
•  » » 5 years ago, # ^ |   +88 6 years ago I wrote the same problem: https://community.topcoder.com/stat?c=problem_statement&pm=10569Yes, d1 med was easier at that time.
•  » » » 5 years ago, # ^ |   +11 Ouch : \
•  » » » 5 years ago, # ^ |   +15 It's funny that I wasn't able to solve the problem back then, but it was a piece of cake today (I didn't remember it at all).
•  » » » » 5 years ago, # ^ |   +8 The other way around would be funny ;)
•  » » » » » 5 years ago, # ^ |   +20
•  » » » » » 5 years ago, # ^ |   +38 I solved it 6 years ago, but WA today... (somehow I thought k and n are the same variable)
•  » » » 5 years ago, # ^ |   0 BTW, consider the other version of the problem I've came up with before this one. It is formulated in my editorial. Are you able to solve it efficiently?
 » 5 years ago, # |   +3 How to solve B?
•  » » 5 years ago, # ^ | ← Rev. 6 →   +7 Write L and R in binary form.Now the problem can be solved independently for each bit: you need to calculate for each bit how much there will be nums in [l, r] with this bit set and unset. And then select the bit value, based on this info. How to count how much nums in [l, r] with such bit set? Traditional trick: it is count in [0, r] — count in [0, L — 1].So how much nums in [0, r] with i'th bit set? let r = A C B (where A value of highest bits, c value of i's bit, B value of lower bits) It is A * 2^i + c * (B + 1).(At first consider all numbers which are less than A * 2^(i + 1), and then the all other)In first group exactly half will be good, and in second none will be good if i'th bit unset (c == 0), and all numbers in [A C {zeros}; A C B] otherwise.
•  » » » 5 years ago, # ^ |   +3 How did you calculate the number of nums in [L, R] with this bit set and unset?
•  » » » » 5 years ago, # ^ |   0 I've written second part and updated comment.
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   0 I dont know how he did it, but I think it can be done easily using DP on digits with state DP(bit, lower, larger, tofix) which is O(323·2·2·) where bit is the bit we are currently on, lower is {0, 1} denoting whether any previous bit is lesser than the bit in R, and larger is {0, 1} denoting whether some bit has been strictly larger than that of L. tofix denotes the bit we are fixing to be true. After that, it can be solved by using a lot of if-elses. I couldn't get it accepted in contest(WA on #10), but I dont think the DP would be wrong. My transition probably has bugs :/Is there anything wrong with this approach?UPD: Damn, extremely overkill :/
•  » » » 5 years ago, # ^ |   +3 Got this strategy but couldn't count how many times it occurs. Can you explain you method to count how many times each bit is set in range [l,r].
 » 5 years ago, # |   +3 For Problem B, finding the number of integers in [L, R] with ith bit set could be used to decide if the required number should have ith bit set or not, to minimize the hamming distance.So, how do we find number of integers in [L, R] with ith bit set?
•  » » 5 years ago, # ^ |   0 Find count of '1' for every position for all numbers from 0 to n;It's linear in number of digits.Then you can do F(r) — F(l-1) to find what you need.
•  » » 5 years ago, # ^ |   0 We can calculate the number of integers in [0, R] with i-th bit set using the following fact: if we consider consecutive blocks of size 2i + 1, the first half of integers has i-th bit set to zero, and the second half with i-th bit set to one. Therefore, one can come up with simple formula.
 » 5 years ago, # |   +50 That awkward moment when your solution to D fails because of  if (c == 0) { cout << 0 << endl; return 0; } 
•  » » 5 years ago, # ^ |   +38 That awkward moment when the bug in your code is that you forget to return your answer... int query(int l, int r, int x) { int res = 0; for (l += n, r += n; l < r; l /= 2, r /= 2) { if (l & 1) { res += t[l].end() - upper_bound(t[l].begin(), t[l].end(), x); ++l; } if (r & 1) { --r; res += t[r].end() - upper_bound(t[r].begin(), t[r].end(), x); } } } 
•  » » » 5 years ago, # ^ |   -17 an awkward moment when you haven't finished reading A, wrote solution in 5:24, sent it blindly and it obviously failed because it never outputs -1 xD
•  » » » 5 years ago, # ^ |   +21 That's why keep warnings flag on always, same thing happened with me 1 year ago and your's is still int returning function mine was bool returning which doesn't show warning also.
•  » » » » 5 years ago, # ^ |   +3 Thanks for the tip.
 » 5 years ago, # |   0 How to solve D?
•  » » 5 years ago, # ^ |   +3 ans(C) = ans(C - A) + ans(C - B), ans(0) = 1 and use fast matrix exponentation.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +6 Sum of required f(x,y) is sum of f(x-1,y)+f(x,y-1)if Ax+By=C, then A(x-1)+By=C-A, Ax+B(y-1)=C-Bso you need to calculate answers for C-A and C-B and sum themthe rest is converting linear recursion to matrix powers
•  » » » 5 years ago, # ^ |   0 Thanks a lot! It was simple but i turned it into a complicated series of binomial coefficients and could not simplify it :(
 » 5 years ago, # | ← Rev. 2 →   +69 Good interesting problems, thanks for the round!
 » 5 years ago, # |   +8 Is there a simple approach for problem E? I have several overcomplicated in mind, however wasn't brave enough to implement any of them.
•  » » 5 years ago, # ^ |   +10 First, you need to compute, for each vertex, how many vertices with a higher number are there in its subtree (nIni), in each of its childen's subtrees (nChildij), and outside of its subtree (nOuti).To compute the numbers, first sort the vertices in the order of preorder traversal. Each subtree will be represented by a contiguous interval in this order. Create a Fenwick tree. Process vertices in the order of assigned numbers, and use position in preorder traversal as an index in the Fenwick tree. Then, you will be able to compute how many already processed vertices are in any given subtree in .Then, you can move the root along edges and maintain current number of inversions in O(1) time for each move. Let's call "current root" the vertex you are currently computing the answer for, and "initial root" is the vertex that you used as a root in the previous steps. The answer can be computed as the sum of contributions of each vertex, where contribution of vertex i is defined as: If vertex i is the current root, its contribution is nIni + nOuti. Otherwise, if i is on the path between the current root and the initial root, its contribution is nOuti + nIni - nChildij, where j is the child that is in the direction of the current root. Otherwise, its contribution is nIni. As you may see, when moving the current root along an edge, only contributions of two vertices may change (ends of that edge). So, the answer can be updated in O(1). Since it is possible to visit all vertices using O(n) such moves, this part takes O(n) time, and the entire solution takes time. Here is the code for better understandingint getSum(int fenwick[], int i) { int res = fenwick[i]; while ((i = (i & (i + 1)) - 1) >= 0) { res += fenwick[i]; } return res; } void updateSum(int fenwick[], int i, int v) { fenwick[i] += v; while ((i |= i + 1) < fenwick.length) { fenwick[i] += v; } } IntList children[]; int pos[], end[]; int cntInSubtrees[]; int cntInChilds[][]; int cntOutSubtrees[]; long ans; int ansPos; int cans[]; long cansSum; void solve() { int n = nextInt(); int a[] = new int[n]; children = new IntList[n]; for (int i = 0; i < n; i++) { a[i] = nextInt() - 1; children[i] = new IntList(); } for (int i = 0; i < n - 1; i++) { int u = nextInt() - 1; int v = nextInt() - 1; children[u].add(v); children[v].add(u); } pos = new int[n]; end = new int[n]; dfs1(0, -1, 0); int sortedByA[] = new int[n]; for (int i = 0; i < n; i++) { sortedByA[i] = i; } sortBy(sortedByA, a); int fenw[] = new int[n]; cntInSubtrees = new int[n]; cntInChilds = new int[n][]; cntOutSubtrees = new int[n]; for (int i = n, j; i > 0; i = j) { for (j = i - 1; j > 0 && a[sortedByA[j - 1]] == a[sortedByA[j]]; j--) { } for (int ii = j; ii < i; ii++) { int cur = sortedByA[ii]; cntInSubtrees[cur] = getSum(fenw, end[cur] - 1); if (pos[cur] > 0) { cntInSubtrees[cur] -= getSum(fenw, pos[cur] - 1); } int cn = children[cur].size(); cntInChilds[cur] = new int[cn]; for (int jj = 0; jj < cn; jj++) { int ccur = children[cur].get(jj); cntInChilds[cur][jj] = getSum(fenw, end[ccur] - 1); if (pos[ccur] > 0) { cntInChilds[cur][jj] -= getSum(fenw, pos[ccur] - 1); } cntInChilds[cur][jj] = cntInSubtrees[cur] - cntInChilds[cur][jj]; } cntOutSubtrees[cur] = n - i - cntInSubtrees[cur]; } for (int ii = j; ii < i; ii++) { int cur = sortedByA[ii]; updateSum(fenw, pos[cur], 1); } } cans = new int[n]; cansSum = 0; for (int i = 0; i < n; i++) { cans[i] = cntInSubtrees[i]; cansSum += cans[i]; } ans = Long.MAX_VALUE; ansPos = -1; dfs2(0); out.print((ansPos + 1) + " " + ans); } int dfs1(int cur, int prev, int cpos) { pos[cur] = cpos++; for (int i = 0; i < children[cur].size(); i++) { int next = children[cur].get(i); if (next == prev) { children[cur].remove(i--); continue; } cpos = dfs1(next, cur, cpos); } end[cur] = cpos; return cpos; } void dfs2(int cur) { { int ncans = cntOutSubtrees[cur] + cntInSubtrees[cur]; cansSum += ncans - cans[cur]; cans[cur] = ncans; } if (ans > cansSum || (ans == cansSum && ansPos > cur)) { ans = cansSum; ansPos = cur; } int cn = children[cur].size(); for (int i = 0; i < cn; i++) { int ncans = cntOutSubtrees[cur] + cntInChilds[cur][i]; cansSum += ncans - cans[cur]; cans[cur] = ncans; int next = children[cur].get(i); dfs2(next); } { int ncans = cntInSubtrees[cur]; cansSum += ncans - cans[cur]; cans[cur] = ncans; } } 
 » 5 years ago, # |   0 Last round I was afraid to submit anything blindly and because of that I was a victim of wrong tests in C. This round I thought I need to risk ans submit something blindly, so since I was pretty sure of D (it can't not work if it works on samples, right?), so I submitted it blindly and it turned out to be only one of my submissions that wasn't right :|. a=b case xd.
 » 5 years ago, # |   0 How to solve F?
•  » » 5 years ago, # ^ |   +13 I've just posted a PDF-version of an editorial: https://yadi.sk/i/1hC1divYsQtTQ
 » 5 years ago, # |   0 Has somebody encountered WA #18 in problem D? I have no idea what's wrong with my code (linear recurrence -> fast matrix exponentiation).
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 It is said in the editorial that A = B in that test.
•  » » » 5 years ago, # ^ |   0 Well, there are smaller tests with the same condition (for example A = B = 100 in test #10), and I did  std::vector A = vector(n, VI(n)); A[0][b-1] += 1; A[0][a-1] += 1; REP(i, n-1) A[i+1][i] = 1; so it's something different I guess.
•  » » 5 years ago, # ^ |   +10 Ooops, WA #18 checks int overflow (C >= 2^31). I feel stupid right now. =)
 » 5 years ago, # |   0 Are there any chances for me to get a T-shirt if I missed Yandex Algorithm Round 2?
•  » » 5 years ago, # ^ |   +5 If you get to the top 512 competitors — yes, sure. You can track your position here.
 » 5 years ago, # | ← Rev. 3 →   0 How to solve E that fast? I create some BSTs and "merge" them in some way to count the inversion, which leads to an O(n log^2 n) solution. My code is a little bit complicated so I wonder if there's a better solution...Edit: Well I just saw the editorial. It seems not easy to implement though...Edit: I saw tonynater's code. Now I know how to solve it :P