Hello Codeforces!

On Jul/30/2021 17:35 (Moscow time) Educational Codeforces Round 112 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **6 or 7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

*Hello once again, Codeforces!*

*It’s been a week since we completed our Harbour.Space Scholarship Contest. It’s was an intense journey, but we are excited to share the results of the contest and take this time to give a word of appreciation to every participant.*

*One more big shout out to the authors and round coordinator who made this contest happen in a short period of time:*

*Thank you again for all your hard work.*

*Congratulations to all the winners and runner-ups who got the opportunity to go through the admissions process and who are eligible for a full scholarship.*

*1st-3rd Places: Ali.Kh, Yousef_Salama, antOntrygubX_y*

*4th-10th Places: sunyx, windazz, IMRED, Meijer, Prosto, kpw29, Huah2*

*11th-15th Places: dhruvsomani, adamant, Kaitokid, khiro, c8kbf*

*We are pleased to announce that we have reviewed all the winners and will make a final decision about additional scholarships soon. Stay tuned and keep an eye on your inbox!*

*Remember, to claim the scholarship you need to respond to the email sent 3-4 days ago. And just to make sure email addresses weren’t misspelt, we want to take this opportunity and ask Yousef_Salama, Huah2, adamant, c8kbf, Naseem17 to contact us via email (almaz.aubakirov@harbour.space) or directly on Codeforces platform (Harbour.Space)*

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | SSRS_ | 6 | 92 |

2 | tourist | 6 | 120 |

3 | WZYYN | 6 | 127 |

4 | Heltion | 6 | 131 |

5 | Tlatoani | 6 | 140 |

57 successful hacks and 612 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | Geothermal | 0:01 |

B | tourist | 0:03 |

C | kaiboy | 0:04 |

D | dario2994 | 0:07 |

E | tourist | 0:11 |

F | rainboy | 0:30 |

**UPD:** Editorial is out

i hope i can get top 10 in this contest

i hope i can get top 10000 in this contest

Not achieving this goal is harder than achieving it.

Not easy for new Learners.

Problem A did make it a lot easier though.

nope is do A every time i buy my data pack

He was talking about 1000 , and misprinted it. Lol

I hope that this contest will be as good as CF Round #735. And maybe even better

Hope this educational round actually have balanced problems unlike the last edu round

Agree Balance is always perfect )

Please don't start hopeforces again

You hope no one hopes again.

28/07 ->

July Cook-Off 202129/07 ->

Codeforces Round #73530/07 ->

`Educational Codeforces Round 112`

31/07 ->

`July Lunchtime 2021`

31/07 ->

`AtCoder Beginner Contest 212`

01/08 ->

`Leetcode Weekly Contest 252`

01/08 ->

`Codeforces Round 736`

Raining ContestsWow! This Weekends's gonna be really exciting!

Wow,seems like you are still living in June

My bad.

Thanks :))

On 31 there is also ICPC practice contest

And my ratings are going to be washed out.

A chance for me to fix the damage caused by the previous contest :( Nice problems btw :)

I hope I can break my unconditional love with FSTs in this round.

:(

Please get me out of this losing streak. I'm doubling in rating loss each time.

You can see my rating graph so that you can get some motivation

good luck to you.

I think @Karry5307_AK_NOI2021 will AK this contest with his ssh because he's the best ssher.

Just waiting for the result.

Karry5307 & ssh forever!

(just a joke)

What happenedKarry5307 used ssh to steal other people's code in NOI (Chinese Programming Competition) and got 100 points.

y would anyone waste their time going to some trash unaccredited university, beyond me tbh

Hoping for a good contest :)

hope i become pupil again

Good luck, guys!

I hope, I won't become turquoise again ^^

Same :)

Good luck to everyone!

My first Contest as Expert , will try my best today to move up more !!

Hopefully this contest won't make you worry about your setters' safety.

It's time to move up.

Good luck for everyone

Hope that there won't be any Bitwise-operators tonight.

I hope I will solve B in this contest

MikeMirzayanov I think something is wrong with my registration. It shows me as a official participant. Can you please fix it? I don't want to lose master.

Maybe there's sth wrong with Problem D.

How can a string which length is 1 can be changed to an "beautiful" string ?

Because it is given that we have to consider only "palindrome of length greater than or equal to two".

just realized why A is the hardest problem ..

