### Misuki's blog

By Misuki, 3 weeks ago,

Except hints/solutions, I try to add a "general idea" section discuss about some general strategy and standard ideas used to solve the problem, hope you would like it :)

2001A - Make All Equal

idea & solution: Misuki

Hint 1
Hint 2
General idea
Solution
Code

2001B - Generate Permutation

idea & solution: Misuki

Hints/General idea of solution path 1
Hints/General idea of solution path 2
Solution
Code

2001C - Guess The Tree

idea: feecle6418, solution: Kaey

Hint 1 for solution 2
Hint 2 for solution 2
Solution
Solution 2
Code
Code 2

2001D - Longest Max Min Subsequence

idea & solution: Misuki, tester's code: SorahISA

Hint 1
Hint 2
General idea
Solution
Code
Tester's code

2001E1 - Deterministic Heap (Easy Version)

idea & solution: Misuki

Hint 1
Hint 2
Further hints for solution path 1 (official solution)
Further hints for solution path 2 (alternative solution)
General idea
Solution
Code

2001E2 - Deterministic Heap (Hard Version)

idea & solution: Misuki

Hint 1
Hint 2
Hint 3
General idea
Solution
Code
• +212

 » 3 weeks ago, # |   0 Someone gotta explain C, cause solution above is unclear.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +9 we can easily find if two nodes have edges or not using a divide & conquer approach. Lets say if we have two nodes $x$ and $y$. querying them will give us a node $m$ such that m is the center of the distance. then we can solve it for $(x, m)$ and $(m, y)$ and so on until the answer of a query is either of the nodes. The second big observation is that the root of tree is 1 so every node will be connected to 1 in some manner. so instead of applying divide & conquer between two random nodes, we can apply divide & conquer to 1 and any of the unvisited nodes yet. Submission
•  » » » 3 weeks ago, # ^ |   0 You mean (x,m) and (m,y).
•  » » » » 3 weeks ago, # ^ |   0 yes, my bad for the typo
•  » » » 3 weeks ago, # ^ |   0 Did they mention that the root is always 1?
•  » » » » 3 weeks ago, # ^ |   0 any node can be the root in a tree. you can fix n to be your root node if you wish, it doesnt matter.
•  » » » » » 3 weeks ago, # ^ |   0 Any idea why I am getting RTE for same logic: https://mirror.codeforces.com/contest/2001/submission/277414456
•  » » » 3 weeks ago, # ^ |   0 Thank you for your excellent solution.
•  » » » 5 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; } I tried the same way, can someone please help why it gives WA on Test 3. 280178005
•  » » 3 weeks ago, # ^ |   +20 For C there is a simpler solution with only n log n queries.You can just "root" the tree in 1, and after that for each node, you'll determine is father. For each node $a$: $x_1$ = query(a,1)$x_2$ = query(a,$x_1$) ...$x_{l}$ = query(a,$x_{l-1}$)When $x_{l}=a$ you stop and you know that the father of $a$ is $x_{l-1}$. $l<\lceil log(n)\rceil$ because each time you divide your path by 2. So at end it'll be n log n queries.Hope I was clear.
•  » » » 3 weeks ago, # ^ |   0 Edit: Sniped above :)
•  » » » » 3 weeks ago, # ^ |   0 Doesn't seem like a edit
•  » » » 3 weeks ago, # ^ |   0 Why can we root the tree at 1? Can't the root be any one of the nodes provided?
•  » » » » 3 weeks ago, # ^ |   0 Since the edges are undirected, any node can become the root. Trying to draw a tree starting from any node at the zeroth level will help to understand this. Random exampleFor instance, (1)-(2)-(3) can be (1) | (2) | (3) or    (1)   /   \ (2)   (3) or (3) | (2) | (1)All these represent the same tree
•  » » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 Any vertex of the tree can be the root of a tree. So, the statement "the root can be any one of the nodes provided" is true. This means we can choose any node as the root and proceed with the process. Nodes 1, 2, ..., n are all valid choices. In this solution, we chose node 1 as the root, but selecting any other node would also be correct. (But please remember: you can only choose one node as the root in a solution. If you choose a different node, for example, node 3, then you need to consider nodes 1, 2, 4, 5, ..., n.)
•  » » 3 weeks ago, # ^ |   0 consider a and b in a tree and distance between them is 7, so x would be some node in distance of 3 from a, and in distance of 4 from b, now you should change b to x (binary search) now you will give new x between a and new b, and distance between a and x is 1, distance between x and b is 2, that means you have an edge between a and x,continue doing this approach for all node from 2 to n, you will find what is the parent of node i, and because we have a tree (we have n — 1 edges, that's why you should loop from 2 to n and not 1 to n), it works true.you can see my code for better understanding,hope it helps.i couldn't accept it during the contest because my previous solution works in O(2*n*lon2(n)) and its more than 15*n.
 » 3 weeks ago, # |   0 Thanks for the super fast tutorial
•  » » 3 weeks ago, # ^ |   +3 I also created a practice contest with easy versions of problem D: https://mirror.codeforces.com/group/7Dn3ObOpau/contest/545195
 » 3 weeks ago, # |   0 Fast Tutorial
•  » » 3 weeks ago, # ^ |   0 what can i say
 » 3 weeks ago, # | ← Rev. 2 →   +14 i got ABSOLUTELY crushed. this contest made me rethink my life decisions and contemplate on quitting CP forever :(gotta give props for the blazingly fast editorial though
•  » » 3 weeks ago, # ^ |   +5 Keep going, I had thought about that, but it is very satisfying to see your improvement over time
•  » » 3 weeks ago, # ^ |   0 Well, I still try to go on even after 44 unsuccessful contests. :( Maybe, you can draw some inspiration from me and ... Spoiler"quit early! :PJust kidding!!
 » 3 weeks ago, # |   0 I don't think I understood B, can someone please explain why for n == 4, 3 1 4 2 isn't valid? I thought that you could build on this for even n, making n==2 the only impossible input.
•  » » 3 weeks ago, # ^ |   +4 Forwards takes 2 passes, backwards takes 3.
•  » » » 3 weeks ago, # ^ |   0 a = [3, 1, 4, 2]The typewriter 1 will go 1 and carriage return once, then go to 2 and carriage return twice and go to 3 and then to 4So the carriage return total of typewriter 1 is 2Now let's consider typewriter 2, typewriter 2 will go to 1 and carriage return then go to 2 and to 3 and carriage return twice and then go to 4 Both of them take 2 carriage return so it should be valid rigtht?
•  » » » » 3 weeks ago, # ^ |   0 Typewriter 1 can go from 1 to 2 without returning in between.
•  » » » » 3 weeks ago, # ^ |   0 "The typewriter 1 will go 1 and carriage return once, then go to 2 and carriage return twice and go to 3 and then to 4"It is possible for typewriter A to collect 1 and 2 without returning. Since we are looking to minimize the carriage return operation, the optimal number would be 2.
•  » » » » 3 weeks ago, # ^ |   0 if we consider minimum carriage returns in your permutation typewriter1 needs 2 returns and typewriter2 needs 3.
•  » » 3 weeks ago, # ^ |   +6 from the pointer facing at 1, to generate 3 1 4 2, you could do 1 2 in one traversal and then return and do 3 4 in 1 traversal. So 1 return in total.but from the pointer facing at n, to generate 3 1 4 2, you first need to get to third poositing and make it 1 then return, then traverse to make 2 and 3 and return again and then make 4 (since 4 comes before 3 that way) so you made 2 returns in that way. Minimum of 2 isnt equal.
•  » » 3 weeks ago, # ^ |   0 for left typewriter it will be 1 return pass as 1 2 return 3 4, but for right typewriter it will be 2 return pass as 1 return 2 3 return 4.
 » 3 weeks ago, # |   0 Super-fast editorial!!!
 » 3 weeks ago, # |   0 We can do binary search on trees ?!?!
