### doreshnikov's blog

By doreshnikov, history, 4 weeks ago,

Hello Codeforces!

Once again, we are glad to invite you all to Codeforces Round #753 (Div. 3), the third division round held on Nov/02/2021 17:35 (Moscow time). This round was prepared (again) by me and MikeMirzayanov. The problems are different but our anticipation is the same :) Hope you will like the problems we've prepared!

Big thanks to MikeMirzayanov for great ideas as well as for helping me with writing good statements and better tests. I'm still a bit slow with some aspects of preparing problems so it's a really noticeable help for me. (UPD: as of this moment, it became much more noticeable, so, really, thanks a lot!)

Also special thanks for testing the round to 01aglupal, From_ITK18_With_Love, Mazaalai, GusMG, nizamoff, 2020akadaver, I_Remember_Olya_ashmelev, p0kemanbr, KoftaIQ and, as usual, to Gassa for valuable comments! And last but not least, thanks to everyone who'll be participating! This round contains 8 problems and is expected to have a decent level of difficulty for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. We tried to make tests strong enough but it doesn't at all guarantee that open hacks phase will be pointless.

You will be given 8 problems and 2 hours to solve them. We remind you that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes. Also please note that the number of problems has slightly increased since the last edit.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them)
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Good luck to everyone!

UPD: Editorial is out!

• +320

 » 4 weeks ago, # |   +5 I hope to become Expert in this round. Please, wish me luck :)
•  » » 4 weeks ago, # ^ |   0 I hope to cross 1500 :)
•  » » » 4 weeks ago, # ^ |   -32 I hope to cross tourist;)
 » 4 weeks ago, # | ← Rev. 3 →   +2 Look forward to great problems in this round! And I find that there is no testers in this round.
 » 4 weeks ago, # |   0 i hope to add 50 points
•  » » 4 weeks ago, # ^ |   +6 you can make it :)
•  » » » 4 weeks ago, # ^ |   +1 Hey I don't see any changes in rating. When will they be updated?
•  » » » » 4 weeks ago, # ^ |   +1 Yes same thing I too wanted to ask
•  » » » » » 4 weeks ago, # ^ |   0 this round is considered unrated in my contests don't know why.
•  » » » » » » 4 weeks ago, # ^ |   0 how do you know that?
•  » » » » » » » 4 weeks ago, # ^ |   0 Just go to your CONTESTS tab and see all unrated contests there this round will be there
•  » » » » » » » 4 weeks ago, # ^ |   0 Yeah, just saw it.Same for me, it's listed under the unrated contests.
•  » » » » » » 4 weeks ago, # ^ |   0 Are you sure that if it's listed there then it means it will not be rated for us? because I feel it's listed under the unrated contests because they didn't finish the rating calculation.
•  » » » » » » » 4 weeks ago, # ^ |   0 I don't know actually just wait that's all we can do
•  » » » » » » » » 4 weeks ago, # ^ |   0 Bro Div 3 contests are rare for us beginners and also 1 done in one month they make it not rated where will we live then
•  » » » » » » » » » 4 weeks ago, # ^ |   +2 Its not unrated guys it always appears in the unrated section until the rating updates . This contest is rated don't worry!!!!!
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Oh, Im so worry
•  » » » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Such a relief to hear that, but do you know when is the update of rating?UPD: nevermind, +173 is here
•  » » » » » » » » » 4 weeks ago, # ^ |   0 same
•  » » » » » » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 adu hi người cùng fanbase :))
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Hii :)) tiện thể học tiếng anh luôn :)))
•  » » » » » » » » » 4 weeks ago, # ^ |   0 =)) add fr đi ô có gì học hỏi
 » 4 weeks ago, # | ← Rev. 2 →   -21 Note the unusual time of the round.
•  » » 4 weeks ago, # ^ |   +2 After the thirth contest it isn't funny anymore
 » 4 weeks ago, # |   -15
 » 4 weeks ago, # |   +38 My first unrated round and this means a lot to me. It feels a lot better than I thought. I put a lot of effort into this in last 3 months and now this feeling is different kind of motivation to improve further. Codeforces has been sort of home to me. A big thank you to the best place on internet.
•  » » 4 weeks ago, # ^ |   +2 U cheated in codeforces round 742 div2. Any explanation for that?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +56 No explanation. There can't be any explanation for cheating ever. I still regret it and never did that again. I was deservedly skipped from that contest. And I can only say one thing and assure you that It will never ever happen again. I never should have done that. I'm Sorry.
•  » » » » 2 weeks ago, # ^ |   0 where are you from???
•  » » » 4 weeks ago, # ^ |   0 I think there is no way to cheat on codeforces, codeforces have too good security to cheat.
•  » » » 4 weeks ago, # ^ |   0 how do you know that he cheated??
•  » » » 4 weeks ago, # ^ |   0 What do you mean he cheated? Did he copy some other submission or something. How does cheating work on codeforces? I genuinely don't know — hence asking.
•  » » 4 weeks ago, # ^ |   -33 U cheated in codeforces round 743 div2. Any explanation for that?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +25 NO, I DIDN'T. I did it only once and have accepted it and will never never do ever again.
•  » » » 4 weeks ago, # ^ |   +13 That contest was made unrated for everyone.
•  » » » » 4 weeks ago, # ^ |   +22 Yes, right. Due to long queue issues.
 » 4 weeks ago, # |   0 Hope to cross 1400.
•  » » 4 weeks ago, # ^ |   -10 Sir, i have one doubt.Is it difficult to increase one's rating in div3 round after one has become pupil?Because in last div3 round, I solved 4 problems and gained only +3 .Moreover the predictor was indicating -10.
•  » » » 4 weeks ago, # ^ |   +20 no, just solve more
•  » » » 4 weeks ago, # ^ |   0 I think rank matters more than the number of problems solved.
•  » » » 4 weeks ago, # ^ |   0 I gained +42 in last div 3 by solving 4 questions try to solve them quickly and without any wrong submission.
 » 4 weeks ago, # |   +14 Is it unrated?