The announcement which came for C, should have come early. I was solving a different C, where Alice is looking for the maximum and then Bob goes with the minimum afterward.

No, you should have read the statement more carefully.

Yeah, you are correct. But the announcement itself proves that the statement was unclear.

No,it proves there were more people like you who didn't read the statement properly and were bugging authors with queries.

Solved D at 01:50, so happy! ^__^

congratulations

After giving yesterday's contest. This one feels so much better. Regained some confidence again. :)

Not being able to do B yesterday was depressing tbh...

When you solve A,C, and D but not B. Sigh...

B had more cases than law courts!

upsolve it, there are at max 6 cases.

for -1

for 0

other 4 for each direction R,L,U,D

Three cases: -1, can fit horizontally, can fit vertically.

Yeah i guess i complicated it a bit. I checked for both sides and found the minimum.

In my opinion, C was much easier than A and B. Thanks.

I think A,B is way more harder than C,D and E lol

I took 47 minutes to solve problem B (+ penalty), but 9 minutes to solve problem C and 15 minutes to solve problem D....

Solved B in when last 4 minutes were left . Solved C and D long ago. :((

I'm so disappointed of myself Idk why my B solution is wrong :( :( I solved C easily I could have read D but I kept saying I will solve this B

Submission

I might have missed it in your code but did you check x1 and y1 to the walls or the walls to x2 and y2?

nah I just realized my mistake I thought we place the second rectangle from (0,0) what a stupid understanding I did

Mathforces. 4 wrong submissions for A :(

score distribution is same for all problems? i have solve only C and D today but ranking is same who slove only A and B.

Its educational round, that's why !

How educational rounds are different from normal round?lazywitt

They are by definition different, as in there is no semantic meaning in this difference. It's not that "oh this is educational so let's teach them how to treat all problems equally" or anything. It's just by definition. Educational and Div3 rounds follow ICPC style contest rules, where Div1, Div2 and most others follow point based score distribution rule where difficult problems are assigned higher points.

Nice contest, E is a very interesting problem.

how did you solve e? I tried doing a nested binary search on the minimum values to take and maximum values but it TLE'd.

I did that too initially, but binary search is actually not needed. Just use two-pointer, extend right bound until the whole interval is covered and then update the answer.

ohh sick

How are using binary search here? After fixing the minimum value, we can do a binary search on max values that's fine. But how can you do a binary search on minimum value ... Then you will have to iterate linearly for minimum value?

Depending on whether or not there are any valid max values(using a certain min value) I will choose to either lower or increase my min value. It sounds pretty dumb and it didn't pass either but if you are really curious you can read my code.

Is downvoting comments complimenting contests becoming a trend?

Why was A and B (didn't read rest) so "heavily" math based compared to other general As and Bs? I'm surprised so many people got A, toughest A and B I've ever seen, also first time seeing both the starting two problems are math.. which is surprising considering most of the people can only do A and B (I'd expect something which has to more with programming than complete maths).

IMOWell, you can't have every A be "you have an array and you need to permutate through it and do and do x". Sometimes there has to be math involved, and let's be honest, it wasn't a lot.

And "toughest A and B I've seen" seems comical when yesterday there was a B rated 1700.

If this is your "toughest A and B", then 1. You haven't done many contests in CF. 2. You don't really know what is a tough problem and what is not.

Unfair constraints for python in problem D

same code for c++ https://codeforces.com/contest/1555/submission/124343239 got accepted but

python code got tle https://codeforces.com/contest/1555/submission/124338639

Headquarters MikeMirzayanov, Round Coordinator BledDest, one of the authors Errichto

please look into this.

1) We are not creators of Python. Go complain to them. I think that CF staff only cares about easy problems being solvable in slow languages.

2) I have nothing to do with this problem. I was mentioned in the blog as an author of the previous round -_-

even though I am a newbie here in code forces or should I say in this whole cp genre .but i know that [1] you must not tag Authors and other GM unnecessarily in (unless you'r LGM YOURSELF). [2] you must wait for editorials to come out before asking too much question [3] be respectful. Nobody here's the homeroom teacher

It's a valid concern. Python may have timed just around the given time limit. So asked organizers to see if time could have been higher for python based submissions. Codechef does it and so do many problems in codeforces have elevated time for problems like the one (https://codeforces.com/contest/1553/problem/B)

PS: It's not unnecessary tagging. Also even with editorial there are times that solution writer didn't go with simple solution. Tagging is just one thing. If you don't think you are right person to answer, just leave it.

I agree with the first part of your reply regarding elevated time for problems. however, there's a place to ask such questions you don't ask them in comments here and

tag people.a better way is to go into to contests "**Ask a question** section..this isn't insta or fb.Didn't knew there was such a thing. I will check that out

Wow. So many downvotes for no reason. I raised a valid concern for god's sake.

The problem https://codeforces.com/contest/1553/problem/B. works in 500*3 (about 10**8) complexity , but my solution in today's contest has time complexity of (12*10^5 + 2*10^5) in worst case and i still got TLE.

It's not a new issue. Many times python and java solutions get TLE due to strict time limit(Ask secondThread lol). Nothing can be done after contest.

By the way you can watch SecondThread raging on this here (https://youtu.be/3tE2N2PkDC8) (headphone warning*).

"""Each participant has the right to choose the language that he likes. Together with all its pros and cons. Yes, Java runs a little slower on average, but it has better static analysis in the IDE. It is quite typical for IT tasks that the tool is chosen for the task. And yes, I'm sure it's not a bad thing that sometimes you encounter purely programming difficulties. Understanding that not all ways to read or write data are the same is helpful. In particular, it is important to understand the basics of buffering. Specifically, in your case, knowing the standard library of the language in which you write is also useful. You are using Arrays.sort, but not reading the documentation. Read it finally.""""

- MikeMirzayanov, March 2021

SpoilerNow it's up to you whether you want to learn how to use the correct tools or you want to just start a debate that has been already done 10000000 times and still would lead to no actions.

SpoilerRegarding downvotes, it depends on how one looks at it. For someone who just started, it's a very important concern. For those who have seen this 100000 times, it's just another spam or rant.

TL DR""A bad workman quarrels with his tools.""

Comm'n man, you have registered 3 years ago and you even ignored standard

Almost always, if you send a solution on PyPy, it works much fasterwarning as well and wants people to take you seriously since it's a valid concern. Eventually, you will have to learn C++ if you want to do CP for a long time, time multipliers are not the only soln here.At lastIf you want to stick with python even now.

Step 0 — Start following pajenegod

Step 1 — Pyrival

Step 2 — Change your template to you fast io otherwise in future you may get TLEs even for reading inputs on div2As.

Thanks for this

Use pypy with some fast io (fast io is an issue even in c++ so it's kind of fair).

Your code ACs in 732ms: https://codeforces.com/contest/1555/submission/124358306

ok.I could have simply taken pypy3 instead of python to save my points. But may be in next contest

a lot of case works in B :/

i don't think there will be lot of case work just have a look on my solution it was pretty short https://codeforces.com/contest/1555/submission/124301671

What the heck is wrong with guy who set up problem B. Like you really want the people to stop logical coding using their thinking skills and just spend 15 minutes considering all the cases like a donkey, and spend another 30 debugging when they get a penalty on the same code. Is this the way the best coding platform wants to evaluate its participants? If yes, then good luck/bye caseforces!

PS : i think the problem setters just wanted to minimize the nuumber of people who could attempt the good questions afterwards by just sticking them to this **** problem!

Cleanish SolutionNevertheless, I did not like problem B either. It was just implementation, no thinking.

More Cleaner igBasically, you can just try moving it along only x-axis or only y-axis. There is no need to move it in both axes.

124351102

what about this.?

Problem F:

I used HLD to solve it. Can somebody please tell does there exists any approach without HLD?

Did you use HLD to find usable edges? I'm not sure but I think the problem boils down to single usage of an edge in the tree formed from all the queries and if that's the case, we can split the tree about an edge that can't be used anymore, and re-root the smaller component with another parent? Just like small to large merging. PS : We can keep splitting a tree into forests by this process.

Initially, I made a tree by using only edges which are first time connecting any two different components, then observed that any cycle can span atmost one edge of the tree. After that, used HLD for max path queries. So after that anytime got validation for adding any edge just set all values of all edges to infinite (basically deleted). To check validation, just did a max path query.

Can you please tell in your approach after splitting into forest how are you checking for any query.

Yes I was thinking of the exact same thing. But just to confirm, please tell me if this is right. First off anytime a tree edge arrives we can add it. Otherwise I found a sum for each node in the tree that denotes the xor of the path from the root to that node. If 2 nodes are in the same tree in the current forest of trees and have xor of Node sums = (edge ^ 1), then they can be connected. Otherwise they cannot be connected. Now if they can be connected, we can disconnect each edge on the path between them using the process i described before and recalculating the sums and root Node for each Node in the smaller component.

dnshgyl21 I think your implementation does not consider the fact that it will be a HLD forest, you always start from root 0.

Model solution is without HLD. We'll describe it in editorial, but shortly, we first find the MST of the graph (using the time when the edges are added as weights, to find the edges that are definitely present in the answer), then create a logarithmic data structure like Fenwick or Segment Tree to mark the edges belonging to a cycle and/or verifying that the cycle we're adding doesn't intersect with some previously created ones.

Can you please describe how can we mark edges on any path in a tree using Segment or Fenwick tree?

Upd : Thanks,i got it now.

There is a way to range addition on the path from $$$v$$$ to $$$root$$$ and range sum on path from $$$v$$$ to $$$root$$$ using two Segment Trees, but it's not needed here.

Since each edge will be marked at most once, you can mark edges one by one while asking a sum on path: all using Fenwick tree on Euler tour.

could someone tell me whether i am wrong with these i have tried my own these problem link

Remember to use spoiler next time :) and you are not even talking about a problem from the contest.

sorry i didnt get you ??

It takes a lot of time to scroll down if people don't want to see your code.

ok sorry for that , i am knew so dont know much about how to use that .

Seems like you are NEW in english too

ya , but that's not the main point, the point is about my question

Are you kidding me? I used old version of problem F statement where cycle was simple if there weren't any repeated edges. And this is the only reason why I didn't get accepted during the contest. I've got accepted in 2 minutes after the round ended, so sad(

We are sorry, we actually noticed the bug in Russian version only, like, 10-15 minutes before the end of the contest :(

Can somebody please explain the solution of problem A?

What I did was, write down N as N = 6a + 8b + 10c. Now this can be written as N = 2 * ( 3a + 4b + 5c ). Now let's take ( a + b + c = S ) , so we equation becomes N = 2 * ( 3 * S + b + c ), and b + c = S — a. So this becomes N = 2 * ( 4 * S — a ). Now just find a and S( and one thing if N is odd take N as N + 1, don't know the reason for this but it just worked for odd numbers because they are not divisble by 2 ).

Now the total time required is TIME = 15a + 20b + 25c. TIME = 5*( 4 * S — a ). This is the answer.

3*S+b+2*c

The question asks to find x, y, z, when 6x+8y+10z is greater than or equal to n, find the minimum value of 15x+20y+25z

Note that 15/6=20/8=25/10=2.5

Let us make an equivalent transformation for the condition 6x+8y+10z >= n.

3x+4y+5z >= (n+1)/2.

Note that gcd(3,5) = 1 , so all numbers greater than 7=3*5-3-5 can be formed by adding several 3 and 5.

For the part less than 7, it can be solved directly by violence.

Code : https://codeforces.com/contest/1555/submission/124347937

the thing N + 1 /2 works because we need "atleast" n pizza slices if n is odd we cant get exactly n slices so we cook extra

if(n<=6) we need only 1 small pizza giving ans as 15 mins Consider x small , y medium and z large pizzas : so number of slices will be n = 6x + 8y + 10z corresponding to it , time spent = 15x + 20y + 25z = 5*n/2 ( in terms of 1st equation) for odd number of slices , u can find that ans modifies to 5*(n+1)/2

I listed out the first 20 values of n:

and noticed that increases by 5 every 2

Yeah that is also what I did, unfortunately it occurred to me after 4 WAs lol

If $$$n<=6$$$, print $$$15$$$

For $$$n>6$$$, if $$$n$$$ is even, print $$$n*2.5$$$

else print $$$(n+1)*2.5$$$

Expected to become an expert today, will probably end up as a pupil...

Spent both the hours on Problem

Aand got 7 WAs, lol.Almost did the same, then decided, 'hey, why not check other problems'.

Can't argue with that, though I spent around an hour trying to figure out why exactly was even a brute-force solution giving me WA (Brute Force on n % 120, 120 being the LCM)...

And I still don't know what exactly is wrong with my code...

Edit:I finally realized that considering n / 120 and n % 120 separately doesn't always give the optimal answer.

Eg: 121: My output would be 315, while the optimal answer is clearly 305.

My program would waste 5 slices of pizza, while the optimal answer would only waste one.

I had a similar approach like this but my code also gave WA, did you try for all i in the range 1 to 16. My code was giving wrong answer in this range and correcting for this got me Accepted

...

If you saw the sample cases, you would've noticed the answer always being ((n+1) * 5) / 2 for n >= 6. Something to do with the fact that 15/6 = 20/8 = 25/10 = 5/2.

Yeah, I guess the

McNugget theoremcan be applied to this problem as well.The McNugget Theorem

6 = 2 * 3, and 8 = 2 * 4.

3 and 4 are relatively prime, so the greatest number which cannot be formed by them is 3*4 — 3 — 4 = 5 (10, because of *2; 10 exists as the third term here, so it too is covered).

Because we only need to consider even numbers (odd numbers can be converted to even), and we are working with *2 here, all the even terms above 6 will be covered.

Numbers below and equal to 6 can be processed as a special case.

hahahha.

Solved 4 but still feeling worthless because of A and B xD

I spent 40 minutes on A and didn't have enough time to solve E ：(

I lost B to precision today.. just changing double to integer made it pass. Significant digits turned out to be so significant today :( The pain though!

B ruined my entire contest. Couldn't even read E though it was pretty doable. :((

The more I read this blog, the more correct Heliac 's comment looks

124312667 this is my submission for problem B during the contest where i took the values float instead of long long and it gave WA. It gave a difference of 2 in one of the TC. 124345470 this is that same approach(everything same just changed float to long long) but got accepted....can any one pls explain why this happened. edit: by mistake initially i gave the link to wrong problem.

precision error

and why will float be less precise than int/long long

Sometimes with floats, it will do things like $$$1.0000001 = 1$$$. This is why, when comparing floating point numbers, I like to do something like this:

thisyes you are absolutely correct but my point is that if i am just having floats of type f.000000 and there is no multiplication just subtraction and addition then why would it give some difference.

it shouldn't

actualy 3 != 2^k

so even with addition you should get precision error

edit: Am I right here?

Like 3.000000 != 3 right?

or just multiply 10000000 and compare normally

C++ has it's own Epsilon value. Check this. Here std::numeric_limits::epsilon()

google "precision error"

it's not something someone can easily explain to you here

Can we do C using dfs ? I think it is the same as Cherry pickup II of leetcode ? please help.

But its a question afterall with a valid difficulty range for qstn. B. Also,its my fault that i assumed it to be something else. It actually didn't have much case work. Apologies..

Absolutely!!

Was thinking I'll regain Expert! But problem B exists lol, ate up huge amount of time :(

Problem D is wonderful.

Considering that a three-letter palindrome can only be

abcabcabc... acbacbacb... bacbacbac... bcabcabca... cabcabcab... cbacbacba...

Each position is symmetrical in rotation. So a simple prefix sum can be done for it. Code : https://codeforces.com/contest/1555/submission/124347304

Of course it is! I came up with exact logic to compare with 3! strings and make prefix array (precompute) and answer queries in O(1) time. But sadly , time ran out and I couldn't implement it fully.

A clean(ish) solution for B.

SpoilerWe need to check for the number of free cells possible in both X and Y directions. (Free cells are the cells not occupied by the first table). If the number of free cells in ANY direction (X or Y) is greater than the number of cells needed for second table, then we can fit the second table in. The first table only needs to move horizontally or vertically to acommodate the second table, it will never have to move diagonally.

SpoilerIf my approach seems wrong, hack it ;)

Is the rating predictor broken?

yeah seems like it is considering previous rating

In reference to problem B 3 actions can be taken: 1. Rename the website to caseforces 2. Ban the guy who set it up from setting up future contests 3. The guy should have some self respect and delete his account

What do you mean? There were only 3 cases: -1, horizontal fit, and vertical fit.

Should we be sad or happy in this case? :(

One of the best contests I have participated at in my life. Beautiful, Balanced and the Best

Actually problem B should be C and C should be B!

hey, guys i am new to this platform, where can i find the editorial for the questions??

It will be published after some time.

hard contest only the first problem was easy

Everything is relative.. I thought A was hard, B and C were easy

:)

4 Div2 (with 2 Div1) Round, 2 Div3 Round, 2 Educational Round, 2 Div(1+2) Round, and 1 Global Round, Total of 11 Rounds held in this Month. So we can say July is the perfect month for all the contestants who like and enjoy every round of Codeforces. Thanks to Mike Mirzayanov and all the problem setters of this month <3

wonder how many guys copy-pasted their segment_tree for E from the Internet

From which part of the Internet? Do you mean that general purpose segment tree libraries are available? Or a complete solution for exactly this problem is available?

Can you please explain the approach of problem E? Where do we need segment tree?

You can use two pointers with segment trees to maintain the minimum value

A solution video for the first four questions of div 2

https://www.youtube.com/watch?v=NMSQ-uu59mQ

why to even use double in problem B as shown in sample output.

it's a trick to fool people, and also it accepts solutions that somehow use doubles

yes

That was just to confuse us so that we start thinking the box both horizontally and vertically as shown in the example diagram.

I wasted 5 minutes thinking that when can the answer be in double.

I misread problem D and thought that input string can contain any 26 letters of Latin alphabet and it is allowed to change any character of the string to one of the first 3 letters and couldn't solve that problem. Can this problem be solved?

I think that it is possible if you spend $$$O(r - l)$$$ on each query or do precalc and spend $$$O(n^2)$$$

The solution to Problem A with Proof:...

Observation:

6 slices — 15 minutes => 1 slice — 2.5 minutes

8 slices — 20 minutes => 1 slice — 2.5 minutes

10 slices — 25 minutes => 1 slice — 2.5 minutes

Thus, each pizza slice is baked in the same time no matter if we pick 6, 8, or 10.

Now, Assuming that N >= 7

Claim: we can represent N = a * 6 + b * 8 + c * 10Proof: N = 2K. so, it is the same as saying 2K = a * 6 + b * 8 + c * 10 => K = a * 3 + b * 4 + c * 5Since N >= 7, K >= 7 / 2 = 3.

Now, we need to prove that K (>= 3) can be represented as a * 3 + b * 4 + c * 5.

Observation: 4 = 1 mod 3, 5 = 2 mod 3.

It is obvious that if K can be of the following types only:

k = 0 mod 3 -> Pick only 3s

k = 1 mod 3 -> Pick only 3s and a 4

k = 2 mod 3 -> Pick only 3s and a 5

Answer = (N) * (2.5) because each slice is now of the same value.

Clearly, for the odd case, we cannot represent N as a * 6 + b * 8 + c * 10 as LHS is odd and RHS is even.

So, we definitely need to bake more slices than required. Thus, we can just add 1 to N and get the same situation as Case 1. Hence answer = (N + 1) * (2.5)

For the claim, you can give a one line proof by induction. It's true for $$$6 \leq N \leq 10$$$ and assuming it is true for all even numbers less than $$$N$$$ with $$$N - 6 \geq 6$$$ we can write $$$N$$$ as $$$N - 6 + 6$$$ and we're done by induction.

Ohh didn't notice that. Pretty cool.

I proved this using Arithmetic mean >= geometric mean

here is my sol for A.

I did like this https://codeforces.com/contest/1555/submission/124321685

Nice round with not easy nor really hard tasks E is especially good!

Can someone guide me on how to solve extended version of today's C problem. Consider N rows and M columns with the same problem statement.

PS: Constraints can be adjusted accordingly

It's nice that there wasn't that version of that task)))

