### DeMen100ns's blog

By DeMen100ns, history, 2 weeks ago, Before the round starts

1713A - Traveling Salesman Problem

Hint 1
Hint 2
Tutorial
Solution
Feedback

1713B - Optimal Reduction

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

1713C - Build Permutation

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Solution
Feedback

1713D - Tournament Coundown

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

1713E - Cross Swapping

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

1713F - Lost Array

Hint 0
Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback Tutorial of Codeforces Round #812 (Div. 2) Comments (211)
 » so quick ^_^
•  » » I think problem D has the I/O time issue.
 » Super fast editorial.
 » Very quick editorial! thank you!
 » so fast
 » so quick，Thank you
 » Anyone got stuck on pretest 2 B? Or am i the only one:(
•  » » 10 days ago, # ^ | ← Rev. 2 →   me too
•  » » me too,Steve .
•  » » » ok, generic dude programming stock image
•  » » me 2
•  » » I got stuck too, but then I tried random graphs like input where I found this, n=10,1 1 1 2 2 3 2 2 3.
•  » » » i got the right idea but it wasn’t complete, instead of using max prefix and suffix array, i just compare a[i] to min(a[i-1], a[i+1]) for the whole array (except the first and the last element) so that’s why i didn’t got AC:(
•  » » » » tf is your dp
•  » » » » » do you mean dynamic programming? if so i didnt use any dp at all, heres my submission if you wanna check out, i only loop through the array and make simple checks :')
•  » » » » i corrected it by noting the slop
 » Super fast editorial
 » Thanks for fast editorial, I really enjoyed the contest!
 » Way more balanced than the last contest.
 » wow editorial came faster than system testing thanks
 » I think problem D has the I/O time issue.
•  » » Yes, and it is too hard for Python users.
•  » » 10 days ago, # ^ | ← Rev. 2 →   Most of the Java users had time limit issues.
 » Fast editorial!Thank you!
 » 10 days ago, # | ← Rev. 2 →   The solution to D is so goated. Just making a simple observation cuts the number of queries just enough so you can pass TC.First time it wasn't binary search lol. Awesome problem!
•  » » really? it's the first time you're seeing an interactive problem that isn't a binary search problem?
•  » » But I think it is too easy for a div2 D problem,and if it is div2 C,it may be a bit hard and strange...
•  » » » The ratings is a little bit different than expected. We expect C to be 1500, D 1900 and E 2200, but luckily it is still balanced.
•  » » » » Yeah C is harder than D imo :p But it is still a really good contest! (Although I didn't find my mistake on problem E till now XD
 » speed++
 » 167303250 Why does this fail on time, same logic is used as in the editorial. Thnx for the super fast editorial.
 » Really fast editorial, good organization, thanks a lot;)
 » If the ML for C was 512 mb instead of 256 mb, some fun flow solutions could have passed. What was the point in cutting off O(Nsqrt(N)) Dinic algo solutions? It is not like that's super popular.
•  » » I did an overkill, but my MBPM solution passed — 167261911 I have also added library reference in code.
•  » » » Can you explain what MBPM is?
•  » » » »
•  » » » » » 7 days ago, # ^ | ← Rev. 3 →   Thank you. Can you explain how your algorithm works?
•  » » » » » »
•  » » Can you provide me with good resources to learn MBPM?
•  » » » I learnt MBPM by referring to many videos on YouTube. Other than that I haven't used any other resource. :D
•  » » » USACO guide has some good resources for flows
 » 10 days ago, # | ← Rev. 3 →   These editorials get uploaded faster than my rating drops
 » Fastest ever seen ~ Appreciate !
 » Question D did not add endl when outputting, which led to debug for a long time. I felt that the input n of the last game did not use cin to set off each other. :C
 » fast solutions , a good round xd
 » Successfully get Wrong Answer in Problem C using the right idea，:( It's time for more training!
 » Thx for the fast tutorial.:)
 » I like this round :) Fast editorial, that's great XD
 » 10 days ago, # | ← Rev. 2 →   Question: in problem D, if you follow the solution, won't the number of queries be 3/4 2^n, since you divide the number of participants by 4 every 3 queries? I thought of this solution too but discarded it due to this thought.
•  » » It is 2 queries, not 3.
•  » » » Oh right, I forgot... I almost got it, but didn't make the second query, only divided it by 2 and got WA
•  » » » 10 days ago, # ^ | ← Rev. 2 →   I have done D the exact way mention in editorial but the difference was i am taking 2 and 3 participant instead of 1'st and 4'th participant but it gave me WA. Can you please share why only taking 1'st and 4'th participant give AC? here is my solution 167295468
•  » » » » 10 days ago, # ^ | ← Rev. 3 →   well you don't have exactly same logic) for example if ans == 1 you suppose that i1 and i2+1 are the winners of their pairs, but is i2+1 always the winner? think of what this might lead to hintask(smth, i2+1) will always be 1 on the next querry
•  » » Going with groups of four at each level: you select 2 out of 4 players based on 1 query. And in the end you do one query to pick the winner.So 2^(n-2) queries required to remove the first half of the players. Or 1+2^(n-1) total. 1+2^(n+1)/4 is less than the limit in the problem.
 » Thanks for the quick editorial! I really like problem D. And if I don't get FST, it seems that I can reach Master :)
 » Such a creative way of applying DSU in E! Nice DSU practice problem
 » Can any tell, for problem B, why the condition if(a[i] < a[i+1] && a[i] < a[i-1])print NO , is insufficient.
•  » » For ex in test:5 1 1 1 5Your condition would say that this array is ok, but in fact we need to do 1 + 4 + 4 = 9 operations here, while we could've sort it like1 1 1 5 5And we would've need only 5 operations
•  » » The input array can have duplicates (eg [2,1,1,2] is NO).
•  » » you can try this : 5 2 2 2 2 5
•  » » 5 2 2 3
•  » » 10 days ago, # ^ | ← Rev. 3 →   loop is from i = 1 to i = n-2. Basically, my idea was, that if there is a valley we can improve the result. PS: My bad, faulty implementation.
 » 7 days ago!!!
•  » » 10 days ago, # ^ | ← Rev. 2 →   We saved it in a draft an only public after contest, like the announcement...
 » 10 days ago, # | ← Rev. 2 →   The problem D is so great!I have never seen a so ingenious problem!
 » Problem D is one of my favourite interactive problems of all time!Small issue in the editorial — I'm unable to open the links to the problems [such as when clicking on 1713F — Lost Array]. It shows access denied.
•  » » Issue fixed, thanks for your report.
 » I think D is such a beautiful problem. Thanks for setting this problem hehe
 » Problem D. You don't need to do the 2nd check on each level, just push two possible winners to the next level. Total queries' count: 2^(n-1)
•  » » I think it's 2^(n-1)-1 comparisons.
•  » » » No, 2^(n-1). The last one is needed to get a winner.
•  » » » » If n=2 then there are 4 people in the bottom layer, then 2 in the second, then 1. Which means you need 2+1 comparisons (2 in bottom, 1 in second). This would give 2^n — 1. If not, what's wrong with this reasoning?
•  » » » » » You only need 2 comparisons for n=2 (4 people): 1st query to filter out 2 people, 2nd query to choose out of 2 remaining
 » lol 7 days ago :))
 » so fast editorial! Thank you
 » Thank you for the fast editorial ^_^ Waiting for the system testing to start.
 » https://codeforces.com/contest/1713/submission/167305017 Getting TLE on D but can't understand why, or this solution's complexity is not O(1<
 » A great contest :) Problem D is so great!!
 » Did my submission for D get WA due to MLE? https://codeforces.com/contest/1713/submission/167297638