•  » » 4 weeks ago, # ^ |   +2 for you, Yes
•  » » » 4 weeks ago, # ^ |   0 so rude...
 » 4 weeks ago, # |   -12 My first unrated round!
•  » » 4 weeks ago, # ^ |   0 me,too
•  » » » 4 weeks ago, # ^ |   0 Hope to join you guys after today
•  » » » » 4 weeks ago, # ^ |   0 +1
 » 4 weeks ago, # |   0 Hello everyone! Good luck to everyone on the contest!
 » 4 weeks ago, # | ← Rev. 2 →   0 hope i solve 5 question
 » 4 weeks ago, # |   0 I hope to add +50 to remove Grey Tag :)
 » 4 weeks ago, # |   0 I hope to cross 800 cause this is my first time and I'm new to coding ^_^
•  » » 4 weeks ago, # ^ |   0 It's not so ez) but wish u luck
 » 4 weeks ago, # |   +4 Hope to solve 5 problems.
 » 4 weeks ago, # |   0 Wish I could also comment My first unrated round. LOL!
•  » » 4 weeks ago, # ^ |   0 How did you type like that?
•  » » » 4 weeks ago, # ^ |   -103 Source CodeWish I could also comment My first unrated round. LOL! 
 » 4 weeks ago, # |   +11 I hope to return to monke in this round.
•  » » 4 weeks ago, # ^ |   +1 Every contest, I stray further from monke :(
 » 4 weeks ago, # |   0 Div 3 contests are real fun! Hoping for a good one!!
 » 4 weeks ago, # | ← Rev. 2 →   0 It's gonna be my first unrated div3 contest
 » 4 weeks ago, # |   0 GL HF!
•  » » 4 weeks ago, # ^ |   0 GG WP!
 » 4 weeks ago, # |   +26 Perfect. A round on my birthday where i can't lower my rating :D
•  » » 4 weeks ago, # ^ |   +15 Happy birthday!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 Wishing you Good Luck!
•  » » 4 weeks ago, # ^ |   +3 Good luck!!! :)
 » 4 weeks ago, # |   +3 Hope to become pupil in this Round, wish me luck :)
 » 4 weeks ago, # |   0 Guys please make div 3 contests on the weekends we can't attend them because of school and different time zones thanks
 » 4 weeks ago, # |   +24 As a tester, I want contribution. :)
 » 4 weeks ago, # |   0 We tried to make tests strong enough but it doesn't at all guarantee that open hacks phase will be pointless.Thank you for your honesty.
 » 4 weeks ago, # |   +16 As a first time tester, I must sayMost importantlyPlease upvote this comment, so that my contribution becomes non-negative:') BonusNumber 1I have tested and hence cannot participate in the official round:D Number 2Problems are very interesting. Make sure you read all the problems.
 » 4 weeks ago, # |   0 Hopefully I will become Specialist after this contest.
•  » » 4 weeks ago, # ^ |   0 wish luck
 » 4 weeks ago, # |   +17 As a tester, i feel problems are very interesting. Hope you get more rating in this contest.Have a nice day :).
•  » » 4 weeks ago, # ^ |   +3 Thank you!
 » 4 weeks ago, # |   +10 I'm +3 away from being green, wish me a good luck guys.
 » 4 weeks ago, # |   +15 At this point, it's really become necessary to remind this:note the usual start time
 » 4 weeks ago, # |   +12 is expected to have a decent level of difficulty for participants with ratings up to 1600.Such a nice word decent.As I have to say, I'm always hoping for solving those decent problems in div.3 in contest. But almost always, it turns out that those problems are too hard for me or even someone else with higher rating than 1600 to pass QWQ.Wish me solve some of these decent problems in the upcoming div.3 round today.
 » 4 weeks ago, # |   +16 Hoping to recover points which i had lost on the previous round :)
 » 4 weeks ago, # |   +4 i guess that div3 is a great choice for the first round ever
 » 4 weeks ago, # |   +2 50 points away from expert, wish me good luck !
 » 4 weeks ago, # |   0 Expert to be ♥
 » 4 weeks ago, # |   0 Where is vovuh :(
 » 4 weeks ago, # |   +1 i have a feeling that my solution for D is wrong and gets ac
 » 4 weeks ago, # |   +12 GG crappy memory limit like FHC
 » 4 weeks ago, # |   +4 can't wait for the editorial, G is a new thing for me
 » 4 weeks ago, # | ← Rev. 2 →   +24 Infinite loop / massive stack memory usage case for MLE on test case 4 of F? Is there no way to get AC without building the solution iteratively?