•  » » 3 weeks ago, # ^ |   +3 Well we can use divide and conquer
 » 3 weeks ago, # |   +10 this contest gave me the encourage to quit CP
 » 3 weeks ago, # |   0 Could someone tell me the prbleam about my code? ~~~~~~~~~~ //this is my code from sys import stdout def ss(x,y): if x!=y and b[x][y]==0: print('?',x,y) stdout.flush() z=int(input()) b[x][y]=z if x==z: a.append(x) a.append(y) else: if x
•  » » 3 weeks ago, # ^ |   0 this is C
•  » » » 3 weeks ago, # ^ |   +5 Could you please put it in a code block for easier visualization?
•  » » » » 3 weeks ago, # ^ |   0 Your code here... from sys import stdout def ss(x,y): if x!=y and b[x][y]==0: print('?',x,y) stdout.flush() z=int(input()) b[x][y]=z if x==z: a.append(x) a.append(y) else: if x
•  » » » » » 3 weeks ago, # ^ |   0 Please use collapse/spoilers the comments are getting quite messy and lengthy.
 » 3 weeks ago, # |   +5 E1 can be solved in a much simpler way (277414233) without any binomial coefficients or combinatorics.
 » 3 weeks ago, # | ← Rev. 4 →   +6 D can be solve in O(n). SoultionFirstly we make a frequencie array to count every element how many times it repeated.Then we make an empty vector to store ans in it, to store answer we will walk through the elements as the input give is, we do mp[a[i]]--,if the element already in ans we continue , if not we push it in best place we can , I mean by that we keep pop back until we put it in best place but we can popback if the back element counter is it's greater than 0, and when poping it we are sure that it's the best move by some condtions. Code277423267
 » 3 weeks ago, # |   0 D was pretty nice, I wish I actually knew trees, so I could attempt C as well. I think I'm gonna reach expert regardless though! very nice contest, thank you!
 » 3 weeks ago, # |   0 B was easy, If we can understand the problem and write some testcasesIn most of such problems , I end up not understanding but today I did B
 » 3 weeks ago, # |   0 SUPER FAST!Thank You!The Problem is funny.I love this round!
 » 3 weeks ago, # |   +4 general idea is really useful.Thanks.Btw, problem D is nice
 » 3 weeks ago, # |   +56 Another approach to solving problem C is to assume that the tree is rooted at vertex $1$. For each vertex $u = 2, 3, \ldots, n$, the goal is to find its parent $p(u)$.By using the function $\texttt{query}(u, 1)$, you can get the midpoint of the path from $u$ to its ancestor $1$. Keep halving the path until $\texttt{query}(u, x) = u$, which means that $x$ must be $p(u)$. This method will find $p(u)$ in no more than $\lceil \log_2 (n-1) \rceil$ queries! Codevoid solve() { int N; cin >> N; auto query = [](int l, int r) -> int { cout << "? " << l << " " << r << "\n" << flush; int ret; cin >> ret; if (ret == -1) exit(0); return ret; }; auto answer = [](auto &vec) -> void { cout << "! "; for (auto [a, b] : vec) cout << a << " " << b << " "; cout << "\n" << flush; }; vector> edges; for (int i = 2; i <= N; ++i) { int L = i, R = 1; while (true) { int M = query(L, R); if (M == L) { edges.emplace_back(L, R); break; } R = M; } } answer(edges); } 
•  » » 4 days ago, # ^ |   0 thanks your easy answer
 » 3 weeks ago, # |   +20 I like that General idea,it really help me much!!!
