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

Pretests of C are horribly bad.

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

Example code: https://codeforces.net/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.

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.net/contest/1899/submission/233223051

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.net/contest/1899/submission/233233780

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.net/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' ?

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.

F was very easy: my code is more simple than authors.
https://codeforces.net/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.

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.net/contest/1899/submission/233145738

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

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

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

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.net/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.net/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.net/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

can someone help me with the problem statement B? I tried a lot but couldnt find the error in my code... link to my submission:https://codeforces.net/contest/1899/submission/235506545

for anyone who is getting TLE on test case 37,use int instead of long long

Hello, would be good if someone could explain to me why my solution is getting MLE and what can be done to solve it! Thank you!

I have 2 main iterations

https://codeforces.net/contest/1899/submission/236010009

(This one I believe is due to the fact that I stored every single permutation so I switched it to a more brute force implementation below)

https://codeforces.net/contest/1899/submission/236019332

(This I am not sure why I will have a MLE)

Edit: I had a bug in my code, ignore thank you!

https://codeforces.net/contest/1899/submission/236063262

This one is accepted

https://codeforces.net/contest/1899/submission/236061994

This one gives a tle.

Both the codes are same just in the accepted one, 1 value of dictionary is initialized. Time complexity is same anyways. Can anyone figure out why is it happening ?

Can anyone please me the problem with my solution to problem C.I have used a two pointer approach. My solution

Can someone explain in problem G that, if we found some number of nodes with In timers within the range of T[IN],T[OUT] of x, then it assumes that the end Timers will be definitely less than T[OUT]. Can someone explain how ?

1899F — Alex's whims problem can be done in O(q) time,

Every day we just need d distance between any two nodes so we will first make the tree by connecting the vertices adjacent to each other, then we can just attach the nth node to the dth node this will give distance d; for ex:- for n = 5

then for d = 3, we will attach 5 to 3

1 - 2 - 3 - 4
        |
        5

so distance between 1 and 3 becomes 3

here is the submission link:- https://codeforces.net/contest/1899/submission/240359161

F can be solved in only O(n+q) by this solution . Given editorial is overkill for the solution.

From a functional perspective, understanding problem B becomes easier. We have $$$(2^a)^{(2^b)} = (2^b)^{(2^a)} \iff \frac {2^b}{b} = \frac{2^a}{a}$$$. Let $$$f(x) = \frac{2^x}{x}$$$. Clearly, when $$$a = b$$$, the equation holds true. When $$$a \neq b$$$, observing the function's graph, we find that the equation holds only when $$$x_0 = 1$$$ and $$$x_1 = 2$$$

Simple solution of Game with integers in Python.

def foo(): n = int(input()) count = 1 while count!= 11: if count % 2 == 1 and ((n+1)%3 == 0 or (n-1) % 3 == 0): return 'First' # elif count % 2 == 0 and count += 1 return 'Second'

if name == '__main__': t = int(input()) for _ in range(t): print(foo())

in 1899B , wouldn't the complexity be n*sqrt(n), instead of n*cuberoot(n)?

I have a solution with O(n+q) for Problem F. Solution

F is actually an easy problem but the problem statement is too difficult to read. It is only asking if we can form a distance d, 2<=d<=n-1 between two LEAVES. We construct a degenerate tree, which has exactly two leaves (let's index them 1 to n), then we can reconnect 1st or nth to any vertex to get distance d. (ex: moventh to (d+1)th vertex)

For G question, I found an easy approach of using dfs + minimum Segment tree. You can check out here, https://codeforces.net/contest/1899/submission/257742336 I got this intution because we need minimum intime of node from l to r, which have intime greater than intime of x and smaller than outime of x.

1899A should have mentioned that the first player has to play at least one turn. -_-

in prob B , why putting mn = 0 and mx = 0 wrong?? and why ew should put 1e18?

.

An easier way to understand and implement F,

https://codeforces.net/contest/1899/submission/266170220

Why is this not used in the main editorial?

what about the 10 moves constraint in the test case where n =1000

F can be solved in O(n+q). First make a linear graph and keep shifting the last vertex so that the distance between the last vertex and vertex 1 is equal to d.

My Submission: https://codeforces.net/contest/1899/submission/280523159