Hello Codeforces!

On Mar/02/2021 17:45 (Moscow time) Educational Codeforces Round 105 (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 Roman Roms Glazov, 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:

*Amazing news once again, Codeforces!*

*We are especially glad to have a chance to share our scholarship opportunities more often!*

*This time we have partnered with OneRagtime again to open the door for an exciting career in technology for the most talented people in our network.*

*In partnership with OneRagtime, we are offering a full scholarship to study a Master’s in Computer Science at Harbour.Space while working as a Full Stack Developer at OneRagtime!*

*Scholarship Highlights:*

➡ *Work in Europe’s most exciting tech cities*

➡ *Scholarship value of up to €31,500*

➡ *Competitive compensation for the internship at OneRagtime (€800 / month)*

➡ *Opportunity to join OneRagtime full-time after graduation*

*Some of the advantages of working at OneRagtime:*

*International team**Fast-paced workplace**Be a part of the OneRagtime adventure!**Be fully immersed in the European tech ecosystem**Thrive within a Venture Capital that does things a little differently**Work in Europe’s most exciting tech cities*

*We have previously partnered with other companies like OneRagtime, Hansgrohe, Coherra, and Remy Robotics to empower young talents around the world and help them boost their tech career. We’ve already filled a few of the positions with OneRagtime including:*

*Full Stack Developer at***OneRagtime**awarded to Alejandro Martinez from Mexico*UI/UX designer at***OneRagtime**awarded to Davit Petriashvili from Georgia

*We are always happy to see Codeforces members join the Harbour.Space family. Apply now to get a chance to learn from the best in the field and kickstart your career!*

*Keep in touch and follow us on LinkedIn for more scholarship opportunities. And follow us on Instagram to evidence student life, events, and success stories from our apprenticeship program students.*

*Good luck on your round, and see you next time!*

*Harbour.Space University*

Congratulations to the winners:

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

1 | antontrygubO_o | 6 | 251 |

1 | Pyqe | 6 | 251 |

3 | 244mhq | 6 | 260 |

4 | tute7627 | 6 | 272 |

5 | Um_nik | 6 | 288 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | noimi | 11 |

2 | neal | 7 |

3 | Origenes | 6 |

4 | Kregor | 5:-2 |

5 | chilliagon | 5:-4 |

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

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

A | noimi | 0:01 |

B | noimi | 0:04 |

C | wygzgyw | 0:15 |

D | conan1412yang99 | 0:16 |

E | thenymphsofdelphi | 0:15 |

F | rainboy | 0:35 |

**UPD:** Editorial is out

Good luck on the contest everyone!(if you are participating that is)

hmmif you were red coder then you would get upvote

I know, but what can I say, it's a RED dominant community.

Lets hope people(like me) losing rating in Global round can gain positive delta in this round :)

Edu Round :- its_Atrap