•  » » 4 weeks ago, # ^ |   0 Just stack memory usage. I had to stop using vector of vectors and use normal functions instead of std::function to get AC.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -30 Accurate enough DFS implementations were accepted, most of the testers' solutions used DFS and got AC :)
•  » » » 4 weeks ago, # ^ |   +19 Anything that stands out to you as problematic in this solution? 134105154Three cases are general non-calculated, cycle found and value already known.I can't really think of much that's removable except removing $on_cycle$ and using a reference to a common int for cycle start node or something like that.Anyway is there a reason for the constraints to be so high in this problem? I can't think of any incorrect solution that needs to be cut off that won't also fail for $n \times m \leq 3 \times 10^5$
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   -27 As I see it: gridx and gridy arrays are unnecessary, there's no point in storing them explicitly solve() can be slightly optimized by making curval global (and x and y also, but it will make code a bit less readable). Also local variables can be inlined I understand that these kinds of optimizations are not what you expect from Div.3 but the main expected solution doesn't use dfs at all, so it's not like we wanted to fail dfs explicitly, we just didnt' tune ML for any dfs to pass.UPD1: (sorry, previous UPD wasn't true, fixed)UPD: We just re-checked your solution in Polygon with double ML after making some modifications and it passed, so I guess we should've made the ML larger. Sorry about that :(
•  » » » » » 4 weeks ago, # ^ |   +11 My solution failed because of that too. I considered that to be a problem. But I didn’t believe that it was a true reason to get ML. After the contest I wrote solution without dfs and it passed
•  » » » » » 4 weeks ago, # ^ |   0 Just wondering, in polygon, does increasing the ML also increase the stack limit (the option given to gcc -Wl,--stack=268435456)?I am debugging in gym and it doesn't seem like setting a higher memory limit changes the stack size. You still get a RTE/stackoverflow when you use above 250ish mb which is making this really annoying to debug.
 » 4 weeks ago, # |   +65 I am completely apalled that you need to do a constant optimization in MEMORY on a official cf round. There are currently 15 PAGES of MLE solutions on F. Even using std::function at all gives MLE. Actually disgusting.
 » 4 weeks ago, # | ← Rev. 3 →   +10 Was it really that necessary to make the limits tight for problem F, so that scc with recursion would TLE/MLE ??? Was it ???
 » 4 weeks ago, # |   0 How to solve D?
•  » » 4 weeks ago, # ^ |   +1 My idea was greedy : first take the blue marked numbers and red marked numbers in the ascending order and keep a variable can = 1 Iterate through blue numbers : if (blue_number>=can) then can++ else we cannot convert this number to any other number in the permutation ans = NO;similarly for red numbers if ( red_number <=can) for each red_number if this too fails then ans = NO in all the other cases ans = YES
 » 4 weeks ago, # |   0 is G greedy?
•  » » 4 weeks ago, # ^ |   0 Yep
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Yup, identify maximum prefix increase of a — b possible for first $i$ nodes. Then as we go backwards make operations so the difference is below the max prefix possible and as close below it as we can get (so it lies above the min prefix possible).I think the intuition is clear, but I do hand wave away some details so maybe there is a small edge case I'm missing and I'll get hacked. Code#include #define int long long using pii=std::pair; using namespace std; const int maxn = 2e5 + 5; int t, n, m, a[maxn], b[maxn], maxpref[maxn]; // max increase to a - b int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> t; for(int cases = 0; cases < t; cases++) { cin >> n >> m; int need = 0; for(int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; int takehi_a = min(a[i], m); int takehi_b = m - takehi_a; int takelo_b = min(b[i], m); int takelo_a = m - takelo_b; maxpref[i] = maxpref[i - 1] + (takehi_a - takehi_b); need += a[i] - b[i]; } vector ops; for(int i = n; i >= 1; i--) { int takehi_a = min(a[i], m); int takelo_a = m - min(b[i], m); int target = need - maxpref[i - 1]; if((target & 1) != (m & 1)) // Swapping 1 from a to b changes the diff by an even amount target--; // solve linear equations x + y = m and x - y = target, but constrain by limits we know int takea = max(min((m + target) / 2, takehi_a), takelo_a); int takeb = m - takea; ops.push_back({takea, takeb}); need -= (takea - takeb); } cout << abs(need) << "\n"; reverse(ops.begin(), ops.end()); for(auto x : ops) cout << x.first << " " << x.second << "\n"; } return 0; } 
•  » » 4 weeks ago, # ^ |   +12 A simple-ish way to think about G is as follows:Given values of a[i] and b[i], there is a minimum amount of each that the tester must eat (sometimes 0). Iterate once through and assign this minimum amount. This leaves a remaining 'variable amount' for each dish, and a starting difference. Iterate through again and assign this variable amount in such a way as to bring the difference back as close to 0 as possible.
•  » » » 4 weeks ago, # ^ |   +12 It feels so good when someone has done the exact same thing that you did and got AC .. Glad I could think this in time..
 » 4 weeks ago, # |   +21 Am I the only one for whom was the 2 hours too tight for this contest?
•  » » 4 weeks ago, # ^ |   0 Nop
 » 4 weeks ago, # |   +14 such a bad div 3 round I have ever given. Authors div 3 is for newbies, so kindly make the problems for newbies and not for pros.
 » 4 weeks ago, # |   0 Where is the solution to these questions?
 » 4 weeks ago, # |   0 Someone please explain problem G, i don't understand :( example: test case inp 3 6 1 8 1 9 30 10 out 7 1 5 1 5 6 0 why the first line = 7 @@
•  » » 4 weeks ago, # ^ |   0 the minimum imbalance after eating for that testcase is 7
•  » » » 4 weeks ago, # ^ |   0 Yeah out 7: 1 5 -> 1 5 -> 6 0 but abs( (1 + 1 + 6) — (5 + 5 + 0) ) = 4 or did I misunderstand
•  » » » » 4 weeks ago, # ^ |   +1 its the absolute value of what is left, not what is eaten
•  » » » » » 4 weeks ago, # ^ |   0 well ~~
•  » » 4 weeks ago, # ^ |   +3 You need to maximize the balance of dishes after the taster eat some of them, not maximize the balance the dishes eaten by the taster.Really annoying statement :(
•  » » » 4 weeks ago, # ^ |   0 oh, can you explain with an example pls :(
•  » » » 4 weeks ago, # ^ |   0 I asked exactly for that while contest.
 » 4 weeks ago, # |   +13 Really annoying G for its unclear statement. The taster needs to maximize the balance of dishes WHICH IS LEFT AFTER EATING BY HIM, not eaten by him. It drops me from rk 40~ to 170 :(
•  » » 4 weeks ago, # ^ |   0 doesnt the first testcase show what they meant?
•  » » » 4 weeks ago, # ^ |   0 I didn't saw it until I finish my program. I think the statement is clear enough, but it doesn't.
 » 4 weeks ago, # |   +7 chad
•  » » 4 weeks ago, # ^ |   +14 You don't need tarjan x)The graph is a functional graph so it's enough to just iterate while you don't cycle and keep track of the nodes you're visiting in a vector. Then, if you visit a node X you visited in the same run, there is a cycle starting at node X and you can recover the cycle with your vectorSee my code here for more details: [submission:https://codeforces.com/contest/1607/submission/134137875]
 » 4 weeks ago, # |   0 I wish , if i could have started this contest 1hr early on time :(
 » 4 weeks ago, # |   +19 the MLE of F is awful
 » 4 weeks ago, # |   +114 I believe, F should belong to an educational round, not to a div3 round. Like I am not against teaching people how to write dfs using stack (though I believe that the authors who design such problems are quite... strange), but asking a beginner to do this optimization? For me it looks like the best way to discourage them from doing cp.
•  » » 4 weeks ago, # ^ |   -7 It's true that DFS is one of the first things that come to mind when one sees this problem, but it's not the only thing that could be used...The ML wasn't set up to explicitly fail all DFS solutions (and I mean it), we just expected a solution without DFS as we know it so we didn't tune the ML for any DFS to pass.Since if you think about the board as a graph, each vertex has only one outcoming edge and you can walk through the graph with a single loop without even knowing that such thing as DFS exists. And that's what actually written in main solution.
•  » » » 4 weeks ago, # ^ |   0 Actually there are some DFS solutions be able to be optimized enough to pass. Yet they are very rare compared to those get MLE.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +60 Well, that's great that you have a solution that does not need any additional optimization. But it seems you don't get the point, the thing is that failing recursive solutions (with correct time and space complexities) is not nice. Did you not think of dfs while setting up this problem? That's really strange, because that's the first thing that comes to mind.I believe that in beginners contest (in any contest, actually, but for beginners it's even more important) the authors should try to cut off solutions with bad complexity and allow solutions with good complexity to pass comfortably and I also belive that this does not hold for this problem.UPD. So you say that none of the testers solutions were close to ML, while having recursive dfs inside? Seems unbelievable. Or you mean that they were able to squeeze dfs into time limit? This is possible, of course, but really, you wanted 1600- rated people to optimize dfs?
•  » » » » 4 weeks ago, # ^ |   +75 Maybe the authors wanted to SendThemToHell
•  » » » » 4 weeks ago, # ^ |   +40 I understood your point, yes. The fact that in the end this task was challenging not because of it's algorithmic difficulty but because of the memory limit is kinda frustrating, this was not how it was intended.Well, I can't argue with the fact that this Div. 3 is not as well-adjusted as the previous one, sorry for that. We'll try to make the next one more pleasant to solve.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 I solved 7 problems in 1 hour. And couldn’t optimize dfs to pass in the remaining hour of the contest :(everything else is super. Thanks for the great contest :) спасибо за интересные задачи
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 Yes most of the recursive solutions fail just because of MLE. But my main point is that there are so rare dfs solutions with heavy optimization to be able to pass, I did not mean that DFS is enough to past. I think that the author make a miscalculation to use 256Mb instead of 512Mb and kill around atleast half of the solutions.Yet some of my CM friend still find it very confusing to optimize further, some even spend an hour without being able to solve it.
•  » » » 4 weeks ago, # ^ |   +9 But is there a solution that even needs to be cut off? If not why set the constraints so high? Additionally you mentioned earlier that some testers had dfs solutions, were none of them close to the memory limit?
•  » » 4 weeks ago, # ^ |   -10 the graph is a functional graph so you can just use a loop [submission:https://codeforces.com/contest/1607/submission/134137875] (although I used a DFS during the round and got few problems)
•  » » » 4 weeks ago, # ^ |   +1 Is there a prerequisite technique on how to find the longest path in a functional graph? I dont get your solution, what do the while loops do?
•  » » » » 4 weeks ago, # ^ | ← Rev. 12 →   +4 First, why do I have that much downvotes :') ?!!I'll try to explain my solution step by step. First notice that in the graph, each node has at most one child. So basically, any connected component has at most ONE CYCLE. Indeed, let's assume you're currently constructing the connected component starting from node $1$. When we're at node $i$ we have two choices: we can either add an edge to node $i + 1$ (so the graph looks like a path and we don't have any cycle) or we can add an edge to some node $j$ such that $j < i$ and we'll create a cycle. Notice that after a cycle has been created, we can't add any more edge.Now let's say we found the cycles. For a given cycle, the length of the longest path is the same for each node of the cycle (it's the size of the cycle).So now we know that a functional graph looks like......x......|......|......vx->x->x->CYCLE(the . are used to align the edges. I'm sorry I couldn't do something clean. I'll try to send a drawing asap)Imagine it as we link some sort of directed tree (where all the edges are directed toward the root) to a cycle.About my code:What you can do is store for each node:1) if it has been visited2) if we are visiting the node (this means the node is part of the path we are exploring right now)3) the longest path starting from this nodeIn my code $ans[i][j] == 0$ if the node hasn't been visited, $ans[i][j] == -1$ is we're visiting the node, else it's the longest path starting from this node.Now let's iterate over each node $u$. If the node hasn't been visited, let's start a walk in the graph (basically we explore the unique path starting from node $u$). We'll keep track of a vector of all the nodes in the path ($curCycle$ in my code) and we'll also remember the length of the path ($cnt$ in my code)This is what I do in the first while loop.Let's say the child of our current node is $v$. If it's the first time we see it then we move to $v$ and keep exploring (don't forget to update $curCycle$ and $cnt$). If we already computed an answer for node $v$, we simply increment $cnt$ by this answer and break. Now, if $v$ is already part of our path (in my code it's $ans[i][j] == -1$), it means we cycled. So we're going to look for the last occurence of $v$ in our array $curCycle$. All the nodes after this occurence are part of the cycle and their answer should be updated accordingly. Notice that as we cycled, we can't expand our path anymore.Now we also need to update the answers of all the nodes in the path (nodes which are outside of the cycle). So we basically start again to walk from node $u$ and we set it's answer to $cnt$. Then when we move to the child of the current node, $cnt$ should decrease because the length of the path is reduced by $1$.The time complexity is $O(N)$ where $N$ is the number of nodes (here $N = nm$). Indeed, we visit each node exactly once because after a node has been visited, it's answer is remembered and we'll never explore again it's path.Essentially, finding cycles in a functional graph is the same as finding if there is a cycle in a directed graph (See CSES Round Trip)The only difference is that:1) As the graph is pretty simple we can use a while loop instead of a DFS2) We're actually finding ALL the cycles of the graph because each connected component has at most one cycleAbout the other part of the algorithm, imagine you "compress" the cycles into one big node with it's answer = the length of the cycle. We now have a DAG (and more specifically it's a kind of directed chain) so we can apply DP (here we have only one transition per node).The while loops are just a more convenient/efficient way to implement the algorithm.A few problems about functional graphs:Usaco silver, Swapity Swapity SwapUsaco silver, Dance MoovesUsaco gold, Exercise (well this one is a bit less related but it's an interesting problem)I hope my explanations were clear, if they weren't just ask me and I'll do my best to explain :)
•  » » » » » 4 weeks ago, # ^ |   0 Thanks a lot! Really helpful.
 » 4 weeks ago, # |   +1 Why the memory limit for F is so tight ? As a beginner I find it very hard to optimize memory further more (though there are better algorithm but I cant just think of it)
•  » » 4 weeks ago, # ^ |   +3 The same for me. Seems recursive programming does not work. Have to do in a loop.
•  » » » 4 weeks ago, # ^ |   0 Most of my friend using DFS are failed due to MLE (and there are CM too). Just one among them be able to pass using kosaraju instead of tarjan.
•  » » » » 4 weeks ago, # ^ |   0 wait, did you really compressed the graph using strongly connected components ?
•  » » » » 4 weeks ago, # ^ |   0 U wrote opposite maybe I believe he would have used tarzan as Kosaraju takes more memory . I too passed it in recursive way but I had to find cycles by simple DFS . And code is still on the edge for MLE .
•  » » » » 4 weeks ago, # ^ |   +3 But isn't Kosaraju also dfs?
•  » » » » » 4 weeks ago, # ^ |   0 I mean that he is the only one among us used DFS and be able to pass lol
 » 4 weeks ago, # |   0 It was timeforces.!
 » 4 weeks ago, # |   0 Someone please tell me why my code is not working in problem D.134132886
•  » » 4 weeks ago, # ^ |   0 You forgot return statement in the flag == 1 condition :/
•  » » 4 weeks ago, # ^ |   0 You misunderstood the problem. The numbers can be completly out of range of 0..n, so the code does not work at all.
•  » » » 4 weeks ago, # ^ |   0 No, they added specific conditions for 'B' and 'R'. Since 'B' can only be decreased by 1 and 'R' can only be increase by 1, it seems right to me.
•  » » » » 4 weeks ago, # ^ |   0 Consider in example all red numbers bigger than n. Obviously output must be No.
•  » » » » » 4 weeks ago, # ^ |   0 Sorry I don't get your point. This is exactly what is done in their code + what I explained.
•  » » » » » » 4 weeks ago, # ^ |   0 No, the code does not check this. The var temp1 never gets incremented if values are out of range 1..n, so output is never No.
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Parts of the code Spoilerif(s[i]=='R') { if(arr[i]>n) { flag = 1; } mp2[arr[i]]++; } and ~~~~~ if(flag == 1) { cout<<"NO"<
•  » » » » » » » » 4 weeks ago, # ^ |   0 Thanks. it works now.
•  » » » » » » » » 4 weeks ago, # ^ |   0 Ah, ok, I did not see that ;)
 » 4 weeks ago, # | ← Rev. 2 →   0 Can anyone help me understand why this is TLE on F? https://codeforces.com/contest/1607/submission/134130569I'm pretty sure it's just linear time complexity DFS with the board size, but why TLE?Is this because it's using recursive and cause stack overflow?
•  » » 4 weeks ago, # ^ |   +5 I see you're using std::map and std::set in your code, both of them will make total time complexity of code as: $t \times n \times m \times \log(n \times m)$ which will surely give TLE over all test cases :(
•  » » » 4 weeks ago, # ^ |   0 even if it's using map and set, the complexity is 4*10^6 log (4*10^6) which is less than 100 millions. Why would that TLE over all test cases?
•  » » » » 4 weeks ago, # ^ |   0 100 millions operations is at the border of the time limit per cases
 » 4 weeks ago, # |   -14 Div.3 sucks
 » 4 weeks ago, # | ← Rev. 3 →   0 134133989 why my submission giving tle. please help. I had used multiset.
 » 4 weeks ago, # |   0 How to solve B? :(
•  » » 4 weeks ago, # ^ |   0 The key observation is that after 4 steps you are where you started.
•  » » 4 weeks ago, # ^ |   0 Just observe all cases of n%4. Take any random case and try doing some observations. You will surely be able to do it.
 » 4 weeks ago, # |   +3 I really like it to solve so much problems as in div3 possible. But today there was also a big difficulty gap from E to F,G,H.
•  » » 4 weeks ago, # ^ |   0 please see my solution also
 » 4 weeks ago, # |   0 This input data is from Test Case #3 of problem D. Test Case :12016 1 17 10 5 2 13 34 20 24 2 9 17 14 31 3 1 8 34 12RRBRBBRBBBBRRRBRRRBRHi doreshnikov, Could you please help me? I wanted to know what is the logic behind this test case. I have stress tested my solution on random 10000 inputs of array length 20 but my generator couldn't catch this.
•  » » 4 weeks ago, # ^ |   +3 Not sure what's so exceptional about this test. If you sort all the numbers by (color, value), you get something like thisAs you can see, all blue numbers can be decreased to the corresponding number from permutation and all red numbers can be increased to get the number from permutation (the first number in the row is the expected number from permutation).It could be the fact that there is a Blue number that you don't have to apply operations to (2), but I was sure a similar case was in the example test...
 » 4 weeks ago, # |   0 WTF! Why do you put a blank line in the input?
•  » » 4 weeks ago, # ^ |   +5 If there was no blank line it would be hard to know which testcase is which. The extra blanks don't affect input
•  » » 4 weeks ago, # ^ |   +9 So it is easier to distinguish tests in a multitest when you read it
 » 4 weeks ago, # |   -30 B was trash
•  » » 4 weeks ago, # ^ |   +20 It was a pretty straightforward observation after dry running any testcase that we land at the starting position after every 4 jumps.
•  » » » 4 weeks ago, # ^ |   -31 oh is it so straightforward? Please teach me how to make observations.Observations suck!
•  » » » » 4 weeks ago, # ^ |   +20 Observations are quite important in the world of competitive programming :) it's pretty valid advice from yasserkhan45: if you can't see the answer immediately, experiment with some test cases. As is pointed out, a single test case was enough to see what happens in general, and a small modification was required for an odd starting position.
•  » » » » » 4 weeks ago, # ^ |   0 What to do if I still can't see through, happens with me most of the times, observational questions are the ones that take up most of my time in a contest, for most people they are straightforward but for me :(, any advice on how to improve?
•  » » » » » » 4 weeks ago, # ^ |   +2 If observation doesn't work, sometimes it helps to write a solution that you know is slow and will not pass but is really easy to implement (in this case it's just to simulate the process).Either you'll find a way to optimize it later so it would get OK (not in this particular problem though) or you'll have a way to search for patterns in answer a bit faster. In IOI format it also may help you to get at least partial score.If nothing else, at least you'll have a solution you can stress-test your main solution with if something goes wrong with it.
•  » » » » » » 4 weeks ago, # ^ |   +4 There's no catch-all answer here and I don't want to reel off any cliches but: practice really does make an enormous difference here: the more questions you solve, the more your past experience can inspire the right ideas. limits often provide a clue. The limits here were big, so it was clear there must be some sort of pattern that did not require us to iterate over all moves. look for patterns. Here, if you choose a starting point of 0 and iterate for a few moves, you get [0, -1, 1, 4, 0, -5, 1, 8, 0, -9, 1, 12, 0, -13, 1, 16, ...]. It's clear that we keep getting back to 0, and that this happens every 4 moves — think about why. It's because every 4 moves, the first and last move go left, and the middle two moves go right. What's happening between those moves? Every other even move (n % 4 = 2) brings us back to 1 (it's easy to consider why this happens). If n % 4 = 1, we're subtracting n from 0. If n % 4 = 3, we're adding n to 1. So this gives us the complete set of cases [0, -n, 1, n+1] for the four possible values of n % 4. Then we add the starting position. If we start on an odd position, it turns out (by similar experimentation and consideration) that the complete set of cases is [0, n, -1, -(n+1)].
•  » » » » » » » 4 weeks ago, # ^ |   +8 you are right but my observation took a lot of time, I guess more practice will help, thanks for the advice :)
•  » » » » » » » » 4 weeks ago, # ^ |   0 Good Luck Patrick, I'm afraid but your psychic powers won't help you much here at Codeforces :D
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Haha,Nice One,
•  » » » » » » » 4 weeks ago, # ^ |   0 It’s took almost 1 hour for me to solve B problem. After contest I asked my friends why B problem is so hard(After B I solve 2 more problems in less than 20 min), I was shocked that we can n%4. My solution is arithmetic progression, after we start in even number we move -1, +2, +3, -4, -5, +6, +7 etc. So I saw we have progression +2,6,10... and 3,7,11... -4,-8,-12... I just don’t know why this problem is B, because C is easier. In C you don’t need to notice anything, just write easy code. In B you have to write complicated arithmetic progression(which is obvious will pass 10^14 tests, after that I just didn’t think about another solution), or notice n%4 somehow.
•  » » » » » » » » 4 weeks ago, # ^ |   0 That’s why you shouldn’t spend much time on one problem. You only read B and didn’t read other problems. Try to read next problems too, because they may be easier for you. If you just skipped B, you would have taken higher place on the contest. For example I solved problems in this order A B C D E H G and F after the contest.
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Thanks for the advice
•  » » » 4 weeks ago, # ^ |   +2 I still think its dumb. If you try to work out an idea instead of looking at the sequence and guessing you waste a bunch of time and get nowhere. To this point i have no idea why my solution works (will probably work it out now that i said this).
•  » » 4 weeks ago, # ^ |   0 It was a trap :DSome problems just so nicely hit my blind spot. Got fixed on the idea of a combo of 4 arithmetic progressions. Lost a lot of time and all my morale. In retrospect, of course, it's so embarrassingly obvious.Oh well… Now I've learned. Again :)
 » 4 weeks ago, # | ← Rev. 2 →   0 134139660 please see my solution .I am getting tle . for no reason .please do not ignore .
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Hello. Note that you are using multiset, so its better to use s.lower_bound(number) here since lower_bound(all(x), number) will be linear complexity. Your sol with this idea: 134140462
•  » » » 4 weeks ago, # ^ |   0 Sir please tell me when to use this form of lowerbound and when to use other
•  » » » » 4 weeks ago, # ^ |   +1 lower_bound(all(v), x) — usd with vectors/arrays s.lower_bound(x) — used with sets/maps
•  » » 4 weeks ago, # ^ |   0 Couldn't wrap my head around your solution. Here is the simple one that I have implemented.cpp codeWe can decrease 'b' and increase 'r' so all the 'b' should come first and 'r' should come at the end as we can increase them after performing the operations. If for any of them doesn't follow the limit(1 to n), answer will be NO.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 I think more people would have checked your code, if it was understandable. Did you here about coding style?
•  » » » 4 weeks ago, # ^ |   0 Ok i will keep that in mind from next time btw thanks
 » 4 weeks ago, # |   0 Question B and C someone please explain approach of these :))
•  » » 4 weeks ago, # ^ |   +2 C, consider the array a[] to be sorted. So the first value is smallest, so gets removed first. Observe that all values allways change by the same amount, so the relative sorting allways stays the same. So the values are removed from left to right.When removeing a[0], a[1] becomes a[1]-a[0], a[2] becomes a[2]-a[0] and so on.When removing a[1], a[2] becomes a[2]-a[0]-(a[1]-a[0])=a[2]-a[1] Same for a[3] becomes ... =a[3]-a[1]When removing a[2], a[3] becomes a[3]-a[2]...So ans=max(a[0], max(a[i]-a[i-1]))
 » 4 weeks ago, # |   0 I got runtime error in test 10 problem H. Can someone fix for mehttps://www.ideone.com/64cEbJ
 » 4 weeks ago, # |   0 thank u very much for this hopeful contest.
 » 4 weeks ago, # |   +18 I guess this is because the pointer in 64bit system is 8 bytes :( ![](https://cdn.luogu.com.cn/upload/image_hosting/ad7o9r88.png))
 » 4 weeks ago, # |   +2 I tried solving F. Robot on the Board 2 using dfs with dp on the matrix using directions as edges and cells as nodes.My idea was to first find a single nodes for each simple cycle for which I used dfs1. Then I used dfs2 to set each nodes of every cycle to it's cycle length. Finally, I used dfs3 to get length of paths for the remaining nodes of the graph. I'm getting Memory limit exceeded due to some bug. Can anyone point out the issue here.Here is my submission #134144883.
•  » » 4 weeks ago, # ^ |   +11 When you have recursion(dfs) system reserves memory for that recursion. It is usually called stack memory. So your dfs uses additional O(N*M) memory. That’s why you got MLE, and me too. Try to solve this problem without recursion.Hint: all cells have only one outgoing edge
•  » » » 4 weeks ago, # ^ |   0 I understood. Thanks.
•  » » 4 weeks ago, # ^ |   +3 My Solution got AC with DFS although it is also on the edge of MLE. You can have a look if u want .
 » 4 weeks ago, # | ← Rev. 2 →   +110 Memory limit was too tight for problem F. I used dfs and got MLE with a memory usage of 283MB using C++17(64). However, I submitted it for C++17 and got AC, only 161MB.
 » 4 weeks ago, # |   0 I hope to become Expert today :) (unless any of my question is hacked :( ) Thanks for this wonderful round!
 » 4 weeks ago, # |   +1 Thank you so much for interesting & worth studying problems :) I really enjoyed it. p.s. Any editorials yet?
 » 4 weeks ago, # |   +11 when will system testing / hack rejudging start??
•  » » 4 weeks ago, # ^ |   0 Normally, I saw rating changes on 9:00(UTC)-ish. Let us be patient
 » 4 weeks ago, # |   +11 I hacked 10 users!When will system test begin?
•  » » 4 weeks ago, # ^ |   +13 I hacked 10 users! — r/lethal
•  » » 4 weeks ago, # ^ |   +8 And I made my first ever hack...Kinda excited for my testcase to appear lmao
•  » » » 4 weeks ago, # ^ |   0 rip whoever got TLE'd by my test lol
•  » » 4 weeks ago, # ^ |   0 any tips for hacking?
•  » » » 4 weeks ago, # ^ |   0 To hack the records whose times are near the bound.If the time limit is 1s,we can find the records in 950~999ms.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 smart way to find victim byou don't use any tools for test case generation?
•  » » » » » 4 weeks ago, # ^ |   0 Oh,i use C++ editor:(
•  » » » » » » 4 weeks ago, # ^ |   0 haha. I like your reply.
 » 4 weeks ago, # | ← Rev. 3 →   -9 how to improve my logic
•  » » 4 weeks ago, # ^ |   0 What do you mean?
 » 4 weeks ago, # |   -8 Can anyone tell how to get rid of MLE in test 4 in problem F. Link to my submission:- https://codeforces.com/contest/1607/submission/134177362I used Kosaraju's algorithm and then did dp in the condensed graph.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 here's what I did: i was earlier using SCC to find cycles, but then I switched to using just DFS iterative DFS using stack, instead of recursive DFS my submission: 134172739
 » 4 weeks ago, # |   -8 This was my first ever contest. I was not able to solve all the problems and wanted to know the solutions of it. PLease tell me where can I find the tutorials
•  » » 4 weeks ago, # ^ |   0 They aren't out just yet, they should be in a short while :)
 » 4 weeks ago, # |   -8 I don't know what is the issue with the 3rd question the same logic in java is giving TLE and running perfectly fine in C++. I have used fast input-output methods in java still this happened.
 » 4 weeks ago, # |   -9 This was my first round, and I solved 7 problems but i'm still unrated :( Is this round unrated for me?
•  » » 4 weeks ago, # ^ |   +5 Rating changes are calculating now, please wait for some times. Hope that you can get high rating.
•  » » » 4 weeks ago, # ^ |   0 Thanks!
•  » » » 4 weeks ago, # ^ |   +1 Who are you?
•  » » » » 4 weeks ago, # ^ |   +8 not an alt, I was a user for another PS website. I'm just not familiar for the Codeforces...
•  » » » » » 4 weeks ago, # ^ |   0 No,i'm asking who are luogu_bot0.:(((
•  » » » » » » 4 weeks ago, # ^ |   +13 uh-oh. sorry.
•  » » 4 weeks ago, # ^ |   -8 gm alt?
•  » » » 4 weeks ago, # ^ |   0 *chinese alt? spoilerjk
•  » » » 4 weeks ago, # ^ |   0 He's obviously not a noob.
 » 4 weeks ago, # |   0 how to do problem C minimum extraction I did a brute force but got tleMy solution
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Time complexity of your solution is $O(n^2)$. There is a $O(n \log n)$ time solution for this problem.1) sort the array2) ans= -infinity3) if array[0] is positive, ans= array[0]4) for i in (1,n): ans= max(ans, array[i]-array[i-1])Note there is a corner case which |array| == 1
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 correction my solutions is $O(n \log n)$
•  » » » 4 weeks ago, # ^ |   0 Thank you very much for replying can you please tell me why this algorithm works.
•  » » » » 4 weeks ago, # ^ |   0 I recommend you to try sample test cases by hand.Write test cases, follow the steps, and get the idea why it works. full solution: 134092282
•  » » » » » 4 weeks ago, # ^ |   0 Thank you for the help!
•  » » 4 weeks ago, # ^ |   +10 $1\leq n\leq 2\times 10^5$And your code is not less than O(n^2).That must come to TLE.
•  » » 4 weeks ago, # ^ |   0 You must calculate the TIME COMPLEXITY before submitting.
•  » » » 4 weeks ago, # ^ |   0 Thank you very much for replying Actually I didn't submit this solution in contest in fact I couldn't solve this. Now when I am upsolving it this is the only solution I can come up with. I wanted to know the actual approach or solution that is why I asked and I also gave my approach I can come up with. I know that is O(n^2).
•  » » » » 4 weeks ago, # ^ |   0 check editorial. It explains quite clearly.
 » 4 weeks ago, # |   0 I solved a question in yesterday's contest but didn't get point till now!!why??
 » 4 weeks ago, # |   0 Is this contest unrated?