•  » » 3 weeks ago, # ^ |   +12 glad you like it :)
•  » » » 3 weeks ago, # ^ |   0 I am sorry to bother you ,but can you tell me the General idea of promlem CI am confused about the Solution.I cant find out the index logic.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +4 It have less standard idea and rely on pure puzzle solving ability more in my opinion, but if you have a good perspectice about the problem it might be easier. For example, I think the problem as some kind of spanning tree problem and try to keep finding edge connect different component. (Solution2 in editorial)
•  » » 3 weeks ago, # ^ |   0 I cant understand problem C .How the binary work? Why use the binary search?
•  » » » 3 weeks ago, # ^ |   0 Sorry, I was thinking hint for my solution when writing it but the solution part is from coordinator. I've add Soluion2 which correspond to the hint section.
 » 3 weeks ago, # | ← Rev. 2 →   +16 Maybe I'm misreading the solution to C, but I think this is simpler. The key idea is that $(u, v)$ is an edge if and only if querying ? u v returns $u$. Then, for each $2\le v\le n$, we can query ? v 1, take the result $x$ to query ? v x, etc, until we reach some node $u$ with ? v u being $v$.In this way, you can think of this as rooting the tree at node $1$ and discovering the parent of node $v$ for each $v\neq 1$ in this rooted tree, which must by definition give $n - 1$ distinct edges. Edit: Sniped above :)
 » 3 weeks ago, # |   +12 It seems I have an alt approach for C. Step 1-1Ask $(1,u)$ and $(u,1)$ for all $u$. Then, try to find $d(1,u)$.Of course $d(1,1)=0$, and if $(1,u)$ returns $1$, $d(1,u)=1$.Now we can restore $d(1,u)$ for all $u$. Step 1-2$d(u,v)$ answers the midpoint of $u$ and $v$ (if $d(u,v)$ is odd it answers the nearest one to $u$).Because of this, for all $u$, if $(1,u)$ returns $x$ and $(u,1)$ returns $y$, $d(1,u) = d(1,x) + d(1,y)$ is always satisfied. From the information on step 1-1, we can found all of $d(1,u)$ in a chain. Step 2For all $u$, begin with $x=1$, repeat $x \leftarrow (u,x)$ until $d(1,x)+1 = d(1,u)$. Now, if the tree is rooted at $1$, the parent of $u$ is $x$. Additional noteNow I notice step 1 isn't needed (we can avoid the step with modifying step 2). Why?
 » 3 weeks ago, # | ← Rev. 2 →   +3 Another way of doing CLet's define an array $\text{parent}[i]$, initially for all $2 \le i \le n$ set $\text{parent}[i] = query(1, i)$.Initially let node $1$ be taken and all other nodes not taken. Repeat until all nodes are taken: find any node such $i$ that $\text{parent}[i]$ is taken and ask $query(\text{parent}[i], i)$. If the result is $\text{parent}[i]$, then $i$ and $\text{parent}[i]$ are connected by an edge, so add it to the answer and set $i$ to be taken. Otherwise, set $\text{parent}[i]$ = $query(\text{parent}[i], i)$.This works because every time we do not take a node $i$, the distance between that $i$ and $\text{parent}[i]$ halves, so for any node we only need to process it $log_2(n)$ times. I find this solution more intuitive than the editorial one personally.Edit: seems like a few other people posted the same solution while I was typing it, lol
 » 3 weeks ago, # |   0 For C I did the following. Initialize a stack of pairs with all (i, j) where i < j. While the stack is empty, I pop (a, b). I check using a DSU if a and b belong to the same connected component (that has been discovered till now, and skip if they do. If they don't, then I query ? a b and push the output x to the stack if x != a. Otherwise, I push the found edge and merge the two components.I think this should always find all edges while remaining under the query limit. But I don't understand why this WAs. Could someone explain?
 » 3 weeks ago, # |   0 For C, I used DFS and it seems to have worked somehow. Could someone explain it?277409228
 » 3 weeks ago, # |   0 Do anyone know a software that have a faster execution for interactive problem?I use jdoodles but it not stable
 » 3 weeks ago, # |   0 I was unsure before submitting the code for problem C but it passed the pretests.
 » 3 weeks ago, # |   0 Problem D is nice idea but it's hard implementation!
 » 3 weeks ago, # | ← Rev. 2 →   +20 Solution D in O(n) (attempt: 277409175)We will store the current response in the ans array. Initially, ans is empty.Let's build an array r, where r[x] is the maximum index i, such that c[i] = xLet's build an array of used, where used[x] = True if the value of x is contained in ans and False otherwise. Initially, all values are FalseLet's go through the c array.Let's consider the value of c[i], if used[c[i]] = True, go ahead, otherwise we will execute the next cycle:If ans is empty, we do nothing and exit the loopIf r[ans.back()] <= i, exit the loop1) If ans.size() % 2 == 0, then1.1) If c[i] < ans.back(), then delete the value of ans.back(), do not forget to put the corresponding value to the array used (used[ans.back()] = False) and return to the beginning of the cycle1.2) Otherwise (if c[i] > ans.back()), check 1.2.1) If c[i] > ans[-2] (the penultimate element in ans), then remove the last two elements from ans, do not forget to change used, return to the beginning of the cycle1.2.2) Otherwise (if c[i] < ans[-2]), exit the loop2) Otherwise (if ans.size() % 2 == 1) we perform actions similar to 1), but change the signs to the opposite ones (> to <, and vice versa) After the loop, add c[i] to ans, do not forget to change used (used[c[i]] = True)When we go through the entire c array, the ans array will be the optimal answer.Since we add and remove each element from ans once, the asymptotics is O(n)
 » 3 weeks ago, # |   +15 Reading question B reminds me of how research papers are written ;))
 » 3 weeks ago, # |   0 The problems were enjoyable, but Problem B lacked clarity. In future contests, it would be great to see more emphasis on covering more cases for such problems.
 » 3 weeks ago, # |   0 What topics should I learn to solve problem D?
•  » » 3 weeks ago, # ^ |   +1 greedy, implementation, sorting , optional -> (priority queue), set
•  » » » 3 weeks ago, # ^ |   0 I spent all my time trying to solve it with DP, segment tree.... (some advanced stuff) and now It's just greedy and implementation :(
•  » » » » 3 weeks ago, # ^ |   0 same here
•  » » » » 3 weeks ago, # ^ |   +8 you can use segment tree
•  » » » » 3 weeks ago, # ^ |   +8 Well, it can be done using segtree277435255
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 277445159 can you please help me what am i doing wrong here ?
•  » » » » 3 weeks ago, # ^ |   +8 can be done via segtreeshttps://mirror.codeforces.com/contest/2001/submission/277440499
•  » » » » 3 weeks ago, # ^ |   0 same
•  » » » » 3 weeks ago, # ^ |   0 Don't overestimate the problem I thought about DP, but the constraint clearly will not help.I thought about segment but i feel like the problem I would struggle with segment could be easily solved by a frequency array
 » 3 weeks ago, # |   0 C does not use binary search as mentioned in the editorial, but some version of binary lifting
•  » » 3 weeks ago, # ^ |   0 Sorry, I've add binary search solution on it (Solution2)
 » 3 weeks ago, # |   +4 Good quality contest, thank you !
 » 3 weeks ago, # | ← Rev. 2 →   0 for B we can just say if n even then not possible and if oddwe can construct like this--for 3 -->1 3 2 for 5 -->1 3 5 4 2for 7 -->1 3 5 7 6 4 2and so on
 » 3 weeks ago, # | ← Rev. 3 →   0 A super simple way to solve C: Spoilerint main() { int t; scanf("%d", &t); while (t --) { int n; scanf("%d", &n); auto get = [&] (int a, int b) { printf("? %d %d\n", a, b); fflush(stdout); int res; scanf("%d", &res); return res; }; vector fa(n + 1); for (int i = 2; i <= n; i ++) { int r = 1; for (int j = 0; j < 15; j ++) r = get(r, i); fa[i] = r; } printf("!"); for (int i = 2; i <= n; i ++) printf(" %d %d", fa[i], i); puts(""); fflush(stdout); } return 0; } 
•  » » 3 weeks ago, # ^ |   0 Please use collapse/spoilers the comments are getting quite messy and lengthy.
•  » » » 3 weeks ago, # ^ |   0 sry, my bad.
 » 3 weeks ago, # |   +3 Awesome work! Love those general ideas!
 » 3 weeks ago, # |   +6 D can be done with simple stack
 » 3 weeks ago, # |   0 First though of dp ,then greedy approach striked but wasnt able to implement it.
 » 3 weeks ago, # |   0 Can someone please help me figure out what is wrong in my soln to D link In this: I have a turn variable which tells us that we have to maximize or minimize the next element to be chosen. A variable lst that keeps the last printed index. A set st that keeps track of the elements that can be selected in future with their indices. A map that keeps the count of elements that are left in the array and are not visited till now.
•  » » 3 weeks ago, # ^ |   +1 Take a look at Ticket 17476 from CF Stress for a counter example.
•  » » » 3 weeks ago, # ^ |   0 Thank you so much
 » 3 weeks ago, # |   0 Does anyone have test cases for D? Looks like I'm failing somewhere on Test 3.
