By Endagorion, history, 2 weeks ago, ,

On Oct/04/2018 10:05 (Moscow time), the Codeforces Round #513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2) will start. This is a special round for the Hello Barcelona Programming Bootcamp, in collaboration with Moscow Workshops ICPC. It is rated for all participants, everybody can register on it regardless of a rating.

Hello Barcelona Programming Bootcamp is sponsored by VTB and Indeed Tokyo, with the addition of team sponsors Phaze Ventures, Spark Labs and REMY Robotics.

VTB, the largest international bank based in Eastern Europe, continues to be an official partner of the Hello Programming Bootcamp series, adding further quality to the 3rd edition of the Hello Barcelona Programming Bootcamp by bringing their own participants, as well as by supporting top teams from around the world.

Indeed Tokyo is Japan's branch of the #1 employment website in the world, giving job seekers free access to millions of jobs from thousands of company websites and job boards. As they sponsor for the second year in a row, Indeed continues to offer the best job opportunities to the boot camp participants.

Wish good luck to all the participants!

There will be 8 problems, common for both division. Score distribution: 500 750 1250 1500 1750 2250 2750 3000.

The problems are prepared by me, Arterm and GlebsHP, with assistance from 300iq, ifsmirnov and gritukan. Have fun!

•
• +220
•

 » 2 weeks ago, # |   +188 A good time for Chinese!
 » 2 weeks ago, # |   -51 Unfortunately, bad time for me because of school
 » 2 weeks ago, # |   -84 A bad time for Indians!
 » 2 weeks ago, # |   -33 I forgot the contest time last time, so I may forget again. I don't want to lose a chance to get high rating!
 » 2 weeks ago, # | ← Rev. 2 →   -91 Endagorion is there any chance that contest can be shifted one hour earlier or at standard codeforces contest time?? If possible please do so.
 » 2 weeks ago, # | ← Rev. 5 →   -114 I am just sad about not getting to participate in the round i was waiting for over a week.
 » 2 weeks ago, # | ← Rev. 3 →   -39 LUL
•  » » 13 days ago, # ^ |   0 Poyasni
•  » » » 12 days ago, # ^ |   0 oh ~
 » 2 weeks ago, # | ← Rev. 6 →   -53 two contests back to back.
 » 2 weeks ago, # |   +31 Thanks to Mikemirzayanov for polygon platform.
 » 2 weeks ago, # |   +104 Please stop complaining about the inappropriate time of the contest for your country. Codeforces has to adopt different timings for other people. Not only for a specific country.
•  » » 2 weeks ago, # ^ |   +16 Right? Like, across US, India, China, and Russia, any time is going to be bad for somebody. What's the point in complaining?
•  » » » 13 days ago, # ^ |   +3 Point of complaining as I think is that you cant participate cause of school/work. If contest would take place on weekend, people could even participate at night. But bad time + weekday is reason enough to complane
•  » » 2 weeks ago, # ^ |   +3 I wasn't complaining. I am just sad to miss the round by such good author & also this contest is after a long time from previous one. Neither I upvoted any comments who asked to shift the contest.
•  » » 2 weeks ago, # ^ |   +32 I wasn't aware "work" and "school" are specific countries, since that's going to be the main reason to skip this round for people in Europe, Africa and almost all of Asia. Then we have the Americas, where it's night. Ok, I guess it's a good time for New Zealand and Oceania.
•  » » » 13 days ago, # ^ |   +28 It's also good for Japan, most of China, a part of Russia, South Korea and some other countries that actually does competitive programming. So it's a pretty good time for many people. About quarter of the earth can participate easily in any contest. It just depends in which quarter.
 » 2 weeks ago, # |   +48 good time for those like me who has a day-off on thurdays!!!!!!
 » 2 weeks ago, # | ← Rev. 2 →   +232 bad time for me, i have to poop at 10:30 AM..
