Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

justHusam's blog

By justHusam, 20 months ago, In English,

Hello Codeforces,

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

The problems were prepared by justHusam (Husam Musleh), Lvitsa (Alaa Abu Hantash), Mohammad_kilani (Mohammad Kilani), Nada_Shamayleh (Nada Al-Shamayleh), AbedAbuhijleh (Abed Abuhijleh), H2A_TLE (Asem Al-Radaideh), and TheDealer (Ahmad Jaber).

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.

 
 
 
 
  • Vote: I like it
  • +43
  • Vote: I do not like it

»
20 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Will there be an editorial?

If not, then how to solve I and B?

  • »
    »
    20 months ago, # ^ |
    Rev. 3   Vote: I like it +13 Vote: I do not like it

    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:

    1. We have the only child. Then we can find an answer for this vertex.
    2. 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:

    1. Some data where key is equal to value[v] - depth[v]
    2. Some data where key is equal to value[v] + depth[v]

    These structures should contain next fields:

    1. map<int, int> count which contains count of vertices by key
    2. count of values with the most occurrences in map (max value)
    3. 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

»
20 months ago, # |
  Vote: I like it +3 Vote: I do not like it

can we have please an editorial ?

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve J? Do i need use long arithmetic(BigInteger)?

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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!!!!

»
20 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve C, F and I?

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve k ?

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve I?