•  » » 3 weeks ago, # ^ |   +3 I figured some out for my submissionHere's one that I failed on: 1 7 4 1 2 4 5 2 1 Answer should be: 4 4 1 5 2 An even simpler one I failed on: 1 5 4 2 4 1 2 Answer should be 3 4 1 2 
 » 3 weeks ago, # | ← Rev. 2 →   0 off-topic but quick question: why is my activity section different for everyone except me? i see a 15 day streak when logged in while in incognito mode i see an 11 day streak, is this normal?
•  » » 3 weeks ago, # ^ |   0 i think it shows it on your local time when you're not incognito, but when you use incognito, your local time defaults to whatever incognito is set to be. so for some time zones you didn't actually keep your streak.
•  » » » 3 weeks ago, # ^ |   0 man i was trying making a 90 day streak, sad :(gotta start again now
•  » » » » 3 weeks ago, # ^ |   0 i wouldnt say you have to start again, youre bound to lose the streak on some timezones that are far from yours. good job on the streak so far though, i hope you'll reach your goal
•  » » » » » 3 weeks ago, # ^ |   0 thanks, looks like you just turned expert too. congratulations!
 » 3 weeks ago, # |   +3 Wasn't able to completed problem D during contest but I liked it.And the general idea section is super useful.
 » 3 weeks ago, # |   0 Can someone please tell me what i did wrong in the 3rd question https://mirror.codeforces.com/contest/2001/submission/277397815It's been 1.5 hours and i have read many other solutions and even the official one, and i do not understand where my logic went wrong. thanks
•  » » 3 weeks ago, # ^ |   0 it looks like you did not flush after each output.
•  » » » 3 weeks ago, # ^ |   0 I thought endl automatically flushes everything
 » 3 weeks ago, # | ← Rev. 2 →   -10 Dear tester, Kind request, when you write program to match the contestant's output, with correct output, Please give some meaningful errors, which can help the user in debugging the issue. wrong answer 3919th numbers differ — expected: '1', found: '3'How am I supposed to know, 3919th number is from which test case ????It would have been great help, if you had simply put here the test case number, I could have used some tricks to find out where my solution is failing :| . cc: Misuki
•  » » 3 weeks ago, # ^ |   0 This have nothing to do with the testers, this is built in checker which compare author solution output and your output, and this is the default output when your output differs.
•  » » » 3 weeks ago, # ^ |   0 cool . no issues.
•  » » 3 weeks ago, # ^ |   0 Actually I would recommend you to write a bruteforce and see where goes wrong with your solution. Since in contest, you can't see the hidden testcase, and it's useful to have such ability as a contestant.
•  » » » 3 weeks ago, # ^ |   0 sure, will adapt. <3
•  » » 3 weeks ago, # ^ |   0 Take a look at Ticket 17477 from CF Stress for a counter example.
•  » » » 3 weeks ago, # ^ |   0 I found the error buddy. Just changing > to >= fixed my code, and got AC. WRONG SUBMISSION : https://mirror.codeforces.com/contest/2001/submission/277418236RIGHT SUBMISSION: https://mirror.codeforces.com/contest/2001/submission/277433853
•  » » 3 weeks ago, # ^ |   0 You can put a counter, set it to zero once it reaches 3919 print that test case. (you should only apply after you tried enough to find the mistake by yourself)
 » 3 weeks ago, # | ← Rev. 2 →   0 What is the difference between Code and Code 2 for the C problem? I tried and was not able to find the difference :(Both look exactly the same. I mean Letter by Letter.
 » 3 weeks ago, # | ← Rev. 2 →   +8 when i trying to hack this submission, it shows "Unexpected verdict". here is gen: #include using namespace std; const int N=3e5-4; int main() { cout << 1 << endl; cout << N+1 << endl; for(int i=1,l=1,r=N;i<=N/2;i++) { if(i%2==1) {cout << r << ' ';r--;} if(i%2==0) {cout << l << ' ';l++;} } cout << N/2 << ' '; for(int i=1,l=1,r=N;i<=N/2;i++) { if(i%2==1) {cout << r << " \n"[i==N/2];r--;} if(i%2==0) {cout << l << " \n"[i==N/2];l++;} } } It seems that some code that should be TLE is incorrectly tagger correctness in polygon, please check this.upd. physics0523 seems facing same question?
•  » » 3 weeks ago, # ^ |   +9 Maybe some intended solution on Polygon also gets hacked or validator is broken or something
•  » » » 3 weeks ago, # ^ |   +29 Turns out a tester's solution TLE on the hacked test, now it should be fixed.
•  » » » » 3 weeks ago, # ^ |   +16 Let's share my generator: #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout << "1\n"; cout << "300000\n"; for(int i=0;i<300000;i++){ if(i){cout << " ";} int a; int j=i%100000; if(j%2){a=1+(j/2);} else{a=300000-(j/2);} if(100000<=i && i<200000){a=i;} cout << a; }cout << "\n"; return 0; } Some false (and maybe too straight-forward simulation) solutions takes $O(N^2)$ in this case.
 » 3 weeks ago, # |   0 Am i missing something in D?Here is what i did (ITS WRONG and idk y):3 arrs: Step 1Original and a Boolean array for the user input, (i think if we use this then we can edit and delete members from our sub array in O(1) time)Another third array digits, which stores each digits index position, essentially this array stores the place where we picked that digit from (-1 if we didn't pick it up at all) Step 2as we iterate over the original array, a[i], we check if digit [a[i]] == -1, if it is update digit[...] = i. (this ensures that we always pick the largest sub seq, also we toggle the boolA[i] = true)now the other possibility is that if digit[...] != -1, this means that we did pick it up before. Last stepIf we picked it up, we check the original's location:if it is odd, this means that we want to keep it as large as possible and hence we will only remove (and hence append) if it is smaller than the next element we have chosen.if it is even you do the same for minimum. finally after one iteration you have the largest sub seq. this gave me wrong answer on pretest-2 meaning that it isn't the correct logic, i just want to know why
 » 3 weeks ago, # |   0 Thanks for the general ideas, hints, and fast editorial. Really appreciate it!!
 » 3 weeks ago, # |   +3 I Think in problem D it is more intuitive to think about storing range min and max in a segment tree and once an element is taken update min value to 1e9 and max value to -1e9.
•  » » 3 weeks ago, # ^ |   0 Agreed, segtree was easier to think in this question.
•  » » 3 weeks ago, # ^ |   0 My solution-https://mirror.codeforces.com/contest/2001/submission/277423515 I have used 2 segment trees, it can be implemented in the same tree using a structure to store min and max or as a pair.
 » 3 weeks ago, # | ← Rev. 2 →   0 I still can't figure out why my submission to C is incorrect and giving wrong ans. Somebody please help ,my implementation is clean My submissionFound it! I was randomly printing the ans at the end , didnt see that we have to print serial wise 1..n-1
 » 3 weeks ago, # | ← Rev. 2 →   0 For A , the hint encourages us to think about the lower bound of the answer . For me it is 0 (the case where all the elements in the array are equal ) , and that doesn't help in any way . What did the author expected as an answer when they gave us this hint ? I know this is a very silly question perhaps even meaningless but any help is appreciated