Is anybody know which testcase is in task b test 2 case 554? My solve fails on it and idk why... Here is link on it https://codeforces.com/contest/1555/submission/124358523 [](https://codeforces.com/contest/1555/submission/124358523) plz say what is wrong...

You ignored the word "minimum". We need to find the minimum and when both horizontal and vertical is possible.

https://www.youtube.com/watch?v=NMSQ-uu59mQ

Where's the editorial?

I think It will be published after the open hacking phase of 12 hr in the educational round. You can refer my video

https://www.youtube.com/watch?v=NMSQ-uu59mQ

GreedyForces

Questions about Karry5307_AK_NOI2022 again:

I think there must be something strange.

I think it is possible that he submitted B and C at the same time because of the bad Internet connection. But a more likely guess is that

somepeople shared this account and solved these problems together.I am sure that this account's owner is not

realKarry5307 because in China nearly nobody will register an ID of "I all killed a contest".But I believe that God Karry5307 has such courage and power.

Although he(they) might cheat,he(they) can't beat me because I am much stronger than h0up1ngze!

You are much stronger than tourist :)

You are much stronger than tourist :)DXqwq

Yes,she is too naive.

You are much strong than tourist :-)

Yeah, you solved F in less time than tourist, then you'll soon become a LIGM(Legendary International Grandmaster) soon :)