•  » » i guess, its unexpected verdict — your code doesn't fit in the required number of queries, and when your code gets -1 like an answer, it must terminate, otherwise you can get any verdict cause interactor stops to read your output
•  » » » Thanks for the advice! I often get confused with the verdict of the interactive problem.
•  » » Take a look at Ticket 15999 from CF Stress for a counter example.
•  » » » Thanks!
 » I could almost have finished problem E !!! So sad:(
 » I like problem D. It's very awesome problem.
 » D is such a genius problem orz orz orz orz orz
 » This is how early all contest tutorials should be uploaded.
 » 10 days ago, # | ← Rev. 2 →   [Deleted]
•  » » Not really, but std::endl does forcefully flush your output. I think maybe you meant this instead?
•  » » » Even without std::endl, it flushes. endl force flushes even with fast io turned on
•  » » » » Oh wow. That's good to know!
 » 10 days ago, # | ← Rev. 2 →   Here's the infamous test case on test 2 on problem D: 3 1 0 2 0 0 1 0 3 
 » Your are faster than me ;)
 » 10 days ago, # | ← Rev. 2 →   Problem D is so good!
 » Amazing speed for editorial，thank you so much.
 » Can anyone tell me why I get wrong answer in E 167313557?
•  » » Take a look at Ticket 16003 from CF Stress for a counter example.
 » 10 days ago, # | ← Rev. 2 →   For problem B, isn't it enough to check if the sequence looks similar to a mountain or not? I mean by a mountain that it increases then decreases, or do one of them only (increases only or decreases only).This is my submission but in no vain I got WA.https://codeforces.com/contest/1713/submission/167261187The weird is that my friend's submission effectively does the same but passed the pretests.https://codeforces.com/contest/1713/submission/167257143