•  » » 3 weeks ago, # ^ |   0 I mean the lower bound of the answer for any fixed $a$, not necessarily with all elements equal
 » 3 weeks ago, # |   0 I am new to interactive problems. My solutions got idleness limit exceeded. It is mentioned in the statement that this happens when you don't flush the output put I do. Can someone suggest what would be the problem?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 If you are using c++. then please refer to this. Don't use the cin.tie() or cout.tie() Define this in your headers. #define IOFLUSH fflush(stdin);fflush(stdout);Whenever you take input, or print any output. just write this statement before and after it, to avoid any sort of issues. IOFLUSHThis should solve the issue.
•  » » » 3 weeks ago, # ^ |   0 I would use cout<
•  » » » » 3 weeks ago, # ^ |   0 I got a bit confused now. If I am setting isos::sync_with_stdio(0) I should use cout << flush; or cout.flush(); ? another question doesn't cout << endl; do the work? I think after the contest when I upsolved the question I just used cout << endl; only
•  » » » » » 3 weeks ago, # ^ |   0 cout<
•  » » » » » » 3 weeks ago, # ^ |   0 ok I undrsyood it, thak you bro
 » 3 weeks ago, # |   0 Can someone hack my solution for problem D 277416865. The complexity is O(nlog²) and I think the worst case is :n , 1 , n-1 , 2 , n-3 , 4 , n-4 , 5....
 » 3 weeks ago, # |   0 Can someone explain me B? I don't think I can understand the task properly(maybe cuz im dumb ;() but why can't i just go forward without returning on bot typewriters, or maybe thats not how pointer works?
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 The problem states that, in a move operation: Such operation can be performed only if after the operation, $1≤i≤n$ holds. Hence, after moving to the last position, the pointer must return to its initial position to be able to write again.The way I understand this problem, a valid permutation should have the same number of inversions of consecutive numbers, going from left to right and from right to left. One way to achieve such a permutation is to start at the middle index and go back-and-forth in the array until it goes out of bounds (or vice-versa).277352967
 » 3 weeks ago, # |   0 Can anyone help me find error in my code? I'm trying to solve D and it is giving wrong answer on test case 3. Here is my submission: https://mirror.codeforces.com/contest/2001/submission/277428182
•  » » 3 weeks ago, # ^ |   0 Take a look at Ticket 17479 from CF Stress for a counter example.
 » 3 weeks ago, # |   0 Can anyone find my error in problem C? This is my submission 277387198, which should be quite self explanatory. I tried to find the edges on the path $1---u$ for all undiscovered node $u$ by querying $(1,u)$. If it returns $x$, query $(1,x)$ and $(x, u)$. Skip the query $(1,x)$ if x is already discovered.The solution looks ok to me, and I got a verdict saying WA on test $5$, but seems like test $5$ is a tree with edges $1-2,1-3,1-4$ which my solution can detect. Any help with the solution or a test case that fails will be helpful. Thanks.
•  » » 3 weeks ago, # ^ |   0 int getNew(int n){ while(true){ newNode = rand() % n + 1; if(nodes.find(newNode) == nodes.end()) return newNode; } } This looks so inefficient. I think getNew(int n) can return 1, running resolve(1,1) will add edge(1,1), which is incorrect. My similar solution https://mirror.codeforces.com/contest/2001/submission/277595574
 » 3 weeks ago, # |   0 I solve problem D using Lazy segment tree. My solution: 277441928I hope it is helpful.
 » 3 weeks ago, # |   +3 Problem D didn't have strong enough test cases a O(n^2) approach gets ac in main test, the triggering worst case test would have been n/2 1 n/2-1 2........ repeated twice.
•  » » 3 weeks ago, # ^ |   0 Came here to say that.
•  » » 3 weeks ago, # ^ |   +3 Sorry about that, I didn't notice such bruteforce solution during preparation, I would take more care about such thing next time :(
 » 3 weeks ago, # |   0 I am not able to understand the last paragraph of the Editorial for Problem D. Can someone explain it in detail? Also How to solve it using segment trees?
•  » » 3 weeks ago, # ^ |   0 Hey,can you help me with C my solution,I used something similar to the editorial but it exceeds 15n queries however for any numbers of node it can only go upto 2^(ceil(log2(n))+1) operations. Code:277462404
 » 3 weeks ago, # | ← Rev. 2 →   0 In question D ,Accepted solutions of the contest are judged till only 30 test cases while judging is now taking place on more test cases. Matter of surprise is that many accepted solutions are now giving Time limit exceeded on test cases after 30.
 » 3 weeks ago, # |   +3 D similar to https://open.kattis.com/problems/earlyorders
 » 3 weeks ago, # |   0 Can anybody tell me why my code gives wrong answer on test case 3 for problem C
 » 3 weeks ago, # |   0 problem C : code for solution 1 is the same as solution 2
 » 3 weeks ago, # |   0 can someone explain d&c wtih dsu solution in problem C
 » 3 weeks ago, # |   0 My solution with divide and conquer: Submission #277404397Why the maximum query count does not exceed 15n?
 » 3 weeks ago, # |   0 I am confuse about problem B, maybe I am wrong, I thought for all odd case, I just need to swap(a[0],a[n//2]), for example: [3,2,1,4,5] -- > type 1: 1 -->2-->3,4,5; type 2: 1,2,3 -->4-->5
 » 3 weeks ago, # |   0 In Problem C I was getting idleness limit exceeded on testcase 2 but when i corrected the logic of the code the error was gone..so i wanted to ask that can idleness limit exceeded error occur also when your code's logic wrong?
 » 3 weeks ago, # |   0 I always get hints for problems rated high like D but don't know why I didn't able to solve the problems
 » 3 weeks ago, # |   0 Both codes for C are the same...
•  » » 3 weeks ago, # ^ |   0 Sorry, it should be fixed now.
 » 3 weeks ago, # |   0 Thank you for the fast editorial and I love the General idea sections.
 » 3 weeks ago, # | ← Rev. 2 →   0 where did the binomial coef come from in problem E1edit : i think i get it using the stars and bars method we can move the size — 1 to a next node or increase the value at the current node till the root