•  » » 13 days ago, # ^ |   +44 This comment actually has more upvotes than the post itself.
 » 2 weeks ago, # | ← Rev. 2 →   -45 Please no
•  » » 2 weeks ago, # ^ |   -80 If you cannot understand, it's IMO logo
 » 2 weeks ago, # |   +6 that's time to participate in this contest after 2 weeks!
 » 2 weeks ago, # | ← Rev. 2 →   0 After a long duration Codeforces contest. Codeforces really awesome.
•  » » 2 weeks ago, # ^ | ← Rev. 3 →   +3 Sorry, you are on the wrong platform. Switch to Codeforc.Upd:- Comment edited.
•  » » » 2 weeks ago, # ^ |   0 Switching is complete Now.:D :D :D
 » 2 weeks ago, # |   +27 Great time for me, 4AM so I get to wake up, do this contest and not miss any classes!
•  » » 2 weeks ago, # ^ |   0 Is this a joke?)
•  » » » 2 weeks ago, # ^ |   0 No
•  » » » » 2 weeks ago, # ^ |   0 I'm interesting, how you can get enough sleep before the contest
•  » » » » » 13 days ago, # ^ |   +51 I don't :P
•  » » 13 days ago, # ^ |   +7 4:20 is much better
 » 2 weeks ago, # |   +48 Good time for those who skip classes for cf rounds
 » 2 weeks ago, # | ← Rev. 3 →   0 feeling happy :) ... hoping an interesting round :)
 » 13 days ago, # | ← Rev. 2 →   -29 A Bad Timing For Banladesh!!But i will try my best to participate this contest..
 » 13 days ago, # |   -13 Hi! Is contest duration known? :)
 » 13 days ago, # |   -30 I want connect into this contest; what can I do!
 » 13 days ago, # |   -29 Bad time for Indians. College time + lunch time + sleeping time(for some).
 » 13 days ago, # |   0 Codeforces — Indeed the best interface for competitive programming
 » 13 days ago, # |   -36 Bad time for me... had to compete Codeforces again...
 » 13 days ago, # |   -42 Score distribution? Careless author.
 » 13 days ago, # |   -21 What is the score distribution or is it acm style?
 » 13 days ago, # |   -37 Bad time for Martians
 » 13 days ago, # |   +20 My last year's Barcelona Bootcamp contest. Wish me luck this time :>
 » 13 days ago, # |   -23 Actually, Chineses are having their National Day's vacation... so it is a good time for sure.
 » 13 days ago, # | ← Rev. 2 →   -41 Another time for me to drop my rating!
 » 13 days ago, # |   +54 Can someone explain me solution for D, probably I am very stupid guy :)
•  » » 13 days ago, # ^ |   +16 On seeing AC solutions, the idea is the answer should be a total of n terms.Also we know only a l can reduce a r or vice versa. So now we take max l (assuming max l is morethan max r) and it should reduce max r ,anything other is suboptimal. Now we have two people combined so we can solve the problem further similarly.
•  » » 13 days ago, # ^ | ← Rev. 2 →   +100 D was pretty neat. Basically, imagine everyone is at their own table originally. it is clear that the number of chairs used for a particular person i is max(li, ri) + 1. Imagine if we put two people at the same table, and say their values are (a, b) and (c, d) respectively. Through some inspection, we can see that this is equivalent to two people (a, d) and (c, b) sitting at their own individual tables*. This implies that we can permute the r values for all the pairs. From there it should be clear that we can minimize the chairs by sorting both the l and r arrays individually and calculating the number of chairs needed if these new sorted people were all at their own individual tables.*To be more precise here, combining (a, b) and (c, d) results in 2 + max(a, d) + max(b, c) chairs, and leaving them alone results in 2 + max(a, b) + max(c, d) chairs. So the former case is equivalent to having two people of values (a, d) and (b, c).
•  » » » 13 days ago, # ^ |   +13 Very nice solution, thanks for sharing it!
•  » » » 12 days ago, # ^ |   +5 Nice explanation.
•  » » 13 days ago, # ^ |   +22 You can say that answer is where pi is a person sitting next to i. Note that pi might be arbitrary permutation. Turns out, the best way to choose this permutation is make it so that lpi and ri are sorted in the same way.
•  » » » 13 days ago, # ^ |   +7 Just for my understanding of the solution can we find who sits right to whom?
•  » » » » 13 days ago, # ^ |   +18 Sure, pi sits right to i.
•  » » » » » 13 days ago, # ^ |   +6 Thanks
•  » » » » » 13 days ago, # ^ |   0 But if pi is an "arbitrary permutation", this still doesn't answer who (in terms of l,r pairs given in input) sits next to who?
•  » » » » » » 12 days ago, # ^ |   +1 While sorting l and r, if you store the indices of the people along with the values, then the person corresponding to the value l[i] sits next to the preson corresponding to the value r[i].
•  » » » » » » » 12 days ago, # ^ | ← Rev. 2 →   0 (deleted)
•  » » » » » » » 12 days ago, # ^ |   0 I got it now, thanks!
 » 13 days ago, # |   +60 Nice problemset today (especially D), but the difficult from E to F is like from Div1B to Div1E...How to solve it anyway?
 » 13 days ago, # |   +10 How to solve F?