•  » » Take a look at Ticket 16004 from CF Stress for a counter example.
•  » » When you use return in your if statement, there can still be some values left to input and you're skipping them.Here is your corrected solution: 167318731
•  » » » ra pro xar
•  » » » That is the faulty logic in my code. Thanks!
 » Auto comment: topic has been updated by DeMen100ns (previous revision, new revision, compare).
 » here are the video Solutions for A-D.
 » A-E video Editorial for Chinese：Bilibili
 » 10 days ago, # | ← Rev. 2 →   After, reading the editorial for D, Hell yeah, it's kind of an observational problem and interesting as well. I wasted most of the time thinking of doing some kind of binary search, {i had a bad habit of relating every interactive problem with binary search LOL}.
 » Hi. I need one help in D. I submitted the same solution with just a small interchange. But I couldn't get why the one that is failing is wrong. Can anyone help? Wrong Submission: https://codeforces.com/contest/1713/submission/167301158Correct Submission: https://codeforces.com/contest/1713/submission/167315386Difference: •  » » Consider the case when n = 3, # of wins for each contestant = [0, 1, 0, 3, 1, 0, 2, 0]. After first iteration, the contestants left is [2, 4, 6, 7]. i.e. # of wins = [1, 3, 0, 2]. For your next iteration, you'd compare contestants 2, 6 for your wrong submission, which will result in a wrong solution.
•  » » » In more detail: if you make a query about the 1st and 3rd contestant just like in the tutorial:If you recieve a 0: that means 2nd and 4th are guaranteed to have won the 1st round and moved on to the next stage.If you receive a 1: that means 1st is guaranteed to have won the 1st round and moved on to the next stage, while 2nd and 3rd are guaranteed to have been eliminated at some point (4th is undecided, so we keep them in the array)If you receive a 2: that means 3rd is guaranteed to have won the 1st round and moved on to the next stage, while 1st and 4th are guaranteed to have been eliminated at some point (2nd is undecided, so we keep them in the array)Because we want to ask about people who actually made it to the current stage, order matters: in case you receive a 2, you should record it as [... 3, 2 ...] so that the next step asks about the 3rd player
 » alot of mathematical problems
 » Why is this giving TLE/ILE for problem D? I have used the same approach as given in the Editorial.My Submission..
•  » » You forget to handle when (sz(curr)==1). look at this submission 167324780
•  » » » Yeah Thanks :)
 » Not able to understand tutorial for problem C can anybody explain with some little example please.
•  » » Try manually writing solutions for first few numbers, like upto n=10, You will observe a pattern where the last few numbers are constructed such that they a[i]+i becomes equal to the perfect square which is >=(n-1). and the problem gets reduced to a smaller problem where the same pattern is continued. Refer to my solution if it helps. 167261412
•  » » I think problem C can be solved by more elegant way of filling in numbers. Your text to link here...
•  » » 9 days ago, # ^ | ← Rev. 3 →   First, an obvious observation: $(a - i) + (b + i) = a + b$. Yes, this is obvious and might seem silly, but just keep this in mind.Suppose we have $n = 11$, so the permutation needs to range from $0$ to $10$. Start with 10. What is the next square we can reach by adding something to 10? Well, the next square is 16, which we get from adding 6, i.e., 10 + 6 = 16. So for index 10, we can place the value 6. If the value 6 works for index 10, then the value 7 should work for index 9, because $9 + 7 = (10 - 1) + (6 + 1) = 10 + 6 = 16$. In fact, we can keep going as follows:$10 + 6 = 16$$9 + 7 = 16$$8 + 8 = 16$$7 + 9 = 16$$6 + 10 = 16$At this point, we have mapped indices $6$ to $10$ with a permutation of values from $6$ to $10$. We are now left with the smaller problem of mapping indices up to $5$, which we can solve the same way.More generally, if your last value $L$ can reach a square by adding $k$ (for $k \leq L$), i.e., if $L + k$ is a square, then we can assign indices from $k$ to $L$ with the values $L$ decreasing down to $k$. We can now use $k - 1$ as our new $L$ and repeat until we eventually complete the case of $k = 0$.(note that it's always possible to assign a value for index $L$ because there must be a square in the range $[L, 2L]$. However, even if you didn't realize this, writing a condition to print -1 if the next square is larger than $2L$ would still be accepted, since the condition would simply never be satisfied)
•  » » » Thank you so much for this explanation
 » How would A be solved if the boxes weren't limited to the x and y axes?