•  » » 3 weeks ago, # ^ |   +11 For anyone else wondering about where the binomial coefficients come from, here's an alternate explanation.Let's try to find the number of unique max heaps using the $k$ operations without worrying about the deterministic conditions. We start with a max heap (since all elements are zero), and doing an operation maintains the max heap invariant. So, we only have to blindly apply the operation on nodes.Let $T = 2^{n} - 1$The first thought that comes to mind is to perform the first operation on a random node, and then recurse for the same tree, with $k - 1$ ops left, i.e, something like$f(k) = T\cdot f(k - 1)$However, this leads to overcounting. Consider Configuration 1 : Node $x$ is chosen in round 1, and it's child $c$ is chosen in round 2. Configuration 2 : Node $c$ is chosen in round 1, and it's parent $x$ is chosen in round 2. Notice that if $k = 2$, these configurations are essentially the same. Hence, we can deduce that round number at which a particular node participated is not important, what's important is how many rounds did it participate in.So, let's call the number of participation rounds for each node as $x_1, x_2 \dots x_T$, then, since there can only be $k$ different rounds, we should have$x_1 + x_2 + \dots x_T = k$So the number of unique max heaps is the non-negative integral solution for this equation, which is pretty well known via Stars and Bars to be $k + T - 1 \choose k$
•  » » 2 weeks ago, # ^ |   0 Could you explain the transitions for E1 in greater detail? I've been stuck trying to understand how the previous states are used to compute the next ones.
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   +4 First, let's find out the number of unique max heaps using the $k$ operations (Let's disregard deterministic properties).$dp[n][k]$ represents the number of unique max heaps on $n$ levels perfect binary tree with $k$ operations. Then, let's think about how many operations will we use at the root, $root \in [0, k]$, and the remaining number of operations is $remain = k - root$.Then, from the remaining number of operations, we need to distribute some operations to the left and right subtree. How many operations can left receive? $left \in [0, remain]$, Therefore, $right = remain - left$. After distributing the operations, the left and right subtree have become independent. Hence, the transitions are: $dp[n][k] = \sum_{remain \in [0, k]} \sum_{left \in [0, remain]}(dp[n - 1][left]*dp[n - 1][right])$Note that $dp[n][k]$ is $T + k - 1 \choose k$, as described in my earlier comment, but I just showed you a DP instead of a combinatorics approach.Now, how do we count unique deterministic max heaps? The first thought that comes to mind is to track the final value of each node, something like $dp[n][k][val]$. However, if you think about it, this value parameter can be inferred from other parameters. The root will always have $val = k$. Then, you might think about blocking the transitions when $left = right$. However, that is also incorrect, because left and right child are allowed to be equal if the node is not on the path defined in the problem. This means that we need to track another DP parameter, which would be a boolean.$dp[n][k][on\_path]$ is no. of unique max heaps on $n$ levels with $k$ operations such that $on\_path$ denotes whether root is on the path.But since 3D DP will be hard to visualize and optimize, let's remove the boolean parameter, and maintain two 2D DP. Define $indp[n][k]$ to be the number of unique deterministic max heaps when the root is in the defined path. Similarly, define $outdp[n][k]$ to the number of such configurations when root is not on the path.To perform the transitions, $outdp[n][k] = \sum(outdp[n - 1][left]*outdp[n - 1][right])$If $left > right$ $indp[n][k] = \sum(indp[n - 1][left]*outdp[n - 1][right])$But if $left < right$ $indp[n][k] = \sum(outdp[n - 1][left]*indp[n - 1][right])$There are $O(N \cdot K)$ states and transitions are $O(K^2)$. Hence, the time complexity is $O(N \cdot K^3)$.How to optimize it? Before we do that, let's consider the problem of finding the sum of pairwise product in an array $\sum_{i < j} a[i] \cdot a[j]$You immediately know a 1D DP approach. But can you optimize this 2D DP. Why or why not? for gap in [1, n]: for i in [1, n]: j = i + gap if j <= n: ans += a[i]*a[j] Optimization is not possible, because when a gap is fixed, there is no pattern, or any number that remains constant. However, we didn't really need to fix the gap, we could've fixed $a[i]$ and inferred all the possible gaps, and come up with $a[i]*suffix\_sum$.We will use the same trick here. Instead of fixing $root$ and then iterating through $left$, let's directly iterate through $left$ and notice its contribution. You'll realize that $indp$ only takes contribution from a subarray sum of the previous row of $outdp$. Hence, you can optimize using prefix sums. for left in [0, k]: remain = k - left: for right in [0, remain]: outdp[n][k] += outdp[n - 1][left]*outdp[n - 1][right] for right in [0, min(left - 1, remain)]: indp[n][k] += indp[n - 1][left]*outdp[n - 1][right] for right in [left + 1, remain]: indp[n][k] += outdp[n - 1][left]*indp[n - 1][right] The time complexity is now $O(N \cdot K^2)$.Code
•  » » » » 2 weeks ago, # ^ |   0 Hey, thanks a lot for the quick reply and detailed explanation! I think I understand your solution, though I think there's a small typo where outdp[n — 1][k] is supposed to be outdp[n-1][left]. Would you also be able to explain the DP transition in the editorial solution?
•  » » » » » 2 weeks ago, # ^ |   +4 It's the same as the transitions in my DP, except it does the heavy lifting through combinatorics (which isn't really required, it can be offloaded to DP).Notice that my $outdp[n][k] = {n + T - 1 \choose k}$. (We can see from combinatorics above, but we also chose to calculate it using DP. Let's call it as $f(n, k)$ from now on. If you don't want to compute it explicitly, just remove the $outdp$ matrix altogether. Then, you'll notice that the $dp[n][k]$ in editorial's solution is same as my $indp[n][k]$. Then, take my old transitions, for left in [0, k]: remain = k - left: for right in [0, min(left - 1, remain)]: indp[n][k] += indp[n - 1][left]*outdp[n - 1][right] for right in [left + 1, remain]: indp[n][k] += outdp[n - 1][left]*indp[n - 1][right] and let's remove all keywords that reference $outdp$ and use the combinatorics equivalent. for left in [0, k]: remain = k - left: for right in [0, min(left - 1, remain)]: dp[n][k] += indp[n - 1][left]*f(n - 1, right) for right in [left + 1, remain]: dp[n][k] += f(n - 1, left)*dp[n - 1][right] The editorial's transitions are written in a fancy way using $x \in [0, j)$ $l \in [j + x, k]$ But my transitions with left and right are doing the same thing, except I use Receiving DP while editorial uses Distributing DP.If you want to visualize how trees are computed using editorial's, you can just visualize how trees are computed using left and right variables above, and apply the same thing there. The crucial idea here is that since you are calculating indp, one of the child would go to outdp, and one would remain for indp, hence that's why you see the product of binomial coefficients with DP. If you understand the above DP, you should be able to understand editorial's DP as well. Let me know if anything specific that you're confused about.
•  » » » » » » 2 weeks ago, # ^ |   0 Yup, that makes a lot of sense now. Thanks a lot!
 » 3 weeks ago, # |   0 can anyone help me figure out why this solution is failing? I have tried a few different things but Im stuck and can’t seem to find the problem 277468507
 » 3 weeks ago, # |   0 Hi, what might have gone wrong here? (Problem C)-Thank you! void dfs(int node,deque adj[],deque&vis1){ vis1[node]=1; for(auto x:adj[node]){ if(vis1[x]==0){ cout<>n; deque v(n+1,0); for(int i=1;i<=n;i++){ v[i]=i; } deque adj[n+1]; queue> q; map,int> vis; for(int i=1;i<=n-1;i++){ q.push({i,i+1}); if(vis.count({i,i+1})){ continue; } while(!q.empty()){ char c='?'; int x=q.front().first,y=q.front().second; if(x>y){ swap(x,y); } q.pop(); if(vis.count({x,y})){ continue; } vis[{x,y}]=1; cout<>node; if(node==x || node==y){ adj[x].pb(y); adj[y].pb(x); } else{ q.push({min(x,node),max(x,node)}); q.push({min(y,node),max(y,node)}); } } } cout<<"! "; deque vis1(n+1,0); dfs(1,adj,vis1); cout<
 » 3 weeks ago, # |   0 Stuck with problem D still.I get it that we wanted to greedily build the sequence by picking the best element within the set of element with the right number of distinct values goes after it,What baffles me is that this is a changing quantity. Let's say the test case is arr: [5,4,2,1,3,5,2,1] we can easily construct cnt (cnt is the number of distinct values goes on or after it) cnt: [5,5,4,4,4,3,2,1] At this point it is fairly obvious that we should choose 5 so that -5 is lexicographically smallest, but then the cnt changes to arr: [5,4,2,1,3,5,2,1] cnt: [x,4,3,3,3,x,2,1] The change is that everything before the last occurrence of the removed element has to have their cnt subtracted by 1.I don't understand how can we solve this with a priority queue (or a bunch of them).
