Will there be a English editorial?

time of contest was so fu....g less than the time it should be

non of problems was that intresting and you can see that in the comments of announcement and there was no hard algorithm problem and i think in problem C you should say that what is a subarray problem F statement wasnt clear at all

E was too easy for an E. In my opinion, D > C > B > E > A in decreasing order of difficulty.

Pretests of C are horribly bad.

So many contestant has 0 if all of the array is negative.

Example code: https://codeforces.com/contest/1899/submission/233111911

Sample Input for Hack:

1

3

-3 -1 -1

NOTE: I am not writing this comment to bury authors (because it has really good problems and it can be best Div. 3 I have ever seen.) but I think how random case generator don't produce this example, it seems really interesting?

don't understand this part -> Since k is a divisor of n , there are O(n−−√3) such k is there a proof?

Can someone explain what problem F is asking? Can't comprehend it =(

Explain what is wrong with my solution 233204396, problem D. I count the number of different numbers, using this information I calculate the number of pairs of identical numbers and pairs from (1, 2), add them up, get WA on the 11th test

Video solution for the Chinese：

BiliBili

Problem F, on example,2nd test case, in the third query already exist a path with distances 3 between 2 leafs , 5-4-2-3, but the answer wasn't -1 -1 -1.I'm receiving WA veredict for that?233191318

Problem G can be solved offline in O(nlogn + qlogn). answer queries in decreasing order of entry time of x. Add the exit time of each vertex v in the corresponding position in the permutation when we process the first query such that tin[x] <= tin[v] In this way, we can guarantee that we've only added vertices that have greater entry time than current x. So we can query for the minimum on segment.