•  » » 13 days ago, # ^ |   +64 We iterate over every root and solve N problems independently. Let us call fixed root as r, and subtree of v as Tv.DP[$v$][$k$]: Probability of survival of r, subject to the last contracted edge between r and v is contracted between k-th and k + 1-th contracted edge in TvWe can calculate it by another DP. Total complexity seems O(N5), but like many tree DP, it is O(N4).
 » 13 days ago, # |   0 why I failed in Pretest 2( the same as the 2nd sample), but I still got the penalty?
•  » » 13 days ago, # ^ |   +16 You don't get penalty if only your program is wrong on pretest1
 » 13 days ago, # |   0 How to solve C?
•  » » 13 days ago, # ^ | ← Rev. 2 →   +7 1) sum(b[i],i=1..n) <= n * max(b[i]) ~~ 2000*2000 = 4*10^6 ,2) let sb[z] — max( y2-y1+1), where sum(b[i], i = y1...y2) <= z. Precalc O(N^2)3) answer = max( (x2-x1+1) * sb[X / sum(a[i],i=x1..x2) ] ), x1=1..n, x2=x1..n. O(N^2)total complixity: O(N^2). with O(N^2) memory.
•  » » 13 days ago, # ^ |   0 Is possible to solve C with binary search?
•  » » » 13 days ago, # ^ |   +1 Actually I used, but I don't know whether it could be ACed yet.
•  » » » » 13 days ago, # ^ |   0 I've read your code, maybe I have a different way. Here is my code (it has some bug) Here
•  » » » 13 days ago, # ^ |   0 I did it, then realize it was unnecessary, cause for both array, we could pre calculate the minimum sum for each range
•  » » » » 13 days ago, # ^ |   0 Yes, I solve it by using BS and too much code to implement.
•  » » » » 13 days ago, # ^ |   0 I've read your code, maybe I have a different way. Here is my code (it has some bug) Here
•  » » » » » 12 days ago, # ^ |   +5 hey, I solved it with binary search (C++'s built-in upper_bound)
•  » » 13 days ago, # ^ | ← Rev. 2 →   +4 The question can be converted into finding a subarray each from A and B such that product of sum of elements of those subarrays is less than or equal to x and the product of their size is maximum.Pre-calculate the minimum sum continuous subarray of array A of each size from 1 to N. For all those minimum sum subarray of size from 1 to N, find the largest subarray in B which satisfies the above condition. It can be done using two pointers. Code: 43769883
•  » » 13 days ago, # ^ |   +11 As JustAni pointed out: "The question can be converted into finding a subarray each from A and B such that product of sum of elements of those subarrays is less than or equal to x and the product of their size is maximum." Now, for both arrays we can calculate in O(n^2) the minimum sum achievable for interval sizes i=1..n, i.e. for array "a" we can calculate "a_min" as a_min[i] = min( sum(a[l]..a[r]) where r-l+1 = i), and the same can be done for array "b".Now simply try all possibilities, track the current maximum and try to update it to i*j when a_min[i] * b_min[j] <= x. The time complexity of this step is sufficient, as it takes O(n*m), and the previous step took O(n^2) + O(m^2).
•  » » » 13 days ago, # ^ |   0 Nice and clean solution. THanks!!!!!!!
 » 13 days ago, # |   0 In problem D what is the answer to this test case : 2 10 10 1 1