•  » » I believe the problem becomes NP-hard, even with Euclidean distances and integer coordinates. What this means is that even with coordinates between $[-100, 100]$, it is believed that the most efficient algorithm would still fail the time constraints. There are some decent approximation algorithms though (only because we're considering Euclidean distances), but an exact answer cannot be found efficiently.FYI, the Traveling Salesman Problem is a very famous problem in a class of known difficult problems (NP-complete).
 » I really appreciate the effort put into the "Before round starts" section. I wish in the future, more people authors would do it. It was really enjoyable to read and it made me laugh a couple of times
 » Why does the hint in 1713D - Отсчет турнира say that Problem D Hint 1 Spoilers$2^{n-1}$ solutions can't pass? Doesn't the suggested solution make more queries? Either I haven't understood the maths behind the number of queries or I've just been baited and thought my solution was wrong as I was reading the hints.
•  » » My guess is that this is a typo that meant to say $2^n - 1$. The naive approach of checking every matchup would require $2^n - 1$ queries. Furthermore, if we assume each query as having only two possible outcomes, then an adversary argument would yield a lower bound of $2^n - 1$. One who is aware of this argument may not have realized that the assumptions do not hold here, e.g., it requires $n - 1$ comparisons to find the maximum/minimum from $n$ values, even if the comparisons are three-way, because the adversary can choose numbers such that equality is never returned, but the tournament setting does not provide such a luxury for the adversary (there must be a lot of equalities). Anyway, I think the point is that one might naturally try a $2^n - 1$ solution, thinking that this is the best that could be done, so the hint is to nudge the reader into revisiting their assumptions and realizing that equality is necessary and can be abused.
 » For problem B, i found that any value in the array cannot be less than both its neighbours, otherwise when we decrease the whole array by 1, we will end up with 'holes' and we will have to do more operations to complete the remaining parts.So i did this : if a[i] < a[i-1] -> the array is decreasing.if the array is decreasing AND a[i] < a[i+1], print "NO"It seems simpler to me
 » cool problems had fun while solving
 » Without recursion solution of problem C Solution#include "bits/stdc++.h" using namespace std; int getSquare(int n) { int x = sqrt(n); if ((x * x) == n) return n; return (x + 1) * (x + 1); } void solve() { int n; cin >> n; int close = getSquare(n - 1); vector ans(n); map mp; int notposs = false; for (int i = n - 1; i >= 0; i--) { if ((close - i) < n and mp[close - i] < 1) { mp[(close - i)]++; ans[i] = close - i; } else { close = getSquare(i); if (mp[(close - i)] > 1) {notposs = true; break;} i++; } } if (notposs) cout << -1 << endl; else for (auto &ele : ans) cout << ele << " "; cout << endl; } int main() { int T = 1; cin >> T; while (T--) { solve(); } return 0; } 167326787
 » all those hints and spoliers make it hard to read
•  » » How comes?Hints done right is a nice idea. Hints done the way they're done are not useful, but I fail to see how they can make it hard to read.
 » 10 days ago, # | ← Rev. 2 →   I wonder why no one has written about the most intuitive (IMO) way of solving C yet.Let's generate all perfect squares that is less than $2n$. Then, iterate from $n-1$ to $0$ and for each $i$, find the largest perfect square $x$ such that ${0 \le x - i < n}$ and index ${x - i}$ is not used. So our answer for index ${x - i}$ is $i$;Total complexity: $O{(n\sqrt{n})}$.https://codeforces.com/contest/1713/submission/167282216I don't know how to prove its correctness though, would be nice if anyone does.
•  » » 9 days ago, # ^ | ← Rev. 6 →   Suppose you found a position $k$ such that for the biggest index $i$ you haven't used (initially $i = n - 1$) the sum is equal to a perfect square, i.e $k + i = pr[j] \iff k = pr[j] - i$ for some $j$. Then I argue that for the whole range $[k, i]$ your code assigns them all to $pr[i]$ (we will later see why $k\leq i$ and why we can use all indices and positions in $[k,i]$). Since in the next iteration index $i^{(2)} = i - 1$ will get matched with position $k^{(2)} = k + 1$ (keeping the sum the same), then $i^{(3)} = i - 2$ with $k^{(3)} = k + 2$ and continuing... $i^{(i-k+1)} = i - (i - k) = k$ and $k^{(i-k+1)} = k + (i - k) = i$.So now the problem is identical given as input $n' = k - 1$. Since we have used all indices in $[k,i]$ and all positions in $[k,i]$. What I didn't mention (but was essential for the above proof to work) was that we had used everything $>i$ (all positions and all indices) and nothing else, which obviously happens in the start and as we saw also happens after the first pile of iterations. Also you are guaranteed to find a perfect square to match with an index because of the property editorial mentions. (for a given $x$ there is a perfect square $y$ such that $x\leq y\leq 2x$)Interestingly, that's essentially the editorial's logic but you start searching from the biggest perfect squares, which also means the respective range $[k,i]$ will be smaller if there are more than 1 perfect square in range $[i,2i]$.
•  » » » Yeah, both approaches are doing the same thing, except they choose a different square to start filling out the suffixes (in the same manner). One who is able to prove the correctness of the $O(n\sqrt{n})$ approach would likely also realize that choosing the smallest square that fits the biggest index would be better (since it's also covered by the same proof of correctness), which leads to the editorial solution, which finds the square faster for an overall linear-time complexity.
•  » » 9 days ago, # ^ | ← Rev. 2 →   I did this as well167266697
 » This is one of my favorite Div. 2 rounds in a long time--the problems felt very elegant, and I particularly enjoyed the process of solving C, D, and F. (I think D took me longer than it possibly should have, but I found it somewhat surprising that the winner could be determined without effectively simulating the tournament, and figuring out how to do so was very satisfying.) The conflict with the TCO Wildcard round was unfortunate, since if I didn't have to leave midway through I think I would have had a solid chance of finishing F, but I very much enjoyed the time I was able to spend participating in the contest, and I'd love to see the authors continue writing problems.As a bit of constructive criticism, E felt a bit standard to me--the two general ideas (transforming the problem into a graph coloring task and then solving that graph coloring problem using DSU) felt very familiar to me. Overall, though, this is a minor critique, and it didn't seem like the problem was known to too many Div. 2 competitors.
•  » » Would you be able to link some problems/resources related to the solution for E? I've never seen this technique before, and searching "graph coloring DSU" didn't lead to anything useful either...
•  » » » I think "2-sat" can help.
•  » » » » Yeah, you're right! This is basically 2-sat with the implicit graph having all bidirectional edges, so you can use a DSU to check for SCCs. Thanks!
 » I think the code of B problem need to use long long.
•  » » Ignore the comment.
 » The implemention of E is so clever!
 » your solution for problem F has a WA :D
•  » » Thanks for report, this is a mistake, i'll fix it now
 » Great round! E was one of my favorite problems I've seen:)
 » About the solution of problem E. Why if par[i] > 0 then the operation k=i should be performed? (sorry my English is not good)
•  » » Because as I have mentioned in the tutorial, $par[u]=p$ if $2$ operations $k=u$ and $k=p$ should have the same state. Suppose $p$ is the root of the $ith$ component, because $par[i] > 0$ and we have performed the operation $k = p$, we should perform the operation $k = i$ too ($2$ operations $k = p$ and $k = i$ should have the same state).
•  » » » thanks a lot :)
 » Please help me with the Unsolved mystery. QAQI can't understand why my first submit of D can't pass test 3. I loaded the data of test 3 after contest, there is nothing wrong with it, local. What does "wrong answer ? or ! expected (test case 1)" means? I've reconstructed my code using scrolling array in contest, but the logic is nothing differerent, but it passed.This is my WA3 code durning the contest.https://codeforces.com/contest/1713/submission/167282903This is debug code(with output & input).https://codeforces.com/contest/1713/submission/167344378This is passed code with scrolling array.https://codeforces.com/contest/1713/submission/167298523
•  » » in WA3 code, in main function, maybe you forget '!' when output the answer for case a.size()==1
•  » » » Oh you're right. Thanks! so sad, why i can make such mistake):
 »  I cannot believe that the two comments are from the same person.
 » Auto comment: topic has been updated by DeMen100ns (previous revision, new revision, compare).
 » Spoiler20 minutes had passed long ago and I still haven't responded yet
 » 9 days ago, # | ← Rev. 2 →   https://codeforces.com/contest/1713/submission/167349436It got accepted but I don't have proof why it worked ,can anyone help me with proof ?
 » Solution LINKApplied logic is similar a[i-1]>a[i]
•  » » it is $a[i] > a[j] < a[k]$ for $i < j < k$, not $a[i-1] > a[i] < a[i+1]$
•  » » » sorry i made mistake while typing.. when i am using upper_bound in code its doing the work of a[k] if any number is greater than a[j] from the (j+1)th index to the end and i am checking this condition whenever a[j-1]>a[j] because whenever this happens we can check as one bigger value is in left side, if its present then the answer is wrong.My intuition was to get atleast one greater number in left side and atleast one greater number in right sideThank You for your reply, plz check the code
•  » » » » 8 days ago, # ^ | ← Rev. 2 →   You can't use upper_bound if the array is not already sorted :)
•  » » » » » ohhh blunder!! Thanks for the reply
 » Thanks for fast editorial ^_^
 » Can the solution for B also be implemented using mountain array, i mean if the permutation is a mountain array(including sorted), it will have least number of operations?
•  » » 9 days ago, # ^ | ← Rev. 2 →   Yup. The requirement for optimality is that the array can be partitioned into a non-decreasing prefix followed immediately by a non-increasing suffix. Either of the two parts can be empty, which leads to the sorted and reverse-sorted array respectively, but having both as non-empty would yield the mountain array. The required invariant is that it must always be possible to cover all non-zero elements in a single operation, which means the 0 values only accumulate at the prefix and/or suffix of the array.
•  » » » Yes, exactly.
 » Simple Solution to Problem-C :
 » Here is another code for 1713C — Build Permutation Code#include using namespace std; #ifdef LOCAL #include "algo/debug.h" #endif const int MAX_PERFECT_SQUARE_BASE = 1e3; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt; cin >> tt; while (tt--) { int n; cin >> n; vector ans(n, -1); for (int i = n - 1; i >= 0; --i) { for (int j = MAX_PERFECT_SQUARE_BASE; j >= 0; --j) { int diff = j * j - i; if (diff >= 0 && diff < n && ans[diff] == -1) { ans[diff] = i; break; } } } for (int i = 0; i < n; ++i) { cout << ans[i] << " \n"[i == n - 1]; } } } 
 » B can be solved in other way with two steps: Squeeze an array (remove consecutive equal elements, leave 1) Check if $a_{i-1} > a_i < a_{i+1}$
 » 9 days ago, # | ← Rev. 2 →   thank you for the fast Editorial.
 » guys i need your help! in 1713D — Tournament Coundown my code has no output in test 3 while i check in my vs that the code is work whats worng? https://codeforces.com/contest/1713/submission/167304528
•  » » 9 days ago, # ^ | ← Rev. 2 →   May be any kind of segmentation fault.
•  » » » i was too stupid to find that
•  » » » » hehe
•  » » Take a look at Ticket 16005 from CF Stress for a counter example.
•  » » » Jury picked n as: 2Participant did not ask any queries.I broke down TAT
 » in the C solution i don't understand this part: int s = sqrt(2*r); s *= s;
•  » » you can consider that is a ceil function
•  » » » Thanks)
•  » » That line means declaring a variable $s$ which is the largest perfect square number not exceeding $2 \times r$.
 » 9 days ago, # | ← Rev. 5 →   i found another way to solve D in only 2^(n-1) queries:)first we ask about the players 1 3, we will have 3 Possible answers: 1 : which means 1 won the first game and since 3 can't be the last winner it dosen't matter if he won the first round or not so we will assume that 4 won which means there will be a round where 1vs42: same as the above but this will lead to 3vs20 : 1 and 3 lost the first round and there will be 2vs4we do the same from 5 to 2^n and now we removed half the players and we do that again :)here is the code https://codeforces.com/contest/1713/submission/167278880
