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

### molney's blog

By molney, 11 days ago, translation, 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

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 Tutorial of Codeforces Round 909 (Div. 3) Comments (148)
 » Will there be a English editorial?
•  » » Added, thank you for the noticing
 » 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
•  » » Cope with it
 » E was too easy for an E. In my opinion, D > C > B > E > A in decreasing order of difficulty.
•  » » I think maybe it's about the problem statements
•  » » 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.
•  » » Nope i dont think so C was the most easiest one just apply sliding window
 » Pretests of C are horribly bad.So many contestant has 0 if all of the array is negative. Sample Input for Hack: 1 3-3 -1 -1NOTE: 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?
•  » » I think it's a typo, he meant to say sqrt not cbrt?
•  » » I don't know how to prove it mathematically, but it's true for n <= 10^9. I found it in this post: https://codeforces.com/blog/entry/651?locale=ru
•  » » » Wow! how did you found this? thanks.
•  » » » » I just typed "асимптотика делителей числа" ("asymptotics of the divisors of a number" in English) in google :)
•  » » If you're good in math, try to read this page) there're enough interesting things en.wikipedia.org/wiki/Divisor_function
•  » » » link: to the page
 » Can someone explain what problem F is asking? Can't comprehend 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.
 » 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
•  » » I'm pretty sure you got an overflow on the line: ans += cnt1 * cnt2; (cnt1 and cnt2 should be long long int)
•  » » int cnt1 = 0; int cnt2 = 0; should be long long int cnt1 = 0; long long int cnt2 = 0; 
•  » » Integer overflow. Change int cnt1 = 0; int cnt2 = 0; to long long cnt1 = 0; long long cnt2 = 0; AC submission link: https://codeforces.com/contest/1899/submission/233205784
 » Video solution for the Chinese：BiliBili
•  » » Is there any video solution in English?
•  » » » I don't know. Maybe someone posted it on youtube
•  » » »
 » 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
•  » » 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.
 » 11 days ago, # | ← Rev. 2 →   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 :(
•  » » same B was giving me wrong for last two tc that wre in the examples
 » 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?
•  » » segment tree working and i guess it cannot be solved by fenwik but i am not sure
•  » » https://codeforces.com/contest/1899/submission/233153696Persistent segment trees
•  » » » your solutions are way simpler to understand thanks a lot! curious whats your real handle?
•  » » Merge Sort Tree, Persistent Segment Tree or Wavelet Tree
•  » » » std::set is enough if you use small-to-large merge.
•  » » » » 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.
•  » » » » 11 days ago, # ^ | ← Rev. 3 →   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 ?
•  » » » » » 11 days ago, # ^ | ← Rev. 3 →   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)$.
•  » » » » » » I was thinking of the same approach, i.e. storing indices of all nodes in the subtree. I'm getting MLE https://codeforces.com/contest/1899/submission/233311333also if you could help me with this comment, I'd be really grateful — https://codeforces.com/blog/entry/122407?#comment-1085776
•  » » » » » » » 10 days ago, # ^ | ← Rev. 2 →   Do you understand why your code is giving MLE?
•  » » » » » » » » 10 days ago, # ^ | ← Rev. 3 →   Yes, for each node x, I'm storing all node indices in the subtree rooted at x. so in the worst case, in a linear tree, starting from the root we will be storing, n-1(root), n-2, n-3, ... 1( leaf) indices for each node, so this will lead to O(n^2) space.but this solution — https://codeforces.com/contest/1899/submission/233219342 also seems to be using O(n^2) space and is passing.
•  » » » » » » » » » Okay, good. So there are two questions you would like an answer to: Why does the author's solution not MLE? Why does my solution (which is similar to yous) not MLE? Answers: The author's solution uses a merge sort tree (a specific segment tree). For the memory complexity of a merge sort tree, see this: https://cp-algorithms.com/data_structures/segment_tree.html#saving-the-entire-subarrays-in-each-vertex Sets should be merged "small-to-large" for a better time and space complexity. See this:https://usaco.guide/plat/merging?lang=cpp If you don't understand something, I can explain it.
•  » » » » » » » » » I've read the doc you shared, i understand how the space complexity appears to be O(n^2) but is actually O(nlogn). I'll try this trick, will check if it'll give me an AC. Thank you for your time and the resources shared.
•  » » Any point-update-range-sum data structure
•  » » » Yes! apply BIT with dsu
•  » » I used the Euler tour technique along with a minimum segment tree: you can check my submission here.
•  » » sqrt decompositon
 » 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
•  » » take mini to be LLong_max or 1e18 something otherwise it overflows
•  » » » Thanks man that worked:)
 » 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?
