**Notice the unusual start time**.

Hello!

Codeforces Round 674 (Div. 3) will start at Sep/28/2020 11:05 (Moscow time). You will be offered 6 or 7 problems (or 8) 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 rating 1600 or higher, can register for the round unofficially.

This round consists mostly of the problems of the first stage of All-Russian Olympiad of School Students in Saratov and will be hosted during the real competition time. The problems were invented and prepared by Ivan BledDest Androsov, Alexander fcspartakm Frolov and me.

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 6 or 7 (or 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 a *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.**

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

**UPD**: Thanks to Ivan MrReDoX Ushakov, Ivan Ivan19981305 Georgiev and Dmitry nuipojaluista Kadomtsev for testing the round!

**UPD2**: Editorial is published!

*Notice the unusual start time.Thank you so much!! I would have missed it.

I think vovuh should update the blog mentioning unusual start time.

weird time tho

Sorry cannot participate because of the practical class at the same time

Same but I am bunking them.

Gonna get my ass kicked for codeforcing at work xD

Me Also. xD :) ()

Why so unusual start time ?? :(

"This round consists mostly of the problems of the first stage of All-Russian Olympiad of School Students in Saratovand will be hosted during the real competition time."I See, its going to be fun then!!!!!!!!!

So unusual time. Its lunchtime here in India.

And the standard time is dinner time ;_;

dont say lunchtime...it confuses with codechef lunchtime ....lol

but lunchtime is at dinnertime

All-Russian Olympiad alright imma skip this one

This is the first (of 4) level of Russia National Olympiad. Problems usually are really easy.

I am trusting you

me too

Me after remembering the previous div2 contest based on russian Olympiad for school students: i am gonna skip this because of unusual time.

Its Div-3 bro, what do you got to lose, its unrated for you

really wanted to participate but wont be able to due to my online classes.hope for some magic

you guys are attending online classes?

No, TBH.

F**k online classes. They are not worth attending!!

I am skipping classes.. not worth enough a CF contest lol.

i am also skipping my class

Really excited for this contest, but it's unusual time is not suitable for most of the college students in India as we have online lecture at that time.

you guys are attending online lectures?

submit F in last 5 seconds and find my output is following:

instead of

Hope my solution is wrong XD

Round is not even started yet, but u already submitted, Ur coding speed is so enormous!

I miss the golden time in which I can delete the misplaced comment. T_T

well looks like your wish came true xD

Deleted for posting at a wrong place.

Too bad this contest is Div 3.

Gonna wake up at 4 am(my local time) for this contest! Very excited!

Time too bad. Have classes. Any after 3pm UTC works fine.

Every time I want to improve my CP skills, my college is letting me down and this is another example.

It would be pretty good if CF were in this time rectangle in the future.

Another suitable time for Chinese......

But "based on" makes me afraid!

I can finally have a CF competition and have not to sleep at 1:00 in China :)

Don't be afraid!It isn't hard at all!

