### GlebsHP's blog

By GlebsHP, history, 4 months ago, translation, ,

In case you want to take part in Yandex.Algorithm 2018 but somehow haven't registered yet, you might want to follow this link.

Qualification round has started at 00:00 Moscow time, February 17th. Round is a virtual competition 100 minutes long. You can start it at any moment of time till 23:59 on Sunday, February 18th (Moscow time).

We recall that in order to be able to participate in elimination stage one needs to accept at least one problem at qualification round. However, everyone who managed to accept at least one problem during warm-up has already qualified to the next stage.

Judges ask all the participant to withdraw from any problem discussion and do not publish any solutions till 01:40, February 19th.

Good luck, we hope that you will enjoy the problems!

•
• +56
•

 » 4 months ago, # |   0 Auto comment: topic has been translated by GlebsHP (original revision, translated revision, compare)
 » 4 months ago, # |   +7 I really enjoyed the problems even if I couldn't solve a lot, very interested in the editorial :). Good job!
 » 4 months ago, # |   +31 Please change English title to English. Because it is written in Russian I firstly ignored this.
•  » » 4 months ago, # ^ |   0 Done, thanks
•  » » » 4 months ago, # ^ |   +33 is it just me or it seems that the title is still not changed.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +169 Haha, Gleb changed it to English title but in Russian language version, not in English :D
•  » » » » » 4 months ago, # ^ |   0 That just happened
 » 4 months ago, # |   +31 Is there a way to end contest earlier if everything is already blind/AC?
•  » » 4 months ago, # ^ |   +5 I don't think so
 » 4 months ago, # |   +28 Why do I have to wait something like 4 minutes for my submission to be included in standings? Is it like that in further rounds as well?
•  » » 4 months ago, # ^ |   +18 We are working on this issue. Hope that during Qualification this is not critical.
•  » » » 4 months ago, # ^ |   +33 It was happening during entire Petrozavodsk camp, so I think that it's problem with whole yandex system.
•  » » 4 months ago, # ^ |   -36 Why are u always complaining btw
 » 4 months ago, # |   +8 6 hours remaining before end of qualification round. Hurry up! :)
 » 4 months ago, # |   +5 I don't get it, is there any advantage to submitting blind??
•  » » 4 months ago, # ^ |   +31 Submitting blind reduces penalty time (which is irrelevant in qualification round)
 » 4 months ago, # |   +5 01:40, February 19th Moscow time has passed. How to solve F?