•  » » 13 days ago, # ^ |   +17 I believe it is 13.
•  » » » 13 days ago, # ^ |   +11 You're right Unfortunately I forgot this sentence : "You can make any number of circles" :(
•  » » » » 13 days ago, # ^ |   +11 Yeah, I had same problem to realize it for a 45 minutes, and after it I still couldn't solve on correct way :D
 » 13 days ago, # |   +84 10 second... give me 10 second to submit F...
•  » » 13 days ago, # ^ |   +68 F
•  » » 13 days ago, # ^ |   0 Could you please explain your solution?
•  » » » 12 days ago, # ^ |   0
 » 13 days ago, # | ← Rev. 2 →   -16 Probably I'm the only one who assumed C to be dp problem :(
•  » » 13 days ago, # ^ |   0 I wasted 2 hours try to fit, from DP to Segment tree, through many other stuff, to C.
•  » » 13 days ago, # ^ |   0 So how do you solve it?
 » 13 days ago, # |   0 How to solve E?
•  » » 13 days ago, # ^ | ← Rev. 2 →   +36 If you have path between two nodes in tree (a, b) equal to len, after adding extra edges in the tree it will be . So, for even paths it will be same as , for odd paths it will be for 1 bigger, i.e (). So, final answer will be , where s is the sum of paths in the tree and o is the amount of odd paths in the tree.
•  » » » 13 days ago, # ^ |   0 I understood it.Thanks!
•  » » » 13 days ago, # ^ |   0 Could you simply explain why it turns out to be (len+1)/2 after adding some extra edges?
•  » » » » 13 days ago, # ^ |   0 It's easy to convince yourself of this by making a few trees on paper (calculating sum of paths before/after extra edges and comparing).
•  » » » 13 days ago, # ^ |   0 How to count s?
•  » » » » 13 days ago, # ^ |   0 let's say for an edge there are 'a' nodes on one side of the edge and 'b' nodes on the other side of edge also a+b=n, now this edge will contribute to a*b paths(think ) do this for every edge and add them finally you will get s. Now to find the o(i.e count of odd length paths in a tree ) we can use dp on trees .
•  » » » » 13 days ago, # ^ | ← Rev. 2 →   +1 In addition to allllekssssa's comment1) Calculating s: First, you calculate subtree_size array, where subtree_size[i] is how much nodes do you have in a subtree rooted at "i" (or equivalently, number of descendants of node "i" + 1). You can calculate this array by first setting all values in array to 1, then computing the postorder traversal of the tree, and then iterating through nodes in postorder order updating that node's parent subtree_size with it's own (subtree_size[parent[node]] += subtree_size[node]).Now, we can easily see that each edge is used exactly the number of times which we get by multiplying number of nodes on both sides of the edge. If we have the "subtree_size" array mentioned, we can simply traverse all the nodes except the root and update the "s" as follows: s += (n — subtree_size[node]) * subtree_size[node]2) Calculating o: The path between two nodes will have odd number of edges iff they are on levels of different parity (level being the distance from the root). So, to calculate "o", calculate the number of odd-level nodes and the number of even-level nodes, and multiply them.3) Solution = (s + o)/2
•  » » » » » 12 days ago, # ^ | ← Rev. 3 →   0 edit: nevermind, I misunderstood and I typed something dumb but I was wrong.
•  » » » » » 12 days ago, # ^ |   0 Oh, the prove is so detailed and beautiful. thanks a lot.
•  » » » » » 3 days ago, # ^ |   0 Thanks. This helped me immensely!
•  » » » » » 3 days ago, # ^ |   0 Nice <3
•  » » » 12 days ago, # ^ |   +1 can you explain how the final answer will be (s+o)/2.
•  » » » » 12 days ago, # ^ |   0 yeah overall ans seems to be (s/2 + o) but this will give error because of integer division property firstly we know that(considering integer division) a/2 + b/2 =(a+b)/2 fails when both a&b are odd, and it works when both or at least one is even and for float division it is always true.a/2=a/2-0.5(left side integer div , right side float div)a/2+1=a/2+0.5. let divide paths into two sets s1(even length paths), s2(odd length paths) no problem is there when we combining the numerator of s1's terms but there is a problem with s2.for s2 to combine terms of s2 we need to take effect and must add 0.5 for each term after combining,it become overall addition of 0.5*o.hence it become overall s/2+0.5*o==(s+o)/2you can check each property
 » 13 days ago, # |   0 What was pretest 9 in problem C?