Oops, sorry It was the wrong post :((

SpoilerCoding is love.

![ ](

Same here bro xdd

vovuh score distribution plzz..

There are no score distributions in Div.3

IN INDIA IT's OUR ONLINE CLASS TIME

It's impossible to conduct a contest such that time will be suitable for everyone across the world.

This is the first time a div3 round is not rated for me!

idk i just want to share this

After a long time, a rated div3 for me :P.

glhf

How to solve F?

we want to count the total number of abc, ab?, ?b?, ???, ??c, a?c, a??, ?bc subsequences occurring in all the strings, we can replace ? with the character that we need to make it abc. I've named variables for better understanding. In my code, k = count of ? so far submission

how to solve c?

For this, I got a pattern of the required number of moves like

`0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, ......`

Hope it will be helpful.

Took time for figuring that out. Found editorialist solution more easy btw.

Suppose we perform the +1 operation $$$x$$$ times and the duplicate operation $$$y$$$ times. Clearly we want to perform all the $$$x$$$ operations first, so that each subsequent $$$y$$$ operation adds as much as possible. Then the sum of the array will be $$$(1+x)+y(1+x)=(1+x)(1+y)$$$. We want $$$(1+x)(1+y) \ge n$$$, so each of $$$(1+x)$$$ and $$$(1+y)$$$ is either $$$\lfloor \sqrt(n) \rfloor$$$ or $$$\lfloor \sqrt(n) \rfloor+1$$$. Then we can just try the cases.

94077437

so each of (1+x) and (1+y) is either ⌊(√n)⌋ or ⌊(√n)⌋+1. Then we can just try the cases.

i didnt get the last part how this is possible?

and why the solution does not go beyond the root n thanks

If we want to minimize $$$a+b$$$ and want $$$ab\ge n$$$, then we want $$$a$$$ and $$$b$$$ to be as close to each other as possible (just try a few values... it's very intuitive). That means each of $$$a,b$$$ must be around $$$\sqrt{n}$$$. In this problem, $$$a=1+x$$$ and $$$b=1+y$$$.

it is better to increase 1 up to some number let say x and then append this x up to when the array sum becomes equals or greater than target value n

here x should be the floor(square root of n) or 1 plus to this value

here is mine solution 94092529

what was the testcase no 10 of problem D??

Something like this.

5

-1 1 -1 1 -1

What will be the correct ans for this

4

Can some one give me idea about B & D

thanks in advance

for B: if any 2x2 tile has diagonal element same then answer will be yes, keep in mind that tile length and width is 2 so the the resultant square will be multiple of two

Problem F is exactly the same as ABC104 Problem D

How to solve D neatly ? I can think of one way where we count the disjoint subarrays with zero sum.

Think of it as you have, say $$$k$$$ intervals (imagine as segments on the $$$x$$$-axis, from $$$interval[i][0]$$$ to $$$interval[i][1]-1$$$) and each interval has elements that sums to $$$0$$$. Now basically, you need to find the total number of vertical lines to make, such that every segment is cut at least once. Implementation

How to solve D? went upto prefix sums and thought if prefixsum[i] is 0 or has already occurred then add 1 to the answer but it doesn't seem to work because segments can collide. Can anybody explain a neat approach?

i counted all the segment that collides in one then also ans was coming wrong on testcase 10 anyone can explain

`went up to prefix sums and thought if prefixsum[i] is 0 or has already occurred then add 1 to the answer`

— it's perfectly okay till now then you just need to clear your container and do everything that you need by assuming the current position of the array as the starting position. Hopefully, it will do your job.Think of it as you have, say $$$k$$$ intervals (imagine as segments on the $$$x$$$-axis, from $$$interval[i][0]$$$ to $$$interval[i][1]-1$$$) and each interval has elements that sums to $$$0$$$. Now basically, you need to find the total number of vertical lines to make, such that every segment is cut at least once. Implementation

Can someone help with with this submission? I could not think of a testcase that fails. 94110488

your code will fail for when n=1 and X =1 Cuz (1-2)/1=-1 So else part will give -1+1=0

Bruh there goes my rating

Thank you

Did codeforces recently changed the rating formula?

I dont know but maybe this might be the reason...the number of participants is less hence you may see less change in delta even if you have good rank.

Yeah, I thought that I was really hoping to touch expert but nevermind I try next round.

Yes and I wanted to be specialist..sed..next round.

I followed you, and I think if you are not hacked, you will turn blue.

Excuse me! Why is E like A in terms of difficulty?

The fact that it is E has psychological effect hence the number of solves is almost 10 times less then A..despite the difficulty level.

Number of solves is 10 times less mainly because there are 3 more questions between A and E which people attempt, and mostly move ahead only when they are done with those.

There is a general thing. People can solve A because its A, people cant solve E even if its easy cause thats E

There is a question: I did not participate in this round because of something. If I hack someone, will I be rated?

No

I started the contest half an hour late... yet managed to solve A,B,C,D ! Today was a good day for me!

Thanks vovuh for the awesome round :)

Why good day? You managed to get lot of penalties with better performance due to be late

Today's Div. 3 (Round #674):Spoiler alert for those who are thinking to give contest (virtually)The advantages of being a Chinese have been revealed ：） The start time is 16:05 for me.

Is there any benefit for

successful hacking, in this round?Why don't we go beyond sqrt(n) in problem C ?

is there any point for hacking in div3?

Can anyone tell me on what test case my solution for B fails? It is hacked. Here is my submission.

1

2 2

3 5

6 4

3 6

5 4

Your code print YES. But the ans is NO

Can someone explain how hacks work for ICPC-style rounds like this one? Is there any competitive reward for successful hacks?

Hands down the best contest I have participated in so far!

Can anyone explain how this works:

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

I see xin_chen, CupCapCup and midheight at places [3, 4 and 5] accordingly. But that doesn't seam right: Their places are increasing but their (finish time + #WA * penalty) is decreasing >> [ (55 + 4 * 10) == 95 , (70 + 2 * 10) = 90 , (62 + 10) = 72] Plus, their number of WA decreasing: [4, 2, 1] but Penalty is increasing: 188, 193, 199 — it could make sense if their finish time was increasing, but it's not the case.

How to make any sense of it? Thank you in advance.

The penalty of xin_chen is: 2 + 9 + 13 + 27 + 42 + 55 (number of minutes since the start until the task is solved) + 4 * 10 (for WA) = 188

Hope that will make it clearer

Wow, Super! Thank you, that made everything clear.

Why my rating is still not updated?

Will it not be rated for untrusted participants? As my ratings haven't changed yet, being < 1600 and already 5+ hours have passed after the end of the hacking phase.

This is because they might be working on the plagarism tests now and removing the cheaters.

As I am new to Codeforces so can anyone tell me that in this contest will I get any rating or not because I have solved the 3 questions but and also got my rank but not any rating and even in my contest section it is not showing anything.

please help me out?

Wait for some time, it will get updated.

When are the ratings going to update for this round?

The same question

Within 12 hours after completion of hacking phase

Isn't it over?

Why hasn't the rating updated after the contest? it's almost 24 hours now...

system testing just begins,omg

When the ratings will be updated?

Hi everyone! Can someone please help me with this solution from ecnerwala. How did he find max-flow in non winning edges in the code here — https://mirror.codeforces.com/contest/1426/submission/94072786

How did he arrive at that one liner solution? Just a little insight will be very helpful.

Thanks a lot