•  » » 4 weeks ago, # ^ |   0 wait 2 more hrs
•  » » » 4 weeks ago, # ^ |   0 Thanks
 » 4 weeks ago, # |   0 Will this contest be rated for me? this is my first ever codeforces contest ? Any information on this will be really helpfull. Thank you!
•  » » 4 weeks ago, # ^ |   +6 It is rated for youRegardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
 » 4 weeks ago, # |   +1 is there anyone whose rating has been updated yet? I am still unrated, so I was wondering if I had to do something more in order to get a rating..
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -7 wait 2 more hrs if you have participated
•  » » » 4 weeks ago, # ^ |   -8 oh okk.... Thank you! :)
•  » » » 4 weeks ago, # ^ |   -8 3 hours ago...
•  » » 4 weeks ago, # ^ |   0 Yeah,it's slow.But the only thing you can do is WAIT.
 » 4 weeks ago, # |   +8 Editorial? doreshnikov
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 Sorry, wasn't feeling well. I promised the previous time that editorial will come out sooner, but couldn't finish it faster this time :(ETA: half an hour probably, I hope...
 » 4 weeks ago, # |   +13 All problems in this round is with multi testcase. Interesting.
 » 4 weeks ago, # |   +14 Sorry, but when is the editorial available? Because last 2 problems I can't solve it T_T
 » 4 weeks ago, # |   0 hahahahah i will get 500000000000000000000000 points by hard sttruggle
 » 4 weeks ago, # |   +11 What's the meaning of the memory limit of Problem F...
 » 4 weeks ago, # |   0 I think A-E are good problems in div3,but F is obviously harder than E，it leads to the speed of solving the first five problems is particularly important.But anyway, I think it is a good round！
 » 4 weeks ago, # | ← Rev. 2 →   +8 n
 » 4 weeks ago, # | ← Rev. 2 →   0 The test data for Problem H is not strong enough. After taste, for the $i$-th dish, $a'_i$ should be in $[\max(0, a_i - m_i), a_i - \max(0, m_i - b_i)]$; In my first submission, I wrote it as $[\max(0, a_i - m_i), a_i]$. It's wrong because I ignored this type of situation: when $m_i > b_i$, taster must eat some of $a_i$. But it got Accepted.Upd: It seems this bug surprisingly can't be hacked, none business of the strength of the test data, sry.
 » 4 weeks ago, # |   0 cannot load the page during the contest (but I can visit other websites except cf), which made the experience a little painful. I wonder if anyone else had this problem yesterday.
 » 4 weeks ago, # |   -22 比赛结束了吗，难度咋样
•  » » 4 weeks ago, # ^ |   -10 What'are you saying?Which language?Chinese or Japanese?Please use English(recommended) or Russian.
 » 4 weeks ago, # |   -37 what the fucking the problem bitch it is a hard problem! who made this fucking question bitch?
 » 4 weeks ago, # |   -18 if you like codeforces.com? then put +
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 or downvote this ↑ comment
•  » » 3 weeks ago, # ^ |   0 OK. We know there are 18 people here who don't like it, or just don't like you.
 » 4 weeks ago, # |   0 Good luck to everyone!
 » 3 weeks ago, # |   0 Used binary search for E: link
 » 3 weeks ago, # |   0 I have created a whatsapp group for discussing questions related Competitive programming It going to be very helpful for beginners and to get momentum into cp. link: https://chat.whatsapp.com/JHLDhLlpoR46aVptVpItNL
 » 3 weeks ago, # |   0 I love China!!(I get too less points so I need to shout out the angry of myself)
 » 2 weeks ago, # | ← Rev. 7 →   +4 Hi
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 thanks
 » 2 weeks ago, # |   0 It would be so interesting, I think.