•  » » 4 months ago, # ^ |   +38 Suppose minimal such distance is d. Then we can place servers on the diameter in vertices that are at distance d from diameter ends. Now we can just binary search for d
•  » » » 4 months ago, # ^ |   +5 Is there a way to solve this if the number of servers > 2?
•  » » » » 4 months ago, # ^ |   +13 I do not see easy way to generalize this solution
•  » » » » » 4 months ago, # ^ |   +41 Alternative approach.Fix d and root the tree. Take a look at node v with maximum depth. For covering it, there should be a server somewhere in subtree of d-th parent of v, say u. With greedy conclusions it's optimal to set one of the servers exactly in u. Then choose v as the deepest node from the set of nodes uncovered by the first server (it can be disconnected but it doesn't matter) and set the second server in the d-th parent of new v.Now check whether each node is covered.Seems to be generalizable for > 2 servers
•  » » » » 4 months ago, # ^ |   +13 If you can solve this problem: https://main.edu.pl/en/archive/oi/16/gas, then you can enlarge the number of servers a little.(I guess...)
•  » » » » 4 months ago, # ^ |   +8 My solution seems to work in with arbitrarily number of server.First binary search the farthest distance d. For a fixed d, I'm going to find the least possible number of servers to cover all vertices within d. Let dp[i] be the critical vertex in the subtree of vertex i, where critical vertex is the deepest one still uncovered, if all the vertice in the subtree of i are covered, the critical vertex is the highest one placed with server.Then, for each vertex i, collect critical points from its direct children. If the critical point is placed with server but farther than d, skip it. For those uncovered critical points, keep the deepest one. For those with server, keep the highest one. Considering following cases: No critical points: If i is root, place a server. Anyway, dp[i] = i Exists a critical point with server and no critical points uncovered or all uncovered points can be covered by the highest critical point with server: dp[i] =  the critical point with server. Othewise: If i is root or distance between i and an uncovered critical point is exactly d, place a server at i and dp[i] = i. Otherwise, dp[i] =  the deepest uncovered critical point. Then, I can find the least possible number of servers to cover all vertices within d.It's somehow greddy and I didn't prove it.
•  » » 4 months ago, # ^ |   0 Find center of tree. Then cut the deepest or second deepest subtree, find diameter of each component is also pass.
•  » » 4 months ago, # ^ |   +11 Find diameter, and centre of tree, if it's an edge disconnect that, if it's a node, disconnect either of the edges from it that are part of diameter. Find diameter of the 2 new trees obtained. The centres of these trees are your answers. Centre is defined as midpoint of any diameter. I don't have a formal proof for it, but it works. Intuitively, since we can prove centre is unique, it makes sense for it to be answer for a single server.Also can be easily generalised for an arbitrary K number of servers since at each step, you find diameters of each tree(of the forest) in total O(N) time, so solution is overall O(N·K). Code#include #include #include #include using namespace std; const int maxn = int(2e5)+5; int P[maxn]; set graph[maxn]; pair dfs0(int node, int par, int ht) { P[node] = par; pair res = {ht, node}; for(auto it: graph[node]) { if(it != par) res = max(res, dfs0(it, node, ht+1)); } return res; } pair cntrf(int node) { int far1 = dfs0(node, -1, 0).second; int far2 = dfs0(far1, -1, 0).second; vector X; int cur = far2; while(cur != -1) { X.push_back(cur); cur = P[cur]; } return {X[int(X.size())/2], X[int(X.size())/2-1]}; } int main(void) { int n, u, v; scanf("%d", &n); for(int i = 1;i < n;i++) { scanf("%d%d", &u, &v); u--, v--; graph[u].insert(v), graph[v].insert(u); } pair E = cntrf(0); graph[E.first].erase(E.second), graph[E.second].erase(E.first); //cout << E.first << " " << E.second << "\n"; pair res = {cntrf(E.first).first, cntrf(E.second).first}; printf("%d %d\n", res.first+1, res.second+1); } 
•  » » » 4 months ago, # ^ |   0 Wow,your solution is cool,but could you tell me about if you should choose 3 nodes,how to proof that your solution is still correct.And I don't know well how to divide the diameter.
•  » » » » 4 months ago, # ^ | ← Rev. 4 →   0 I think the 3 server nodes would be the original tree center, and the 2 centers of the partitioned trees. I don’t have a way to prove/test it, but it seems somewhat intuitive by the same arguments as for 1 or 2 servers.However, now that you mention it, I believe it is non-trivial to extend this for more than 3 nodes, possibly just doing a greedy(choosing node that minimizes current answer most) works, but I can see why it might not.
•  » » » » » 4 months ago, # ^ |   0 Nope: 7 1 2 1 3 1 4 2 5 3 6 4 7 The only optimal solution for three servers is 2, 3, 4, but the center is 1.
 » 4 months ago, # | ← Rev. 2 →   +5 How to solve E?
•  » » 4 months ago, # ^ |   +5 Use 2 pointers to find, for each left index, the rightmost right index such that all words are covered
 » 4 months ago, # |   +5 How to solve D?
