Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

molney's blog

Разбор Codeforces Round 909 (Div. 3)
By molney, 11 days ago, translation, In English

1899A — Game with Integers

Idea: EJIC_B_KEDAX, development: EJIC_B_KEDAX.

Editorial
Solution

1899B — 250 Thousand Tons of TNT

Idea: zwezdinv, development: zwezdinv.

Editorial
Solution

1899C — Yarik and Array

Idea: meowcneil, development: meowcneil.

Editorial
Solution

1899D — Yarik and Musical Notes

Idea: zwezdinv, development: molney.

Editorial
Solution

1899E — Queue Sort

Idea: Vladosiya, development: Vladosiya.

Editorial
Solution

1899F — Alex's whims

Idea: EJIC_B_KEDAX, development: EJIC_B_KEDAX, zwezdinv.

Editorial
Solution

1899G — Unusual Entertainment

Idea: EJIC_B_KEDAX, development: Sokol080808.

Editorial
Solution
  • Vote: I like it
  • +61
  • Vote: I do not like it

»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Will there be a English editorial?

→ Reply
»
11 days ago, # |
  Vote: I like it -43 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think maybe it's about the problem statements

    → Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After not being able to implement B, i just tried C and didn't even bother to read D. But after this comment i read E and yupp ... this the correct order of difficulty mentioned by you.

    → Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nope i dont think so C was the most easiest one just apply sliding window

    → Reply
»
11 days ago, # |
  Vote: I like it +20 Vote: I do not like it

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?

→ Reply
»
11 days ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Initially, you have to assume any tree of n vertices. Then, there are q queries. Query is: You have given distance x, if the distance between any two leaf nodes equals x, then do nothing. If it is not then you have to make a change in the tree (only one operation).

    The operation is like this — choose any three vertices u, v1, v2 such that there is edge b/w u and v1 and there is no edge b/w u and v2. Then, remove edge b/w u and v1 and add edge b/w u and v2.

    → Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like 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

→ Reply
»
11 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Video solution for the Chinese：

BiliBili

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Uh actually the wrong answer you're getting is for the case when D = 4 (Q = 4). According to your construction Tree at Q = 4 (1-2-3-5 & 2-4) here D is not 4. You make a change instead of -1 -1 -1 to preserve the answer for the upcoming query.

    → Reply
»
11 days ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

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.

→ Reply
»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    segment tree working and i guess it cannot be solved by fenwik but i am not sure

    → Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    Persistent segment trees

    → Reply
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      your solutions are way simpler to understand thanks a lot! curious whats your real handle?

      → Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Merge Sort Tree, Persistent Segment Tree or Wavelet Tree

    → Reply
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it +57 Vote: I do not like it

      std::set is enough if you use small-to-large merge.

      → Reply
      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I believe array is enough if you use Mo's on trees (we can use block technique for turning on and off). I solved it using small_to_large and segment_tree during contest tho.

        → Reply
      • »
        »
        »
        »
        11 days ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Can you tell why my solution is not giving MLE 233219342 when I am trying to store indices in the subtree of current node in a set for all the nodes.

        Check in the merge function.Isn't the memory consumed is O(n^2) I am new to this method. Can you explain ?

        → Reply
        • »
          »
          »
          »
          »
          11 days ago, # ^ |
          ← Rev. 3   Vote: I like it +8 Vote: I do not like it

          Every element is copied only $$$O(\log n)$$$ times, so every element can appear in at most $$$O(\log n)$$$ sets. Thus, the memory is $$$O(n \log n)$$$.

          This is the same argument as for why the time complexity is $$$O(n \log n \cdot (\text{time of a single insertion})) = O(n \log^2 n)$$$.

          → Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any point-update-range-sum data structure

    → Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I used the Euler tour technique along with a minimum segment tree: you can check my submission here.

    → Reply
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sqrt decompositon

    → Reply
»
11 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Thank you so much!

→ Reply
»
11 days ago, # |
  Vote: I like it +20 Vote: I do not like it

