justHusam's blog

By justHusam, 2 years ago,

Hello Codeforces,

I would like to invite you all to participate in the 2018 Arabella Collegiate Programming Contest. The contest was originally held on 28th of April, and it will launch in Codeforces Gym tomorrow Saturday, 03 November 2018 10:00 UTC.

Thanks to Hasan0540 (Hasan Alhamsh), Dehayat (Mohammad Dehayat), and Zuhair (Mohammad Zuhair) for testing the problem set.

The duration of the contest is 5 hours, and the registration will be open 6 hours before the start of the contest.

Good luck to everyone, and I wish you all accepted solutions.

UPD: Registration is currently open.

• +43

 » 2 years ago, # |   +4 Will there be an editorial?If not, then how to solve I and B?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +13 B:After some drawing it becomes easy to see that if the vertex has more than 2 children, then the answer is -1.If the vertex is a leaf then the answer is 0.If any children has no answer(-1), then current vertex also doesn't have an answer. And there are two situations left: We have the only child. Then we can find an answer for this vertex. We have two children. Then we also can find an answer for this vertex, but none of the parents will have an answer. First of all we have to make an observation that the answer for a current vertex is a path that starts somewhere deeper (or starts here), goes up to the current vertex and then (maybe) goes down. Vertices in this path should form an arithmetic progression. Sometimes I will suppose that we start at the vertex v, but it doesn't change anything.Let's explain what to do when we have the only child (first situation):Suppose we have some vertex v with the value x written on it. Then we want to form a sequence x, x+1, x+2 and so on (or x, x-1, x-2 and so on), this sequence starts from v and goes deeper. So if we don't want to change a value written on it, we should change some other values on this path so they will be equal to what we want. So one of the possible answers for this vertex is just count of vertices we have to change so that they will be equal to what we want (vertex that is our child has a value x+1, child of our child has a value x+2 and so on).But what if we want to change our value? So, here is a very useful trick that literally solves the whole problem. Suppose we want to change our value to some other value x so that we can form a sequence x, x+1, x+2 that starts in current vertex. Also suppose that our child is c1 and the child of out child is c2. Then we can represent its values in the other way: value'[v] = x - depth[v], value'[c1] = value[c1] - depth[c1], value'[c2] = value[c2] - depth[c2] and so on. You can see that if some of these values form an arithmetic subsequence the values written in it will become the same. So now we just have to take the value that has the most occurrences (it will be res) and our answer may be equal to children_count - res + 1.Returning to the situation when we don't want to change our value. To compute an answer we should take count of children which have the value'[c] == value'[v], lets call it res. An answer may be children_count - res.Okay, now I'll explain the second situation:Lets call our children left and right.We have 2 children and 2 choices: We want to change our value or we don't want to change our value.Suppose we don't change current value. Then one of our paths should go down with delta = +1 and the other should go with delta = -1. So we have value1[v] = value[v] - depth[v] and value2[v] = value[v] + depth[v]. The answer can be updated with left.children_count + right.children_count - left.count1[value1[v]] - right.count2[value2[v]].If we want to change the value, we should iterate over all values in the left children, suppose which value should be written in the current vertex and solve the same situation with fixed value (described above).Now it's clear that the problem is solvable by dfs that returns null if it becomes impossible to build a path somewhere in the parents, or it returns a pair of structures: Some data where key is equal to value[v] - depth[v] Some data where key is equal to value[v] + depth[v] These structures should contain next fields: map count which contains count of vertices by key count of values with the most occurrences in map (max value) total count of values (sum over all values) If you are in leaf you have to create a new structure and add you vertex to it.If you are in the first situation you have to add your value to the structure obtained by dfs on this child and then return it.If you are in the second situation you should return null since it's impossible to build any path when we have such a subtree.Some tips: When you're in situation 2 don't forget to swap children and do the same computations, otherwise you may skip some possible answers (I've got +2 on this problem during the contest just because I didn't swap it). Also never forget to try to go down with delta = -1 and delta = +1.After doing all the computations add current vertex to the structure you are going to return.The whole solution works in O(nlogn): Every vertex can be added to the structure exactly once and when we are in second situation, we iterate over all the vertices added before and then forget about those vertices so this is NOT O(n^2).I think it's enough to solve the problem. Sorry for any possible errors in the text and feel free to ask anything about this solution =)You can try to practice this trick on the problem from SnackDown 2018 Round 1A: https://www.codechef.com/SNCK1A19/problems/PERIODIC
•  » » » 2 years ago, # ^ |   0 Can we replace negative value for some node?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 There are no restrictions on new values, so you can use negative ones.
 » 2 years ago, # |   +3 can we have please an editorial ?
 » 2 years ago, # |   0 How to solve J? Do i need use long arithmetic(BigInteger)?
•  » » 2 years ago, # ^ |   0 The formula represents pascal's triangle.The number of odd elements in row i = 2 ^ (#1's in the binary representation of i)So answer = n + 1 — 2 ^ (#1's in the binary representation of n)
•  » » » 13 months ago, # ^ |   0 Y is that correct?
 » 2 years ago, # |   0 Can anyone explain why this submission for problem H is accepted and this got TLE? Basically of both them are same, but after removing some unnecessary lines from accepted code, it gave TLE!!!!
 » 2 years ago, # | ← Rev. 2 →   0 How to solve C, F and I?
•  » » 5 weeks ago, # ^ |   0
 » 2 years ago, # |   0 how to solve k ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 it is yours mugiwara7
 » 17 months ago, # |   0 How to solve I?
 » 4 days ago, # |   0 can anyone explain the formula to solve problem ci see these two formulas but i can figure out how to reach itthese two formulas :my formula so far : (if anyone can help with what is wrong in it , it will be so great)https://ideone.com/6J2QzDThanks in advance!