•  » » This solution is wrong. Unfortunately our tests were not strong enough to kill it.
•  » » I suppose, the below numbers of wins will hack your solution: 2 0 0 1 3 0 1 0 2 0 1 0 4 0 1 0
•  » » » I tried them, they does not
•  » » » » Yeah, you are right. Nice trick on x==2. It does matter!!
•  » » » » » Thx, i first tried it without it but i got wa so when i changed it it work
 » Hi, is there any specific strategy you use when approaching problems like yesterday's C? I got stuck with an R->L constructive solution, and wasn't able to understand why exactly it was wrong during the contest.
 » There is a typo in hint 1 for problem D.
 » Hi, my solution for B is giving me runtime error, although if I start debugging everything seems fine. I thank in advance everyone who wants to help.Good morning!https://codeforces.com/contest/1713/submission/167403306btw it says that the error may be on line 35, but it says core dumped after g[p — 1] has reached a size of 4 and i process two queries.
•  » » Take a look at Ticket 16012 from CF Stress for a counter example.
 » can anyone please explain the proof why always answer exists for problem c? by taking an example
 » My solution for B was to calculate in O(n), the number of operations needed to make the input array all 0's. If this was equal to the maximum element, then the answer is Yes (the maximum element in the array gives you the minimum number of moves of one of its permutations). Otherwise, the #of operations has to be greater, so the answer is No. To get the number of operations itself, I tried "extending" operations from elements before me. EX: If element i is a 5 and element i-1 is a 7, then I can extend 5 operations from the previous element for free. If element i is a 7 and element i-1 is a 5, however, then I can extend 5 operations from the previous element for free, but I'll need 2 more operations.167242256
 » How dsu is applied in problem E. Can anyone explain me from basics? My mind is completely out of that negative numbers/parent idea. Thanks in advance!