•  » » 3 weeks ago, # ^ | ← Rev. 5 →   +4 Video editorial for DYou count array changes in each iteration, yes. But there's a smart way to do a lazy update of this count array in amortized $O(n)$.You have already deduced that something strange happens when an element appears for the last time. So, let's mark all such indices in RED. We will mark all the other indices as green.arr: [5, 4, 2, 1, 3, 5, 2, 1]col: [G, R, G, G, R, R, R, R]It's easy to see that the size of the answer is equal to the number of red indices. What more can you infer? Consider the first red index. Every green index to the left of it will have the maximum number of distinct elements to the right. Hence, all of them are possible candidates for the 1st element. However, notice that since this is the first red index, this is your last chance to take one copy of the element that it's representing. So you need to greedily construct subsequence from the prefix ending at red such that the value of the final element selected is equal to the value of the red element.So, suppose you take 5, of course, the count array changes, but the color array gives you the required info to track this change. Specifically, all elements between the last chosen element and the second occurrence of the red index would have the maximum number of distinct elements to the right that is possible and they are the only possible candidates for the second element. (Why? Because if you go past the second red index without taking it, you will lose one element forever).The crucial idea here is to notice that it's a hard task to update each element in the count array, so we instead focus only on the updated values of the possible candidates, and we also don't need to keep track of the number of distinct elements to the right, we only care about candidates that have the maximal number of distinct elements to the right which are not yet taken. And this can be easily maintained by that color array I showed you.Code implementing this idea
•  » » » 3 weeks ago, # ^ |   0 Thanks, with your help, I finally get this accepted.I hope the code is clear — it is basically your idea by only keeping the valid candidates, no need to worry about the number of distinct elements of any other invalid ones.I think I might be able to simplify it a lot more if I delete the element more lazily, having to implement a priority queue that support deletion seems too much for a contest problem.
•  » » » » 3 weeks ago, # ^ |   +1 Sir, come to C++. We have priority queue that supports deletion :) It's calledset
•  » » » » » 3 weeks ago, # ^ |   0 Yay, it worked.
 » 3 weeks ago, # |   0 This is some text. I don't understand why I exceed time limit in problem B.Can someone please tell me? // this is code #include using namespace std; int main(){ int t; scanf("%d",&t); int num; for(int i=0;i=1;j-=2)printf("%d ",j); for(int j=2;j<=num-1;j+=2)printf("%d ",j); } printf("\n"); } return 0; } The rest of the text. close
 » 3 weeks ago, # |   0 Help needed in my C solution, according to the code as far as I can think my solution should have asked <15n queries but it isn't and is failing.someone please have a look,it's idea is somewhat similar to the editorial. Code:277462404
 » 3 weeks ago, # |   0 Here's an $O(n)$ stack solution for D.277484094The problem is very similar to the LeetCode problem 1081. Smallest Subsequence of Distinct Characters but this time we have two stacks, one for the even indices and odd ones.Then, when checking to pop and replace an element in one of the stacks, we can only do so if both stacks' top elements appear later on in the sequence.$^{\star}$There was a bit of annoying casework on the lengths of the stacks (the max stack length is always $\geqslant$ the min stack length) to get it all to work.$^{\star}$ slightly oversimplified, if both stack sizes are equal and we wish to replace the min stack's top, we don't need to check the max stack's top since it for sure comes before the min stack's top. The max stack case is handled similarly.
•  » » 3 weeks ago, # ^ |   0 I also solved that LeetCode problem before and noticed that it's very similar (unfortunately I didn't look at D during the contest because of C), but for some reason my implementation is getting "wrong answer 119167th numbers differ" on test 4, not sure if anyone had a similar problem
•  » » » 3 weeks ago, # ^ |   +1 Take a look at Ticket 17481 from CF Stress for a counter example.
•  » » » » 3 weeks ago, # ^ |   0 Thank you very much, found the issue very quickly from there — I didn't skip the value if it's already in the stack.
 » 3 weeks ago, # |   0 No general idea given for C, here's my suggestion: Usually half/middle indicates binary search applies to the problem.
 » 3 weeks ago, # |   +9 Please continue this General idea thing for the upcoming contests on codeforces, they are really useful.
 » 3 weeks ago, # |   0 how does the calculation of NCR(x+2^i−2,x) work for E1? how to find (x+2^i-2)! %p or (2^i-2)! %p when i is up to 500?
•  » » 3 weeks ago, # ^ |   +8 We can write C(x+sz-1,x) = fact[x+sz-1] * ifact[x] * ifact[sz-1] = sz*(sz+1)...*(sz+x-1) * ifact[x]
•  » » » 3 weeks ago, # ^ |   0 sz can be up to 2^500??
•  » » » » 3 weeks ago, # ^ |   0 Ya but we only need sz%p which can be calculated using binary exponentiation
•  » » » » » 3 weeks ago, # ^ |   0 I just tried to understand the formula and it made much more sense now. Thanks!
 » 3 weeks ago, # |   +3 Finally solved C after 10 wrong submissions!
•  » » 3 weeks ago, # ^ |   0 congrats
 » 3 weeks ago, # |   0 I could not understand the problem C.
 » 3 weeks ago, # | ← Rev. 2 →   0 MisukiI think in E2, the first condition of the last picture's transition (the second case in counting) needs to be:$L' > L > R'$ and $L' > L > R$
