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!

I hope to become Expert in this round. Please, wish me luck :)

I hope to cross 1500 :)

I hope to cross tourist;)

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.

how do you know that?

Just go to your

CONTESTStab and see all unrated contests there this round will be thereYeah, just saw it.

Same for me, it's listed under the unrated contests.

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 :)))

=)) add fr đi ô có gì học hỏi

Note the unusual time of the round.

After the thirth contest it isn't funny anymore

help me https://codeforces.com/blog/entry/96497

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.

U cheated in codeforces round 742 div2. Any explanation for that?

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.

where are you from???

I think there is no way to cheat on codeforces, codeforces have too good security to cheat.

how do you know that he cheated??

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.

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

Hello everyone! Good luck to everyone on the contest!

hope i solve 5 question

I hope to add +50 to remove Grey Tag :)

I hope to cross 800 cause this is my first time and I'm new to coding ^_^

It's not so ez) but wish u luck

Hope to solve 5 problems.

Wish I could also comment

`My first unrated round`

. LOL!How did you type like that?

Source CodeI hope to return to monke in this round.

Every contest, I stray further from monke :(

Div 3 contests are real fun! Hoping for a good one!!

It's gonna be my first unrated div3 contest

GL HF!

GG WP!

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 :)

Guys

please make div 3 contests on the weekends we can't attend them because of school and different time zonesthanksAs 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.

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.

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 ♥

Where is vovuh :(

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`

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 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

MEMORYon aofficial cf round. There are currently15 PAGESof 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.

CodeA 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.

Where is the solution to these questions?

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.

chadYou 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.com/contest/1607/submission/134137875]

I wish , if i could have started this contest 1hr early on time :(

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 [submission:https://codeforces.com/contest/1607/submission/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

ALLthe 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 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

It was timeforces.!

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

Spoilerand ~~~~~ if(flag == 1) { cout<<"NO"<<endl; } ~~~~~

Thanks. it works now.

Ah, ok, I did not see that ;)

Can anyone help me understand why this is TLE on F? https://codeforces.com/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`

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 :(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

Div.3 sucks

134133989 why my submission giving tle. please help. I had used multiset.

How to solve B? :(

The key observation is that after 4 steps you are where you started.

Just observe all cases of n%4. Take any random case and try doing some observations. You will surely be able to do it.

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.

please see my solution also

This input data is from Test Case #3 of problem D.

Test Case :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). 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)]`

.you are right but my observation took a lot of time, I guess more practice will help, thanks for the advice :)

Good Luck Patrick, I'm afraid but your psychic powers won't help you much here at Codeforces :D

Haha,Nice One,

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).

It was a trap :D

Some 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 :)

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?

Ok i will keep that in mind from next time btw thanks

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

thank u very much for this hopeful contest.

I guess this is because the pointer in 64bit system is 8 bytes :( ![](https://cdn.luogu.com.cn/upload/image_hosting/ad7o9r88.png))

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 useddfs2to set each nodes of every cycle to it's cycle length. Finally, I useddfs3to 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??

Normally, I saw rating changes on 9:00(UTC)-ish. Let us be patient

I hacked 10 users!

When will system test begin?

I hacked 10 users!— r/lethalAnd 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:(

haha. I like your reply.

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.com/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

justyet, they should be in a short while :)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.

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?

spoilerjk

He's obviously not a noob.

how to do problem C minimum extraction

I did a brute force but got tle

My solution

Time complexity of your solution is $$$O(n^2)$$$. There is a $$$O(n \log n)$$$ time solution for this problem.

1) sort the array

2) ans= -infinity

3) 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

correctionmy solutions is $$$O(n \log n)$$$Thank you very much for replying can you please tell me why this algorithm works.

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

Thank you for the help!

$$$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.

I solved a question in yesterday's contest but didn't get point till now!!why??

Is this contest unrated?

wait 2 more hrs

Thanks

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..

wait 2 more hrs if you have participated

oh okk.... Thank you! :)

3 hours ago...

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

hahahahah i will get 500000000000000000000000 points by hard sttruggle

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.

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.

比赛结束了吗，难度咋样

What'are you saying?Which language?Chinese or Japanese?Please use English(recommended) or Russian.

what the fucking the problem bitch it is a hard problem! who made this fucking question bitch?

if you like codeforces.com? then put +

or downvote this ↑ comment

OK. We know there are 18 people here who don't like it, or just don't like you.

Good luck to everyone!

Used binary search for E: link

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

I love

China!!(I get too less points so I need to shout out the angry of myself)Hi

thanks

It would be so interesting, I think.