Nice problemset. B was tough for me to understand :(

Bad problem state b and d! Also don’t like any of 1st 5 problems. Although it was fun to participate. Best luck for me and also for the problem setter. Plz try to explain some of the test cases.

Which data structure do I need to know to solve G?

Thank you so much!

G can be solved with small to large too

Can someone tell me why this code for problem B is not working

hash-table(for e.g., std::unordered_map in C++) can help to solve problem D with O(n) complexity, but, of course, O(nlogn) is enough to get OK

Problem b: 2^(a⋅2^b)=2^(b⋅2^a)⇔a⋅2^b=b⋅2^a how did we get the second part from the first part?

F can be solved with an easy O(n) solution

E and F both were extremely easy if you consider the given Testcases gave away the entire solution process

G can be solved using a normal segment tree or a Fenwick tree by offline query.   First, let's solve this the other way around. You don't have to find a descendant; you have to find an ancestor.

1. You can just DFS and keep adding each node to the segment tree or Fenwick tree as you traverse.
2. Once you reach node 'u', you check all queries and find the sum between [l, r] for each query.
3. Remove the node once the whole iteration is done.

Now here, the sum initially doesn't change when you return because we remove the sum for all the children in step 3 before again reaching node 'U'. So we will remove step 3, and to make sure for each query we received any descendant, we will store the initial sum (number of nodes between L and R), and after we iterate all the children for node 'U', we recheck the count, and if there is any descendant, our sum will increase.

Submission Here

You can check code if don't understand the explaination.

G can be solved using a normal segment tree or a Fenwick tree by offline query.   First, let's solve this the other way around. You don't have to find a descendant; you have to find an ancestor.

1. You can just DFS and keep adding each node to the segment tree or Fenwick tree as you traverse.
2. Once you reach node 'u', you check all queries and find the sum between [l, r] for each query.
3. Remove the node once the whole iteration is done.

Now here, the sum initially doesn't change when you return because we remove the sum for all the children in step 3 before again reaching node 'U'. So we will remove step 3, and to make sure for each query we received any descendant, we will store the initial sum (number of nodes between L and R), and after we iterate all the children for node 'U', we recheck the count, and if there is any descendant, our sum will increase.

Check Code Here

You can check code if you don't understand explaination.

For F, you can just connect the first $$$n-1$$$ as a sequence tree and keep the $$$nth$$$ node away. For each query you can just connect the $$$nth$$$ node to the $$$d_i$$$ and the distance will be $$$d_i$$$ from node $$$1$$$ (node 1 is a leaf node).

    int n, q;
    cin >> n >> q;
    for (int i = 1; i < n - 1; i++)
    {
        cout << i << " " << i + 1 << "\n";
    }
    cout << "2 " << n << "\n";
    int cur = 2;
    for (int i = 0; i < q; i++)
    {
        int x;
        cin >> x;
        if (x == cur)
        {
            cout << "-1 -1 -1\n";
            continue;
        }
        cout << n << " " << cur << " " << x << "\n";
        cur = x;
    }

for D, Put the equation $$$\left(2^{x}\right)^{2^{y}}=\left(2^{y}\right)^{2^{x}}$$$ in a graphing calculator the graph directly shows x=y and (1,2),(2,1) . Then write code.

Why were the problem statements so vague? is this the first time that they are organizing a contest?

Easy sqrt-decomposition online solution of G: 233217422

For problem D, there is a simpler proof, without much symbolic manipulation.
We know that $$$2^a \cdot b = 2^b \cdot a$$$.
Write that as $$$2^a / a = 2^b / b$$$.
The function $$$2^x / x$$$ is increasing for $$$x > 2$$$.
So, the equality can not hold for any numbers greater than $$$2$$$.

Why don't you guys just rephrase the problem statements using chatgpt? The prompts were actually painful to understand.

Editorial has such a strange solution for F. You can just make a tree which is a straight line from $$$1$$$ to $$$n-1$$$ and attach vertex $$$n$$$ to vertex $$$d_i$$$ for all queries. Both vertex $$$1$$$ and $$$n$$$ are leaves and distance of $$$1$$$ from $$$n$$$ is $$$d_i$$$. Complexity $$$O(n)$$$.

https://codeforces.com/contest/1899/submission/233223051

B problem editorial not clear for me. Is it slower to find all divisors of n, and iterate over them than ignore it and just iterate over all possible k? I am sorry I am missing something in editorial although I solved it right after contest. I can't find how O(n⋅n−−√3) compares to O(nlogn) asymptotically.

Contest unrated? rank not updated

easiest A-F lol

F: At the beginning, let the tree be a chain, with the edge of (n-1) ->(n) constantly moving. It would be easy to set the distance between 1->x as d. https://codeforces.com/contest/1899/submission/233233780

More simpler solution to F is by just maintaining the last node we connected our nth node to https://codeforces.com/contest/1899/submission/233238323

A more simpler solution to F by just maintaining the last node we connected the nth node to- https://codeforces.com/contest/1899/submission/233238323

Problem B. can anyone explain why my code fails.

solution link: https://codeforces.com/contest/1899/submission/233239115

For b problem, how did yall find out we gotta use long long instead of int?

Problem 1899F - Alex's whims can be solved easier like this:

Is there a counter to this method? Was quite surprised to see such small constraints.

void solve(){
    int n, q; cin >> n >> q;
    for(int i = 1; i < n; i++){
        cout << i << " " << i + 1 << endl;
    }
    int x = n - 1;
    for(int i = 0; i < q; i++){
        int d; cin >> d;
        if(d == x){cout << "-1 -1 -1\n"; continue;}
        cout << n << " " << x << " " << d << endl;
        x = d;
    }
}

For problem F many have written the condition where last_node == current_node and printed -1 -1 -1 in that case but my code where i have commented the same condition is also accepted.

Submission link: https://codeforces.com/contest/1899/submission/233250281

But it shouldn't as the question mentioned for every u v1 v2 there should be an edge between u and v1 and no edge between u and v2. but my code outputs the same v1 and v2 for some cases and is still accepted. Am I missing something or the question was phrased slightly incorrectly?

Can someone explain 'F' ?

Can someone explain 'F' ?

I'm wondering if the successful hacking attempt goes into the final test data. I wrote a brute force dfs in G, which only works when the data is given randomly, it passed pretests, but I think it's easy to hack when the give tree is a chain. I don't know why it passes the hack.

Didn't realise that F was an easy problem....

F was very easy: my code is more simple than authors.
https://codeforces.com/contest/1899/submission/233117295

There is a simpler solution for F: 233147982. Plus G is solvable with just std::set + small-to-large technique by storing inverse indexes and lower-bounding the left bound of a desired segment.

Why is my submission 233141859 timing out? I've used an unordered_map to solve it in O(n).

Problem G can be solved offline in $$$O((n+q)*log(n))$$$. First, push back all queries for node x into a vector. Then just DFS and for each node, you store its descendants' pos in array $$$p[]$$$ in a set. You can merge all sets of its children faster by swapping 2 sets to put all elements of the smaller set into the bigger one. In that way, you can answer all queries $$$[l,r,id]$$$ of x by using $$$lower bound$$$ to check that is there any element in the set sitting between l and r, and update the answer for the id-th query.

This is my submission: 233162558

For those who feel(like me) that the observations in problem D are hard to make analytically(and at the same time be sure that no edge case was missed), we can use high school calculus to solve this in a more structured and generalized format, which may be useful in some other questions-

After you get the equation a⋅2^b=b⋅2^a, rewrite it as (a.2^-a)=(b.2^-b). This holds when a=b. Furthermore, we ask, "For what distinct integral values of x is f(x)=x.2^-x equal to itself?" We can see this by making a rough plot of f(x). There is only one critical point(x=(1/ln2)~1.4), which is a maximum (we can easily observe this using just the first derivative). So the curve looks like a bell, strictly increasing before 1, peaking between 1 and 2, and strictly decreasing thereafter.

The equality cannot hold on either side of the peak since we have a strict ordering. Therefore the only possible equality is if f(1) matches with some x>=2. Now we can either find that this holds for x=2 by trial and error, or more rigorously...wait for it...binary search. Search on the strictly decreasing array for f(i) i>=2 for the value of f(1), to get x=2. Then we can count the occurrences using standard techniques.

why long long lmax = LONG_MIN, lmin = LONG_MAX; this line gives wrong answer why this one gives right answer? long long lmax = -1e18, lmin = 1e18; why?

I was trying to solve 1899G with a different approach, but getting MLE.

For each node x, I'm keeping track of all nodes in the subtree rooted at x, but I'm not actually storing the child nodes directly, but rather their index in P. i.e if nodes 2,4 are in the subtree rooted at 3, I store mem[3]={idx[2],idx[4]} where idx is the index of 2 in P ( in sorted order ).

Then I can run Q(l,r,x), in mem[x] in log(n) time.

T(n) = O(nlogn) S(n) = O(n*n) — MLE

when I see the solution, even in the ST, for each segment we are storing an array of start times, even that would have a S(n) = O(n*n). how does it not give MLE?

For problem F, Can's I just maintain a chain and keep moving the last node to the dth node?

    int T; cin >> T;
    rep(t, 0, T) {
        int n, q; cin >> n >> q;
        rep(i, 1, n) cout << i << ' ' << i + 1 << '\n';
        int pre = n-1;
        // we keep modify the last node of the tree
        rep(_, 0, q) {
            int d; cin >> d;
            cout << n << ' ' << pre << ' ' << d << '\n';
            pre = d;
        }
    }

Why is O(NlogN) solution of D giving TLE in C++? LMAO Just checked that map is getting accepted but not unordered_map! WTH??? Someone tell the author that this isn't Div1. Also, if they wanted to use such tricks then at least they could have included these test cases during the contest. https://codeforces.com/contest/1899/submission/233145738

New to CPP ; anyone could give reason as to why I'm getting TLE on problem D : https://codeforces.com/contest/1899/submission/233162158

When I would easily be able to solve this in python, and it's O(N) normally...?

void solve()
{
    int n,q; cin >> n >> q;

    for(int i = 2 ; i <= n ; i++){
        cout << i-1 << " " << i << endl;
    }

    int currDistance = n - 1;
    int node2 = n;
    int node1 = n - 1;

    while(q--){
        int distance ; cin >> distance;
        if(distance == currDistance){
            cout << "-1 -1 -1" << endl;
            continue;
        }
        cout << node2 << " " << node1 << " ";
        node1 = distance;
        cout << node1 << endl;
        currDistance = distance;
    }
}

O(n + q) Solution for F 233329854

Did anyone solve Codeforces Round 909 (Div. 3) G with Treap?

It can be solved by it according to this USACO Guide article on Small-To-Large Merging :

$$$"$$$It's easy to merge two sets of sizes $$$n\ge m$$$ in $$$\mathcal{O}(n+m)$$$ or $$$(m\log n)$$$ time, but sometimes $$$O\left(m\log \left(1+\frac{n}{m}\right)\right)$$$ can be significantly better than both of these. Check "Advanced — Treaps" for more details.$$$"$$$

If anyone got TLE (like me) in the problem 1899D - Yarik and Musical Notes, maybe look at this blog post about unordered_map.

Why at problem D solution with unordered map get TLE and that with map dosent

Why are we performing lower_bound — lower_bound instead of upper_bound — lower_bound, given that in the instance where we have an entry time of 1,2,3 in the merge sort tree and our time in and time out of x is 2, then wouldnt lower_bound — lower_bound return 0 instead of returning 1?

In problem C while checking the parity of two consecutive numbers in array ~~~~~ int res = a[0]; int ans = a[0];

for (int j = 0, i = 1; i < n; i++, j++) { if (res < 0) res = 0; if ( (a[j] % 2) == (a[i] % 2) ) res = a[i]; else res = res + a[i]; ans = max(ans, res); } cout << ans << "\n"; ~~~~~

int res = a[0];
int ans = a[0];

for (int i = 1; i < n; i++)
{
     if (res < 0) res = 0;
     if ( (a[i] & 1) == (a[i - 1] & 1) ) res = a[i];
     else res = res + a[i];
ans = max(ans, res);
        }

        cout << ans << "\n";

In problem C while checking the parity of two consecutive numbers first code is accepted and second code is causing error just because i use % operator for checking parity in "if" why is it so?

First code (Accepted)

int res = a[0];
int ans = a[0];

for (int i = 1; i < n; i++)
{
     if (res < 0) res = 0;
     if ( (a[i] & 1) == (a[i-1] & 1) ) res = a[i];
     else res = res + a[i];
     ans = max(ans, res);
}
cout << ans << "\n";

Second Code (Causing error for testcase n=3 101, -99, 101 it outputs 103 but it should 101)

int res = a[0];
int ans = a[0];

for (int j = 0, i = 1; i < n; i++, j++)
{
     if (res < 0) res = 0;
     if ( (a[j] % 2) == (a[i] % 2) ) res = a[i];
     else res = res + a[i];
     ans = max(ans, res);
}
cout << ans << "\n";

the difference in both piece of code is... below line...

if ( (a[i] & 1) == (a[i-1] & 1) ) res = a[i];
if ( (a[j] % 2) == (a[i] % 2) ) res = a[i];

Please help... why don't the second code just assing the value to variable 'res' in 'if' ?

Accepted code link 233406392

Error code link 233406621

Будет что почитать сегодня

Can anyone tell me the pre requisites for the last question along with similar questions like this?

Can someone tell the pre requisites for the last problem? Also does anyone have similar problems like that

F but simpler 233608256

During practice, I submitted this solution for problem F.

void TATAKAE()
{
    int n, q;
    cin >> n >> q;
    int last = n — 1;
    for (int i = 1; i <= n &mdash; 1; i++)
    {
        cout << i << ' ' << i + 1 << '\n';
    }
    while (q--)
    {
        int d;
        cin >> d;
        if (last == d)
            cout << -1 << ' ' << -1 << ' ' << -1 << '\n';
        else
            cout << n << ' ' << last << ' ' << d << '\n';
        last = d;
    }
}

It got accepted and is much simpler than the editorial's solution and its time complexity is O(q). Submission link: https://codeforces.com/contest/1899/submission/233759099

Linear O(n + q) solution of problem F 233781812

Linear / O(n + q) solution of problem F 233781812

i have a doubt plz can anyone help !!!

D). Yarik and Musical Notes

