Tutorial for F shows the one for A.

Very nice contest, thanks!

I guess by mistake you have put the editorial of A in F ;-;

rating changes?

when we get our rating?

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!

Very good contest, thanks.

Has this contest become unrated?

When the rates update

Edi not linked on contest page

So when will rating update?

Will the ratings not get updated.

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

// Problem in the rating system
bool problem = false;
cin >> problem;
if (problem)
{
    cout << "Please tell us the type of the problem:" << endl;
    string x;
    cin >> x;
    if (x == "cheaters")
    {
        cout << "Post their names on the blog and block them from the website." << endl;
    }
    else if (x == "It becomes unrated")
    {
        cout << "Why? Please give us some reasons!" << endl;
    }
    else // It will be posted, but there are technical problems
    {
        cout << "Okay, you should have told us, but it's fine. I'm waiting — please give us a deadline." << endl;
    }
}else
{
cout << "No there is a problem, I am sure check it again" << endl;
}

// please don't hack the code

325760640

I tried this approch in problem A and it works

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

is rating updated for educational round div 2

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://mirror.codeforces.com/contest/2112/submission/326045388

I would be grateful if anyone help me with these

Thanks for the editorial

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

Have you checked MOSS yet?

Drop the ratings please :)

Hello Codeforces Team,

I have received a message that my solution for problem 2112B (#325782053)coincides with many others. I want to clarify that I wrote my code entirely by myself and did not copy it from any source, nor did I share it with anyone.

I used VS Code, and I didn’t post or share my solution publicly. If the coincidence happened due to unintentional exposure (like online IDE visibility or similar logic), I sincerely apologize and assure you that I’ll be more careful in future contests.

Please reconsider the decision if possible, or let me know if there’s anything I can do to provide more details.

Thank you. tanwarbrijessh

I am absolutely stunned by problem E and its solution

A very beautiful problem indeed.

Does anyone have more problems that uses similar arguments?

I got the following message :

"Attention!

Your solution 325720028 for the problem 2112B significantly coincides with solutions LuzZ_ShayanZ/325720028, khanna_dhruv/325731757. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked."

I would like to clarify that I did not engage in any form of cheating or code sharing during the contest. I wrote my solution independently using VS Code on my personal computer, without using any online IDEs or shared environments. The problem was quite straightforward and naturally leads to a limited set of logical steps — such as checking adjacent differences and detecting local extrema — which explains the similarity in approach.

All my problems A to D are skipped. This was a big bump in my rating so please help me or guide me what to do.

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.

hello biru

I am still not able to understand C solution. I got it that lower bound is to figure out the range, but not the particular conditions!. Can someone explain me? Stuck for four days!

for shrinking array B Question

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?

E is such a good problem

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.

Hi, I am currently practicing the problems in this contest & I seem to have gotten stuck on problem D. I have implemented the solution in Python based on the approach in the editorial.

https://mirror.codeforces.com/contest/2112/submission/327620250

However, I keep getting runtime error on the 9th test case, & it beats me as to what the issue might be. Would be lovely if I could get some pointers on this one.

Problem D seemed almost to be a copy of a previous problem https://mirror.codeforces.com/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

Can anybody tell that why this code is giving wrong answer for problem C(2112C — Coloring Game)

// clang-format off
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define vi vector<int>
#define endl "\n"
// I/O helpers for variables, vectors, and matrices
template<typename T> void in(vector<T>& v) { for (auto& x : v) cin >> x; }

int aaGayaCodeDekhne()
{
    int n;
    cin >> n;
    vi arr(n);
    in(arr);

    auto func = [&](int i, int j) -> int
    {
        int s = j + 1, e = n - 1;
        int ans = 0;
        while (s <= e)
        {
            int mid = s + (e - s) / 2;
            if ((arr[mid] + arr[i] + arr[j]) > max(2 * arr[mid], arr[n - 1]))
            {
                ans = mid - j;
                s = mid + 1;
            }
            else
                e = mid - 1;
        }
        return ans;
    };

    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            ans += func(i, j);

    cout << ans << endl;

    return 0;
}

int32_t main()
{
    int t = 1;
    cin >> t;
    while (t--)
        aaGayaCodeDekhne();

    return 0;
}

/*
1
11
27 32 35 37 45 57 65 65 71 87 96

123 - my
125 - correct
*/

For problem c, here is the two pointer implementation

def solve(a):
    count = 0
    for i in range(2, len(a)):
        l, r = 0, i - 1
        while l < r:
            if a[l] + a[r] + a[i] <= a[-1] or a[l] + a[r] <= a[i]:
                l += 1
            else:
                count += r - l
                r -= 1

    return count

My solution for C iterate to each i and j. Let a = arr[i] ,b = arr[j],sum = a + b Now for the third elements will be between j+1 and the last element.

So now the third element (let it be c) should meet these conditions — a + b + c > arr[n-1] and a + b > c We can find these ranges with the help of lower bound and upper bound. And by taking the intersection for each case, we add to the answer variable to get the answer. Time complexity = (n2logn)