•  » » 13 days ago, # ^ | ← Rev. 2 →   +1 I don't know what was the pretest, but after five WA at 9th pretest this is what I did and I passed it. "If you can take sum=10 with X ways then you can take every sum more than 10 with X ways as well. This means that you need to update your array like this arr[i] = max(arr[i], arr[i — 1])"
•  » » » 13 days ago, # ^ |   0 My approach was completely different than yours, so can you explain in more general terms.
•  » » » » 13 days ago, # ^ |   +1 My way was to precalculate all possible sums for array A and B. Now lets say X = 10. If we get sum from array A equal to 5(let say from elements 2 and 3), then we need to get a sum from array B equal to X / 5 = 2 or less. So the key here is the word "less". You don't care only for the value X/sum, but for all the values that are less than that.
 » 13 days ago, # |   -47 I think this guy have cheated yuanmaoheng.
•  » » 13 days ago, # ^ | ← Rev. 2 →   +5 With whom? And how you got this info??
•  » » » 13 days ago, # ^ |   -58 Let see his submissions in the past and compare it with this contest. Seem like he have known all the problems. 5 submits and got 5 ACed. Wow!?!
•  » » » » 13 days ago, # ^ | ← Rev. 4 →   +3 This is not a sufficient reason.1. Especially when first 5 problems had ~500 submissions.2. No extra lines are added in his code. And his code is Accepted not skipped which proves that his code does not match with someone else.By this logic, tomorrow If I will solve 5 questions in Div2, then you will point me as a cheater.I'm not commenting If he cheated or not. But the reason you mentioned is not at all sufficient to doubt if he is guilty.
•  » » » » » 13 days ago, # ^ |   +7 Fyi, Skipping solutions (ie Plagiarism detection) takes place after system testing.
•  » » » » 13 days ago, # ^ |   0 There are many reasons for submissions of several problems in quick succession, like power-cut, network-dropdown or something.You can still think without power/network coverage, please.
 » 13 days ago, # |   +10 When the next Div.3 round is going to be?
 » 13 days ago, # |   0 my level of regret for trying D instead of C is over 9000
 » 13 days ago, # |   +16 Is it legal that leave a special case for hacking. http://codeforces.com/contest/1060/submission/43777486
 » 13 days ago, # | ← Rev. 2 →   +28 I made a very funny bug in D. Instead of an easy solution with sorting both arrays independently I overdid and created two sets with pairs (one ordered by first component and the other by second component). As in easier solution I considered maximum of first components and maximum of second components. But when considering two pairs (l_max, r_not_max) and (l_not_max, r_max) I wrote a code removing both them from sets and inserting an element (l_not_max, r_not_max) (like we placed two people with corresponding segments alongside). Of course, if two pairs are the same we don't have to insert anything — we just remove this pair from both sets.When checking if actually two pairs are the same I did stupid mistake and wrote an always-true condition. if (ppl._2 == ppl._2) { stl.erase(stl.begin()); str.erase(str.begin()); } else { // manipulate with sets } But it appeared that this mistake didn't ruin the solution. When we simply remove maximal elements from both sets we have a situation similar to a one with two independently sorted arrays (as in easier solution). After the contest my friend showed me this mistake and I was upset because didn't realize that easier solution works. But surprisingly it got AC, and now I understand why :)
 » 13 days ago, # |   +52 Even though I did not perform well today, I will probably remember this round as I hacked a solution with an anti-quicksort testdata.
 » 13 days ago, # | ← Rev. 3 →   -175 Today Chinese guys did so great. There were 4 Chinese in top 5, 7 Chinese in top 10 and 13 Chinese in top 20. How do you guys train?There must be a secret technique. ;)