this is my code below and it is giving TLE but when i use map instead of unordered_map it accepted ,why???? :-

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{  
   int t;
   cin>>t;
   while(t--){
            int n;
            cin>>n;
            int arr[n];
            unordered_map<ll,ll> m;
            for (int i = 0; i < n; ++i) cin>>arr[i];
            for (int i = 0; i < n; ++i) m[arr[i]]++;
            ll ans=0;
            for(auto i : m) ans += (i.second*(i.second-1))/2;
            ans += m[2]*m[1]; 
            cout<<ans<<endl;

   }  
   return 0;
}

мне нравится название 2 задачи :)

Can someone explain me why printf is printing zeroes ? this is submission for Alex's whims problem F

https://codeforces.com/contest/1899/submission/234314307

I changed printf to cout and it got accepted, do I need to select a specific compiler while submitting code containing printf because it worked find on my personal computer

D wasa bit time consuming to process, but it was definitely doable!!

Problem D Why does this solution give a TLE on test case 21 even after it being an O(n) solution ? https://codeforces.com/contest/1899/submission/234901875

Problem D: I got tle on test case 21 ......Can anyone tell me why??? int n; cin >> n;

unordered_map<int,int>mp;

for (int i = 0; i < n; ++i) { int x; cin >> x; mp[x]++; }

LL ans = 0;

for(auto &val: mp){ int x = val.second; if(x > 1) { ans += 1ll* x * (x-1) / 2; } }

if(mp[1] > 0 and mp[2] > 0) ans += (1LL * mp[1]*mp[2]);

cout << ans << '\n';

}

How can you get -1 in E? Can't it always be sorted. Can't understand editorial