Solutions to the problems are not accesible.

Решал задачу С с помощью дп. Было три дп массива: в одном хранился ответ для i-й вершины, если приравняли именно эту вершину 0; во втором дп хранился ответ для i, если эта вершина не выбрана, но есть вершина выбранная до нее; в третьем хранил ответ для i-ой вершины, если никакой вершины до нее не было выбрано, и она также не выбрана. Получаю wa-7. Интересно узнать можно ли заслать задачу моим решением.Код

I think problem C, we don't need to consider the first case which root's value equal 0. Doing the latter is enough.

In problem C, in the sample code, I dont understand this line.

if (koll[i] >= dist)
            ans[v] = max(ans[v], del[i]);

Should it not be ...

if (koll[i] >= dist-1)
            ans[v] = max(ans[v], del[i]);

Since, its enough to have only d-1 divisors from the root to that node in that path, why should we check dist, when dist-1 itself satisfies the condition? Could someone help me out with this?

"Let's build a segment tree on the eulerian tour of the tree." <3 <3 <3

I did not understand the solution for the D question. Could someone please explain the solution?

In problem C div 2 , i tried dfs(int node , int max , int simple_gcd) , here max is the maximum beauty possible of parent node if we have already set 0 on an ancestor node and simple_gcd is gcd of all numbers excluding the node we are on .....

At each node i can either make the current node 0 (in this case the gcd will be previous/parent node) or let 0 be in previous optimal position ( take gcd of max with current node a[n] )...

For example if we had a 5-->10-->7-->15 (1-->2-->3-->3-->4) , we would maintain two variables max and simple_gcd at each step initially, for the root node ans[1] = a[1] = 5 , and for 1st node under root , i.e 10 ans[i] becomes max(a[root], a[node]) which means we make minimum element 0 , now dfs starts to find ans of all nodes below, for node 3 we have max = 10 (0 is set at 1st node(5) ) and simple_gcd = 5 (no zero set uptill now therefore simply the gcd uptill here) , now i compare max of (simple_gcd , gcd(max , a[3]) ) which gives me ans[3] = 5 , and i keep moving on this way...

Currently i am getting WA on test case 4...anyone has any suggestions ?? Here's my submission http://mirror.codeforces.com/contest/842/submission/29929743

In problem A it is said that efficiency may be a non-integer number, but in editorial we think that it is integer and don't check if exp = k*cost is non-integer

Помогите, пожалуйста!

Я сейчас пытаюсь решить задачу C, но, думаю, столкнусь с той же проблемой, что и в задаче C/Div.2 (Codeforces Round #428).

Подскажите, пожалуйста, почему моё решение такое медленное? Вот моя программа: http://mirror.codeforces.com/contest/839/submission/29901357.

Help me, please!

I'm trying to solve problem C, but I believe I will face the same problem as in problem C / Div.2 (Codeforces Round #428).

Tell me, please, why my solution is too slow? Here is my programm: http://mirror.codeforces.com/contest/839/submission/29901357.

Задачу Е можно решить, на мой взгляд, сильно проще. Заметим, что если вершина не является концом никакого диаметра, то она не будет им ни на каком из следующих шагов. Тогда можно посчитать концы какого-либо диаметра на каждом шаге, а затем бинарным поиском найти момент для каждой вершины, где она перестанет быть концом диаметра. С помощью Sparce Table это можно сделать за O(N logN)

In Problem C tc1 shouldn't the answer be 6 2 , bacause in 1 gcd is 6 , but in 2 gcd is gcd(ans[1],a[2]) that means gcd(6,2) which is 2..

I noticed that problem E is also labelled with the "binary search" and "divide and conquer" tags, may someone share how to solve the problem in this alternative approach? :)

Can problem C be solved like this?

Let f(u, x) is the maximum beauty for node u and we have chosen x parent nodes (0 <= x <= 1) to change their value to 0 (because only the value of ancestor vertices affect the beauty of node u) . Then we have this formula:

Let p be the parent of u.

f(u, 0) = gcd(f(p, 0), a[u]).

f(u, 1) = max(f(p, 0), gcd(f(p, 1), a[u])).

Then for each node u the answer will be max(f(u, 0), f(u, 1)).

I haven't tested this solution, but I wondered will this solution work? (correct me if I'm wrong)

for problem E:

this is a quite simple code! http://mirror.codeforces.com/contest/842/submission/29919946

But I can not understand why this is correct,who can help me :(

For Div.2 C. Why the editorial solution guarantee that result will be max? I don't get it.

For Problem A — Kirill And The Game — it may be very time-consuming to iterate on cost from (x) to (y), or to iterate on experience from (l) to (r), when ( y — x ) or ( r — l ) is a very large number, as all these numbers range between 1 and 10,000,000.

A much more efficient loop-free approach is to compute the intersection of the two intervals:

1. k . x <= experience <= k . y
2. l <= experience <= r

expressed as: min_experience <= experience <= max_experience, where min_experience = max( l, k . x ) and max_experience = min( r, k . y ).

The answer to the problem instance is "YES" if the experience-interval intersection is not empty and contains at least one multiple of k; otherwise the answer is "NO".

In order to not iterate through the intersection interval, it is sufficient to compute the corresponding cost interval: min_cost <= cost <= max_cost, where min_cost = min_experience div k and max_cost = max_experience div k.

The answer to the problem is "YES" if ( min_cost < max_cost ) or ( min_cost = max_cost and min_experience mod k = 0 ); otherwise the answer is "NO".

The following is a C++14 implementation of this algorithm.

http://mirror.codeforces.com/contest/842/submission/29941778

Just for curiosity, there is some way of do the A in O(1)?

Glebodin In problem C , you are considering only root to be 0 and comparing it with dfs2 results, but when calculating beauty of other vertices, other than root vertex can also be zero. Also why did you write

for (int i = 0; i < del.size(); i++)
        koll[i] -= (mas[v] % del[i] == 0);

at the end of dfs2() ? ans[] in upper recursion calls are already calculatd. we are not using koll[] in upper recursion calls. then why update it?

Помогите пожалуйста разобраться, как получать наименьшее возможное число с помощью бора (поесть функция Get в коде-разборе).

Can someone please tell why my code is getting WA at test 14? Link Thanks in Advance!

For Div2 C, if 0 would be an allowed value for a[i], (and hence root's value could be 0 initially) then how would one go about solving the problem?

For problem E : Can someone explain to me what "diameter of the tree" is, please ? Sorry for my bad English .

Can Div. 2 C be solved like this?

I am maintaining 3 arrays. Their definition is like this:

total[i] holds the gcd of all number on the path from root to node i.

zero[i] holds the beauty value if we put 0 in the node i.

not_zero[i] holds the beauty value if we don't put 0 in the node i.

Then lets have a function that gives me the beauty value named beauty(_node,par) that gives me the beauty value of _node which has parent named par.

If I put 0 in current node, then I couldn't put any 0 in any of the previous node on the path from the root.

If I don't put 0 in current node, then I could put a zero in any of the nodes that are on the path before this node.

beauty(_node,par){
    total[_node] = gcd(val[i],total[_par]);
    zero[_node] = total[_par];
    no_zero[_node] = max(gcd(val[i],zero[_par]),gcd(val[i],no_zero[par]));

Then the answer for each node is max(total[_node],max(zero[_node],no_zero[_node]))

But this solution gives WA on test case 7. Can anyone give a small test case for which this solution is wrong?

How to solve problem D? Editorial isn't clear.