•  » » 13 days ago, # ^ |   -21
•  » » 13 days ago, # ^ |   +181 Maybe the time is good for Chinese?
•  » » 13 days ago, # ^ | ← Rev. 2 →   +141 It was because of the timing. The contest started at 15:00 in China during the National Day vacation, when almost everyone can participate with full energy.
•  » » 13 days ago, # ^ |   +143 The only thing is this round was held in the afternoon in UTC+8 and others were mostly at midnight.
•  » » » 13 days ago, # ^ |   -82 China needs new online judge like codeforces
•  » » » » 13 days ago, # ^ |   +94 Do you know UOJ and LOJ?
•  » » 13 days ago, # ^ |   -20 I'll just post this good old meme here.
•  » » 12 days ago, # ^ |   +39 Because they accepted thousands of hard problems.
•  » » 12 days ago, # ^ |   -16 You are just a Specialist. YOU ARE NOT EVEN QUALIFIED TO JUDGE IT!
 » 13 days ago, # |   0 can anyone will tell me the approach for problem B ? thanks in advance .....
•  » » 13 days ago, # ^ | ← Rev. 2 →   +7 Any digit (except for the first one and any nines that may appear) in the number n can result either from simple addition (d1 + d2 = dn) or addition with "carrying" (d1 + d2 = 10 + dn. So one possible solution is to check all bitmasks from 00...00 to 11...11 where 0 denotes that a certain digit is produced by simple addition and 1 that it was produced by "carrying" with taking care to discard masks that have 1 in a position where there''s a 9 followed by a 0.However, simply adding to seems to work.
•  » » 13 days ago, # ^ |   +1 For a,b what matters is the sum of digits (and not the number itself) and for max sum have as many 9's in a as possible.So number of number that a can be 10 * (number of digits in n).Permute through all a's such that a < n and b = n-a and the find max(S(a)+S(b)). Link to my solution:43764388
•  » » » 13 days ago, # ^ |   0 Hi, I understand the algorithm, but I would like to know if you can prove the correctness of the algorithm. That is why the algorithm always works?
•  » » 13 days ago, # ^ |   0 Though there were easy number theories for this problem, don't know why the idea of digit dp hit my mind. My solution using digit dp was not very complex though. Just construct every number a less than n and store maximum s(a)+s(n-a) in the dp table.My solution: 43766071
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 My solution is an easy one. Just find most close number ending with most 9s.a = n — (n % (10**(len(str(n)) — 1))) — 1; b = n — a
 » 13 days ago, # |   0 How to solve D?
•  » » 13 days ago, # ^ |   +2 First sort l[] and r[]. Then iterate from reverse direction — if(l_i and r_i are of different person) then add max of them to answer because we can place them on adjacent places and left of one will be right of other. if(l_i & r_i are of same person) then form new group and add max of l_i and r_i to answer.
•  » » » 12 days ago, # ^ |   0 Thanks!
 » 13 days ago, # |   +20 I wonder if there will be a tutorial? Or has it not come yet?
