**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 ZeroAmbition Stepanova, Mikhail pikmike Piklyaev, Maksim Ne0n25 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 sladkayaKlubnichka 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 :) ()

we r really waitin!! 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!!!!!!!!!

yeah...i think all contests should be held usual time:)

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

Bruh this contest is suit for me but i think i won't participate(because of the unusual start time)

Aw man, I think a lot of people (including me) won't be able to participate because of the unusual timing :/

Edit: I'll miss because I've to attend online lectures, just though I'd add this here..

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

Nope :)

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

4 AM for me then.

Deleted for posting at a wrong place.

Too bad this contest is Div 3.

Bruh ,you ain't getting me this time .

I still remember that russian 6th grade student's round . This one is for all russian student olympiad. Even more tougher.

BledDest and vovuh are gem problemsetter

are ratings updated?

not yet !

oh fine.Normally how long does it take for updation? I am new here so I don't know much

it may very contest to contest , we can say anything that in that amount time it will update, usually in div 3 it take more time then div 2. hope it help you . all the best keep coading bro

thanks for the info.Yes i will :)

should i eat lunch or give this contest?

Why not both?

I'll be eating and crying at the contest time as it's lunchtime and I suck at 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.

really weird time !

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

Coding is love.

![ ](

Same here bro xdd

us fr

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

No

`as a tester, I would say sth`

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

glhf

haha .... i had to choose between this and online class :(

After the contest ends, how to solve D?

How to not double count subarrays with zero sum?

You can have a look at my submission

https://codeforces.com/contest/1426/submission/94110582

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

started from back of string and kept the count of subsequences of type abc,bc and c

how to solve c?

binary search

Can you please elaborate ?

how?

It can be solved without binary search too, simple arithmetic calculation

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.

I found x*(x+1)>=n using binary search but it wasn't correct for last two sample test cases and then I found x*x>=n as well as x*(x+1)>=n separately and took minimum of both, it got accepted.

but why you have to find x*(x+1) in the first place?

thanks

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

ohh ok got it thanks

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

https://codeforces.com/contest/1426/submission/94102291

I hope this makes it clear.

I pre calculated maximum possible sum for i operations (1 <= i <= 63244). To maximise, wee can use floor(i/2) operations of type 1 and ceil(i/2) of type 2.

When the values are precalculated, we can just use the lower_bound to find the index for a particular n.

https://codeforces.com/contest/1426/submission/94156182

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 you just have to input 4 nums n times , let's say x,y,a,b and check (y==a && m%2==0) since it is not possible to build a 2X2 tile in odd m , and for symmetric if you have y==a you can just use only that tile many times to build a matrix.

OPS i was checked for (x==d&&y==a)

that's why i got wrong verdict It's my bad luck

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

In your B, a doesn't have to be equal to d, just b should be equal to c and m should be even.

i Was check for a==d && b==c that why i got wrong verdict

For B,

let say matrix is

A B

C D

If m is odd, answer will be NO

For even m If for any matrix B == C then answer will be YES else NO

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

The number of participant's are not so many for the unusual start time.

Since the contest time is unusual,I bunked my class to participate in the contest.The Dashboard was quite interesting and I enjoyed the contest very much.

thanks vovuh for fast editorial ^.^

Wow,The editorial is ready!!!

Just when I was submitting the D problem ,my electricity supply went off,gave the contest from phone...poor me,but problems were superb and am glad I participated..Thanks vovuh

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.

i'm also very close to 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

Solving 4 problems in 1.5 hrs was a boost in confidence for me! I think that matters more than the penalties :)

Today's Div. 3 (Round #674):Spoiler alert for those who are thinking to give contest (virtually)When will rating will be changed

Rating for Div3 and Educational rounds(Div2) will be updated 1-2 hours after the open hacking phase is completed.

not updated till now

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?

Has anyone's rating changed?

waiting for rating changes ...

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.

You can see your rating predictions on cf-predictor. It's pretty accurate.

https://cf-predictor-frontend.herokuapp.com/

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.

https://cf-predictor-frontend.herokuapp.com/

Found this predictor in another comment by

abhijit, check it out.Generally within 12 hours after completion of hack phase, rating change occurs

when will the ratings change...how long does it generally take??.

I solved 3 problems and I hope that soon change of my rating class come up to me from newbie to pupil!!

Well cf rating predictor says you are getting 22 points h5jam.

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?

System testing is on I guess.

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?

Was this Contest unrated ?

maybe

They have updated the ratings

Solved 3 for the first time and I get a 0 rating change

I also face the same issue, I had solved three problems in less time. I think the rating should be increased but the rating is decrease for the same. why?

I had no rating change....when will it happen?

For whatever reason, the final updated rank is significantly higher than what it was initially after the contest. Generally as far as I've seen, the rank drops, as the ones out of competition are taken off the list. Is this peculiar only to me or am I not seeing something?

I'm asking again, please can someone tell why don't we proceed beyond sqrt(n)+5 in problem C. Is there any mathematical proof for it? Thanks in advance!

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