Привет, Codeforces!
В 17.05.2020 12:20 (Московское время) состоится Educational Codeforces Round 87 (рейтинговый для Див. 2).
Пожалуйста, обратите внимание на необычное время проведения раунда.
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Также спасибо Neal neal Wu за прорешивание задач.
Удачи в раунде! Успешных решений!
Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Привет, Codeforces!
Мы хотели бы пригласить вас на вебинар под названием Digital Lockdown: AI against COVID-19, который проводит Сергей Гордейчик, руководитель нашей программы Cyber Security.
Во время этого вебинара Сергей поделится своим анализом и инсайтами о том, как положительно и отрицательно искусственный интеллект используется во время глобальной пандемии COVID-19. Настройтесь узнать некоторые практические примеры того, как компании используют ИИ для инноваций и разрушения во время кризиса, исследуя такие темы как медицинская визуализация для КТ-анализа, диагностики и массового наблюдения.
Присоединяйтесь к нам в четверг, 28 мая, в 12:00 (BCN), чтобы получить знания и углубить свое понимание того, как мы можем использовать ИИ для решения как операционных, так и социальных проблем.
Принимая участие в этом часовом вебинаре, вы получите сертификат участника, специальный цифровой подарок от Сергея и получите шанс выиграть БЕСПЛАТНЫЙ 3-недельный модуль в Harbour.Space University, в зависимости от наличия и условий курса.
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | square1001 | 8 | 294 |
| 2 | Anadi | 8 | 305 |
| 3 | tfg | 8 | 681 |
| 4 | 244mhq | 7 | 192 |
| 5 | xay_naive | 7 | 248 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | qwscaln | 29:-2 |
| 2 | Ankit | 5 |
| 3 | the_redback | 3:-1 |
| 4 | lvao-x | 3:-1 |
| 5 | WICK_ED | 2:-1 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| 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: Разбор опубликован
Good Luck ..
wow you reposted my meme
Penalty : downvotes
agree
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
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
Its the time for afternoon nap for indians
I have a bad feeling about this
hope this round will not get cancelled
XD
Codeforces is entertaining quite by regularly holding contests in Lockdown. I'm enjoying. What about you guys?
its very good
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.
@meeooow pretty cool rating graph btw
thanks :)
I like your contribution :P
Did you make a new Codeforces account to 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.
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.
Does the hacking phase got any points? Or will it affect the rating?
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.
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
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.
Unfortunately, we cannot shift the round time because it is tied to a local contest in Saratov.
Codeforces evolution ->
2017 — Spamming "Is it rated?"
2020 — Spamming unfunny memes
I 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 ^_^
deleted
It will be rated for the participants with rating lower than 2100
deleted
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://mirror.codeforces.com/contestRegistrants/1354/friends/true and unregister
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 TIME or its just fun? :)
http://mirror.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.
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 .
Contest Extended!
Actually it's postponed
Ya Sorry for my poor English hope I will not repeat the mistake in future.
Delayed?
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.
I think now most of them will give the contest by fake id!
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
The voltage increases... another ten minutes.
delayed:c
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
A penalty of 10 mins to everyone!! HAHA Another 5 mins! Congratulations
Delayed by 10 mins : hope server is fine
Quite unfortunate seeing 10 mins extension. Google Kickstart starts at 4:30 m today, 15 mins earlier than this contest ends. :(
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.
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
Another delay
Amazing.
Another 5 mins....
yo come on xd
okay now i am probably gonna take part in atcoder instead of kickstart (:
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
Now the overlap is 20 minutes!
just forget about Kick Start
Seems its a trap now :)
Why are they playing with our feelings?
my patience is giving up .
5 more mins?
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.
While(onClick("Start Contest") { startTime+=5; }
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?
Once more!! Once more !!
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 ??
Testing our patience? xD
What should be the priority kickstart or codeforces ??
Depends upon your comparator
Now we'll get to see real CF fans
Maybe they are waiting for 20K registrants.
Another 5 min, Hope clear statements !
delayforces /qiang
How to solve A?
Just do binary search for the time
first 10 min then 5 then 2 then 1
glhf
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
Will they keep delaying it until unusual time becomes usual ?
Will educational rounds have points for hacking??
No
Very nice Time for Chinese participants!! like it!
Testing our patience? xD
Kickstart guys going to suffer
Every delay is costing you a lot of participants!!
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)
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).
there is a condition:
the contest will not start until there is +20000 participants
Is it rated?
for(;time<=4:30;start_time+=5)time++;
If they add 5 min more, I'll wait 5 min more
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://mirror.codeforces.com/contest/1354/challenge/80496838
How to solve C?
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
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.
.
By using sine, we will get the circumcircle radius right?
What's the point of problem C?
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)
without using lazy propogation. https://mirror.codeforces.com/contest/1354/submission/80515718
Use 4e5 instead of 5e5
Please miss us with the geometry problems.
Normally I would agree, but it helped that all the formulas were online ;)
I've always wondered: Is it moral/allowed/good practice to google formulas or algorithms? It feels wrong to me :(
this argument can be used to saving code templates for speed , or having a text with for example a standard segment tree code.
yes it is moral and good practice as in competitions like icpc or even actual jobs , you can get those easily.
Hey, I have an exam in a month's time. Is it moral and good practice for me to use my phone to look it up on Wikipedia? When I'm doing an actual job, I can access wikipedia easily.
if it is allowed to do so , totally acceptable ;).
where did you find the formulas? i also searched for them in internet but couldn't find.
https://www.mathopenref.com/apothem.html for C1
http://www.murderousmaths.co.uk/books/longdiag.htm for C2
I don't get how is that related to C2: The article you cite has the formula $$$1/2sin(pi/2n)$$$ when $$$n$$$ is odd, but here $$$n$$$ is the number of sides in the polygon. In problem C2, the number of sides is $$$2n$$$
Wait hmm
Lol
Wait actually I incorrectly assumed that I was dealing with an odd polygon and I was somehow convinced that it worked. Even I am confused now :|
LOL, When see you post the link related to the C2, I just feel unhappy but now I feel better because it doesnt seem to work.
The link I posted for c2 and the formula in it DOES work, I’m just not sure why
Well, though upset but have no choice about it. Maybe because I'm not a native English speaker so it's hard for me to search a web like that. But during the contest I didn't get the idea to google because I just thought CF didn't have anything that can be googled. If I were at the contest again and I knew that could be googled, I wouldn't google it because I think that doesnt help you anymore as all of the region contests cant google anything!
I don't how how, but 80516401 got AC with this formula.
Same formula that I used but idk why it works.
loyal reader of the murderous maths (I am a primary student)
how to solve C1 and C2 ?
Twice the apothem of the polygon is the side if the square https://en.wikipedia.org/wiki/Apothem Applies for C1
Can anybody explain how to solve C2?
If n is even, twice the apothem. If n is odd, just the diagonal. **Longest diagonal
I tried it on the contest, did not work, are you sure you are not wrong?
Pretty sure. Check
Thanks man! But can you explain, why do we have answer 1.9... if n == 3? The diagonal of hexagon is equal to 2 * side of hexagon, so the answer must be 2. Why my logic is incorrect? (I studied this formulas in school, but checked in the Internet)
C2: Don't you think formula implemented by you is in case number of side is odd http://www.murderousmaths.co.uk/books/longdiag.htm but we are given that number of side is even.
Hi! What do you mean by "just the diagonal". for C2, I tried this which worked for $$$n==3$$$ and $$$5$$$ but not for more: tilt the $$$2n-gon$$$ so that its longest diagonal and square's longest diagonal coincide.
How did you get $$$1/2sin(pi/n)$$$?
Longest diagonal Here
OK, but how is that related? The article you cite has the formula $$$1/2sin(pi/2n)$$$ when $$$n$$$ is odd, but here $$$n$$$ is the number of sides in the polygon. In problem C2, the number of sides is $$$2n$$$.
For problem C2, the answer for a polygon of 2*n sides is half the longest diagonal of a polygon of 4*n sides, i.e.,
1/2sin(pi/4n)I don't exactly know why this works, but I solved it by inscribing the given polygon in another regular polygon with twice the number of sides, then inscribing that in the square like in C1. Only difference is that the side length of the new polygon would no longer be 1, so you need a little trig to find that new length.
I hear some solved it by ternary searching for the optimal rotation angle, but I haven't yet mastered that technique
Underrated and beautiful solution. Kudos !!!
Some visualizations for the same. https://www.imageupload.net/image/pSqCh https://www.imageupload.net/image/pShXM
Thanks. I could only find the hexagon example online, so I tried a different conjecture that turned out to be wrong before finding the right one
PS. please change them to links instead, the embedding didn't work. I had to use right click
I solved it post contest and I came up with few things.
The previous orientation which was used for C1 for n being even would be suboptimal. (The hint comes from the obvious first testcase where n=3 and yet the answer is not 2)
If you place it in the similar manner as done in C1 there will be some gap left both from top and from bottom to the horizontal sides (In this case if we take the hexagon and place it normally with the centre diagonal as the side of square the top and bottom leaves some space)
So we have to re-orient the polygon and the rotation turns out to be 45 degrees. (I do not have a concrete proof but the square can be squeezed down the most in that orientation)
I would like to explain further but it would require me to show it via illustrations and I don't know how to do so.
The answer is sum of two particular lengths (which are within the polygon and make up for the length of the side of the square) which depend on the side length of the internal angle based triangles. (the 2*n triangles formed from the internal angle)
http://www.murderousmaths.co.uk/books/longdiag.htm
Many java users including myself had intended solution with BIT but still MLE? I don't think its ok that even intended solutions fail, really ruined the entire problem for me.
Likewise, I was spending the rest of time looking for memory optimizations to fit within 28Mb. [ https://mirror.codeforces.com/contest/1354/submission/80506407 ]
If you look at the error you will see MLE is due to your input class which is using buffered reader. I am guessing it reads the initial array as a string which have max length of 8e6(n*(len(1e6)+1)) which exceeds memory.
I was initially doubtfull if BIT would fit into memory but it luckily did. My solution is in Java
Problem-B was on Stackoverflow
you can solve the exact same problem on leetcode only difference is they are considering alphabet instead of numbers
Video Editorial for today's D
Nice questions and good round! I only managed to solve A and B :( I couldn't derive anything for C1 because I was blank in the middle of the round. Anyone, ideas for C please? I tried D but TLE'ed on Test-9. It's probably one of those cases where I'd perform complete $$$O(nk)$$$ operations. I couldn't figure out how I could bring down complexity to $$$O(k)$$$ (I later tried a prefix sums like approach which I couldn't make work). Could anyone help me optimise my solution?
Link: https://mirror.codeforces.com/contest/1354/submission/80505930
EDIT: Okay, nevermind. I read BIT and Segment trees in a comment above and realised my approach is no better than naive approach. I don't know how to implement either of the two yet :(
for C1, symmetry is the key! Seeing symmetry, what i did is i calculated summation of cosine of angle of every segment with horizontal axis till n/4. (I assumed i am placing the first segment horizontally.)
I could not do c2.
How to use PBDS for multiset , on web i got i need to change less to less_equal , but after that begin() , end() operations were not working
PBDS shall not pass.
why PBDS is not ok ?? does it take extra space ??
It takes extra space and its constant factor is also high, So I don't think it will fit in the TL also
You should use Fenwick Tree to implement
if the memory limit is large enough, you can simulate multiset with PBDS like this https://mirror.codeforces.com/contest/1354/submission/80491415 — here it wasn't, unfortunately
pbds doesn't work, but in general if you want to use it as multiset you can use pair<value, count> and your set turns into multiset
Im waiting for someone to post the geometry meme under this announcement
Am I the only one who noticed that today's problem B == 701C? :D
UPD: Well, I wasn't happy for that. I was just astonished as I've solved the problem before with exactly the same idea. I wish they were all unique, but just saying. Thanks for efforts.
how to solve C2?
Simulate building the polygon length by length, Keep track of the biggest & smallest x & y positions, and from this get the lengths of the square All that's left to check is the best rotation of the shape, My solution was to ternary search the angle of rotation between 0 degrees & 360/n degrees My solution — https://github.com/OisinDavey/CodeForcesRounds/blob/master/edu87/C.cpp
Thank you!
I wrote a code with ternary search with similar ideas. But after a rotation, I was finding the minimum length of the square in a slightly wrong approach.
"Keep track of the biggest & smallest x & y positions"
Then, this part of your comment saved me. Thanks :D
Math of C killed me . :(
And me (I'm a real pupil which means primary school student)
oh my god i'm so dumb i thought it said 7:35AM again so i woke up at 6:20AM and didn't realize that the contest was running the whole time LOL
Why does std::multiset give memory limit error??????
Maybe because it has high constant factor in memory consumption.
if i use vector then will i succeed in time limit, insertion is quite slow :(
Геома, ммм, вкусно
Can someone explain why this solution fails? Instead of finding the length of the side directly, I found it using an indirect approach. Submission
I found the length of the longest diagonal and then using Pythagorean theorem the side of the square can be found. I think there were some precision issues with square root calculation. How to go around this?
Edit: Got the problem. The
setprecision()is in the wrong order :(Очень понравились задачи С1 С2 <3 <3 <3, дают прекрасную возможность выучить алгоритмы которые в будущем можно будет использовать для решении кучи задач, раскрывают невероятно полезные свойства линейки карандаша и циркуля, учат сидеть и гуглить формулы. Таких задач определённо должно быть больше в мире спортивного программирования.
Видимо, Вы из тех, кому в принципе математика для программирования не нужна. Математика же не поможет, например, сайты верстать или случаи разбирать. Подумаешь, что на финале ICPC обычно есть одна геометрическая задача, которая иногда решает — получишь ты медаль или нет.
Подумаешь, что на IOI нельзя делать задачи на тригонометрию.
Воу, не знал. Ну тогда если вы планируете закончить свои выступления с окончанием школы, то задача действительно не для Вас.
И как ваши знания геометрии? Помогли в финале ICPC?
А как твои знания IOI Syllabus? Помогли на IOI?
Мне, например, знаний не хватило. Учился бы больше — может выступил бы лучше.
А вот по факту мы собрались чтобы задачки по проге порешать, а не над геомкой думать, где смысл давать задачи на геому на Educational раунд, её нужно в школе учить, а не на кф.
А зачем говорить о математике в целом? Задачи на алгебру вполне хорошо заходят для программирования, но вот геометрия всегда вызывала общее негодование.
Непосредственно в том сообщении — для преувеличения. А вообще, считаю, что отделять геометрию от математики неправильно, но было бы логично, если бы геометрия не пересекалась бы с программированием. Но она пересекается, и сильно.
Лично я сам далеко не всегда в восторге от геометрических задач, но я не понимаю необоснованного хэйта, где за броскими фразами о ненужности геометрии скрывается простой посыл: "задача — говно, потому что я ее решить не могу".
Там тернарный поиск по углу поворота, задача чисто техническая, не понимаю о чем Вы, сдается с плюса и ручка с бумагой не нужна
How did the solutions of D with complexity o(q * logn * logn) got accepted? In worst case the no of operations will exceed 1e8
It seems that for people who had the same intended solution one might have passed and another didn't. That's mainly why I didn't like this problem, it is just optimization hell.
There are 1.5s and the number of operations done in 1s can exceed 1e8, like <= 3e8, so it could get accepted
Yes,it can pass.I just use BIT + binary_search.
Exactly what I did but still MLE...
No look at mine: https://mirror.codeforces.com/contest/1354/submission/80501761
Yes, I have the same intended solution which has memory limit exceeded. [80506407]
Actually you cant even read the input to memory unless you use byte arrays in java. I wonder if the testers actually solved the problem in java before using such low memory constraints.
. There are only 6 accepted solutions so far in java for the problem. My solution (in which I always use StringTokenizers to parse input was failing to even read the input.!!!
Your solution and my solution are almost the same but still, my solution gave TLE on test case 37. Why is it so? My submission: https://mirror.codeforces.com/contest/1354/submission/80507579
Because of "long long".It is much slower!
Thanks a lot for your help. The same code got accepted when I changed them to ints. Isn't it a little bit unfair to keep the time bounds so strong that the same solution fails just because of using long longs in place of ints?
The intended has a lower complexity, so it's not really unfair. Solutions of higher complexity may or may not pass.
Also, I would advise thinking whether the data type can reach long long. If there is no doubt it cannot, use int's because I have seen various cases recently where this is the difference bw TLE and AC.
Gary2005 why have you taken the case of -1 as a query in a seperate case?
Because it is special case.I thought it wouldn’t work well with binary search.
I got TLE
I don't get why people hate C1/C2. Yes, it is a geometry problem, yes, it can be solved with pen and paper work.
But:
1) The geometry itself is very simple and does not contain any case-bashing, just a simple formula.
2) There is a way to solve this problem almost without any greedy ideas and formula-deriving, with standard algorithms such as binary/ternary search.
Normally I dislike geometry problems but these were at least simple enough and good for an educational round.
I dislike geometry problems. That's that.
In fact they can be solved just with junior middle school math !
How to use optimal searching (binary/ternary) in these problems as you mentioned?
I think it's cool. I'm looking forward to the editorial!
Probably because we're here for coding problems, not pen and paper problems. If I wanted that I'd go look for math tests online.
If you're not here for pen and paper work, then you could code a solution that does not rely on pen and paper at all (except for rotation formula).
I could write long code for all div2 A 1-liners too, but that doesn't mean it makes the problem any better from my view. It's usually easier to solve a 1 line equation problem in 1 line than doing something like b-search, it's less time consuming, and it's not very satisfying to finish when you've just written a single equation.
If it wasn't a coding contest I think it'd be a good problem, but I didn't enjoy it here. Tbf I didn't solve c2 which probably makes me not like it more lol, but in general I don't enjoy 1 line sols.
people like to code more than to solve by hand some geometry problem. This is codeforces not geometry forces. Also please ban pikemike from problemsetting.
Seriously? Someone has set 80+ Educational rounds and you're requesting to ban the guy. Wow.
actually a lot of people could guess both formulas for c1 and c2. And in educational rounds for each problem you get one point, so i don't think that's totally fair
how to derive formula for c2... how to do this with binary search?
Fuck you and your geometry problems
We came here to write code and not to solve math problems
okay fake account we don't care about "we"
Thanks BledDest for the problem. How do you solve it using BSearch/Tsearch? What would the
check(int len)function look like?The problem is by adedalic, not me.
Solution for C2 with ternary/binary search:
Suppose that one of the sides of the polygon is parallel to the side of the square. When you start rotating it, the difference between its $$$x$$$-coordinates starts decreasing, and the difference between its $$$y$$$-coordinates starts increasing, until some moment when it begins to go vice versa (and, at some moment, the height and the width are the same). After the polygon is rotated by $$$\frac{\pi}{n}$$$, the difference between $$$y$$$-coordinates becomes maximum possible, and between $$$x$$$-coordinates — minimum possible.
Since we want to find a moment when the difference between $$$x$$$-coordinates is the same as the difference between $$$y$$$-coordinates, we may use binary search on rotation angle to check whether the angle is too small or too big.
Or, for a more straightforward solution, we can write a function $$$f(ang)$$$ which gives us the size of the bounding box of the polygon, if it is rotated by angle $$$ang$$$, and use ternary search to find its minimum. The proof that this works is the same — initially the width decreases and the height increases, and at some moment, they are equal.
Yeah, C1 and C2 were excellent problems. I dont understand why people hate it. Its just basic high school maths.
I don't get why people hate C1/C2. Yes, it is a geometry problem, yes,
it can be solved with pen and paper workit can be easily googled .Can anybody help me out in C2 with some proof .
General idea for C2 (without proof):
Consider the line segments connecting: - vertex 1 with vertex n+1. call these vertices V1 and V2. - vertex (n/2) with vertex ((n/2) + n). Call these vertices V3 and V4.
Let's assume vertex 1 is located at angle 0 (positive x axis direction) without losing generality. We need to rotate the polygon by an angle alpha until the horizontal difference between V1 and V2 and the vertical difference between V3 and V4 are equal.
let beta be the angle of V3 compared to the polygon center of mass. The goal above will be achieved when: cos (alpha) == sin (beta + alpha) in other words: (Pi / 2) — alpha = beta + alpha
Then you find alpha and multiply it by the distance from the center of mass to any vertex.
Oh... I miss the contest :'( I thought the contest starts at 14h30 utc.
Oh Lucky You !
Nah~, I really like join contests even I can make my rating down. I only care what experience I can get from it <3
How to solve E?
If any component is not bipartite answer is NO. If you fix the vertices which will get color 2, then you can color remaining vertices as 1 or 3. Now it's just knapsack problem.
The key observation is that colors $$$1$$$ and $$$3$$$ are interchangable: if we have a good coloring and change $$$1$$$ to $$$3$$$ in it (or vice versa), it is still good.
So let's instead solve the problem where we paint the graph into $$$2$$$ colors: $$$1$$$ and $$$2$$$. To do this, find all connected components and check if they are bipartite. If there is a non-bipartite component — the answer is NO. Otherwise, we either assign $$$1$$$ to the first part of the component and $$$2$$$ to the second part, or vice versa.
Our goal is to assign $$$2$$$ to exactly $$$n_2$$$ vertices, so if the number of vertices with $$$2$$$ in the $$$i$$$-th component is $$$cnt_i$$$, then we must have $$$cnt_1 + cnt_2 + \dots = n_2$$$. For each $$$cnt_i$$$, we have two possibilities: it is either the size of the first part of the component, or the second part. So we may write a knapsack-like dp to satisfy this equation.
E is very educational,thank you for you effort!Though I didn't pass it during the contest because I forget that 'dp' starts from '0'.
First, observe that there is no answer if the graph contains cycle of odd length.
Second, observe that if we have fixed the position to fill the 2's, we are free to decide to fill 1 or 3 in remaining nodes (as long as we have enough such number)
We can consider the answer in each connected component and do a DP, detailed as follows:
Detect if there exists odd cycle (this can be done by considering the depth of nodes when visiting a already-visited node)
Find the size of each connected component.
For each connected component with size, try to fill 2 in alternate depths. There are only two ways of such filling, one of them uses $$$A$$$ 2's and another of them use $$$B$$$ 2's ($$$A+B$$$ is the size of the connected component)
Do dynamic programming on the values of $$$A$$$ and $$$B$$$ you got in each component (you will need backtracking)
With the DP table you have built, determine if you can have an answer having exactly $$$n2$$$ 2's. If so, also fill the remaining spaces with 1 and 3.
Do check this , I have implemented this using top down dp (with comments). https://mirror.codeforces.com/contest/1354/submission/80571115
[Deleted]
Why was the limit on $$$N, Q$$$ for problem D so tight? To avoid a policy-based data structure solution to fail? Is it expected for an $$$Nlog^2(N)$$$ solution to pass system tests, given that it would take approx. $$$4.10^8$$$ ops?
The intended was BIT sol and 1.5 seconds gives enough leeway for it, despite this many BIT sols failed so I am not entirely sure how the authors were trying to educate us with problem D.
I think you're supposed to use nlgn sol using trick to bsearch on fenwick faster.
I got MLE not TLE :think: also unoptimized bsearch passed for people
I think it's because you used class, that adds extra memory overhead. Try getting rid of all template stuff to use less memory, though idk if that would work.
To let the contestants using fhq-treap fail because of MLE.
But it won't .
For D, q*lgn*lgn passes with cin/cout but times out with print/scanf.
Do the organisers have any solutions for D that work with any version of python? Given that there were no accepted submissions during the contest (and at the time of writing still none)...
OK there are now some (at time of writing 2 independent) accepted submissions in pypy3, so I take back what I said. Still incredibly tough for us python users, but I guess that is the cost that comes with using a more handy language...
smallest-square-that-can-be-fitted-outside-the-regular-hexagon
The colon ':' is missing after https in your link.
E is a good problem. C1&C2 are too bad
E is wack shit that shouldn't be in an Edu round in the first place. C is the real skill that one should hone.
Why? C is simple formula problem and in fact, it should be a complete math problem instead of a competitive programming problem, which is not situable in an edu round.
I agree E doesn't require much creativity but why E isn't suited for edu round(I think it bring concepts of bipartite graphs, knapsack and the building dp answer which is educational)
For real, asking people to answer up to 3 (why not 2), tracing dp (which is an abomination) and leaving such problem in the E position.
If only colors to be used are 1 and 2, arriving to the concept of bipartite will be instantaneous. And it's just a couple of more lines of code. Tracing dp is hated but so is geometry so your claim for C can be loosely applied here. Where do you suggest to place this problem in problemset?
If you liked E, there's a similar problem on AtCoder that is very nice also:
E — Independence
Formula for C2 (without proof):
C1: 1/tan(π/(2n))
Link: https://mirror.codeforces.com/contest/1354/submission/80516480
C2: cos(π/(4n))/sin(π/(2n))
Link: https://mirror.codeforces.com/contest/1354/submission/80516821
Can you give at-least some intuition? How did you come up with this?
https://mirror.codeforces.com/contest/1354/submission/80533336 First of all orient the polygon such that one of it's main diagonals(consider this x-axis) is parallel to a pair of sides of square.Then,you'll notice that if we rotate this diagonal by some phi say in counterclockwise direction.The length of projection(along x) of this main diagonal will shorten and become 2*circumradius*cos(phi).At the same time height one of the points belonging to the side of polygon that is || to the main diagonal starts increasing and it becomes 2*circmumradius*sin(psi+phi) where psi is initial angle made by this point with x-axis i.e psi=(n/2)*pi/n.So the optimal case is when cos(phi)=sin(psi+phi).So we get pi/2-phi=psi+phi i.e. (pi/2-psi)/2=phi.So our answer is 2*circumradius*cos(phi).
can you give a diagrammatic explanation of this, which could make things more clear.Please!! Your approach seems to be interesting and simple too.
https://imagehost.imageupload.net/2020/05/18/IMG-20200518-WA0005.jpg See the reason I am focusing on point 1 and 2 is that they are the points whose x distance and y distance respectively from origin is maximum.
thanks for the explanation. very well explained!!
How to solve problem G?
IDK
Well, here is a solution (I think, I did not participate, and nor do I intend to implement this to check).
First, we choose random 31 elements, and then find the maximum among them. This can be done in 30 queries. The probability of the maximum being a stone is atleast $$$1 - (1/2)^{30}$$$. Now, we have the index of one stone. Remove this index from the array.
Now use this and query it against the first stone. If the first stone is lighter, it is a gift. Else, it is also a stone. Use the first two to query 2,3. If 2,3 is lighter than 1 and our stone index, then there must be a gift among them. Binary search that. If not, use 1,2,3 and our stone (4 stones now) to query 4,5,6,7.... etc. This whole thing can be done in less than 20 queries (10 for the "forward" binary search, 10 for the "reverse" binary search).
Well, I too thought of a similar idea. But, I am interested in a deterministic solution.
I think this was the intended solution, since "Hacks are forbidden".
Note that obvious ideas to make the first step deterministic such as partition totally array in 2 and always choose heavier subarray fail on a case like [20 20 20 1 20 5 19 19] — the algorithm will end up choosing 19.
How to solve div 2 problem B
well, this is pretty standard. You can use Two pointers and find the answer in linear time. Another approach is using binary search: If there exists a valid subarray of length $$$l$$$, also this is true for all $$$y \ge l$$$, so you can apply binary search over the length of subarray and check each subarray of current length in linear time, so complexity is $$$O(n\cdot \log n)$$$
Anyone has good solution for D?
Imagine we have a frequency array that counts how many times each integer appears. Well, now use a Segment Tree of Sum over that array, you can do each operation in $$$O(\log n)$$$-time.
Was D added to fuck all Java participants?
Yes, it was really unfortunate :(
sqrt bucketing, solvable using O(n) memory.
I do not expect to have to do that for a Div 2 D, though :/
actually idea is not that hard, even easier than segment tree (but I guess we are more familiar with segment tree). Most of sqrt bucketing ends up with T: O(n*sqrt(n)) S: O(n)
How would it use less memory than fenwick if implemented with just array?
not talking about fenwick tree.
I think what he is talking about is that the solution that most used is fenwick tree which is also O(N). So sqrt bucketing is probably worse>
Even worse is that sometimes it passes with the same memory, other times it doesnt. [80497819 has the same memory used as my solution [80506407 but passes. I changed the way I read inputs from StringBuilder to DataInputStreams and that passes too !!
awoo, is it possible to at least rejudge java solutions in the contest adding a little bit of memory overhead, otherwise I think its completely unfair!
It's unfortunate, but it is well known java's limitations compared to cpp, so if you choose to use it that is at your risk, especially if there are solutions that do pass.
How do you know it's well known limitation? Only 6 solutions in java passed during the contest. I have been doing CP for almost 8 years now, with the same (or similar input readers) and never had to face this kind of issue. On a positive note, I did learn a more efficient way to read inputs (but was that the intention of the problem authors?) A well known limitation of java is to use Scanner to read inputs vs other buffered readers, (and similar to output). But this is really new and one of a kind issue. If the authors had not intended it, they can just acknowledge and care about it from next time (would be nice of them to re judge the solutions of java in the contest, but not required). If they did intend it, then I can start looking for even more efficient ways to read inputs from next time :)
I meant in general java is slower and uses more memory, which is well known, and this is why most people use cpp, so using java in general puts you at risk. I do think that the input method being the problem is pretty bs though, and that should've been tested.
For Problem D
CPP solution is working fine with memory = 4 * n
But Java solution is getting Memory Limit Exceeded for memory = 4 * n
This looks unfair, kindly let me know if I am missing anything.
Java solutions using
new StringTokenizer(in.readLine())fail because the entire line is too big to fit in the memory constraints. Need to use a better I/O method to pass :(My solution and I/O method below.
First time I came to know that $$$π$$$ is not equal to $$$22/7$$$.
uh...
My submission for D got TLE on test case 37. Its time complexity is O( q*log^2(n) + n*log(n) )
Here's the link: https://mirror.codeforces.com/contest/1354/submission/80507579
But almost the same code which is O( q*log^2(n) ) got accepted. (I submitted it after the contest)
Here's the link: https://mirror.codeforces.com/contest/1354/submission/80514775
I don't understand why? Please help me out.
UPD- Found the mistake. I used long longs instead of ints :(
The same thing happened to me but I didn't find any mistake. Even I compare them.
Your same AC solution is giving TLE on test 13 Link
Problem B was available on GeeksForGeeks and Stackoverflow . So all those participants who copied from there would get plagiarism or not ??vovuh
I guess number of dislikes is the number of people who took B from above mentioned platforms. XD
It is totally fine to use code from other sources (as long as it is not from other participants during contest). Even ICPC allows prewritten material.
This problem was easy enough to derive in like 1 minute anyway
Yes it was pretty straightforward 2 pointer question but to save time things might have been copied .
Yes and it doesn't matter. Most people have templates of code saved up anyway...
I didn't take part in the contest and even more I didn't prepare any problems, but I disliked you because why do you need to mention me? How do you know if I'm tied with this problem somehow?
I am extremely sorry. I didn't mean it that way. I just wanted to ask you about that fact that wether or not is there a plagiarism check for these kind of things since you are a problemsetter and you might know about it and I didn't tied you to that problem .Just a general doubt. I didn't mean to insult you in any way . Just curious.
Is this an open invitation for TLE hacks?
Yes. :D
Is special memory problems a new "thing" in CodeForces now?
Did anyone else spend a long time on D bcz they thought the BIT sol was so standard you must have to use less memory than a 1e6 array? I was thinking for a long time how to only store value on input and compress, but then decided to try BIT and was dissapointed to see it worked.
With simple maths we know that we can have around 28*1024*1024/4 = 7340032 integers, which is definitely more than 1e6. I think it's important to know how to evaluate the data we can store in such tight memory limit question. Yet this question is still very unfriendly to people using java and python :C
I did that but assumed there would be memory overhead causing the need for a tighter sol, which happened to be the case with other languages, but not cpp.
Btw BIT solution was already available on the web.
Damn. I should have searched for Order Statistics tree implementation, instead of BIT implementation during contest.
Umm say the multiset contains all numbers from 1 to n, then I would need an array of n size to store it, right? Otherwise I wouldn't be able to tell which number is there or not. And BIT uses the same amount of memory as the array. So I cannot understand how you thought that even lower memory must be used.
I thought it'd be something similar to bloom filter, so I was thinking along that line.
I feel that all the java submissions for problem D should be re-evaluated as the contest seems to be biased towards cpp guys! The same code is accepted in one language and not the other. This is simply ridiculous,never seen this happen before!
I agree...
Problems B + C1 + D + E
Nice! I love watching your videos :)
thanks.
https://mirror.codeforces.com/contest/1354/submission/80472333 can somebody explain this code of c2
https://mirror.codeforces.com/blog/Kirill22 Надеюсь, это распространится и буду приняты необходимые меры.
Why do you completely hate Python?
I like programming in python. I had a perfectly creative and good solution for D with a segment tree. I created a list with around 2,000,000 zeros. MEMORY LIMIT EXCEEDED. in python3.7 python2.7, pypy3 and pypy2. And the sad thing is that it makes sense, because the memory limit was 28MB, and each int is about 32bytes. After the competition I transformed the solution to C++, and lo and behold, it was ACCEPTED. Would it have been so terrible to limit the memory to 80-100MB instead of 28? It just seems super unfair to me in this situation.
Also, you keep telling us to USE PYPY2. But on two separate occasions now (one in yesterday's competition as well, in young explorers), when you have to print many test cases,I get a time limit exceeded, which I DON'T get in python3.
You can check my profile to see I'm not making this shit up.
Why do you completely hate Python?
I like programming in python. I had a perfectly good solution for D with a segment tree. I created a list with around 2,000,000 zeros. MEMORY LIMIT EXCEEDED. in python3.7 python2.7, pypy3 and pypy2. And the sad thing is that it makes sense, because the memory limit was 28MB, and each int is about 32bytes. After the competition I transformed the solution to C++, and lo and behold, it was ACCEPTED. Would it have been so terrible to limit the memory to 80-100MB instead of 28? It just seems super unfair to me in this situation.
Also, you keep telling us to USE PYPY2. But on two separate occasions now (one in yesterday's competition as well, in young explorers), when you have to print many test cases,I get a time limit exceeded, which I DON'T get in python3.
You can check my profile to see I'm not making this shit up.
No one cares about python..Understand it or accept it
Dude, Atcoder, Google kick start (and other), leetcode are all accept python. CF is the last platform that has c++ benefits (even Java sucks here).
It's surprising how almost the same set of authors can set absolutely horrible contests (like this one) and very well balanced contests (like last Edu round).
Is it horrible? Nope. How, I found this one interesting. Specially C1 and C2. You can get to a formula where you don't need to think of precession errors.
C2 is too hard to be Div2C. D is just dumb. I do CP because usually getting the asymptotic complexity right is enough. Policy Based Data Structures also use O(N) memory, but memory limit on D is set too low just to fail PBDS. That's absurd.
Nope, C2 isn't too hard for div2C. I am assuring you as a class 10 student with no prior math olympiad experience. And it would be like a cup of tea for an IITian because of massive difficulty level geometry questions they went through. You probably had a very bad day, in other day, you may get accepted in only 5 minutes.
But D is just a trash. It's just an unfair advantage towards cpp guys
Number of submissions to the problem say otherwise.
I also don't know where you got the misconception but an IITian does not need to know proper geometry — it's only coordinate geometry and trigonometry which are part of the syllabus.
yeah it requires some basic geometry only ....... as one can easily understand by taking diff values of n and fitting polygon inside a square that the square must have side equal to length of longest diagonal .......which is the line connecting exactly opposite vertices....... then do some geometry .... and get the results.... I am still not able to find the fact that why people are considering C2 as tough or maybe it was easy for me as maths and geometry are my fav topics being in ICSE board upto 10th i like goemetry very much
You did not solve C2 and here you are talking about its solution and difficulty level. Its not that simple. Your statement — "that the square must have side equal to length of longest diagonal " is absolutely wrong. For solving c2, it won't be the case. You can fit a hexagon inside a square where none of hexagon diagonal is parallel to square side hence your statement is wrong. For solving it you can have diagonals making some angle with square's side and then computing this angle is the key part.
question also says that you can rotate the polygon....please read the question first then give knowledge to others,,,,,,,,,
Try C2 and solve it. I already gave you hint how to do it. You will understand what I meant :)
If PBDS was allowed, the question would be like : Do what's written in the statement!
I myself also tried a PBDS solution but I think low memory limit was justified (Not talking about Java/Python users..that's a completely different issue).
Agreed. I am not saying they should have allowed PBDS. I am simply saying it's a bad question when you have to set constraints to fail one O(n+q) memory solution (PBDS), while allowing the other (Fenwick Tree) to pass.
Any solution with correct asymptotic complexity should pass if the question is good.
Уважаемые организаторы Educational Codeforces Round, проверяйте своих участников на списывание. А то уже у меня есть основания полагать, что не один человек просит у знакомого скопипастить код
До сих пор под впечатлением?
Бывает :)))))
Like almost all Educational Rounds, i think this round too lived upto its expectations. I personally found the problems very interesting, especially for a guy like me who is still in the learning phase. PS: I found an exponential jump in difficulty of problems after C1.
C2 is not that hard man. Just similar to C1 with little observation. There is no big gap
Can you prove your solution?
Sure. Here is the square for hexagon.
Rest is easier to do.
How to solve c2(without formula)?
https://mirror.codeforces.com/contest/1354/submission/80472333 .. if you get it please explain it to me also.
editorial?
The D problem was really interesting , same as that the problems C1 and C2 are really worst.
authors: make problems with simple geometry us: GEOMETRYFORCES XDDDDDDD
In problem G, is there any special use of the fact that k <= n/2 ? Won't just k >=1 suffice?
Just curious, why aren't hacks allowed in G? My very very incorrect solution to G passed.
Edit: Now I get, the intended solution was using random.
congrats on kickstart rank
It allows a solution to quickly check if an element is a stone, with high probability using ~ 30 queries. Probably hacks are forbidden to avoid hacking seeds etc.
I still don't see the point of adding math problems in a programming contest
Please can someone explain it!
when will the next normal round be held , cz from 29th may it's showing kotlin only
NEVER use problems like C1 & C2 ever again! it's a total time waste! what's the point of applying an equation you can easily find online to get the answer! either use quality problems or postpone the round till you have something worthy, but this.. this is not acceptable at all.
Can anyone tell me Why ordered_set gives memory limit exceeded in D?
I too want to know, what ordered set gives mle and segment tree with lazy propagation got accepted? Thanks in advance.
I guess MLE proves the high constants involved in the implementation of ordered_set. And by constants I mean memory — O(n*c) ,where c is quite high to fit in the memory limit of the problem.
This was one of the most unbalanced contest.
D was so unfair for various languages. Further C was designed to be a dull geometry problem.
Hi, I am facing an issue. My first Submission to the problem D was showing TLE during the contest but after the contest when I resubmit the exact code, it got accepted. why?
what's the point of lying , it isn't the exact same code you added a new value (mx) and used it to change multiple conditions.
Bro, I said First Submission you checked 4th submission. Why would I lie if anyone can check my submission? Please Compare 80504013 and 80527339.
i apologize. this is actually quite weird someone should look into it.
What should I do? I dropped a mail to the mike and problem setter.
It is probably just barely on the edge of time limit. Problem D was super dumb anyway and designed to be on the edge of TLE / MLE which is absolutely dumb :/
You are taking too close to the TL. During load (like a contest), the time taken is more than normal. So for unstable time taken, you may or may not TLE, it's luck then.
Even I have had this happen in a round, sucks but is fair.
I solved C2 by searching the web Largest hexagon that can be inscribed within a square.
Then I guess the 2*n sided polygon should be put n/2 sides chord to the b right triangle hypotenuse, and n — n/2 sides chord to the c hypotenuse. Code
please explain your code a bit .....thanks
dia is the diameter of the circle which the polygon is inscribed in. You can computed it by half of the side length of the triangle and half of the center angle of each triangle, we get 0.5/sin(PI/n/2). The chord can be computed by the diameter and the center angle. n/2 sides center angle is PI/n (n/2) , half it we get PI/n(n/2)/2. The half of the chord is dia * sin(PI*(n/2)/n/2), the chord is dia * sin(PI*(n/2)/n/2) *2.
How could WindScanner solve C1 after D only 20 seconds? This comfused me:(
80460341 80460643
Maybe he read both the questions and solved them, but didn't submit until he had solutions of both problems ready. tourist surprises us with this strategy many a times.
And also in 1324 , as an untrusted participant, WindScanner solved D&F almost at the same time when it is only 10 minutes from the comptition started and got 4th place in the end. I don't think that is normal, I think he is just a cheater.
Weird indeed, because it's not even the same code template. Hopefully, it won't be, but it seems like cheating. We have already seen here some cases of pair of cheaters on-contest
fakeMatrixCascade Have you noticed his submissions still count? He ascended to candidate master
80530953
Inviting you folks to hack my F, it seems super simple and I cannot fathom why there's 6 second timelimit for this task.
Time limit is set to $$$6$$$ seconds to allow flow solutions (I think that even though they are slower than exchange argument dp, they should be still allowed to pass).
Thanks for the insight! Can you give a rough sketch of a flow solution?
The answer looks like that: we choose $$$k - 1$$$ minions and place them in some order, then we choose $$$n - k$$$ minions which are placed and instantly destroyed to give a bonus to previous minions, and then we place the remaining minion.
Let's analyze which value each minion adds to the answer. The first minion adds $$$a_i$$$ to the answer (since it doesn't give any bonus), the second one empowers the first, so it gives $$$a_i + b_i$$$, then $$$a_i + 2b_i$$$, and so on. The minions that are summoned and destroyed give $$$b_i \cdot (k - 1)$$$, and the last one gives $$$a_i + b_i \cdot (k - 1)$$$ power.
For each minion and for each position, let's calculate the value we will get if we choose that minion for that position. Then we should distribute the minions into positions so the sum of values is maximized, and this is a well-known assignment problem which can be solved with Hungarian algorithm in $$$O(n^3)$$$, or with mincost flow in $$$O(n^3)$$$ or $$$O(n^4)$$$.
Most stupid round ever!
Oh really? So you solved all the problems and got to the conclusion that it is soo stupid. The fun with this round begins with problem E (E-G). The first 4 problems (A-D) were just problems that somebody might enjoy, other's not so much, because of the math, memory limits or other things. I solved only the easiest problems from this round and the only frustration i have is that i didn't have time to think about E-G and i still don't think that it's stupid. For mediocre guys competitors like me there are the first few problems, for the cool guys there are the last 3. Why do you think red's are not complaining that C was sooo mathy and D was sooo tricky. It is because it's just too easy for them. There were problems for everyone. Who is good with math had C, who is good with DS had D, who is good with observations and maybe coloring problems had E, dp F, again observations and interactive problems had G. This round has it all and i really don't think that you are to say what is stupid or not.
I agree with everything you said except for problem D. Many also saw the obvious BIT solution but were screwed over by the MLE. I don't know the hate for C since it seemed not too hard with only slight bit of math that you can find online.
Well yes as i said, some might like some problems others might not because of various reasons (programming language, math background...).
Also screw you for posting from a fake account.
Why is there a $$$6$$$ seconds time limit for problem F?
I was amazed by looking at the second question in today's contest. It's the same as this standard question which I was doing today at 1:00 PM IST as practice for LeetCode Monthly contest. I didn't even change the code a bit, I just returned the size of string instead of an original string as given in the question in the link. My code is here.
yeah as it is a very general sliding window problem, so it can be seen on any platform!
The contest announcement post with negative votes! Rare records. Anyways, thanks for the contest.
Is there a simpler way to solve D without using a Segment tree/Fenwick or smth similar?
Considering the memory limits, I doubt it.
I mean it's interesting that they asked to output any element left. So I thought maybe there is a smart way to find an element which will for sure be left in the multiset. But maybe there is no such a solution so idk.
Yeah I also thought it was a non-standard sol which you had to do something smart. I guess not
Binary search like this(from rank2)
I'm really glad to see that the announcement of this round has negative contribution. No one wants to solve non computational geometry problems. Those are meant to appear in math competitions not in programming competitions.
Totally agree.
also they did not cared about kickstart......
Why should they? Someone participating in Kickstart should have just skipped this round, after all, there are many contests ahead.(Downvotes incoming ig)
you are a narc
This round should be unrated.
I didn't like many problems too, but c'mon, people still put time and effort into making the round, and I don't think it deserves downvotes. It was a functional round with semi-interesting problems (except D), and I don't wanna see 1-liner pure math geo either, but it was still decent problem for what it was. Just probably they should not have something like it next time, as now they see people's reaction.
Why do you hate geometry problems?
+1
Round should be unrated!
Has the tutorial been released?
WHY WHY WHY do those with a rating of more than 2100 stand in the standings as officially, will this change?
You guys need to stop laying bricks, math problems are tier 1 borderline chief. All hail Mikhail.
So you Div 2 trash have downvoted a round for a problem you can't solve? Well done, wish you stay in Div 2 forever and never realize geometry is not the worst topic.
I downvoted because my solution for D gave MLE ,However the same idea passes using c++. I spent more than half the contest trying to optimize it which isn't fair, i even sent a message to the coordinators during the contest and their reply was "Unfortunately, the memory limit in this problem is tight. Make sure that your solution is memory efficient." Anyway apart from D ,the contest was good.
Let me tell you, they cant see the bright side.
Cuz C was only geometry problem, there wasn't any programming. And B problem was at the internet already
I don't think that's C is really "geometry", imo it is "math". For me problem is "geometry" if it requires some shitty geometry algorithms.
What is the reason for so many down votes on this announcement ?
People cannot understand why it is called Educational round
I think we people do not appreciate the efforts made to create such rounds. Authors and testers are not angles who do not make mistakes.
If you think you can create a better round, why don't you propose a round to codeforces and see how participants react to your work although you might have spent a month preparing the round(people might call your work trash).
People do not want math nor geometry problem because they cannot think. they want something they can solve, and when they cannot, they turn around and say it is a bad contest (nature of human).
I myself did not solve C1 nor C2 nor D but I think they are beautiful educational problems.
I just wanna say thank you for all the authors and testers.
When i encounter a problem i cannot solve that's when the excitement starts
You said my words, thank you for understanding.
I am trying to make a contest by myself, and its never easy to make good problems, so even if the problems weren't as nice as hell, then its still fine.
It seems the problems are too googlable, and so, i guess its not acceptable.
all the best!! i hope you are able to make some very interesting problems
Just a shitty contest once in a while but please keep it unrated ! I work hard for ratings and I don't google during contests ! Today I payed a -80 rating drop for not googling between contests.
If you're really worth your rating you will get it back later
Atleast authors should say something about easily googlebale tasks ! why are they all just silent ?
Because its an Educational round. Read the rules and you can see that these rounds can contain well-known problems.
Yeah, you are totally right!1! I spent 10 minutes googling related formulas like incircle radius but that didn't help me to come up with my solution... So my rating should be bigger (xD, trolling)
When is the editorial coming ?
Probably right after the hacking phase ends. Or some hours later than that.
Can anyone explain a simple O(n) solution for B?
This can help you
Convert 111333211123 into arr = [[1,3],[3,3],[2,1],[1,3],[2,1],[3,3]]. arr[I][0] represent number. arr[I][1] represent how much arr[I][0] was in a row. go:
2+arr[i] cuz we need only this nums 1 1 1 2 2 3 3 3
How much long will it take to display the ratings on our profiles?
After the open hacking phase and system testing.
About problem C2, seems like the side of the square is equal to FJ(The samples matched). I submitted without proof why it works. Can anyone please check the math, and explain why it works. I can't figure it out!
code: https://bit.ly/2LFcU4A
Angle subtended by an chord or arc of circle at circumference is half of angle subtended by same arc at centre(Its a properties of circle). So now we know one side and opposite angle and we can calculate the other side by using basic trigonometry(as triangle formed is right angled triangle).
Hey man, I know that property, and that's how I came up with this sketchy solution. My question was, for 2*n sided (n is odd) regular polygon why the smallest square where the polygon can be inscribed has side length FJ (or Aj, since AJ = fJ)?
I think this contest should be made unrated for everyone because the solution of problem B,C,D could be directly found in google.This makes this round a test of our googling skill not coding skill.Many contestants have taken advantage of it.Even some of them copied directly from the source websites.I found some solution were directly copied from geeksforgeeks. It's really funny that they submitted the solution with the comments of the website.If this round is still rated, that would create a very wrong practice among the coders.Now everyone will google the problems in first place in the next contests. Anyway,happy coding.
I mean like there is nothing wrong with googling. In most rounds google is not applicable (for the most part) and even if does create a "bad practice" people will immediately realize that they will not always be able to use google in future rounds. Also many use templates of prewritten code which is also allowed by ICPC so overall I don't see any problem with it. However, I will agree that problem D was terrible this round because of how it screwed over so many people with the intended solution.
I don`t understand your position on D. Problem has straightforward O(n*log(n)) solution with segment tree. If you do not know that some intended solutions can get TL or ML than you should read name of the round. Otherwise, it is your risk to use intended one or think on better algorithm.
Of course segment tree and BIT are the obvious solutions, especially BIT. I am talking about how many non c++ users used exact same solution as c++ users with BIT and still got MLE.
That is not fair that you can read and split whole array in 1 line and I need to write whole for(;;) loop. Java have clear advantage. Sry for exaggerating but sometimes it is normal that a person in sneakers can run faster than in boots :)
I realize that this is an educational round but I don't find anything educational about optimization hell.
This exact thing happens to Python coders all the time. Is the solution then to throw out problems that can’t be solved in Python? Where is the line drawn?
The reality of the situation is that you need to know how to handle stuff like this if you want to code in Java. Problems that are optimization hell get set in ICPC, two from the top of my head this year are ICPC Camp from NAC and Jumping from SER.
A contest I went to earlier this year at Mercer had a problem where you had to print a double to 3 decimal places. It turned out that the data was written in C++, and the rounding procedure for printf in Java did not work. Thus, all the UCF teams there (except the one team with a Python coder) could not solve the problem.
Stuff like that will continue to happen as long as the majority of the competitive programming community uses C++. It’s the reason I switched from Java to C++, and it’s the reason you should know some basic C++ if you want to be successful in Java.
Yeah I guess you're right. I mean it doesn't typically happen where using a different language matters but I am just a bit frustrated because over the past few contests I have gotten screwed over for Java's slowness, and considering Java is the second most used CP language, I would think that there would be some care taken to make sure solutions for it pass. I am trying to make an active effort to switch to C++ but I am not sure how well that will go while I'm in the midst of learning new algorithms and such.
Yeah, I understand the frustration.
It took me about two months to reach the same proficiency in C++ that I previously had in Java. My advice (YMMV) is to just dive headfirst into coding in C++, and only submitting stuff in Java if you have no idea how you could do it in C++. At the start, you might only solve a couple problems per contest in C++, but over time that will increase to half, to most, and finally to all. It might cost you some penalty points, but if the reason you're doing contests on Codeforces is to practice for more important contests (like USACO or ICPC), then the practice you get for those is more important than your rating. Besides, if you deserved the rating that you have, you will get it back quickly once you are more proficient in C++.
For people who complain that C2 is non computational geometry problems, I share my binary search solution: https://mirror.codeforces.com/contest/1354/submission/80487561
Can you explain the solution
If the square is without rotation, the minimum square will have spare space on one side. We consider the minimum rectangle, and rotate it. when the rectangle rotate, the long side of it will decrease while the short side increase. when it becomes a square, it is the answer.
i believe this is also the expected solution. going on the problem now shows binary search and ternary search tags.
This is actually a cool solution
this is a great round. thanks pikmike. those who downvote this round dont love math and cant realize beauty of geometry. it was a classic problemset. however i cant solve problem c2 and d , but i learned very much from these.
OMG, I just looked at problom E and misunderstood: |colu−colv|<=1 , then got no idea...
Ok, thanks in advance, I need help to know a thing. Today's Problem D(MULTISET) I user policy-based Data Structure (Orderset) and I assume that my code took (2n) Space Complexity, it got MLE. But I saw some solution used up to (4n) Space complexity (Segment tree) and yet that solution got Accepted (y). Can someone please help me to know why??
Policy-based data structure is implemented as a balanced binary search tree, if I'm not mistaken. BBST has hidden memory costs associated with pointers, as well as with the augmented information on nodes (if I'm not mistaken, subtree size, which is used to determine the index of elements). Hence, it actually takes a lot of space because each node in the BBST stores a lot of information.
Also, properly implemented segment tree should only use up to 2n space complexity. For struct segment tree, you can prove this by drawing the structure of the tree and observing that it is a binary tree with n leaf nodes, which means it should have n — 1 internal nodes.
By "properly implemented segment tree" do you mean the iterative one? (all the recursive segtree implementation I know uses 4*N memory ) If so, how do you binary search on it?
The memory consumption of recursive segment tree is in fact higher than iterative, but that is more of the fact that you need to store pointers to the left and right child nodes. In terms of actual number of nodes created, it can be proven to be 2N-1: each internal node is a union between two disjoint sets of leaf nodes.
I don't use an iterative segment tree, but I think a similar logic to "seg descend" method could work here: you start at the root and check whether the left child satisfies your requirement. If so, go to the left child. Otherwise, go to the right child. Just code it iteratively rather than recursively.
Edit: for the specific problem given, I think there is a recursive segment tree implementation that stores 6N 32-bit signed integers. However, given that it is 28 MB memory limit and this algorithm uses 24 MB, plus probably some overhead here and there, I'm not sure whether it passes. Intended solution is probably Fenwick tree or iterative (array) segment tree, not recursive (struct) segment tree.
Edit 2: Just to check, I coded the struct segment tree solution. It MLEs on test 4.
The iterative segment tree I'm refering to is this (using 2*N memory) and it treats the segment tree as a forest of binary trees, which makes it tricky to do binary search like the recursive versions.
Actually for this problem because the limit on n, 10^6, is so close to the next power of two, 2^20, I think you could just create an iterative segment tree as described in that post with 2^20 nodes, which means that it's always a perfect binary tree, which should make binary search easier.
That's a nice idea xd. Anyway right after posting that comment, I actually mananged to do binary search without changing the size by just storing all the roots when initializing.
I applied the same logic using recursive segment tree with 4*n size and it passes easily ..you can check my submission here https://mirror.codeforces.com/contest/1354/submission/80530927
I was talking about pointer-based struct segment tree when I said "recursive". Sorry about the misunderstanding.
Yep, yours looks about right. Because you're using array indexing to keep track of left and right children in your segment tree, you don't need to store explicit pointers, which was probably what caused MLE for mine.
Lol even rating update and editorial release has been delayed.
Is the system test is done? I didn't notice it...
Probably not. Well I may be wrong.
Bruh, the contest evaluation status is seen in the “standings” column of the “contests” page. And its been “Final standings” (Was “Preliminary Standings before that) since about 5:30 IST for Edu. 87. So it is indeed the case that ratings haven’t been updated but system testing is done.
Not exactly. For
Educational Rounds, theFinal Standingappears both before and after system test.When the test details contain the hacks, it means that the system test is done.
Sorry for my bad English. :(
I'm pretty sure I saw it change. But if you want further proof, enter the contest and check the status on the right hand side. It says "practice". It usually says "system test pending" in case it hasn't been done.
Now the system test is on :D
Yeah, sorry...my bad. The signs were misleading. And regardless, your English isn't bad :))
Obviously, those are not the final standings. You can see that still grandmasters and masters are there in the final standings (even after you click on show unofficial button).
I hope you are now aware of the fact that your perception was indeed wrong.
Why the editorials are not out yet after 12 hrs to Contest.
Maybe because the system testing is yet to be done.
Why does system testing matter for releasing the editorial?
If the editorial is out then people will hack others weak submissions by reading all the conditions from the editorial and thus their rating would decrease and this would be unfair because person didn't put his mind to find the flaw rather used the editorial
Since the open hacking phase is over, why would that matter?
It doesnt matter since the solution is going to fail in system test anyways. The hacker is not going to be benefitted since there is no reward.
there is no system test for educational round as solution is already accepted and if your solution is hacked after the open hacking it doesn't affects your rating but it would affect if done within hacking period
Seriously? I had no idea.
Why there are no editorials for this contest ??
When will this contest be rated?
The rating calculations include some manual actions. The most persons usually initiating these actions live in a timezone where it is currently more or less early in the morning.
my BIT & O((q+n)log(n)) solution for probloem D
https://mirror.codeforces.com/contest/1354/submission/80567274
Just change binary search strategy a bit.
Hi, I was trying similar in the contest. I got a Memory Limit Exceeded on test 4 80499850. Can you explain your modified binary search a bit, I was doing a conventional binary search in the case of deletion to find the minimum index for which getsum function of BIT will return k[i]. Can you explain these lines of your code:
know little of python, sorry.
In my BIT, I usd array d[n+1] to store the amount of numbers, like
n=8
mutiset: 1 2 3 4 5 6 7
d: 1 2 1 4 1 2 1 7
when get q: -6, I try to find bigest ans, while less than 6 numbers is in (0,ans]
guess ans=8, d[8]=7 numbers in (0,ans], too big
guess ans=4, d[4]=4 numbers in (0,ans], ok
**so, the final ans is at least 4. I still try to find bigest ans, while less than 6-4=2 numbers is in (4,ans] **
ans=4+2, how many numbers are in (4,6] ? d[6]=2 , too big
ans=4+1, how many numbers are in (4,5] ? d[5]=1, ok
final ans=5
less than 6 numbers is in (0,ans]
NOT less than 6 numbers is in (0,ans+1]
so ans+1 is the 6th number
I read various comments regarding the quality of the problemset. I totally agree that B C D were easily found on web and this is a bad practice in rated contests . But frankly speaking, many might have learned binary search with BIT , lots of concept related to regular polygons. Atleast I have learned few new concepts. So until and unless there is some learning for everyone in the contest, it is a good one .
Also, the Educational Rounds are for this purpose only. If somebody would read what the Educational Rounds are all about here: https://mirror.codeforces.com/blog/entry/21496, he/she can clearly notice that these rounds are not for competition but to gain knowledge about the data structure, algorithms or techniques that one might know already. And for those who know them, it is just a practice for them.
When will this contest be rated?
It was a good game! Many stupid people criticize the game just because they didn't finish the problem, it's ridiculous
editorial?
It's taking a longer time to get system testing started. I wonder when it will start.
I really liked problem G! I solved with a randomized solution. I assume $$$N \geq 5$$$ in the solution written in following.
Step #1. Find one stone between $$$3$$$-rd to $$$N$$$-th box
Because of $$$N \geq 5$$$ and $$$K \leq 0.5N$$$, there is at least one stone between $$$3$$$-rd to $$$N$$$-th boxes.
Let's take $$$G$$$ boxes randomly in $$$3$$$-rd to $$$N$$$-th boxes. Here, in my solution during the contest, I set as $$$G = \min(N - 2, 23)$$$.
Since at least half boxes contain stone, the probability for all boxes to be gifts will be at most $$$2^{-G}$$$, if $$$G < N - 2$$$. If there is at least one stone, compare weight of two boxes $$$G-1$$$ times, and the heaviest one is the stone.
Step #2. Find the range that "no gifts in box $$$1$$$ to $$$x$$$, but at least one gift in box $$$x+1$$$ to $$$2x$$$
First, we'll check if there's no gift in box $$$1$$$ or $$$2$$$. You can check by comparing weight of this box and the stone found in step #1. If there's, we got the answer. Otherwise, we ask the question like following:
- Is there any gift in box $$$3$$$ to $$$4$$$? We can get by comparing weights of boxes $$$1$$$ to $$$2$$$, and boxes $$$3$$$ to $$$4$$$. If there's, then terminate by setting $$$x = 2$$$.
- Is there any gift in box $$$5$$$ to $$$8$$$? We can get by comparing weights of boxes $$$1$$$ to $$$4$$$, and boxes $$$5$$$ to $$$8$$$. If there's, then terminate by setting $$$x = 4$$$.
- Is there any gift in box $$$9$$$ to $$$16$$$? We can get by comparing weights of boxes $$$1$$$ to $$$8$$$, and boxes $$$9$$$ to $$$16$$$. If there's, then terminate by setting $$$x = 8$$$.
We continue until we found and double the range for each iteration.Step #3. Find the least-index boxes in $$$x+1$$$ to $$$2x$$$ that contains gift
We find the least $$$p$$$ by binary search that holds following:
The $$$p$$$ will be the requested answer! If $$$N \leq 1000$$$, we will use at most $$$23, 2+9, 9$$$ steps in step #1, #2, #3, so it asks $$$43$$$ questions. My submission is 80502712. You'll learn a lot about binary search if you solve this problem.
Anyway, I'm so honored to get the 1st place (though system test is yet to start) in this round! Thanks to awoo and other writers for organizing this contest.
by chance, the round didn't become unrated, creators((??
Kickstart, Coderforces Educational, AtCoder Beginner Contest 168 all together why?
Wait, is there any test case with $$$m>5000$$$ in E? The constraint says $$$m\leq 10^5$$$.
So,after this round,Is it any round exists recently?(except Kotlin Heroes)
Is this round rated?
Yes
Why ratings aren't updated yet?
The system test hasn't started.
when do we get editorials for Educational Codeforces Round 87 ? waiting since yesterday
People who are waiting for editorials....
Try this
How does it work? I can't catch the point.
Comment deleted!
I want to know when to start the final system test
whenever you want everyone is waiting for it.
Seriously, someone should atleast confirm when would the ratings be updated. This is really sad and frustrating
Yeah, its been almost 24 hrs to when the contest started yesterday and yet the ratings haven’t been released. Why isn’t the process automated?
what's going on?? it's almost 24hours
Why it happened again?
when will the system testing start?
Please refrain from downvoting the announcement. Author put in considerable effort to come up with good problems. Late release of rating changes has nothing to do with him. Even if you are angry for late editorial and rating changes etc.. please don't downvote.. the author deserves that much atleast for his effort. Thank you.
Can somebody tell if this contest was up to the mark in any aspect? (2 times delay in starting time, delay in editorials, delay in system testing, delay in rating changes, googlable solutions for C1, C2, and D, it's more like a codeforces delay round instead XD)
I agree with your point. But I hope as per submissions in C2, D there are very less submissions .So most does not get googlable solutions.
System testing finally started :D
OMG... Why can't you all just sit and wait? Instead, everyone would downvote the contest and add his "super important" comment about how much pain it is for him to wait.
You know what real pain is? I tell you what. Finding something relevant to the contest while reading your senseless comments about how long you've been waiting for your rating to be updated after crushing the round with getting accepted googled solutions with no idea of why they pass system tests. Not to mention the fact the browser goes mad loading all these comments.
Waiting is acceptable, just worrying about waiting for so long but suddenly announce unrated.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Alisher_Kamolov's hacks. Seems like cheating.
I tried to use segment tree in Problem D and I submitted exactly the same code twice. One using
GNU C++17 (64)got TLE (80590272), the other usingGNU C++17got AC (80590625) with the time only 873ms.Can anyone kindly provide an explanation on this? Thanks.
Rip no update yet, its been over an hour since the system testing finished...
cf-predictor-frontend.herokuapp.com/ This is the link to get prediction of rating change. The rating may have error of +5 to -5. Thanks.
Yeah, I know the site, in fact according to that I'll be become an expert again. Hence the impatience :(
it's been updated at last.
Congratulation man!! Expert Again....
Thanks!
Is this announcement with maximum comment and minimum votes?
I am glad that my name is among yellow's and red's (in first to solve each). I never imagined that this is even possible (for a person like me).
In problem B, I have used the binary search logic by storing every occurrence index of '1','2' and '3' and submitted the code in the contest with verdict accepted. In the code I have checked whether it is possible to have substring with all the three characters present in it by multiplying the sizes of the 3 vectors storing the indices and compared it to zero. It went wrong on test number 41 in system testing as it gave output 0.When I submitted the code by comparing individual sizes to 0 it got accepted. Initial Submission(accepted in contest and wrong on test 41) — https://mirror.codeforces.com/contest/1354/submission/80476580 Final Submission (accepted on all test cases) — https://mirror.codeforces.com/contest/1354/submission/80621256 Can someone clarify!
In your if statement, the product of all three vector size are overflowing. By just adding 1LL in front of it, your solution got accepted. https://mirror.codeforces.com/contest/1354/submission/80627780
But can you tell me why is it overflowing insider_pants? It's well within the limit of LL
what you did originally was you just multiplied the sizes of all three vectors but by default compiler typecasts the size of vector into int. So basically, you were doing int * int * int and int has limit of around 2*10^9. It can overflow as the size of the string is in range of 10^5. By adding 1LL in front of it ensures that the compiler typecasts all the sizes into long long and then multiply and now the product cannot overflow.
There is no upcoming div-2/3/4 or edu contest on the list. It made me sad.