•  » » 13 days ago, # ^ |   +21 I have been refreshing this blog page since last two hours to check for Tutorial update. Don't tell me there will be no tutorial.
 » 13 days ago, # |   +19 where is the editorial?
 » 13 days ago, # |   +2 Problems were good. Eagerly waiting for the Editorial for some up-solving.
 » 13 days ago, # |   -8 Could you tell me where i can get the editorial? I can't understand the O(n^2) algorithm of C.PS:It seems that D is much easier than C.I use ACDeny this account in this contest and get 3 problems except C. --Sorry for my poor English :)--
•  » » 13 days ago, # ^ |   +18 It seems that if you could not solve D quickly, then it would be really difficlt... I solved A to E except D :( For me, the algorithm for C is more familiar.
 » 13 days ago, # |   +16 Problem D is great! But I was too stupid to solve it in the contest:(
 » 13 days ago, # |   -15
 » 13 days ago, # |   +21 Could you share the tutorial?
 » 13 days ago, # | ← Rev. 2 →   +6 How does D work? I still don't understand the solutions. Will there be a formal proof for this sorting method? For some reason I can't convince myself that it's correct...
•  » » » 12 days ago, # ^ |   0 Hey, thank you very much, I understand it now.
•  » » » 11 days ago, # ^ |   0 Very nice explanation
 » 13 days ago, # | ← Rev. 2 →   +105 My solutions to some of the harder problems:E: recursive DP. If the distance from u to v in the original was d, it is now ceil(d/2). Within a subtree, keep track of sum of distances to all descendants at odd depth sum of distances to all descendants at even depth number of descendants of odd depth number of descendants of even depth With this information, one can link a new subtree to a parent in O(1) time. There are four cases, and in each case you can compute the sum of lengths of all paths through the new edge, as well as how much to add to account for the ceil().F: we'll solve separately for each query (fortunately N is small to we don't need to be too careful about efficiency). Place the query node at the root. Now consider some subtree. For the first few shrinks, it won't matter which label is chosen, but at some point this subtree will be rooted at the root of the whole tree and then any shrink involving the root has to pick the root label. So we can use DP to answer this question for each subtree and each K: if the first K shrinks are "safe", what is the probability that the shrinks won't eliminate the root? We start from the leaves, and build up a tree using two operations; 1. Add an edge above the old root. To answer this, we need to consider each possible position this new edge can have in the sequence of shrinks of the subtree. 2. Join two trees together at the root. In this case the events in the trees are independent, but he have to consider all possible partitions of the safe shrinks between the two trees.H: I had an algorithmically correct solution to this, but just ran out of time debugging it (I wasted a lot of time before reading that the other cells contained 1, not 0). Since we can add numbers, we can multiply a number by any constant, and we can do it in log time using the same trick normally used for fast exponentiation. That also means we can divide by a constant (just multiply by the inverse mod p), we can construct 0 (multiply anything by p) and negate numbers (multiply by -1).We can compute xd, (x + 1)d, (x + 2)d, ..., (x + d)d, and express each as a linear combination of 1, x, x2, x3, ... xd. The resulting matrix can be inverted to allow any xi (0 ≤ i ≤ d) to be expressed as a linear combination of (x + j)d (0 ≤ j ≤ d).This means that we can square numbers, and since xy = ((x + y)2 - x2 - y2) / 2, we're done.