•  » » 9 days ago, # ^ | ← Rev. 3 →   You can see all the elements of the diagonal as nodes in a graph. For each of these elements, you can either leave them in their original position, or "flip" them. Each element of your diagonal has 2 possible states, so your graph will have 2*n nodes (for a n*n matrix).Then, the edges between those nodes represents constraints. Consider this matrix: 3 3 1 2 1 1 3 1 3 2 3 2 2 3 3 1 Here, you would want to swap a and a, So that means you either want k0 flipped, or k1, but not both (k0 being the first diagonal element, and k1 the second). So in your graph, you would have an edge between k0 and k1', AND k1 and k0' (k0' representing the flipped state of k0).You would store these relationships using DSU, and only add constraints if ki and ki' would not end up in the same tree, because a node cannot be flipped and 'not flipped' at the same time. Try to draw the graph and the constrains by hand, it helped me understand the problemHope it makes more sense.
•  » » » Thanks a lot! Now , I understood the approach. This was really a nice question.
•  » » » 6 days ago, # ^ | ← Rev. 4 →   thanks
 » Optimal reduction( B ) can be done using single iteration over the entire array, and with O(1) space complexity. This solution is too complex.
•  » » Wait B can be done in O(1)? Elaborate further pls
•  » » » $O(1)$ space complexity. The best possible time complexity is $O(n)$.
 » 8 days ago, # | ← Rev. 2 →   Here is a much simpler way for 1713B — Optimal Reduction #include using namespace std; #ifdef LOCAL #include "algo/debug.h" #endif long long f(vector a) { long long res = a; for (int i = 1; i < int(a.size()); ++i) { res += max(0, a[i] - a[i - 1]); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt; cin >> tt; while (tt--) { int n; cin >> n; vector a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } long long x = f(a); long long min_x = *max_element(a.begin(), a.end()); cout << (x == min_x ? "YES" : "NO") << '\n'; } } First, let's find f(a) and then find that array's minimum f possible permutation. It can be proved that the minimum possible f is equal to the maximum element of the array. (We know that we must have at least x operation (max element). Now we give an example for that -> sort the array in reverse order and then do f on it)Now we have found the lowest f of permutations of a.if it's equal to f(a) then all of the other permutations are greater or equal to f(a) and the answer is YES otherwise NO.
 » I've updated the new tutorial for B. The old tutorial is super trash that the idea is simple yet i tried to make everything so complicated.Sorry for the inconvenience!
