Tutorial for F shows the one for A.

Very nice contest, thanks!

rating changes?

I have another interesting solution for E since I couldn't come up with that dp idea. My solution brute forces and generates all the possible answers for n (vertices count) and doing this for all n <= 24 seems enough and if you can implement it carefully it will pass the time limit. Code.

did anyone else not have his rating change, because I did and when I checked it said that it was unrated for me but I am under 2100 and I participated as rated

The problems are very nice, especially for B,E and F :)

325787868 what was wrong with my logic?

Thank you for a wonderful contest, D was beautiful. I was wondering how to count number of good pairs given a directed tree as in D

Forgot to use long long… lesson learned.

I wonder how to use two pointers to improve the time complexity of $$$C$$$ to $$$O(n$$$^$$$2$$$$$$).$$$

32595261 Hey can anyone tell why this is failing. I modify the for loop to seperate the logic to check for 2 consecutive elements and 3 consecutive elements and it starts working. I wanted an example testcase for which this code wont work. Thanks!

When the rates update

Edi not linked on contest page

So when will rating update?

Does anyone could say something about rating changes? If it's been a problem or it's in process, etc. We would like to know something please

Can someone explain me this part better for E?

Note that if a vertex is not green, its entire subtree must be colored the same color: for example, if the vertex is blue and it has a green or yellow descendant, the root is unreachable from that descendant without passing through that blue vertex. At the same time, the green vertices do not impose any additional constraints.

why is this tree illegal? (green)-(blue)-(green)

This is also the third example of the pretest 1, but I don't understand why this coloring has to be excluded

Can anyone explain why we need to add dp[x-2] i.e. dp[m] = dp[m/x] + dp[x-2] in E.

when will rating change

Cana anybody tell that why this is not working for problem C

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    int t;
    cin >> t;
    while (t--)
    {
        ll n,ans=0;
        cin >> n;
        ll a[n];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        sort(a,a+n);
        for (int i = 0; i < n; i++)
        {
            for (int j = i+1; j < n; j++)
            {
                auto it=lower_bound(a,a+n,a[i]+a[j]);
                if (it==a+n)
                {
                    ans+=(n-1-j);
                }
                else{
                    int index=it-a;
                    index--;
                    if (index>j && a[i]+a[j]+a[index]>a[n-1])
                    {
                        ans+=(index-j);
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

This is my submission id , it is giving error in test case 1 of example 3
https://codeforces.me/contest/2112/submission/326045388

I would be grateful if anyone help me with these

In D I have a doubt!!!!!, I have No; in test 2 case 1507 (hidden case), the thing is as per editorial, the only sufficient condition for n good pairs is to have a vertex with 2 components, but I think we need a vertex with 2 components and one of those component should be 1 degree (connected to only 1 component). I am checking that and if not found output 1.

Because as per my logic, if lets say I have a component of 2 degrees connected to each other, no matter what dirc I change, I will always create more paths than n. So I don't know why.

Can someone give me a test case where this is true!!!!!

My code for ref, if needed here

I am absolutely stunned by problem E and its solution

A very beautiful problem indeed.

Does anyone have more problems that uses similar arguments?

Does dp[m/x] + dp[x-2] imply that no subtree has more than 2 children? I understand why we can use dp[x-2], but doesn’t dp[m/x] represent the minimum vertices in a single tree with that many colorings? Why can’t the optimal tree have many children whose coloring product equals m/x? Does dp[m/x] work in this case? Edit: never mind, I believe it is because dp[x-2] accounts for the last subtree and dp[m/x] accounts for the root + remaining subtrees. Please correct me if I am wrong.

Nice problems, thanks!

I want to share a bit different approach on problem E.

1. Let's say that C(T) is number of ways to color tree T.
2. Let's say that Cs(n) is set of all C(T) among trees T with exactly n vertices.

Let's find Cs(n) for all n's that can be the answer. It can be calculated using dynamic programming like this:

const int MAXM = 500000; // the maximum value of `m` from the statement

// k is size of the first subtree of root
for (int k = 1; k < n; k++) {
    // iterate over the number of colorings of tree without the first subtree
    for (int x : Cs[n - k]) {
        // iterate over the number of colorings of the first subtree
        for (int y : Cs[k]) {
            // add two colorings: all-yellow and all-blue
            y += 2;
            // we don't need too large numbers of colorings
            if (static_cast<long long>(x) * y <= MAXM) {
                Cs[n].insert(x * y);
            }
        }
    }
}

And then if you print the sizes of Cs[n], then you can notice that it stops growing after n = 25. So you don't need to iterate for more than that. Then you can simply find the smallest n for any number of colorings.

I don't know the complexity of this solution, but it is fast enough to pass the testcases with 546 ms. The submission can be found here: 326206231.

Some observations for problem E:

m must be a an odd number. why?

Let cnt(v) denote the no. of colorings of the root v of a subtree given that it is green.

If it’s children are u1,u2,…,uk then they have cnt(ui) + 2 total colourings. +2 for all blue and all yellow cases.

Since all subtrees are independent, cnt(v) = (cnt(u1)+2)(cnt(u2)+2)…(cnt(uk)+2)

Consider the base case of a leaf node, it has 3 possible colorings(i.e. odd).

and any answer that is formed from these base cases is a product of odd numbers which is also odd. So, m must be odd.

If m is a power of 3 then the tree with smallest number of nodes is the tree with a root attached to n leaves where n is the power of 3, so n+1 in total.

Using a linear chain we can create all odd number of colorings starting from 1. //Edit : please consider the following to be void for now.

For any given m, find it’s prime factorisation and write it such that the product shows all factors distinctly. E.g. 75 = 5*5*3.(not 5^2*3)

Then the optimal tree is the root connected to n linear chains whose no. of possible colorings are equal to the prime factors(we can have any prime no. using a chain). where n is the total no. of prime factors, considering recurring equal factors to be distinct.

You can simply determine the no. of nodes in each children chain and form the total answer. I guess the dp solution achieves this in an easier way.

For problem E, I'm confused on the line of the editorial "if a vertex is not green, its entire subtree must be colored the same color". If I am coloring a tree with only green and blue (i.e., not coloring any node yellow so there are no yellow-green paths), can't I have green nodes in the subtree of a blue node?

Can anyone help me to clear the doubt for tutorial A? Suppose a,x,y=1,2,3 then is there any position for Bob to get the prize always? Even though he chooses 4 as position he will never be able to get the prize at x=2 because a is at 1. The questions asks for a guaranteed position for Bob not that position where he may win conditionally. I may be wrong can anyone help me with this?

Shouldn't the correct condition should be: ~~~~~ int dist = min(abs(a — x), abs(a — y)); int side = (x — a) * (y — a); if (dist > 1 && side > 0) cout << "YES" << endl; else cout << "NO" << endl; ~~~~~ At least a distance of 1 so,that Bob can take that position as Alice and Bob cannot be at same position.

Problem D seemed almost to be a copy of a previous problem https://codeforces.me/problemset/problem/1144/F but anyway Thanks for contest !

I suggest to improve the description of the problem F. 'The variable $$$a_{x_i}$$$ gets assigned' or 'The $$$x_i$$$-th variable gets assigned' not 'the variable $$$x_i$$$ gets assigned'. BledDest