G can be solved with small to large too

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    take mini to be LLong_max or 1e18 something otherwise it overflows

    → Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Since the exponential function is strictly increasing, the equation 2^x = 2^y is equivalent to x = y.

    → Reply
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      okay i get it now, but for the last part, shouldn't we get: 1/(2^k) = 1/(2^(a(1-2^k))) rather than: 1/(2^k) = 1/(2^(a(2^k-1))) ?

      → Reply
      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, because

        $$$\displaystyle\frac{2^a}{2^{a\cdot2^k}}$$$

        $$$\displaystyle=\frac{2^a}{2^{a\cdot2^k-a+a}}$$$

        $$$\displaystyle=\frac{2^a}{2^{(a\cdot2^k-a)+a}}$$$

        $$$\displaystyle=\frac{2^a}{2^{(a\cdot2^k-a)}\cdot2^a}$$$

        $$$\displaystyle=\frac{1}{2^{a\cdot2^k-a}}$$$

        $$$\displaystyle=\frac{1}{2^{a(2^k-1)}}$$$

        → Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's define x = a * 2 ^ b and y = b * 2 ^ a.

    We know that 2 ^ x = 2 ^ y, so x = y <=> a * 2 ^ b = b * 2 ^ a, which is what you asked for.

    I hope that you understand!

    → Reply
  • »
    »
    11 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    apply log2 to both sides you get :

    log(a)+ b*log(2) = log(b) + a*log(2)

    hence

    b — log(b) = a — log(a)

    this only occurs when 1,2 or when a=b

    → Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    take log base 2 of both sides, then you will get the expression

    → Reply
»
11 days ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it +23 Vote: I do not like it

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.

→ Reply
»
11 days ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

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).

Visualization
Code
→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hey can you explain why the code still works if we remove the condition 

    if (x == cur)
{
    cout << "-1 -1 -1\n";
    continue;
}

    because in the question it mentions for u v1 v2 there should be an edge between u and v1 and no edge between u and v2 but for the above case v1 and v2 are same and there is definitely an edge between u and v2 so shouldn't the code be wrong. Here is my submission:

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

    → Reply
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Testcases are weak I guess

      → Reply
      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        even then the answer where v1 and v2 are same shouldn't be accepted as correct because it is mentioned in the question

        → Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solved using the same exact idea.

    → Reply
»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
11 days ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Easy sqrt-decomposition online solution of G: 233217422

→ Reply
»
11 days ago, # |
  Vote: I like it +31 Vote: I do not like it

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$$$.

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That is not actually you who does the rephrase of problem, which is actually a problem solving skill. Chat-GPT does it for you. I do not do this because I have work ethics

    → Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe because each and every detail is very important and chatgpt might morph a detail.

    → Reply
»
11 days ago, # |
  Vote: I like it +38 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Contest unrated? rank not updated

→ Reply
»
11 days ago, # |
  Vote: I like it +4 Vote: I do not like it

easiest A-F lol

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B. can anyone explain why my code fails.

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

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try put 1e18 instead of INT_MAX and put 0 instead of INT_MIN

    → Reply
  • »
    »
    11 days ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Bcoz ai<=10^9 ..and if u take sum of any subarray of some length lets say K then you can easily see it will become greater than intmax. Hence u had to take llong

    → Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    since the whole array can be 1e9, n > 3 can lead to sum overflow

    → Reply
»
11 days ago, # |
  Vote: I like it +5 Vote: I do not like it

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

Spoiler

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

Code
→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same thing, and as far as I can see, the solution is completely right. They must've made the constraints low to troll participants.

    → Reply
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I literally saw the problem in last 4-5 mins and thought of this solution but I somehow convinced myself I'm wrong (Read: low confidence) and spent the time in understanding the problem statement of B (which also I failed).

      Anyway, great performance avighnakc, Congratulations on reaching Expert!!

      How did u get this good so quick? Did u practice a lot of $$$C, D$$$ of Div.2s or is it something else?

      → Reply
      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I did CSES, practiced quite a lot of codeforces div2B’s and C’s and also 1500-1600 rated problems, and up solved some ABCs. Honestly, it’s all about how much effort you put in. I’m not that special per-se, if you grind as much as me, you’ll also improve fast. Good luck, and thanks!

        → Reply
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      The constraints are low because to check if the solution is correct or not the checker needs O(n^2q) operations minimum. If the constraints were too large it would have taken ages to check each test case.

      → Reply