•  » » 4 months ago, # ^ |   +44 If we want the smallest possible sequence which we cannot form a triangle, it will be Fibonacci sequence. consider at most the first 100 numbers in a range, because Fibonacci numbers get larger.
•  » » » 4 months ago, # ^ |   +8 Wow that's an easy solution.I solved it with two pointers and sets to find dp[L] which gives you the leftmost right border so that this interval havs a valid triangle .. and then in the quereies I see if dp[L]<=R and I print the triple .. and it passed :D .. I don't think the writera meant my solution.
•  » » » » 4 months ago, # ^ |   +8 How did you calculate dp[L] ?
•  » » » » » 4 months ago, # ^ |   +5 you keep moving with the right pointer until you have found a triangle ... but how know that you found one?You have two sets, one for the lengths of the current interval, and one for saving the 3 indices that form a triangle (there may be more than one triple). Then when you move one step to the right you add this length to the lengths set and you see it's neighbors one to the right, one to the left, two to the right and two to the left and try to form triangle with them. If some triple forms a triangle you add it to the second set with the minimum index first to sort them by index. So when the second set is not empty that means that you have found a triple so you can stop, and by that you have found the leftmost R that you can form a triangle with.
•  » » » » » » 4 months ago, # ^ |   +3 I think we can improve a bit this approach. We can store only one triangle and there is always be R index. When move left border we must check only existence triangle with R (if one of the indexes was L). If no such triangle move R.
•  » » » 4 months ago, # ^ |   +5 I learned this idea from the editorial of 766B.
•  » » » 4 months ago, # ^ |   0 But we should get first 100 sorted elements in range [L;R] (using segment tree for example), isn't it?
•  » » » » 4 months ago, # ^ |   0 you don't have to, for each query sort the first min(100, size) elements in temporary array. , it's fast enough to pass the time limit.
•  » » » » » 4 months ago, # ^ |   0 I tried to make up antitest and understood what did you mean :DNice idea.
 » 4 months ago, # |   +15 i have 2 questions on yesterday's yandex. 1: can some one plz give me a proof for why this solution for c works. https://ide.geeksforgeeks.org/dkwmWVvF882: And i used segment tree for d in which i find the 3 maximum elements in a segment. And if those 3 cant form a triangle, print -1. But it doesnt work. failure on last test case. here is the code https://ide.geeksforgeeks.org/KsnMcNWu6K
•  » » 4 months ago, # ^ |   0 2: How did you decide that choosing the largest 3 elements will be sufficient?Counter-case 3,4,5,10
•  » » » 4 months ago, # ^ |   0 ohh yeah! i din notice. THanks.
•  » » 4 months ago, # ^ |   +25 For C, the answer is n^((n-1)^2) because after you fill the top-left (n-1)x(n-1) submatrix with anything, there is exactly one way to fill the remaining cells so that the matrix is valid.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Can you proof that the rightest lower cell would be always correct ? UPD: oh, i understood why is it works )
•  » » » » 4 months ago, # ^ |   0 can you elaborate it
•  » » » » » 4 months ago, # ^ |   +5 1) Consider the top-left (n-1)x(n-1) submatrix 2) The sum of right column will be equal of sum of those elements plus the rightest lower cell 3) The sum of the bottom row will be equal the same => exactly one way to fill value to the last cell.
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 how do you say that there exists one way. why cant you have 0 ways?. no number to fill it. cuz these 2 sequences are entirely different and how adding those integers will give the same number modulo n.
•  » » » » » » » 4 months ago, # ^ |   0 We should proof, that sum of bottom row is equal to sum elements of right column. an, 1 + an, 2 + ... + an, n ≡ a1, n + ... + an, n (n), we can sub from both sums an, nLet's proof it.=> they both contain top-left (n-1)x(n-1) submatrix => the sums are equals => there's exist a value for an, n
•  » » » » » » » » 4 months ago, # ^ |   0 ok. Thanks
•  » » » 4 months ago, # ^ | ← Rev. 3 →   0 Another way to explain: you can fill all cells except for main diagonal with any values. After that you can set the desired values to the main diagonal elements.UPD. This solution is wrong. But it led me to a correct formula due to the double mistake. Thanks God, I'm an idiot!
•  » » » » 4 months ago, # ^ |   0 main diagonal?for all cells except the both diagonals, doesn't it?
•  » » » » » 4 months ago, # ^ |   0 I don't think either idea works, you can't fill center in these cases for N=3  [_,1,1] [1,_,1] [1,2,_]  or  [_,1,_] [1,_,1] [_,2,_]
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 ohh!! understood it. Thanks for both of you.
 » 4 months ago, # |   0 Any ideas why my solution of problem D gets WA on first test (though it passes the samples)? https://pastebin.com/iiMfq5fJ Maybe I misunderstood something
•  » » 4 months ago, # ^ |   +5 Successful hacking attempt of Stroustrup's solution. 5 2 1 1 10 1 1 1 5 2 4 
•  » » » 4 months ago, # ^ |   +10 Thanks a lot, I see now, something went terribly wrong with my two pointers approach
 » 4 months ago, # |   0 For Problem C, there is an easy edition in CF: 894B - Ральф и его магическое поле.