:( People using my handle to get upvotes :P

Edu Round :- people are using me to get the +ve delta :(

Edu Round: Into_Your_Arms

Sad 4hours and still no upvotes, this clearly indicates I was not wrong :P

And even downvotes :(

[DELETED]

My chance to become specialist :-P

Such a long announcement

True Lol

It would be very cool too see in future video editorial from the authors!

P.S Sorry for bad English.

Hope for green.

And, I am hoping for

VIOLETXDIs there any points system associated with educational rounds and how do successful/unsuccessful hacks affect the points system (if there is one), ranking and the rating?

The person whose solution you back will get deduction of points as his solution will be marked as wrong. You will not gain any point for successful hacking and neither loose any point for unsuccessful hacking .

Thanks!

Reality :)

So real for me

Worst Experienced :(

Did you change your PC in the meantime? :D

Got messed up and shifted to adjacent PC :D

That feeling when you got a 1500th place in the beginning and tried to solve B problem the rest of the time and you end up in 4000th place

maintaining speed solving is necessary.I was not solving easy problems in last few days.That really backfired

Somebody can explain how to solve problem B

4 corners, each having 2 choices (black/white). Iterate over 2^4=16 possibilities

hhhhhhhhhha

Let's just hope that problem A isn't 2 lines of code while problem B requires 3 dimensional dynamic programming and you need to precalculate all the stock market crashes in the next 5 months.

I hope there are no adhoc/constructive/geometry/very mathy problems.

Sooo what would be left? Backtrack and graphs?

Both of them are taught in math. We're left with a round with 0 tasks

Wait! This isn't codechef.

I wish higher problems had higher points :(

.

I have participated in 50 contests! Will i be CM before my 100th contest?

of which state?

Uttar Pradesh

My Last brain cell during contest:/Ahh life's too stressed ....wake up 12 in the noon pass the time learning algos till 7...then CP till 11 and then Counter Strike till 3 am ,sleep at 4:30 and repeat. I guess i messed up this lockdown .

What about college?

Your rating graph is so close to mine, surprised to find such a guy

I wish I can do well in this round!

Delayed by 10 minutes!

The last time this happened, the round was declared unrated...

The last time this happened, the round was declared unrated...

Lol.

Didn't check before posting that I was a newbie again ;)

Well, it's delayed. Here we go again)

delayed by 10 minutes..duh

.

Delayed by 10 mins.Hope the contest to remain rated

Contest has been delayed so I'm here because I don't know what to do with my life for the next 10 mins.

Read a book lol

We can just pray It starts after this 10 minutes, otherwise we won't know what to do for few more minutes xd

What ever the reason of delay is, I hope the contest doesn't become unrated again.

.

I just pray it don't go unrated.:(

why they extend time , it affects mindset of some coders ,what do u think guys ?

you do realize they don't delay it for fun right?

oh,a delayed contest may lead somthing unlucky and I hope the contest will go well.

10 more minutes of TWICE it is :D

I this 10 min I realize how useless I am..

Hope to become cyan.

This type of Div 2 B demotivates me very much

bruteForces

I really hated this B because I tried to solve it the wrong way I guess

Some one please tell me about process of B i was trying since 1.5 h but i can't find a answer. Please help me to find out the answer

It's almost same as A, just bruteforce the 4 corners (2^4), and check if 4 numbers are not negative and less than n — 1.

why should all be less than n-1 ?

Because you already know the 2 corners for each row/column so you have n-2 remaining cells.

just a thought.

"2 corners for each row/column so you have n-2 remaining cells"If above is the reason for

"check if 4 numbers are not negative and less than n — 1"in your first comment, It's more clear in the first glance if you say

"less than or equal n-2"instead of"less than n-1"I dont think A and B are almost the same

What do you think about this for B

Codecheck for n = 4, u = 1, r = 1, d = 1, l = 4.

should it be no?

no

Can someone tell how to solve B

Brute force cases for corners and fill the edges, then check if it's correct.

Gap between B and C was very huge , fucked up in the contest literally fucked up !!

It's actually hard to achieve...

And It seems that E is easier than D (aftering having a look... XD

Yes it is! Regret not looking at it during the contest while spent 1+ hour on D and got nothing :(

This round seems more educational. :(

Less dp problems, more implementation problems...

ImplementationForces

UPD:AC code`it == a.end()`

should come prior to`*it`

I guess.Really bad problems

Problems were hard, indeed, but I think there is no bad problem.

In problem B, you only need to check 4 corners, which is totally 16 situation, and just brute force all of them, If you use if else... if else..... you will probably get WA till the end.

Can you tell the 16 situations?

{{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 1, 0}, {0, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 1}, {1, 0, 0, 0}, {1, 0, 0, 1}, {1, 0, 1, 0}, {1, 0, 1, 1}, {1, 1, 0, 0}, {1, 1, 0, 1}, {1, 1, 1, 0}, {1, 1, 1, 1}}

Thanks a lot shekharmaheswari

Cheers

Also, in problem A you only need to check 6 situations and find if at least one of them will get a regular brackets sequence :)

See my code here: 108894342

My impression when i see the accepted on B after 1.44 hour continuous trying xD .. I am getting negative delta but still happy xD

SpoilerSpoilerFor B just try all combination to make 4 corners black, nothing else.

You can just check the minimum number of blocks that should be black in the border columns. You can check my submission for more clarity.

I hope to become a potato now.

basically https://codeforces.com/blog/entry/88284?#comment-767085

Is the solution to C a two pointers?

Either two pointers or binary search (I think the latter is easier).

The main idea is to split the line on $$$0$$$ to get two independent problems. After that, suppose we are pushing blocks to the left (solve the part with negative coordinates). We should push them so the last block we pushed coincides with some special position. We can iterate on this position, calculate the number of blocks we push with, for example, lower_bound, and then calculate the number of special positions in the resulting segment of blocks with another lower_bound.

Thanks a lot! I think the binary search is easier to implement. I spent 1h 50min on C, and I just realized one variable was misswritten. Got AC with the two pointers idea :/

Oops !!! I was trying to coincide the first block with some special position and got around 10 WA on pretest 2 :(

Could you tell me any test case, why matching the first block to some special position leads to non optimal solution.

I think there is nothing wrong in putting the first block in the special position. But it was difficult for me to track how many blocks will be one after another from the first block which I realised after the contest. I think both approaches are correct.

Yes, I got AC by placing the first block in the special position.

Hey,is there any reason why we had to use complicated language like supervisor etc for Probelm-D? Stating it simply in graph theoretic terms like "There exists a rooted tree, each node has has a number and a value. The value of each node is strictly greater than the value of each of its children. You are given the number of leaf nodes and the value of the lca node of each pair of leaf nodes. Construct any such possible tree". I was so confused for so long thinking the given values for each pair was the minimum of direct supervisors.

Most problem setters have majored in literature and they don't want us to forget that fact. (EDIT: Just kiddin)

VerboseForces

In D, I did the following: if two vertices' common salary is the maximum overall, it means that the root of their tree must have that salary. Thus, we can start with an initial set of leaf nodes, and split them into two sets according to which ones have the max common salary or not. Then create a new root node and recursively process the two sets.

Is that approach incorrect? I can't find a counter example :(

Here's my submission: https://codeforces.com/contest/1494/submission/108943905

Thanks.

One vertex can have more than 2 sons. Test:

Could u please help me in finding the error in my logic as well?

I claim — "That every distinct value written in the 2D array is a new node in the tree"

Let's say, that for some

`val`

, which is connected to nodes $$$a0,a1...ak$$$, we will create a new`node`

and make`top_most_parent[a0], top_most_parent[a1],... top_most_parent[ak]=node`

.The idea is motivated from the idea of LCA itself, which is, that the $$$LCA(a,b)=parent(topMostParent[a])=parent(topMostParent[b])$$$

It seems, that Ashishgup also implemented the same idea. I don't know what went wrong.

Link to my code

Link to Ashisgup's code

Thanks in advance!

I havent look at the code, but there csn be many nodes with same value.

Do you mean to say, that for some value

`val`

, instead of having just one new node, we might have more than one new nodes?I think in that case also, we can create just one single node

I understand my mistake now. Thanks for helping !

Well yeah, there can be many nodes with the same value. Test:

Ok, I got it, thanks!

Screencast with commentary (the quality will get better when YouTube will process it)

Solution: https://codeforces.com/contest/1494/submission/108942229

LCA of 1 and 3 should be 5 but checker says that it is 4. Is there anything wrong ? Is my output format is wrong ?

same problem

3rd line you need to output the root of the tree, not the number of edges

Oh, okay thanks.

got it thanks

The 4 in the third line should be the index of the root, not the number of edges. So for your solution, it should be 5.

I solved A and B in a similar manner (brute force). For A, I iterated from 000 to 111 (Binary) and checked every possible string b. For B, I iterated from 0000 to 1111 (Binary) and checked all possible black intersections.

Thanks for reminding bitmask idea, I brute forced using recursive functions which was more messy to code.

it was a bit different. did anyone else get stuck in B?

Yes sir

In my case, not only was I stuck at B for almost two hours, but also I have a -130 rating change :(

how do you know your rating change before finishing contest?

Use CF-predictor plugin or CF rating predictor website

:'(In my case, this meme perfectly summarises (almost) the whole contest

same

i thought i should output number of edges in problem D :(.

me too. And I fall into the hell of WA1 :(

Why sometimes "out of bound" gives WA and sometimes RE for the same compiler on codeforeces?

I think the last educational round was very easy than this one.

what's the wrong with my idea of problem A.. My idea was in a greedy fashion. every balanced parenthesis start with ( and ends with ")". so I checked s[0] and converted all of with "(". then I checked s[n-1] and converted all of them with ")". then, there is only one character(A or B or C) in S. at first, I convert that with ")". after that with "(". then, checked the validity for this two options. But wrong answer. my submission may you help me ?

Maybe you missed the case where s[0]=s[n-1]

Its because you may get cnt as negative that means you will have more number of closing brackets than the opening one which is not true..

GraphForces

I know it might be out of context but I wanted to say this for a while.

I think the point system in educational round(also div-3) is a bit unfair. All of the problems are assigned 1 point even though they are in increasing difficulty. For instance if somebody has solved problem A and C but not problem B (unlikely but still happen sometimes) then his ranking would be similar to someone who has solved A and B but not C. Even though the first person was able to solve a tougher problem(theoretically and practically) he is still in the same position as the second person which seems unfair to me.

A problem with higher difficulty should have more points, For instance the score distribution in Edu and div-3 contests should be 1,2,3,4,... so on. What's the problem with this score distribution? Maybe I'm missing something.

Open to criticism :)

`(unlikely but still happen sometimes)`

It's more likely than you think

If the first person couldn't solved the easier problem then apparently it wasn't an easy one for him. If he could solve the easier problem he should have solved it, since he already know the rules before the contest.

`Even though the first person was able to solve a tougher problem(theoretically and practically) he is still in the same position as the second person which seems unfair to me`

ICPC

It is classic ICPC format

sent by mistake

For Div 2B,

Can anyone please help me with the testcase where my code fails? 108917717

I am unable to understand the issue with my code.

Try this case:

Your Answer :

`NO`

Actual Answer:`YES`

.

Try with

`ABBAAC`

. Your code thinks that`())(()`

is okay.many of the solutions of F can be hacked with the case

there seems other hack case for other participants which couldn't hack with this case too. Is the testcases prepared for the system test strong enough??

Seems like todays winner is not alone check his submissions.

результаты

Why do you say That he is not alone! am I the only one who didnot get it?

because both have rank1 due to the same score and penalties

One of shorter solutions for

Bobtained by factoring out symmetries: 108950466 -(Perl). Idea was to squeeze all posible corner cases. I.e. consecutive`n 0`

is impossible, and it is symmetric to`0 n`

in reversed direction.I don't know Perl but your submission looks like it's begging to be hacked

Can someone tell me case number 78 in test case 2 for problem C? Here is the link to my submission that fails at 78th test so can't figure out why. Thanks!

Same

Hi, i got the same wa, and found that case (isn't the 78th, but breaks the code)

1

4 5

1 2 4 6

4 5 7 15 17

Correct answer it's 3.

can you help me out with case 126 of TC 2 in problem C. Here is my link to submission

My Approach:

Divided the problem into two parts (1. positive 2. Negative). solve the negative part in the same way as positive. positive part ( made 2 array for positon to be kept/ special position(sp) and original position our block(p) ) 1. I made a suffix array of already set blocks.

Traversed through the sp(i = 0 to i < len(sp)) and lowerbounded on p with sp[i] those whose position is <= sp[i] , say found the val at j(index in p).

lowerbounded on sp with sp[i] — j (which would give us the maximum contiguous block such that some or all of them are on special position having end at sp[i]), say found at k.

the no of blocks satisfying the condition = k-i+1+bolcks that are alredy on the special position after this position(suf[i+1]).

found maximum for all all indexs

The idea it's okay. But your code has a little a bug:

ll j = lower_bound(p.begin(), p.end(), sp[i]) — p.begin();

if(p[j] > sp[i]) j--;

if sp[i] it's bigger than maxValue on P, then your code will access to an unkown position. Same for negative one.

You can fix it by put this before the iteration:

p.pb(INF); n.pb(INF);

ohhh, I thought of that secenario but for some reason i always thought it would be handled automatically.

thank you , For clearing my doubt.

Will keep this in my mind next time.

Thanks!

How to overcome pain in ass when you keep getting WA on test 2 after implementing for almost 2 hours ?

Today I waste 1.5h to solved problem B but still I can't solved it. that's make me ☹

Realy bad contest ,, its just about hard implementation not about problem solving. also late editorial .

I think that's why it is educational. A lot of "how to get that parts right...". Not so much "lets have fun".

SIMULATION-FORCESBut now it got unrated :(

What? Where did you see this? It's not in the announcement section!!

Yours is also unrated :(

Go to see your rating graph or click here

I think it will be updated soon as i think there is no official announcement. Wait for some time, rating changes for educational rounds take some time.

In B, I am trying every possible move by recursion

can anyone point out what's wrong in it ?

code`Your code is giving YES for this but I think it's wrong.`

Thanks for your help :)

Please share some memes I can laugh at; to ease the pain.

A non-intern student can earn twice that amount while doing less work. What a joke! (assuming internship = 40 hours/week, location = Paris|Barcelona)

In which country/city? Tell me, I am interested to relocate

In most western EU countries, Germany, France, Ireland... you can check the minimum wage across these nations which is compulsory as long as the word 'intern' doesn't apply.

Well, for a western country or a big city, the 800 Euro sum doesn't seem like something big. In my city though, it's three times the average salary

The same for my home country (enough for 1 year of living if you live in the village) but what I am trying to criticize here is the fact that they are exploiting student labor. An intern is practically just a student but the pay gap is huge because it is compulsory in their curriculum even though the work is similar.

How many of you think that awoo was better as the coordinator for edu rounds.

PS I thought pikmike !=awoo

What is the expected solution to problem F?

I thought about the following one, but it recieved WA on test 19:

If the graph contain 2 or 0 odd degree nodes, just find an Eulerian Path.

Otherwise, I claimed that: It is not possible to start a shift on node U, go to neighbor V and dont return to U immediately. Suppose that we went to node V and didnt return to U immediately. This means we didnt deleted the edge (U, V) so we must delet it later. Then, we will traverse a path that goes back to U, using the shift, implying that there will be edges on this path that will survive, leading to a contradiction, because we would never destroy all the edges of the graph.

Then, it follows that: After some "Eulerian Path" that ends on a node U, the remaining graph must be a star centered on U. Is this solution incorrect? (There are some cases regarding to the part of the code that finds the possible star, but is all coded here: https://codeforces.com/contest/1494/submission/108965452)

Try this:

SpoilerThe answer my code is printing is 0. Oh, I see, there is an answer. Thanks!

I'm very vegetable.

When we got editorial?

Cu ball(have the same question)

Please upload the editorial..!!

Will this round be unrated now?

NEED EDITORIAL. PLEASE UPLOAD THE EDITORIAL.

How to solve problem A. Iam new to this please help

So given a string, we need to check if it will be a regular bracket sequence,

We can only use '(' and ')' to replace the characters of the string, it is also mentioned that all the A's should be replaced with the same bracket, all the B's should be replaced with the same bracket, and also all the C's should be replaced with the same bracket, this narrows down the problem much more, for any bracketed sequence to be a regular bracket sequence it needs to start with '(' and end with ')', this can only happen when the first and the last characters of the string are different so that all the occurrences of the first character can be replaced with '(' and all the occurrences of the last characters can be replaced with ')'. If this is not the case then it is not possible. So for now replace all the characters of the string as given above,after this there exist 2 cases:well, that is it :) my method is a bit lengthy and brute force-y haha but it gets the job done, comment if you did not understand anything.

Solution my code in python, ignore the staring wrappers and functions the solution is from the checker function.

See my comments above

When will the ratings be out?:)Is this round unrated? For the first time I got 4k rank and now my rating doesnt change ;(

wait for it i guess

It shows unrated in my previous contests column, thanks for answering anyways

It was rated for div 2 but why it is showing unrated to me?

Mine also showing unrated ;(

If it's rated I could become green :(

Can someone help me figure out why is the first pretest failing for me for Problem D. https://codeforces.com/contest/1494/submission/108949724 . The tree i have built doesn't seem to have LCA as 4. It should be 5.

The root of the tree should 5, you have printed 4

Oh thanks ! Rookie mistake.

Because your root is 4 your root need to be 5

Someone, please tell me why is this code failing for B 108907428

Codethis is the test case you failed at: 2 1 1 2 2

.

Are the system tests over?

yes

How to solve D? Please if someone knows explain it! Thanks in advance xD!

Put pairs of points with the same point weight in a vector and enumerate the point weight from smallest to largest. Maintain a merge set, and for point pair (i,j), get the ancestors x and y of them. if they are the same then skip. If one of them has the same point weight as the currently enumerated point weight, then connect the other point to that point. Otherwise, a new point is created and both x and y are connected to the new point.

You can see ny code at https://codeforces.com/contest/1494/submission/108925449

Sorry that I'm Chinese and I use DeepL to translate. Never mind the mistakes in my words.

Wating for rating changes & tutorial...

When will the editorial be out?

WAITING FOR RATING CHANGE .....2 HOURS LATER........ WAITING FOR RATING CHANGE .....2 DAYS LATER......... WAITING FOR RATING CHANGE .....2000 YEARS LATER..... WATING FOR RATING CHANGE

Guys, please give editorial if not rating changes !

Edit: Nevermind, ratings updated!

Time to downvote the article to get attention.

Already started 163->154

E was easier than B.

We had a similar question in Round 699 ( I guess it was D). So E was even more easier because of that.

I was wondering If I have seen this before. Yeah, it's almost the same.

Me: getting positive delta and waiting for the rating changesMike: It's time for another testMe: What's that ?Mike:Patience TestWhy edu rounds take too much time updating rating even after hacking phase?

Literally me when edu rounds rating changes appear :)

Does it take this long for every Edu round or is it only because we had a delay this time?

It's normal for Educational Rounds

Oh okay, thanks!

I think I have a short greedy solution for problem B (as it passes system tests).

This is my solution: The variables na, nb, nc, nd (in my code) represent the number of black cells left after taking away the black cells that also belong to other sides. So, if there is a side with n black cells, I reduce each of the two variables that represent adjacent sides by 1. If there is a side with n-1 black cells, it means there is one or two sides that share with it a black cell. I greedily reduce only one side — the side that has more black cells left. I return "YES" only if none of the variables has become negative.

Has anybody done the same? Was this intended to work? Link to my solution: https://codeforces.com/contest/1494/submission/109001204 109001204

Yeah, mine solution is the same as yours and it passed the system test too.

I have done the same.

Same here, tho I made the picking of the side to add 1 black cell to for a side with n-1 black cells a little complicated. And i wasn't also sure if it works starting from any random side, so i looped, the algo to run 4 times starting from all sides then checking the one that works.

when will ratings get updated??

when the next Halley's Comet will be seen... You will get your rating! XD

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).For editorial try this

If the rating change system is slow, you could release it as a problem for the next Div 1 contest and get 1000 better algorithms.

At last!!

Editorial is ready: https://codeforces.com/blog/entry/88344

But ratings are not updated yet :(

It seems to be (being) updated now! Finally!

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Is it rated?-- The contest seems to be under-rated.

The round hadn't much lags and hadn't long queues. It had nice problems, all seem original, having wide diversity. B wasn't about implementation, but about logic and patterns, solving of which reduces implementation difficulty.

Thanks for organizers team.

I published my code on ideone.com with default settings as public. It was a coincidence. Please restore my ratings. I'm just a newbie so I didn't know much about this. I'll take care about this in future, I'm so sorry.