•  » » 3 weeks ago, # ^ |   0 Thanks you, I've fix it. the second one is $L' \ge L + R$ because the nature of the operation (i.e. whenever you add $1$ to a node, you would also add $1$ to its ancestors)
 » 3 weeks ago, # |   0 My solution for C:https://mirror.codeforces.com/contest/2001/submission/277413728Idea: root the tree at 1, find the path from all nodes to 1. Mark all nodes that have found the path to 1. Let c = query(a,b), if c==a then there is a is connected to b; else recursively query(a,c) and query(c,b), then mark a and mark b. If a and b having already been marked, that mean we already found the path from 1 to a and from 1 to b, there are already a path from a to b, so we don't need to find again.
 » 3 weeks ago, # |   0 277619651this is my submission for D. Can anybody help in finding the issue. My approach is very similiar to that of the editorial. I iterate over the pairs (last index of x, x), and maintain a multiset of elements of "a" between any two pairs, greedily picking max or min. (WA on tc3)
•  » » 3 weeks ago, # ^ |   0 Take a look at Ticket 17483 from CF Stress for a counter example.
•  » » » 3 weeks ago, # ^ |   0 Thanks a lot
 » 3 weeks ago, # |   0 can anybody tells me if there are any problems?wa3,i am really sick of it ~~~~~ int ask(int x, int y) { cout << '?' << ' ' << x << ' ' << y << endl; cout.flush(); int res; cin >> res; return res; }void dfs(int x, int y) { if (x == y)return; if (mp[{x, y}])return; mp[{x, y}] = 1; int ans = ask(x, y); if (ans == -1) { return; } if (ans == x || ans == y) { res.push_back({ x,y }); } else { dfs(x, ans); dfs(ans, y); } return; }void solve() { mp.clear(); int n; cin >> n; for (int i = 2; i <= n; i++) { dfs(1, i); } cout.flush(); cout << '!' << ' '; for (auto item : res)cout << item.first << ' ' << item.second << ' '; cout << endl; mp.clear(); res.clear(); }~~~~~
 » 3 weeks ago, # |   0 How to efficiently calculate combinatorics in E1? I thought it takes 2^i operations to calculate
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   -8 You will see we can calculate it with $O(X)$ if you see submissions or official code.
 » 3 weeks ago, # |   0 D is a tough problem but Shayan implementation is so clean and easy to understand! Thank you for your video tutorial!
 » 3 weeks ago, # | ← Rev. 2 →   0 Can someone help with this submission failure for problem D? 3rd test case is failing: wrong answer 7289th numbers differ - expected: '1', found: '2'https://mirror.codeforces.com/contest/2001/submission/277681400
•  » » 3 weeks ago, # ^ |   +1 Take a look at Ticket 17485 from CF Stress for a counter example.
 » 3 weeks ago, # |   0 My solution for D gives me tle, but I don't think I should get tle277711569
 » 3 weeks ago, # | ← Rev. 2 →   0 Help Needed with Problem D : Longest Max Min Subsequence (Codeforces Round 967 Div. 2)Hi everyone,I'm currently working on Problem D : Longest Max Min Subsequence from Codeforces Round 967 (Div. 2). You can find the problem here (https://mirror.codeforces.com/contest/2001/problem/D?mobile=true ).I've been stuck with a "Wrong Answer" on test 4. You can check out my submission here(https://mirror.codeforces.com/contest/2001/submission/277854508).The checker log says that the 79924th number is different than expected, with my code outputting '4' instead of the expected '3'. Would appreciate If someone could point out the bug or find the test case where my code is failing .
 » 3 weeks ago, # |   0 I am getting WA on test case 3 void query(int i,int j,vvi &ans,map &check){ if(check.find({i,j})!=check.end()) return; check[{i,j}]=1; cout<<"? "<>temp; cout<>n; map check; vvi ans; for(int i=2;i<=n;i++) query(1,i,ans,check); cout<<"!"<<" "; for(auto i:ans) cout<
 » 3 weeks ago, # |   0 why this solution for C is giving TLE link code#include using namespace std; #define int int64_t signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tt=1; cin>>tt; while(tt--) { int n; cin>>n; // vectorg[n+1]; vector>st2; int cnt[1005][1005]; memset(cnt,0,sizeof(cnt)); for(int a=1;avis(n+1,0); for(int b=a+1;b<=n;b++) { int cur=b; while(!vis[cur]) { vis[cur]=1; // if(a!=cur) cout<<"? "<>num; if(num==a) { if(!cnt[min(a,cur)][max(a,cur)]) st2.push_back({min(a,cur),max(a,cur)}), cnt[min(a,cur)][max(a,cur)]++; // break; } else cur=num; } } } cout<<"! "; for(auto it:st2) cout<
 » 2 weeks ago, # |   0 It's a great solution and tutorial!! Thank you very much!!
 » 2 weeks ago, # | ← Rev. 3 →   0 E2 editorial is impossible to understand even if you've already solved the problem before. (or it's just me being weak)UPD: nah, it's ok.
»
2 weeks ago, # |
+1

### getting wrong ans in tc3 at last tc..can anyone explain whats wrong in this method bcoz that tc is at very end so its hidden!

#include<bits/stdc++.h>
using namespace std;
#define int long long int
const int mod = 1e9 + 7;
bool cmprt(pair<int,int>& a, pair<int,int>& b)
{
if(a.first!=b.first) return a.first>b.first;
else return a.second<b.second;
}
bool cmplft(pair<int,int>& a, pair<int,int>& b)
{
if(a.first!=b.first) return a.first>b.first;
else return a.second>b.second;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif

int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<int>v(n);
for(auto &it:v) cin>>it;
vector<int>dist(n);
unordered_set<int>s;
for(int i=n-1;i>=0;i--)
{
if(s.find(v[i])!=s.end()) s.erase(v[i]);
dist[i] = s.size();
s.insert(v[i]);
}
int len = s.size();
deque<pair<int,int>>dq[len+1];
for(int i=0;i<n;i++)
dq[dist[i]].push_back({v[i],i});
unordered_set<int>taken;
int takemxi = 1;
int cur = -1;
vector<int>ans;
for(int i=len;i>=0;i--)
{
while(!dq[i].empty())
{
if(takemxi)
{
sort(dq[i].begin(),dq[i].end(),cmprt);
while(!dq[i].empty() && (taken.find(dq[i].front().first) !=taken.end() || dq[i].front().second<=cur))
dq[i].pop_front();
if(!dq[i].empty()){
ans.push_back(dq[i].front().first);
taken.insert(dq[i].front().first);
cur = dq[i].front().second;
takemxi = 0;
}
}
else{
sort(dq[i].begin(),dq[i].end(),cmplft);
while(!dq[i].empty() && (taken.find(dq[i].back().first) !=taken.end() || dq[i].back().second<=cur))
dq[i].pop_back();
if(!dq[i].empty()){
ans.push_back(dq[i].back().first);
taken.insert(dq[i].back().first);
cur = dq[i].back().second;
takemxi = 1;
}
}
}
}
cout<<len<<endl;
for(auto &it:ans) cout<<it<<" ";
cout<<endl;
}
return 0;
}