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 RisingWizard, Capta1n_Shy, Mazaalai, GustavoMG, nizamoff, 2020akadaver, ashmelev, p0kemanbr, Kofta 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!
I hope to become Expert in this round. Please, wish me luck :)
I hope to cross 1500 :)
Look forward to great problems in this round! And I find that there is no testers in this round.
i hope to add 50 points
you can make it :)
Hey I don't see any changes in rating. When will they be updated?
Yes same thing I too wanted to ask
this round is considered unrated in my contests don't know why.
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.
I don't know actually just wait that's all we can do
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
Its not unrated guys it always appears in the unrated section until the rating updates . This contest is rated don't worry!!!!!
Oh, Im so worry
Such a relief to hear that, but do you know when is the update of rating?
UPD: nevermind, +173 is here
same
adu hi người cùng fanbase :))
Hii :)) tiện thể học tiếng anh luôn :)))
Note the unusual time of the round.
After the thirth contest it isn't funny anymore
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.
.
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.
I think there is no way to cheat on codeforces, codeforces have too good security to cheat.
U cheated in codeforces round 743 div2. Any explanation for that?
NO, I DIDN'T. I did it only once and have accepted it and will never never do ever again.
That contest was made unrated for everyone.
Yes, right. Due to long queue issues.
Hope to cross 1400.
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.
no, just solve more
I think rank matters more than the number of problems solved.
I gained +42 in last div 3 by solving 4 questions try to solve them quickly and without any wrong submission.
Is it unrated?
for you, Yes
so rude...
My first unrated round!
me,too
Hope to join you guys after today
+1
I hope to cross 800 cause this is my first time and I'm new to coding ^_^
...
Hope to solve 5 problems.
Wish I could also comment
My first unrated round
. LOL!How did you type like that?
I hope to return to monke in this round.
Every contest, I stray further from monke :(
It's gonna be my first unrated div3 contest
GL HF!
Perfect. A round on my birthday where i can't lower my rating :D
Happy birthday!
Wishing you Good Luck!
Good luck!!! :)
Hope to become pupil in this Round, wish me luck :)
As a tester, I want contribution. :)
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.
Please upvote this comment, so that my contribution becomes non-negative:')
I have tested and hence cannot participate in the official round:D
Problems are very interesting. Make sure you read all the problems.
Hopefully I will become Specialist after this contest.
wish luck
As a tester, i feel problems are very interesting.
Hope you get more rating in this contest.
Have a nice day :).
Thank you!
I'm +3 away from being green, wish me a good luck guys.
At this point, it's really become necessary to remind this:
note the usual start time
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.Hoping to recover points which i had lost on the previous round :)
i guess that div3 is a great choice for the first round ever
50 points away from expert, wish me good luck !
Expert to be ♥
i have a feeling that my solution for D is wrong and gets ac
GG crappy memory limit like FHC
can't wait for the editorial, G is a new thing for me
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?
Just stack memory usage. I had to stop using vector of vectors and use normal functions instead of std::function to get AC.
Accurate enough DFS implementations were accepted, most of the testers' solutions used DFS and got AC :)
Anything that stands out to you as problematic in this solution? 134105154
Three 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$$$
As I see it:
gridx
andgridy
arrays are unnecessary, there's no point in storing them explicitlysolve()
can be slightly optimized by makingcurval
global (andx
andy
also, but it will make code a bit less readable). Also local variables can be inlinedI 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 :(
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
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.
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.
Was it really that necessary to make the limits tight for problem F, so that scc with recursion would TLE/MLE ??? Was it ???
How to solve D?
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
is G greedy?
Yep
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.
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.
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..
Am I the only one for whom was the 2 hours too tight for this contest?
Nop
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.
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 @@
the minimum imbalance after eating for that testcase is 7
Yeah out 7: 1 5 -> 1 5 -> 6 0`` but abs( (1 + 1 + 6) — (5 + 5 + 0) ) = 4 or did I misunderstand
its the absolute value of what is left, not what is eaten
well ~~
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 :(
oh, can you explain with an example pls :(
I asked exactly for that while contest.
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 :(
doesnt the first testcase show what they meant?
I didn't saw it until I finish my program. I think the statement is clear enough, but it doesn't.
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 vector
See my code here for more details: [submission:https://codeforces.net/contest/1607/submission/134137875]
the MLE of F is awful
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.
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.
Actually there are some DFS solutions be able to be optimized enough to pass. Yet they are very rare compared to those get MLE.
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?
Maybe the authors wanted to SendThemToHell
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.
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 :) спасибо за интересные задачи
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.
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?
the graph is a functional graph so you can just use a loop 134137875 (although I used a DFS during the round and got few problems)
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?
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
......|
......|
......v
x->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 visited
2) 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 node
In 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 DFS
2) We're actually finding ALL the cycles of the graph because each connected component has at most one cycle
About 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 Swap
Usaco silver, Dance Mooves
Usaco 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 :)
Thanks a lot! Really helpful.
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)
The same for me. Seems recursive programming does not work. Have to do in a loop.
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.
wait, did you really compressed the graph using strongly connected components ?
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 .
But isn't Kosaraju also dfs?
I mean that he is the only one among us used DFS and be able to pass lol
Someone please tell me why my code is not working in problem D.
134132886
You forgot return statement in the flag == 1 condition :/
You misunderstood the problem. The numbers can be completly out of range of 0..n, so the code does not work at all.
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.
Consider in example all red numbers bigger than n. Obviously output must be No.
Sorry I don't get your point. This is exactly what is done in their code + what I explained.
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.
Parts of the code
and ~~~~~ if(flag == 1) { cout<<"NO"<<endl; } ~~~~~
Ah, ok, I did not see that ;)
Can anyone help me understand why this is TLE on F? https://codeforces.net/contest/1607/submission/134130569
I'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?
I see you're using
std::map
andstd::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 :(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?
100 millions operations is at the border of the time limit per cases
How to solve B? :(
The key observation is that after 4 steps you are where you started.
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.
This input data is from Test Case #3 of problem D.
1
20
16 1 17 10 5 2 13 34 20 24 2 9 17 14 31 3 1 8 34 12
RRBRBBRBBBBRRRBRRRBR
Hi 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.
Not sure what's so exceptional about this test. If you sort all the numbers by (color, value), you get something like this
As 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...
WTF! Why do you put a blank line in the input?
If there was no blank line it would be hard to know which testcase is which. The extra blanks don't affect input
So it is easier to distinguish tests in a multitest when you read it
B was trash
It was a pretty straightforward observation after dry running any testcase that we land at the starting position after every 4 jumps.
oh is it so straightforward? Please teach me how to make observations.
Observations suck!
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.
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?
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.
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). Ifn % 4 = 1
, we're subtracting n from 0. Ifn % 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 ofn % 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)]
.you are right but my observation took a lot of time, I guess more practice will help, thanks for the advice :)
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.
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.
Thanks for the advice
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).
134139660 please see my solution .I am getting tle . for no reason .
please do not ignore .
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
Sir please tell me when to use this form of lowerbound and when to use other
lower_bound(all(v), x) — usd with vectors/arrays s.lower_bound(x) — used with sets/maps
You should read this — https://www.cplusplus.com/reference/set/set/lower_bound/ https://www.cplusplus.com/reference/algorithm/lower_bound/
Couldn't wrap my head around your solution. Here is the simple one that I have implemented.
cpp code
We 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.
I think more people would have checked your code, if it was understandable. Did you here about coding style?
Question B and C someone please explain approach of these :))
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]))
I got runtime error in test 10 problem H. Can someone fix for me
https://www.ideone.com/64cEbJ
I guess this is because the pointer in 64bit system is 8 bytes :(
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.
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
I understood. Thanks.
My Solution got AC with DFS although it is also on the edge of MLE. You can have a look if u want .
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.
I hope to become Expert today :) (unless any of my question is hacked :( ) Thanks for this wonderful round!
Thank you so much for interesting & worth studying problems :) I really enjoyed it. p.s. Any editorials yet?
when will system testing / hack rejudging start??
I hacked 10 users!
When will system test begin?
I hacked 10 users! — r/lethal
And I made my first ever hack...
Kinda excited for my testcase to appear lmao
rip whoever got TLE'd by my test lol
any tips for hacking?
To hack the records whose times are near the bound.
If the time limit is 1s,we can find the records in 950~999ms.
smart way to find victim b
you don't use any tools for test case generation?
Oh,i use C++ editor:(
how to improve my logic
What do you mean?
Can anyone tell how to get rid of MLE in test 4 in problem F. Link to my submission:- https://codeforces.net/contest/1607/submission/134177362
I used Kosaraju's algorithm and then did dp in the condensed graph.
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
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
They aren't out just yet, they should be in a short while :)
This was my first round, and I solved 7 problems but i'm still unrated :( Is this round unrated for me?
Rating changes are calculating now, please wait for some times. Hope that you can get high rating.
Thanks!
Who are you?
not an alt, I was a user for another PS website. I'm just not familiar for the Codeforces...
No,i'm asking who are luogu_bot0.
:(((
uh-oh. sorry.
gm alt?
*chinese alt?
jk
how to do problem C minimum extraction
I did a brute force but got tle
My solution
$$$1\leq n\leq 2\times 10^5$$$
And your code is not less than O(n^2).That must come to TLE.
You must calculate the TIME COMPLEXITY before submitting.
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).
check editorial. It explains quite clearly.
Will this contest be rated for me? this is my first ever codeforces contest ? Any information on this will be really helpfull. Thank you!
It is rated for you
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.
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..
Yeah,it's slow.But the only thing you can do is WAIT.
Editorial? doreshnikov
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...
All problems in this round is with multi testcase. Interesting.
Sorry, but when is the editorial available? Because last 2 problems I can't solve it T_T
What's the meaning of the memory limit of Problem F...
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!
n
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.
比赛结束了吗,难度咋样
What'are you saying?Which language?Chinese or Japanese?Please use English(recommended) or Russian.
if you like codeforces.com? then put +
OK. We know there are 18 people here who don't like it, or just don't like you.
Good luck to everyone!
Hi
thanks