»
11 days ago, # |
  Vote: I like it +10 Vote: I do not like it

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?

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain 'F' ?

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yeah sure, here I have used the pointer approach. So, initially, we will consider the tree to be like a long stick. So all the nodes will lie in a straight line. Now, We will only move the end node and no other node and this will solve our problem easily. So initially we have the tree something like 1->2->3->4->5->6->7. So in this case we will only move the 7th node. Now, we know that 7 is connected to 6 initially so the dist between 1 and 7 will be 6. If 7 is connected to 3 then the dist between 1 and 7 will be. So, wherever the 7th node will be connected the dist will be equal to that node itself. Check this implementation now, or see my last submission.

    void solve(int xx){ int n, q; cin>>n>>q; rep(i,2,n+1)cout<<i-1<<" "<<i<<endl;

    int pnt = n-1;
rep(i,0,q){
    int x I;
    if(x!=pnt){
        cout<<n<<" "<<pnt<<" "<<x<<endl;
        pnt = x;
    }else{
        cout<<"-1 -1 -1"<<endl;
    }
}

    }

    → Reply
»
11 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 days ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    I mean, honestly, you didn't need to observe that (1,2) are the only solutions. You could just observe that since $$$(2^a)^(2^b) = (2^b)^(2^a) => \frac{2^a}{a} = \frac{2^b}{b}$$$, you can store the values of $$$\frac{2^a_i}{a_i}$$$ in a map and count that way.

    → Reply
    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yes, you are right! That makes absolute sense and is a much simpler way to solve this. Even in my original solution, I did not observe that (1,2) is the only solution, instead came up with a way to efficiently find all possible solutions using sorting and two pointers(based on the growth rate of exponents), Although I kept getting WA due to integer overflow(facepalm).

      But I feel that without this observation we end up doing more computation than is required(even though asymptotically it is the same) so I just wanted to wrap my head around it.

      → Reply
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But how you will store $$$2_i^a$$$ when a becomes 1e9

      → Reply
      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Check my submission, you can just store the exponent and divide out all factors of 2 from $$$a_i$$$.

        → Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
10 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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;
        }
    }
→ Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    1. std::unordered_map is not $$$O(n \log n)$$$. It's $$$O(n)$$$ on average, and $$$O(n^2)$$$ with many hash collisions. std::map is guranteed $$$O(n \log n)$$$.
    2. In Div.3, all tests from the authors are included during the contest. In system testing the only new tests are tests from sucxesful hacks. This test wasn't included by the authors, it was a hack test.
    → Reply
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am still shocked why so many people (including author) have used map for this question. I agree it is my fault for not using custom hash function for unordered_map but what is the point of using map when it is slower than unordered_map on average?

      → Reply
      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why does it matter that std::unordered_map is faster on average, if it has a slower worst case performance?

        People use std::map more often than std::unordered_map because hacks against std::unordered_map are very common on codeforces. If you use std::map, you cannot get hacked with those types of hacks. You should read this blog for a more in-depth explanation of this. That blog also contains a way you can still use std::unordered_map and not get hacked.

        Also, std::unordered_map isn't even that much faster on average. Even though it is $$$O(1)$$$ per operation and std::map is $$$O(\log n)$$$ per operation, std::unordered_map has a massive constant factor which makes it almost as slow as std::map, even on average (unlike for example arrays, which are also $$$O(1)$$$ per operation but they are much much faster).

        → Reply
        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for the info ^_^

          Friendship ended with unordered_map, now map is my best friend!

          → Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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...?

→ Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Someone hacked the solution that uses unordered_map :(

    Read this blog for more info https://codeforces.com/blog/entry/62393

    → Reply
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah read this... Feel like when you're at the point where you need to create your own hash function because the tests cases are designed such that standard library hashing function is going to fail, it's not really CP anymore and just tedious knowledge requisite... If my solution is O(n), it should pass....

      Thanks for the link !

      → Reply
      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        You're right. $$$O(n)$$$ solutions should (and do) pass. But your solution is $$$O(n^2)$$$, unfortunately.

        → Reply
        • »
          »
          »
          »
          »
          10 days ago, # ^ |
          ← Rev. 2   Vote: I like it -16 Vote: I do not like it

          I mean, if the hill you want to die on is that hashmap insertion is O(n), more power to you, but I believe, that pretty much everyone would say that hashmap insertion is O(1) (invite you to read about amortized operation ; are vector insertion O(n)?). Like if the goal is for hashmap to be unusable in the contests, we should just say so somewhere. No amount of pseudo-randomness is going to be enough if I really want to come up with an example which will destroy your hash function.

          Oh well, just another reason why python is just better than c++, shoulda known better !

          Also, just to be clear, no O(n) solutions exists for the problem from your point of view, so no, they don't pass !

          → Reply
          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I mean, if the hill you want to die on is that hashmap insertion is O(n), more power to you, but I believe, that pretty much everyone would say that hashmap insertion is O(1) (invite you to read about amortized operation ; are vector insertion O(n)?)

            Hashmap insertions are $$$O(1)$$$ on average with random data, they aren't $$$O(1)$$$ amortized. If some operation is $$$O(1)$$$ amortized, even if a single operation can be $$$O(n)$$$ in the worst case, it is guranteed that $$$n$$$ such operations will work in $$$O(n)$$$ total time. But with many hash collisions $$$n$$$ hashmap insertions with a bad hash work in $$$O(n^2)$$$ $$$\Rightarrow$$$ not amortized $$$O(1)$$$.

            Like if the goal is for hashmap to be unusable in the contests, we should just say so somewhere.

            In my opinion it's a feature of the language, and the participant is responsible for understanding how their language works.

            No amount of pseudo-randomness is going to be enough if I really want to come up with an example which will destroy your hash function.

            Maybe it won't prevent it, but it will definitely slow down the creation of such hack test cases. And how are you going to deal with time-initialized randomness when creating those hacks?

            Oh well, just another reason why python is just better than c++, shoulda known better !

            Python sictonaries can also be hacked similarly (at least in PyPy), see this. And if python is supposedly better, why so you even use c++?

            Also, just to be clear, no O(n) solutions exists for the problem from your point of view, so no, they don't pass !

            $$$O(n)$$$ solutions do exist, like the hashmap solution with a randomized (and time-initialized) hash function, which can't be hacked. Or can you prove me wrong by providing a hack to the custom hash in the blog linked in the original reply?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              You're right about amortized, I was just making an analogy (poorly written I'll admit) to how you could make the same argument for amortized operations, the point being that talking about worst case is (in some cases, and in my opinion) non-nonsensical. I don't think anyone would call n insertions in a vector O(n^2), even if worse case is O(n), because we know it's O(1) amortized (which while not the same as average, is comparable).

              In my opinion it's a feature of the language, and the participant is responsible for understanding how their language works.

              What's the point to that though...? All this ends up doing is that everyone has to put some pseudo-random implementation in their template and then not think about it ever again. It's not about learning how the language work or anything deep, it's literally just another implementation of something that is in the standard library...

              O(n) solutions do exist, like the hashmap solution with a randomized (and time-initialized) hash function, which can't be hacked. Or can you prove me wrong by providing a hack to the custom hash in the blog linked in the original reply?

              Give me an implementation, an infinite amount of time and I will eventually find a test case which, at a particular time, will make you TLE. The complexity of your solution does not change because finding such a test case is harder, which is what I'm arguing against. Hashmap always will have that O(n) worst case, you can't change that no matter the implementation. Even worse ; a pseudo-random implementation makes it so that the same exact code that passed a problem super easily could TLE in another time, you're just gambling. To me, it's not a super interesting problem to solve, so either we should just say somewhere that hashmaps are not to be used ever, or we realise that hacking standard library implementation of hashmap is not really pertinent to the task of solving the problem...

              → Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it 

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

→ Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.$$$"$$$

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
9 days ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry for my comment ...i was not considering abs() ...ignore my comment.

    → Reply
    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, unfortunately negative modulo in cpp is weird

      → Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

F but simpler 233608256

→ Reply
»
7 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

During practice, I submitted this solution for problem F.

My Code

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

→ Reply
  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes, i did it exactly in the same way.

    → Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply