Hello, Codeforces!

We have planned this round as a Div. 4, but testing showed us, that problems are more suitable for Div. 3. **Therefore, instead of the previously announced Div. 4 we will hold Div. 3 round**.

<almost-copy-pasted-part>

Hello! Codeforces Round #644 (Div. 3) will start at May/24/2020 16:35 (Moscow time). You will be offered 8 problems with expected difficulties to compose an interesting competition 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. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 8 problems and 2 hours to solve them.

Note that **the penalty** for the wrong submission in this round (and the following Div. 3 rounds) is **10 minutes**.

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

The problems for this round were invented by MikeMirzayanov and prepared by me and Stepavly

Thanks to MikeMirzayanov for platforms and coordination of our work. Thanks to antontrygubO_o, iankury, bfs.07, kocko, Ilya-bar, arsijo, pashka, Gassa, neal, vovuh for help in round preparation and testing the round.

Good luck!

</almost-copy-pasted-part>

UPD: Editorial is out

Look forward to this round. Thanks for offering div 3 and 4!

the pawns strike back

what does pawn mean in this context?

People who getting faster round acception for being in relationship with Mike (By his opinion)

I think Mike doesn't like favoritism at all. This is all about practice.

A pawn = puppet, marionette

Extremely rude.

Extremely rude.

Finally other author than vovuh for div3 contest

Last time vovuh wasn't one of the authors of a Div3 contest was 23 Div3 contests ago!!

As the contest was prepared to be a D4 one, also everyone knows that vovuh doesn't prepare D4 contests(at least until now), so there is no vovuh as an author here.

I hope that you rock this round. All the best chota haath mota pait.

Because of the round previously announced as div. 4 :D

This made me LOL, at least provide translation if you don't want downvotes lol

Hiruem chill h bro! Ye apne(indian) he hai jinhe samajh me sab aata h par phir bhi downvote karte h! Par apne ko ghanta pharak nhi padta bas thodi hasi thitholi ho jaye wahi bahut hai. I dont know why they cant take things as a joke.

Yaar, tu to bahut chalu hay

Great!

The time link always shows the Moscow time rather than the local time, please fix it

Div4 was an experiment. Keep maintaining the standard of Codeforces.

[deleted]

Thanks for the div3 instead of div4 :)

This weekend is lit , as CF contest at 7pm IST and at 9.30 Codechef Cookoff . Noice

Yup. And then 2 codeforces round + lunchtime this week!!

MikeMirzayanov Do you have any plan to run Division 4 regularly?

That was supposed to be div4. So, i think yes, he do.

[Исключен]

did you even bother reading the first line of this blog...

You are accepted anyway, isn't that great!

Where is vovuh :|

LOL, maybe it's the first div3 round which vovuh is not involved in.

No its rare but not first time

First time there will be 8 problems in Div3!!!

Is it rated since Division was changed from 4 to 3?

When it was div4 then it was rated for div4. Now it is div3 so it is rated for div3.

Every time contest is organised after so many days, I get excited. It's other thing that I'm not able to solve more than 2 or 3 problems in contest.

I'm starting to miss vovuh already. :(

And it has just been 9 days! .·´¯(>▂<)¯`·.

not div 4 Orz

We missing out on a potential DIO meme here xD.

Can anyone suggest best apps for writing code like codeblocks ( other than codeblock) for a windows user

Sublime Text, VS Code

You might enjoy using https://cpeditor.github.io/.

Isn't it unfair that those who have ratings 1599 can participate in the contest and make their ratings 1800+ but those with rating 1601 can't change their ratings?

I'm sorry but I have found candidate masters who find questions from div 3 contests interesting.

So,what should be the boundary? If it is x, will not it be unfair to people with x+1 rating? :v

One solution may be to cap the maximum achievable rating in div3 contests to 1600.

It is a matter of fact that nearly all reds started at aprox 1580-1595 and then instantly jumped over 2000... where they happily lived ever after. Not.

What is this nonsense about? You where below 1600 for like two years.

Codeforces never let someone stay above his skill level. If someone has skill level for rating 1600 then if he somehow gets 1800 rating then he will come back to 1600 within two contest. If someone gets uneven rating increment in one contest then he will distribute it in next contest. He will not take the rating home and sell it in local market. Codeforces will never let him carry a rating which he doesn't deserve. So one uneven increment doesn't matter too much.

I find a master who thinks div3C is too hard for my level. Yes. He is myself.

wat, then how are you a master, sir? Even me, the holy noobie can sometimes do div3C

Because I am not rated in div3, and I do well in div1(div1C is sometimes easier than div3C)

show me a div1C easier than a div3C, sir

1338C - Perfect Triples is easier than 1216C - White Sheet

This is a platform for practice so,if u are looking for placements wise even if u are expert company will hire you, if you are skilled. Happy coding!!. Take it in positive.

Please insert by before Sir MikeMirzayanov

Finally a contest after so many days. It will now be rated for me. Excited!

8 problems!!This will be fun.And here we go "A non-vovuh Div3 round" after consecutive 23 Div3 rounds. Hats off to vovuh for this 23 round streak. Good luck to new authors.

Maybe you could add one or two easier problems and delete the hardest problem, and then the contest could be div3 and div4, just like div1 and div2 in the past.

Will the problems include sub-tasks?

No

your photo represents my sanity

Can someone elaborate on what this line means:

do not have a point of 1900 or higher in the rating.

If someone has maximum rating 1900 or more then he will not be considered as trusted participant.

Can someone elaborate on what this line means: trusted participan

Sometimes some high ranked coder make fake account and participate in div3 rounds. So they get high rank on that contest. As a results, real participants can't know their real position in div3 contests. So, people who din't participate in at least two rated contests, then he will not be a trusted participant to stay in final standing. So, there will be no fake account on final standing and real participants can know their real position on standing.

A high rank coder can loose rating on purpose to reach less than 1600 points and get a good rank officially in div3 rounds. So if a contestant has 1900 or more maximum rating then if loose rating towards less than 1600 them he will also be not considered as trusted participant and will remain out of final standing.

Good luck to all! Live solving the problems 15 mins after the contest finishes:

https://youtu.be/gFepyRGn1vs

Only on Algopedia!

To be honest,vovuh & MikeMirzayanov always makes nice problemset:)

.

Eid Mubarak to all the contestants. Hope it will be a great contest for us before EID.

It is div4, lol.

How to solve C?

It is div3+4.

[deleted]

It should not have been a div3.

+1

Exactly

I didn't receive a reminder email

Yep, it is our human mistake. We will double-check it next time.

https://codeforces.com/blog/entry/78942

WHAT?! This is the first time I see that codeforces removes comments

From time to time somebody talks about problems while contest.

Video Tutorial for today's G

Quick editorial in Python. For more editorials visit this discord: http://interview.solutions

## Question A

Question A - TutorialWithout loss of generality, say the width of the rectangles are atleast the height, and fix the first rectangle. Now consider all possible orientations and placements of the second rectangle. We can see that only stacking it directly on top of the first rectangle in the same orientation makes sense. Under that placement, the side length of the square is max(2 * height, width).

Question A - Code## Question B

Question B - TutorialSort the strengths. The quantity |max(A) — min(B)| must be one of the differences s[i+1] — s[i], and it is possible to arrange the teams in this way (set A = all strengths <= s[i], B = the rest.)

Question B - Code## Question C

Question C - TutorialIf there are an even number of odd and even elements, then we can pair odds with odds and evens with evens, and we are done.

Otherwise, because n is even, there are an odd number of odd elements, and an odd number of even elements. We must pair some odd element with some even element. If we do, then the rest can be paired as before. If we can't, the task is impossible.

Question C - Code## Question D

Question D - TutorialRephrase the problem: we want the largest d <= k such that n % d == 0, and then we return n // d.

Let's simply try every divisor of n and take the best.

Question D - Code## Question E

Question E - TutorialIf there is a 0 below and to the right of a 1, then the 1 could not have "landed" when shot by a cannon. This is a necessary condition for success, but actually it is sufficient too.

We could build the matrix layer by layer, starting with the last row and column and moving towards the first row and column. For example, these are the layers of a 5x5 grid:

Each layer's construction is similar: its guaranteed by the condition that only cannons that fired last layer could potentially fire this layer.

Question E - Code## Question F

Question F - TutorialBecause the limits are low, basically any solution will pass. We just do the laziest thing, which is for each word, we know neighbors(word), the set of words that the answer could be. We take the interesction of all these possibilities.

Question F - Code## Question G

Question G - TutorialSay the grid is R rows and C columns, and has horiz_ones ones per row, and vert_ones ones per column.

The number of ones in the grid is R * horiz_ones, but its also C * vert_ones. If these values are different, the task is impossible.

Otherwise, it is possible, and we show a construction. Let's have each row r consist of ones from c =

`horiz_ones * r`

to`horiz_ones * (r + 1) - 1`

, possibly wrapping around. It clearly has the right number of ones per row. Because horiz_ones * R is 0 modulo C, each column also gets an equal number of ones.Question G - Code## Question H

Question H - TutorialBinary search for the answer. Let's say we have some guess

`x`

for the answer: the rank of our guess`x`

would simply be`x - (number of a[i]'s that are below x)`

, which we can find with another binary search.Question H - CodeMen, thank you so much, you make this editorial faster than the speed of light

Problem G better version: https://vjudge.net/problem/LightOJ-1330

Solution available on net.

But your G solution hacked .LOL

1st time I solved

6questions in a contest. Yipee!!Can anyone help me with what peculiar case can be in Case#2 of problem F ?

I kept getting WA on Case#2.

try this

1

4 4

abcd

aacd

abbd

abcc

G is same as lightOj 1330.

Not the same because you are not asked to output the lexicographically smallest, but is true that the solution of LightOj works for today's G

Why greedy isnt working for G?

The greedy I came up with would give "NO" for 3 3 2 2

Can someone tell me why this got TLEd - https://codeforces.com/contest/1360/submission/81243429 and this got accepted - https://codeforces.com/contest/1360/submission/81245539

Both are exactly the same code.

Seriously it's div3. Nope. I think it's the actual div4. Where you would have trivial A, B, C, D, E and not so trivial F, G and really hard H. G was super cool though. Felt like a fool after solving this.

The input data of Problem H is 6MB at worst. Using cin will get TLE, using scanf will not get data because of strange '\n', using some other library also fail.

A problem's difficulty should be how to solve it, not how to input it!!I didn't believe there was an issue with problem G, since I solved it using cin, with the same expected complexity as given in the editorial.

Check the editorial. Our solution use cin and get AC.

MikeMirzayanov Does increasing the number of questions of DIV4 makes the round DIV3? I hope thats not true for DIV2 round.

I

(personally)don't think so, since usually some contests that are harder or have more problems have their time extended, instead of increasing their division. Also, I(again, personally)believe problems G and H were more suitable to a div. 3 contest, rather than a div. 4 contest.Then again, I did not participate in the problem-setting nor testing of this round, so who knows ¯_(ツ)_/¯

I actually spent more time debugging than reading and thinking combined..

Can anybody kindly show me a test case where this bruteforce(!) solution fails?

1

2 3

bbb

baa

the answer could be "bab" , your solution prints -1.

I hope this is the first and last div3 that you organised.

Can I see due to which test case my solution was hacked>?

What is the best time complexity one can achieve for problem F ?

Definitely this is not the best, but let's analyze this:

Take i-th string. Then for each position j, you try each of the N letters in the j-th column of input. There are N*N*M possible strings making this procedure. Then you need to check if that string works, in N*M complexity. Final complexity of this is O(N^3*M^2). I wonder if there's a O(N*M) solution

O(N*M) is possible: https://codeforces.com/blog/entry/77846?#comment-628882

For the first time in my life solved 5 problem. Thanks to the authors.

In F , I used the brute force concept and my run time complexity was O(n^3*m^2). How to solve it with larger constraints ?

It can be solved in O(26*N*M^2) by trying to change every letter in the first string, to every possible value. Then you check if that string works.

This div3.5 contest was awesome

I think it was better to keep it div4. Div 3 E F problems are generaly much harder than all of these problems.

MikeMirzayanovThis two people are copying codes i guess https://codeforces.com/contest/1360/submission/81303569 and https://codeforces.com/contest/1360/submission/81306780 other solutions of them are also similar. Their previous contest submission are also same. Sorry for bad english. Please look into such acts.

Edit: I just saw that all their submissions are similar. They are taking plagiarism to next level.

you forgot to mention that they are from the same university in Indian. And... they have the same rating graph =))

Can anyone help me with what peculiar case can be in Case#2 of problem F ? I kept getting WA on Case#2 https://codeforces.com/contest/1360/submission/81313261

I used bitmask dp to solve F in O(t*(1<<n)*m*n^2) and It got accepted in 31ms ... Can anyone provide a testcase which can find the upper bound of runtime .....here is the submission — 81323908

I did the same but i forgot to mark my visited array because which my solution is running exponentially and guess what.. it still got accepted

I think this will pass. In the recent educational contest my soln with 3e8 operation got accepted with 900ms.

Actually I know this will get accepted....My problem is that it got accepted in 31ms which I didn't expect and it's 0(10^8). While O(10^9) shows tle in 5 sec....

how did you guys approach, your thought process to find out how to arrange all the one's

I used a network flow to solve G lol. Anyone else?

Can you please tell how to apply network flow here?

You can build $$$n$$$ nodes on the left and $$$m$$$ nodes on the right, representing the rows and columns. And link an edge from every row to every column, with capacity $$$1$$$. Then link an edge from the source to every row, with capacity $$$a$$$. Also an edge from every column to the sink, with capacity $$$b$$$.

If the edge from the $$$i$$$-th row to the $$$j$$$-th column is full, put $$$1$$$ on $$$(i,j)$$$.

Thanks for reply. But i have a doubt. Can you please tell — since the graph will not be unit-graph so complexity will be $$$O(V^2E)$$$ instead of $$$O(EV^{1/2})$$$ for unit-graph. Also edges will be of order $$$V^2$$$ So for $$$1000$$$ test-case time will be $$$O(1000*(50)^4)$$$ but still it's not giving TLE. why? Am i wrong in computing complexity? Please Help.

Oh it seems I got the complexity wrong. I didn't realise $$$E=n^2$$$ and thought it is $$$50^3$$$ per testcase. I don't know why it isn't giving TLE, maybe on such special graph the complexity is actually lower?

Can some cool guy explain the fact that when anyone ask "Is it rated",he must get many downvotes

Generally, it is written in the announcement if the contest is rated or not.

Why do ppl still do that? :) Was that supposed to hide from hack?

=> 81289430

maybe to not get caught by a plagiarism checker

Pretests for Problem D were quite weak..... Lot of problem D solutions were hacked.... Felt demotivated after hacked question, as it affects rankings a lot.....

I'm so sorry I was upvoting your comment but it got downvoted. What did I do I'm so sorry!

Has the system testing finished? If so when will the ratings change?

Wait till evening

What why?

Why am i still unrated even after participating in the contest and given solution 3 problems?

Cuz they haven't given out the rating updates yet. Look system testing started. It'll happen soon enough I guess.

Ok I am new to this site . Thanks for helping out

If you had felt that the problems are bit difficult for DIV4 you should have put some easy problems in place of those hard problems and make the contest as DIV4. I think the problems are easy for DIV3.

Will i be awarded points for successful hacks in this contest... If Yes then how will it be adjusted to the final rankings

No, you won't be awarded any extra points for a solution hack. It's just that it will affect others' solutions after the system test, and your rank might move up the table (because of others moving down).

Hacking doesn't yield extra points in Educational and Div 3 rounds (both follow extended ICPC rules for scoring).

Thank You for Information.....

A very fast system test today after quite some time. Even after the number of participants.

Yes hardly took 40 mins to finish

My first screencast. Would take suggestions to improve.

I would like to appreciate MikeMirzayanov and his whole team for an amazing round. There was no queue during the contest and it ran very smoothly. So it was great work by codeforces team. I hope future rounds are going to be the same one as this.

Dang its been almost 3 hours since the system testing finished, how come no rating update yet?

why is my rating not changing even after the final standings of the contest are out

I have the same question.

for F question. I haven't copied the code and it is entirely different anyways...please resolve the issue asap. I think this may be caused due to the input reader method. Not the logic of the question. manish_98 solution: https://codeforces.com/contest/1360/submission/81281906 my solution: https://codeforces.com/contest/1360/submission/81299107

update : issue resolved by Mike :)

Funny that my first time I solved 5 problems, I decreased in rate :P

Can someone explain how this user went to CM without solving even a single problem?

I think it's because of changes made for the new rating distribution, and I think they messed up somewhere.

According to the post, that user should get -100, but since the first contest displays a rating of 500 + (rating that the user should differ by in the contest), the user was able to get +400 rating.

Wow, is this even real?bug?

Probably. The latest contest's rating changes are rolled back right now. I hope mine will change to make me an expert :P

What the hell! New Ids becoming Master/International Masters with +800 Rating.

I see many success stories on the way titled "How I became an International master in 2 hours "

I have observed that problems in CF Round #644 (Div 3) were quite easy. Except the last, all problems had 2000+ successful submissions during the contest. Due to this, the rating of participant in 1400-1600 exploded. Adding more to this, new accounts became masters just by solving 2 problems last night. LOLzz.

This might be due to new rating system. However, this completely destroys the motive of the new rating mechanism, that was to reduce creation of new accounts.

I propose two points after seeing what happened:

Withdraw the new rating system.

Make prev. round unrated for participants who were in 1400-1600 before the contest. As the problems were indeed suitable for Div 4 contests only.

Comment if you agree/disagree with my proposal.

First one is more appropriate

Disagree. When the problem setters already claimed that this set of problems was more suitable for Div 3, then why debate on it? They have much more experience (along with better coding skills) than us. And, don't forget that among those 2000+ successful submissions, there are also submissions made by unofficial contestants.

+1

rating changes are rolled back already

I become expert today for the first time..That's a great feeling .

From my profile page, Rank displayed is 6204.

Whereas from the contest's standing page, it's 8146. Is this a bug or is there some reason behind it?

The rank which you are seeing on the contest standing page also includes the particants with rating above 1600(i.e the ones not eligible for Div3)

Can u explain me Spy Strings

There is a problem in test case 2 (20) in problem 2.

Let me guess: You solved it, but the grader says "wrong answer".

Yes. What is the problem here? I solved it manually also, it shouldn't be answer it shows.

If you link your submission propably somebody can tell you.