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), Shanks (Mohammad Kilani), Roze (Nada Al-Shamayleh), AbedAbuhijleh (Abed Abuhijleh), H2A_TLE (Asem Al-Radaideh), and Jester (Ahmad Jaber).

Thanks to Hasan0540 (Hasan Alhamsh), Ptrq (Mohammad Dehayat), and MohammadZuhair (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.

Will there be an editorial?

If not, then how to solve I and B?

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:

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:`key`

is equal to`value[v] - depth[v]`

`key`

is equal to`value[v] + depth[v]`

These structures should contain next fields:

`map<int, int> count`

which contains count of vertices by keyIf 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 isNOT 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

Can we replace negative value for some node?

There are no restrictions on new values, so you can use negative ones.

can we have please an editorial ?

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

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)

Y is that correct?

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

How to solve C, F and I?

i -> https://ideone.com/lbR51L c -> https://ideone.com/3UZo7U f -> https://ideone.com/uYqraJ

how to solve k ?

it is yours _Mugiwara_

How to solve I?

can anyone explain the formula to solve problem c

i see these two formulas but i can figure out how to reach it

these two formulas :

https://paste.ubuntu.com/p/jq2ZkWHhsy/ , https://ideone.com/3UZo7U

my formula so far : (if anyone can help with what is wrong in it , it will be so great)

https://ideone.com/6J2QzD

Thanks in advance!