•  » » 12 days ago, # ^ | ← Rev. 3 →   +94 A few different solutions for problems E and H:E: Each path of length d becomes a path of length . This means the total sum of paths is equal to (sum of all path lengths + # of paths of odd length) / 2. Sum of all path lengths can be computed quickly by noting that each edge is crossed exactly sizeleft * sizeright times, where sizeleft and sizeright are the sizes of the two subtrees on either side of the edge. Number of paths of odd length can be computed similarly -- it's just nodd * neven where nodd and neven are the number of nodes with odd and even depth from the root, respectively.H: Consider the polynomial (a1 + a2 + ... + aD)D. It contains the term D!a1a2...aD as well as lots of other extraneous terms. Inclusion-exclusion on the D-th powers of each subset sum of ai leaves just this D!a1a2...aD term (since it's the only term that encompasses all D elements ai). Now apply this idea with a1 = x, a2 = y, a3 = a4 = ... = aD = 1 and you're done :)Really interesting to see this strategy in H of obtaining x2 from x. From looking at a few other contestants' solutions it looks like most people followed this route -- curious how you all thought of the idea!
•  » » » 12 days ago, # ^ |   +23 Nice solution to E.On H, I wonder if your solution was the intended one — it would explain the very low constraint on D, since your solution takes operations, whereas mine takes . As to how one thinks of it, I started with (x + y)d as the obvious way to get products of x and y, and then saw that as long as d=2 it would work out easily.
•  » » » 12 days ago, # ^ | ← Rev. 2 →   +10 No, O(2d) solution was not expected, could you describe it? (I see you already did.) The constraint for d was kinda random.You can came to x2 idea by setting x = y. The reason we made no samples was to hide this idea, because it's quite apparent even from case d = 2, p = 3.
•  » » » 12 days ago, # ^ |   +10 For E is it possible to do ceil(ans/2) instead of counting odd and even? Thanks in advance.
•  » » » » 12 days ago, # ^ |   +10 Nope, let's say there are 3 paths of length 3 in the original tree, after adding the edges they would become 2, so 6 in total. ceil(9/2)=5
•  » » » » » 12 days ago, # ^ |   +10 Oh I see, Thanks!
•  » » 12 days ago, # ^ | ← Rev. 2 →   +18 How to proof that the coefficients of xd, (x + 1)d, ..., (x + d)d are linearly independent under modulo p?
•  » » » 12 days ago, # ^ |   0 That's a good question. It's something I remember (at least for the real numbers, and I just trusted it would also work out in the field mod p), but I can't think of a proof at the moment.
•  » » » 12 days ago, # ^ |   +8 If you look closely at Lagrange interpolation formula, you'll see it works while d < p.Alternatively, if you put coefficients in a d + 1 × d + 1 matrix , one can see it is (almost) Vandermond's matrix, and its determinant can be calculated directly.
 » 12 days ago, # |   +65 Where is the editorial?
•  » » 12 days ago, # ^ |   +72 It's dead .
 » 12 days ago, # | ← Rev. 2 →   +95 The editorial is very funny.
•  » » 12 days ago, # ^ |   +5 Where is it ? Has it been released ?
 » 12 days ago, # |   0 i am new to BST. can anyone tell me the source or links for basic questions on BST for practice ? thanks in advance...
•  » » 12 days ago, # ^ |   0 BSTs are usually asked in Interview questions rather than competitive programming.I think Hackerrank here has a really good collection of BST questions.
•  » » » 12 days ago, # ^ |   0 thanks a lot man .....
•  » » » 12 days ago, # ^ |   0 hey man.. i am from GBPIET pauri..
 » 12 days ago, # |   +59 Well I've waited for the editorial for a whole day...
•  » » 9 days ago, # ^ |   +21 Well I have waited the editorial for four whole days.
 » 11 days ago, # |   +50 When you see this comment,you have wasted lots of time waiting the dead editorial.
 » 10 days ago, # |   +11 Does anybody know where the tutorial is?
•  » » 9 days ago, # ^ |   +9 I think there won't be. Because last year's round by Barcelona Bootcamp doesn't have tutorial.
 » 8 days ago, # |   +11 where is the Tutorial? I'v been waiting for several days!I want to know how to solve F and H!
•  » » 6 days ago, # ^ |   0 still waiting lolz
 » 7 days ago, # |   0 This algorithm is great! It has helped me alot in this problem!