•  » » Since the exponential function is strictly increasing, the equation 2^x = 2^y is equivalent to x = y.
•  » » » 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))) ?
•  » » » » 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)}}$
•  » » » » » okay got that too, thank you all<3:)
•  » » 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!
•  » » » yes! thanks<3
•  » » 11 days ago, # ^ | ← Rev. 2 →   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
•  » » » thanks
•  » » take log base 2 of both sides, then you will get the expression
 » 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. You can just DFS and keep adding each node to the segment tree or Fenwick tree as you traverse. Once you reach node 'u', you check all queries and find the sum between [l, r] for each query. 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 HereYou can check code if you don't understand explaination.
 » 11 days ago, # | ← Rev. 2 →   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 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; } 
•  » » 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:
•  » » » Testcases are weak I guess
•  » » » » even then the answer where v1 and v2 are same shouldn't be accepted as correct because it is mentioned in the question
•  » » Solved using the same exact idea.
 » 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.
•  » » that's nice!
 » 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$.
•  » » Applied the same thought
 » Why don't you guys just rephrase the problem statements using chatgpt? The prompts were actually painful to understand.
•  » » 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
•  » » maybe because each and every detail is very important and chatgpt might morph a detail.
 » 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
 » 11 days ago, # | ← Rev. 2 →   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
 » 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?
•  » » Try put 1e18 instead of INT_MAX and put 0 instead of INT_MIN
•  » » 11 days ago, # ^ | ← Rev. 3 →   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
•  » » since the whole array can be 1e9, n > 3 can lead to sum overflow
 » Problem 1899F - Alex's whims can be solved easier like this: Spoiler Make the edges 1->2, 2->3, 3->4 ... n-1->n For every di, move node n to node di. This way, the path from 1 to di will be di. Complexity becomes O(n+q) Is there a counter to this method? Was quite surprised to see such small constraints. Codevoid 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; } } 
•  » » 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.
•  » » » 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?
•  » » » » 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!
•  » » » 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.
 » 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/233250281But 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' ?
•  » » 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<
•  » » » Thanks for making it easy.
 » 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
 » 11 days ago, # | ← Rev. 2 →   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).
•  » »
•  » » » Ah, thanks! Frustrating to get the right idea and lose out on something minor like this :'(
•  » » » » at least you've learned something new)
 » 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.
•  » » 11 days ago, # ^ | ← Rev. 3 →   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.
•  » » » 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.
•  » » » But how you will store $2_i^a$ when a becomes 1e9
•  » » » » Check my submission, you can just store the exponent and divide out all factors of 2 from $a_i$.
 » 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?
•  » » It should be LLONG_MIN and LLONG_MAX for long long Reference
 » 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={idx,idx} 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) — MLEwhen 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?
•  » » use small to large
 » 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; } } 
 » 10 days ago, # | ← Rev. 2 →   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
•  » » 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)$. 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.
•  » » » 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?
•  » » » » 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).
•  » » » » » Thanks for the info ^_^Friendship ended with unordered_map, now map is my best friend!
 » 10 days ago, # | ← Rev. 2 →   New to CPP ; anyone could give reason as to why I'm getting TLE on problem D : https://codeforces.com/contest/1899/submission/233162158When I would easily be able to solve this in python, and it's O(N) normally...?
•  » » Someone hacked the solution that uses unordered_map :(Read this blog for more info https://codeforces.com/blog/entry/62393
•  » » » 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 !
•  » » » » You're right. $O(n)$ solutions should (and do) pass. But your solution is $O(n^2)$, unfortunately.
•  » » » » » 10 days ago, # ^ | ← Rev. 2 →   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 !
•  » » » » » » 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?
•  » » » » » » » 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...
 » 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
 » 10 days ago, # | ← Rev. 2 →   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.
•  » » Thank you! I was scratching my head over this.
 » 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?
 » 9 days ago, # | ← Rev. 7 →   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; int ans = a; 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; int ans = a; 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 233406392Error code link 233406621
•  » » sorry for my comment ...i was not considering abs() ...ignore my comment.
•  » » » Yeah, unfortunately negative modulo in cpp is weird
 » Can someone tell the pre requisites for the last problem? Also does anyone have similar problems like that
 » F but simpler 233608256
 » 7 days ago, # | ← Rev. 2 →   During practice, I submitted this solution for problem F. My Codevoid TATAKAE() { int n, q; cin >> n >> q; int last = n — 1; for (int i = 1; i <= n — 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
•  » » 7 days ago, # ^ | 0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } yes, i did it exactly in the same way.
 » Linear / O(n + q) solution of problem F 233781812
 » Can someone explain me why printf is printing zeroes ? this is submission for Alex's whims problem Fhttps://codeforces.com/contest/1899/submission/234314307I 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