You are much stronger than tourist :)

If you check his submissions you can notice that after he submitted D, he coded F for 31 minute, but then got WA, after one more submission for F, he coded E in something like 2-3 minutes (the only code he actually wrote is in main, so I believe 3 minutes were enough), and after that he returned to F. In total he spent ~34 minutes for the last problem, which is quite legit.

Oh, I finally got it. Sorry for my misunderstanding :(

Can we do C using dfs ? I think it is the same as Cherry pickup II of leetcode ? please help.

DFS would be overkill here. You can simply use prefix sum and compute the result for each

(Alice will move down). Then take the minimum result.iCan anyone help me with problem B solution?? What I am doing wrong here? It is failing 2nd test. Here is the verdict:

`wrong answer 530th numbers differ - expected: '0.0000000', found: '1.0000000', error = '1.0000000'`

here is code:

please help me what I am doing wrong here

i think the problem is that you are not considering the case where u can fit it both vertically and horizontally.

so i would suggest to look in both direction. Like here after going in elseif. it is not going to go in else to check if u can get a smaller ans

yes correct. Thank you.

1 5 8 1 3 4 5 2 3 Test case for your reference it should give 0 but your code giving 1 b/c it not checking vectically.

Have the solutions been rejudged yet? When will the ratings change?

Interesting Round, thanks!

Can we just appreciate that there is no pretest for D where m < n, so I got RTE. Nice.

what's the binary search solution for E? I am more interested in how to write the predicate function in o(logn) or so ?

MikeMirzayanov My submissions of this round skipped getting an unexpected warning that my submission to the problem C 124303153 coincides with the submission 124301236 by NZB. This is totally unexpected. The solution to problem C is super simple. I request you to manually check the submissions and the solution to problem C. I'm totally disappointed with this kind of wrong warnings from such a reputed platform like codeforces. Because this is the second time I have been convicted without doing any kind of violations. I wrote a detailed blog on this after getting my first warning but nothing changed. Please read the blog Unexpected warnings from CodeForces. Hope you will look into the matter. Thanks.

MikeMirzayanov same thing happened with me for Question C. The problem was a very simple one.Please look into this

The idea and code of problem C are really quite simple. So, the chances of having similarities in codes are high. Even, my submission's main function has a lot of similarities with you: 124324875. It's quite unfortunate and saddening to see such false-positive cases. I hope, MikeMirzayanov will look into this matter and sort out this thing.

MikeMirzayanov This same thing happened to me too... I received an unexpected message from System saying that my submission was similar to some 10+ other submissions for this problem? This was purely coincidental at least on my end, since the problem's solution was so short.

Here is mine: 124296686.

Also my submission ID was earlier than every other submission mine was considered similar to, so there's no way I could've copied/cheated from any of these people.

Someone, please explain the first test case of question 5

The following segments are sufficient enough to reach from 1 to 12. However, you can additionally take other segments. But they will not minimise the answer.

Check out this tutorial for problem C: https://youtu.be/L7AhdGhO2v4

Please post the editorial asap

Did anyone who solved F use lca,dsu & merge small into large?

How A can be solved using chicken nugget theorem .

How can we solve C using dp?

When I tried solving problem B using long double for output, I was getting WA on Test 3. But when I used long long instead of long double in the same solution, it got accepted. Why? Can someone please explain?

I think it's because of your output format. You used cout for printing double value. But you didn't set any precision or width. A good way to print double/floating value using cout is:

`cout<<fixed<<setprecision(10)<<res<<endl;`

. Your failed solution was printing in this format:`6.55587e+006`

. Which might have led to the precision error.Thanks a lot for replying. It worked.

One constructive feedback : It would be really nice if educational rounds had atleast one problem with a high upsolve value for Div2 contestants, i.e. problem that is slightly out of reach for majority of Blue/Purple contestants.

In this contest, E is a very standard lazy segtree problem and F is (seems ?) too hard.

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Can anyone please advise how is it possible to pass the TL5 challenge in problem D? Here is my submission, cannot yet figure out the bottleneck. Thank you!

It turns out changing

`vector<int> p : r`

to`auto& p : r`

solves the problem.