Hello Codeforces!

On May/17/2020 12:20 (Moscow time) Educational Codeforces Round 87 (Rated for Div. 2) will start.

**Please notice the unusual time.**

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.

Also thanks to Neal neal Wu for testing.

Good luck to all the participants!

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

*Hi Codeforces!*

*We would like to invite you to a very special webinar called Digital Lockdown: AI against COVID-19, by Sergey Gordeychik, director of our Cyber Security programme.*

*Sergey is CIO of Inception Institute of Artificial Intelligence, and former CTO at Kaspersky.*

*During this webinar, Sergey will share his expertise and insights on how AI is being used both positively and negatively, during the COVID-19 global pandemic. Tune in for some practical examples of how companies are using AI to innovate and disrupt during a time of crisis, exploring topics like Medical Imaging for CT analysis, diagnosis and mass surveillance.*

*Join us on Thursday, May 28th at 12h (BCN) to gain knowledge and deepen your understanding about how we can use AI to solve both operational and societal problems.*

*By participating in this 1hour webinar you will get a certificate of participation, a special digital gift from Sergey, and have the chance to win a FREE 3-week module at Harbour.Space University, depending on the availability and prerequisites of the course.*

Congratulations to the winners:

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

1 | square1001 | 8 | 294 |

2 | Anadi | 8 | 305 |

3 | tfg | 8 | 681 |

4 | mhq | 7 | 192 |

5 | xay_naive | 7 | 248 |

Congratulations to the best hackers:

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

1 | qwscaln | 29:-2 |

2 | Ankit | 5 |

3 | lvao-x | 3:-1 |

4 | the_redback | 3:-1 |

5 | WICK_ED | 2:-1 |

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

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

A | fedoseev.timofey | 0:02 |

B | Ashishgup | 0:03 |

C1 | hitman623 | 0:04 |

C2 | square1001 | 0:15 |

D | Not-Afraid | 0:10 |

E | autumn_eel | 0:17 |

F | squarepants | 0:47 |

G | riantkb | 0:37 |

**UPD:** Editorial is out

Good Luck ..

wow you reposted my meme

Penalty : downvotes

agree

that not good

Problem D video editorial for N log^2 N approach: Link

Problem D video editorial for N log N approach using Binary Lifting on Fenwick trees: Link

well explained

NlogN approach with FenwickTree gets MLE with Java while the very same code gets AC in C++. :(

Wow this is really a good time in the Philippines! We can finally experience to join a contest at 5PM

good for Chinese too

6 am for brazilians lol

5:00am for cubans :'v

2:30 for indian

now its 2:45 for indians :)

lol yes

wow, 5 more minutes now, 2:50 pm IST

It's extending just like Lockdown LOL

True

What is happening

3:20 am for El Salvador, Center American

well 2:45pm XD

whats going on

Its the time for afternoon nap for indians

I have a bad feeling about this

hope this round will not get cancelled

XD

Again! Unusual time.

Codeforces is entertaining quite by regularly holding contests in Lockdown. I'm enjoying. What about you guys?

its very good

Good Luck & Have Fun!

Hope the round will go smoothly like last round!

awoo , MikeMirzayanov with all due respect , can you please reschedule the round to next day or during usual time since kickstart will start 5 minutes before this round will end . We can't code for 5 hours straight .

Did you make this account just to make comments?? I wonder what could be the psychology behind this o_O

Making alt accs just to make comments help as it helps you to be the jerk you are without ruining your real reputation. Though this comment isn't exactly being a jerk.

You have my upvote.

You have my downvote

— And My Sword

— And My Bow

— And My Axe

meeooow can you plz try to achieve 0 ranting I really really wanna know if it is possible or not

Yes it's possible, even negative rating is possible. The lowest rating right now is -41. Check the last page of ratings table

yep. trying my best to reach -ve asap. Though there are quite a few of them who've reached this milestone before. :)

It's "rating", and not "ranting" btw.

Ratings can also be negative.

I've seen a few negative rated profiles.

@meeooow pretty cool rating graph btw

thanks :)

I like your contribution :P

Did you make a

new Codeforces accountto say this?I agree. Yesterday's Round 643 was stressful too which affected the Codejam after it. I would hate to skip a codeforces round especially made by such good writers.

:( .contest delayed by 10+5 minutes.Now 20 minutes of overlap .

5 more minutes. But why?

I'm pretty sure you can just close the tab and go to Kickstart.

Well, if you perform poorly in today's round that will affect your kickstart participation so it's not just about time.

And now the constest is delayed by 15 minutes more. Not a pro coder that I can solve all here and then go for kickstart as well.

Seems like they deliberately wanted the contests to overlap. The 15 minutes postpone just strengthens this hypothesis.

Whatever time it is the participants always show up in large numbers. I'm proud of this community :)

Hey, this will clash with Kickstart round C for the last 5 minutes of contest, could you please schedule it something like 10 minutes earlier?

Thanks

Back to back contests.. That's why I love codeforces.

It's great that there are so many contests but why this unusual timings ??? It's just irritating.....

Back to back unusual time contests !!! Oohhh no...

Does the hacking phase got any points? Or will it affect the rating?

Go google it kid.

No. Educational and div3,4 hacking phase hacking has no points.

I have rarely seen unusual time in educational rounds. What is the reason for unusual time?

I am not very sure but as far as I know, the contest time depends on the availability of the setters/testers during the contest. So the reason might be the mutual time decided by the setters/testers as their available time. Someone correct me if I am wrong.

EDIT: It seems one of the setters has already notified the reason. This contest is tied to a local contest in Saratov.

IDK

Maybe because of some other coding events(or contests)

It is tied with a local contest in Saratov.

thx

I think it's clashing with Google Kickstart round C. Though just 5 minutes but still it matters

There is no break between the two contests that is only problem, usual time would't have created this problem. At last it is up to problem setters, they have their reasons.

Can someone help me with the problems of kickstart round C. Where can I find the editorial?

Will it be easier than general codeforces round of div 2 ? (I have fewer experience about educational round )

I feel educational rounds slightly more difficult than regular div 2.But be sure to learn newer things.

maybe harder cause its problems is from GCJ

from my experiences the difficulty is pretty much similar. but the open hack phase introduces some new challenges for us

This contest has a clash of 5 minutes with Kickstart Round C. It would be better if this contest gets preponed by 5 minutes or so.

I kindly ask newbies and pupils not to participate in this round, you are causing big queues. you are wasting time. Stop programing!!!

Says the person with a 666 rating... :/ tbh probably an alt

This isn't person, this is satan

satan is not as dumb as you are

OMG Ice Cube is so cool cruisin' in this Impala

Respected awoo BledDest MikeMirzayanov vovuh sir,

I want to bring it to your notice that today there were back to back codeforces contest and google codejam for many of us and tommorow also we are having google kickstart and educational round as well, but the problem tommorow is that both of the contest clashes. Today there was a gap of 25 minutes bectween the two but tommorow its -5 min i.e. it clashes with each other. Moreover there isn't any upcoming schedule (except kotlin heros) so it can easily be shifted on some other day. If you still think that contest should be organised tommorow then please give a gap of at least 30 minutes so that everyone could refresh and take part in second one with fresh and cool mind and sorry I am bit shy. Please ignore and forgive me if I am pointless.

Thank you

STOP POSTING GOD DAMN NOT FUNNY MEMES. please.

Ok thank you for your suggesion.

Sorry if it was so aggressive(i said please in the end :) ), its fine if you are trying to make people laugh.

ITS FUNNY FOR ME. STOP BEING A TOXIC.

funny or not, it shouldn't be here.

loll

Unfortunately, we cannot shift the round time because it is tied to a local contest in Saratov.

RIP our concentration and brain. Thanks for letting us know

Codeforces evolution ->

2017 — Spamming

"Is it rated?"2020 — Spamming

unfunny memesI feel it's my fault :P

No bro you are the legendary grandmemer of codeforces ,soon you will be among the top contributors

Thx <3 but Nah I won't reach top contributors the higher your contribution is the harder it gets to gain more and I'm running out of memes

Ngl, I look out for that one single meme of yours in every contest announcement. They really make my day. :D

Thx ! you made my day with your comment <3

Why this feels so cheezy !!

Kickstart -> Educational -> Atcoder. This is just usual Sunday !!!. what's the hurry ?

Chocobar its Educational->Kickstart->Atcoder

yours one should fail system test as its not in sorted order

for blues it's ok

Until it get hacked

See what I said , now you are no longer blue. RIP ratings

i'll be blue again soon. :D

so should we just abandon last 5 minutes of this contest for kickstart ?

Last 15 mins*

20 ^_^

I love Educational Round <3

Is it rated?

It will be rated for the participants with rating lower than 2100

Hence, I am rated, right?

How do I unregister from this round?

it will not matter if you have registered and you don't appear for round, the round will go unrated for you. :)

go to https://codeforces.com/contestRegistrants/1354/friends/true and unregister

thank you :)

Nice contest time :)

3 consecutive contests right?

sorry for downvote

Finally, I didn't do codeforces in the early morning. This unusual time is too nice for me

It's a good time for Chinese people, but it may not be good for other places :)

Should I skip this round for kickstart or should I give both. Any suggestions?

Maybe you should give up one , cuz there's an atcoder round in the evening(in Japan)

agree

Do you mean the Japanese online judge atcoder?

Live epic upsolving after the round:

https://youtu.be/SdwVz4qzhkY

looking forward to this

Hey, how come no more non-Kotlin Heroes contests scheduled after this Educational round? (Like dang, many hours past the contest...)

Just meme :-)

Lol! Underrated!

Nice creativity!

You forgot to include AtCoder Beginner Contest ))

sorry bro, my bad :(

I think codeforces community is trying to know which time is the best time for holding contest so we don't encounter any problems. I think it is the strategy to find the most suitable time.

Is there any specific reason for

UNUSUAL TIMEor its just fun? :)Yeah, there is... Kickstart round C is scheduled to start at 11:00 UTC.

http://codeforces.com/blog/entry/77454?#comment-623977

It is tied to a local contest in Saratov.

Now the Unusual Time is more unusual by extending it 10 minutes. LOL!

Now the Unusual Time has crossed the limit of Unusual time. LOL!

Hope this contest will have some graph and DS problems.

Great time!! Thanks for arranging contests so frequently . Thanks in advance for the webinar.

If possible, set the time in such way that it does not clashes with another contest.

A really good time for Chinese! We can enjoy the contests this weekend without staying up late.

It's the first time I am sitting for contests back to back. Hope the results will be good.

Less than 20k participants after a long time . Results of Kick start clash may be . Looking forward for an another interesting problemset .

I thing, it's good time for Bangladeshi Muslims. Because, in evening, we have evening prayer and Ifter. And in night, we have night prayer with Salatut Tarawih. But, this time,most of us are free. By the way, thank you Codeforces.

Ever heard of something called as kickstart

Contest Extended!

Actually it's

postponedYa Sorry for my poor English hope I will not repeat the mistake in future.

The contest got delayed 10 minutes and now the overlap with Google Kickstart is 15 minutes

exactly ! sux :(

when is google kickstart

Thats my boy!!!

https://codingcompetitions.withgoogle.com/kickstart/schedule Just after this contest ends :(.

Deleted

Actually there is already an option to unregister.

you can deregister by going to the list of registered participant , on the top it will be your name click on cross sign

I think now most of them will give the contest by fake id!

Who knows, if it will be further extended due to long queue :)

It's 20 minutes overlap now. Way to go !

Now it is 20 minutes overlapping with Google Kickstart.

Delayed for 10 minutes.

Reason?

delayed :(

Kick Start is in 2 hours. Lost 15 min:(.

Why tho?

No point in wasting 1 hour 45 minutes. I think I will give all to cf first then Kickstart.

Delayed by 10 minutes!!!

15

20!

The voltage increases... another ten minutes.

what the hell is going on ??

Damn it, it's getting even worse now we have to abandon last 15 minutes of this contest

Codeforces should have preponed this round or kept at 8:05, owing to know Kickstart's schedule. :)

Yeah very true

See bledest replied the reason why the didn't did so

Delayed 10 mins :)

What the hell is going on ?? :(

A penalty of 10 mins to everyone!! HAHA Another 5 mins! Congratulations

Delayed by 10 mins : hope server is fine

Now a 15 minute overlap with kickstart,rather than 5

I don't think it's very sensible to further delay the contest with an overlap of 15 minutes with Kick-start (which is a fairly popular competition and has almost 10k+ participants this year..)

Everyone said make it 5 min earlier. Boom you delay it by 10 min. People start worrying for Kickstart. Meanwhile Codeforces : "Here comes another 5 min, you guys just probably spamming"

again delay!!

Let's start side by side with Kickstart, what say?

let's hope this delay is not a sign of long queues during the contest

Contest should be postponed.It directly overlaps with Google Kickstart 2020.

15 minutes of kickstart already lost Can't you see awoo

Google Kick Start! :(

And there's 5 minutes more!

Is this a measure by the problem-setters to decrease their competitors in Kickstart? >.<

In that case, people will do Kick Start instead of this contest.

I don't think so, Kickstart has it's prestige but to people who want rated contests, they might skip Kickstart(or join late).

For the First time, a 100 minute contest! XD

another 5 min delay

5 More mins??

ok so no one is going to participate now +5min more delay

Another delay

no..its still 2 hour contest

Amazing.

Another 5 mins....

again

yo come on xd

okay now i am probably gonna take part in atcoder instead of kickstart (:

As per my suggestion prefer kickstart as atcoder contest take place every sunday but not so frequent for kickstart

Same ^_^

Another 5 mins :(

THis has become irritating now...

They dont even care to tell the reason of the delay.

This is frustrating

Now , i m not participating

Me too!

Man, You guys are killing me. Delayed further by 5 Mins. Its a 20 min overlap now.

Please make sure not to start to early ;)

I am truly amazed by the arrangements.

WTF is happening. Again 5 min delay.

Why delayed again?

JUST TELL ME THE FINAL TIME OF STARTING CONTEST. GETTING PRETTY ANNOYED BY CHANGING TIME.

I want my 20 minutes back

I was already ready to go in, as here again the transfer for 5 minutes )

By using GP (infinite) 10+5+2.5....=20 so contest will have 20 minutes delay

just forget about Kick Start

What's up with the delays?

Seems its a trap now :)

Why are they playing with our feelings?

my patience is giving up .

What the hell is that,2 delays?

The contest is delayed by 15 minutes, so now we have 20 minutes intersection with Kickstart. Tough spot to be in.

Here we go again!

10 minute delay had a bonus!

Again Delayed! It hurts more than a breakup.

WTF dude! Please check your server and conduct this round after kick start....

While(onClick("Start Contest") { startTime+=5; }

5 more minutes ?

1 is okay but 2 is a bit frustrating

Server in trouble?

delay the round without notice is really uncomfortable...

Are you guys planning to delay it over and over so that it starts exactly at the same time as Kickstart?

`wtf???????`

why is starting time getting postponed every 5 minutes?

I wonder what had happened to this round.

Now 20 min penalty woaah why cf ??

What should be the priority kickstart or codeforces ??

That's exactly what the codeforces want.To pick the best platform for programming contests.

Depends upon your comparator

Why are you extending the time again and again. I have been waiting for 30 minutes for this contest t begin.

why the contest is getting late???

Could be technical issues or unclear problem statements.

Now we'll get to see real CF fans

Maybe they are waiting for 20K registrants.

Another 5 min, Hope clear statements !

delayforces /qiang

Now delay the contest to some other day THIS IS NOT DONE!!

How to solve A?

Just do binary search for the time

first 10 min then 5 then 2 then 1

glhf

why delay again !???

When I say myself,**"Now we go",**then Suddenly I see 10 min left,and after 10 min ,again I boosted myself ,and again I see 5 min to go

I am getting a meme feeling

Will they keep delaying it until unusual time becomes usual ?

I already ready for program but codeforce said please hold patient .

Will educational rounds have points for hacking??

No

Testing our patience? xD

Kickstart guys going to suffer

Guys, don't mess with cf. They will add 5 minutes delay for each meme xD

a contest with 100 min xD (until kickstart begins)

Why has the contest been postponed two times?

I am wondering how are you holding an onsite contest during the COVID-19 epidemic?

UnusualtimeForces × DelayForces √

delayforces :(

Yet another 5 minutes extended.

They should either reduce the length of the contest for everyone or postpone the contest altogether (IMO).

Putinforces?

Is it rated?

10min+5min delay.

Hope all goes well.

No offense!! Participate in kickstart. Nothing is left with educational rounds :/

for(;time<=4:30;start_time+=5)time++;

If they add 5 min more, I'll wait 5 min more

SPEEDFORCES!!!

Time limit exceed in test case 3 in A problem :((

how to solve D? my q*lgn*lgn using binary indexed trees(bit) ofcourse times out :(

UPD — my same code with cin cout passes?!

you don't need binary search, traverse the BIT to find the answer ~810ms

And I kept getting Memory Limit exceeded for some reason!!

Use binary jumps

Either fast descent on BIT or segment tree (in $$$\log n$$$), or the following:

Suppose we are trying to find the minimum element in the resulting multiset. To do this, let's implement a function that counts the number of elements not exceeding $$$x$$$ in the resulting multiset in $$$O(n + q)$$$ as follows: if we distinguish only between elements greater than $$$x$$$ and not greater than $$$x$$$, we can maintain the multiset as two simple counters. To find $$$k$$$-th statistics, simply check that the number of elements $$$\le x$$$ is not less than $$$k$$$; if it is so, $$$k$$$-th statistics is not greater than $$$x$$$.

That way, we can count the number of elements $$$\le x$$$ in $$$O(n + q)$$$, and to find the minimum element in the resulting multiset, we may binary search the first $$$x$$$ such that the number of elements $$$\le x$$$ is non-zero.

My q*log^2(n) luckily passed, please hack it https://codeforces.com/contest/1354/challenge/80496838

I used binary search on Binary Indexed trees(BIT) and it passed. Here's my submission in Java 80546129

How to solve C?

I think $$$\cot(\pi/n)$$$ works for C1.

For C1,i solved it by finding the inradius of the polygon multiplied by 2.

1.0/tan(pi/n)

C1: 2 times the apothem of the polygon, meaning

C2: I have literally no ideea.

C1: 1/tan(π/(2n))

C2: cos(π/(4n))/sin(π/(2n))

can you explain problem C2

is binary search intended solution for C1,C2?

Can you explain the solution of C2 ?

Hey can u explain one thing tan(angle) = tan(angle*(pi/180))

then in case of tan(pi/(2n)) why it is not equal to tan((pi/180) * (pi/(2n))) ....please help me in this:)

Here is how to solve C1 (C2 is a whole other story). It requires you to know a little bit of trigonometry (sin, cos, tan formulas)

Take a look at the above image, what we are looking for is the blue line. If we find the length of the line we can double it and that is our answer.

How to do that: We can find the angle x by dividing 360/n where n is the number of vertices. Now we need to divide that by two so we can have half the x angle, lets call v = (360/n)/2 = 360/(2*n)

We managed to create an imaginary right triangle and we know one angle (v) and the opposite side (with length 1/2 = 0.5), notice that the blue line is the adjacent to the angle v.

Tan formula: tan(v) = opposite/adjacent For our case we solve for the adjacent and we have adjacent = opposite/tan(v) = 0.5/tan(v)

So i hope that now it is clear that our answer is 2*(0.5/tan(360/(2*n))), just remember to double the n value at the beginning because we look for a 2n-agon.

I saw a bunch of submissions of c1 by doing some sort of summation of cosine of angles. what was that all about?

Some people solved both C1 and C2 with the same code and made the same submission. I guess that C2 requires some addition. I didn't manage to solve it but I think that the solution can be broken down to finding two different sides that sum up to the total square side. (or at least that was my approach)

So C1 and C2 are not suitable for pupils(I mean students of primary schools). :(

Luckily I find out the solution :D

why can't we use sin() to calculate directly please explain. My approach was same i just used sin, so that sin(x) = side(0.5)/radius hence radius radius = side(0.5)/sin(x).

Because sin = opposite/hypotenuse in our case we don't need the hypotenuse but the adjacent. You could use both sin and cos to factor out hypotenuse and solve for the adjacent (because tan = sin/cos) but is simpler to use the tan formula instead.

ohh there i go wrong i was actually taking hypotaneous. thank u very much for correcting me.

.

By using sine, we will get the circumcircle radius right?

.

yes, somehow I got messed up with diameter of circumcircle and side of square. haha

Thanks for the explanation.

What's the point of problem C?

Twice the apothem of the polygon is the side of the square [C1] https://en.wikipedia.org/wiki/Apothem

It seems C1 is without rotation, and C2 has a slight rotation, but I didn't manage to find out by how much

Same with you, and for C1 I even dont know how to get the accurate answer, I just tried and tried and finally get the answer which I even dont know why.

For C2, I just continued to try, but unfortunately, I didnt get the answer. I find some rotation might be correct but seems it is just my guess not the answer.

Mathforcse /cy/qiang

stO Qiuly Orz

Why does lazy propogation give TLE/MLE for problem D.

80500739

Memory limit is 28mb.

How can this problem be solved using segment tree WTF?

A classic segment tree uses 4*N memory (I've heard this can be tightened, but I use the 4*N version). So you'll keep a leaf for every possible value in the set, representing the count of elements in the set with that value. Then you build the ST saving the sum of children. So, when you are asked to add an element K, you can do that in O(log(N)) adding 1 to every node in the path from leaf to root. If you are asked to remove the Kth element, you make a "binary search" over the segment tree. This is, if you are in node A:

*Is the left leaf enough to find at least K elements? That means to check if ST[A*2] >= k. If it is, then you'll recursively find the Kth element in that branch *Is the left leaf not enough? Then you go to the right leaf, recursively, but the call will be query(A*2+1, k-ST[A]) because the left leaf will cover part of the "prefix" you are looking for, so you need to subtract it from K.

There's a base case, when A is a leaf, you simply return the value associated to that leaf. Once you've found that value, you also need to update the ST by substracting 1 to every node in the path from leaf to root.

So you see every operation is log(N)