•  » » 7 days ago, # ^ | ← Rev. 2 →   I wanna share my B solution, I think it can be interesting for someone.Let's find the $f(a)$, it's equal to $\lfloor \frac{a_1 + a_n + abs(a_2 - a_1) + abs(a_3 - a_2) + \dots + abs(a_n - a_{n-1})}{2} \rfloor$.Now we want to $f(a) \le f(b) \rightarrow f(a) = min(f(b))$. The one way to get minimum $f(b)$ is sort array $a$. Now we have to compare $f(sorted(a))$ and $f(a)$167622000
 » I tried solving E with the hints but got stuck, please help!Think of the most to the least significant cell of the matrix.I try to fix cells least first to most significant at last to make it lexicographically smallest.How many positions in the matrix can a cell travel to after performing the operations?2And for each position that that cell can travel to, how many ways are there we can make it?2 — either swap the column or rowis my above reasoning correct, if yes how can i try 2 ways to swap efficiently?
•  » » If you have gone this far and still haven't figured out the answer yet, please read the tutorial :)
 » thanks for the great contest and fast editorial (even though my comment isn't so fast)
»

Can anyone help me why this solution isnt acceptable? Approach Used-> If we have to go to any coordinate on any axis then while returning to (0,0) the total number of moves would be 2*max(coordinate-1, coordrinate-2).

# include <bits/stdc++.h>

using namespace std;

int main() { int t; cin>>t; while(t--) { int n; cin>>n; int cnt=0; while(n--) { int a,b; cin>>a>>b; a=abs(a); b=abs(b); int k=a+b; cnt+=k; } cout << cnt*2 << endl; } }

 » 6 days ago, # | ← Rev. 6 →   In problem C when i am using vector>>v i am getting tle on test case 3 167745306 but , when i am using this vector>>v it is getting accepted 167745148can anyone please explain why ?
•  » » This may be because the time complexity of the add, delete, modify, and check operation of set is O(logn), while the time complexity of queue is O(1), I guess
 » 6 days ago, # | ← Rev. 4 →   codeforces round 812! (problem E) diagonal elements are to be untouched as they play no role in swap. Every non diagonal element can have two relative positions A[i][j] and A[j][i] only if A[i][j]!= A[j][i]. Then for certain k ( 1<=k<=n) row can be swapped with it's corresponding column to make matrix lexicographically smallest. Here( for upper half of diagonal) we have to choose some i where i A[j][i] or A[i][j]< A[j][i]. Then why is it we require DSU .Here initially DSU represents k different sets where each number ( 1<=k<=n) is it's own parent. Then through union and find operations the set's have to be segregated into two forms that the operation can be performed for kth node or not. ( find using path compression optimization. This concept can be find here int n; int arr,p; int find(int u){ if(u==p[u])return u; return p[u]=find(p[u]); } //simple union void Union(int a,int b){ a=find(a); b=find(b); if(a!=b) p[a]=b; } void solve(){ cin>>n; int mat[n][n]; //matrix input for(int i=0;i>mat[i][j]; } } /* let's consider 2n nodes , where first half of the nodes depict the group that have same states whereas another group depicts elements to have different states. example matrix 0 1 2 3 0 a b c d 1 e f g h 2 i j k l 3 m n o p suppose we compare for b and e , and b>e then we have two options either to do operation for k=0 or k=1. so we put (0 + n )and (1) in same group and (1 + n ) and 0 in same group. Here one more condition can occur if bmat[j][i]){ /*if they are already in same groups don't dipatch them as already it is leading to answer*/ if(find(i)==find(j)||find(i+n)==find(j+n)) continue; else{ /*if not then form groups */ Union(i+n,j); Union(i,j+n); } } } } /* remember diagnol elements doesn't change */ for(int i=0;i>t; while(t--) solve(); } `
•  » » 5 days ago, # ^ | ← Rev. 3 →   thanks for negative feedback.
 » 6 days ago, # | ← Rev. 2 →   I've tried submitting a solution to problem D ------>167785392 But I get Idleness limit exceeded on test 3, I modified a small part ------>167782691, but it seems to be working Ok, how it works?it confuses me.
•  » » When n is even q1.size will never be 2 (eg for 6 on the test case you are failing q1.size will be 64 -> 16 -> 4 -> 1) and the second loop never gets run. As you've moved the print outside the loop in the second version it works.
•  » » » Thank you very much. You've helped me a lot. I always make mistakes in details，haha:)
 » What does it mean by "fill the three dots with (0,0)"?
 » For problem F, very interesting by the way, I get stuck in the last part, when we have array b of size n and want to expand it to b' of size m.The editorial says: Create array c with sum over supermask, then set zeros the positions [m-n, m) and do sum over supermask again. Why sum over supermasks, and do it two times?(I understand that sum here means xor).
 » Naive solution for problem C(almost TLE lol) 168047272