Привет, Codeforces!
В 12.07.2020 17:45 (Московское время) состоится Educational Codeforces Round 91 (рейтинговый для Див. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
UPD: Контест отложен на 10 минут.
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | Geothermal | 7 | 341 |
| 2 | natsugiri | 7 | 362 |
| 3 | LayCurse | 7 | 387 |
| 4 | GyojunYoun | 7 | 415 |
| 5 | tribute_to_Ukraine_2022 | 7 | 430 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | celestialcoder | 15:-2 |
| 2 | dapingguo8 | 9 |
| 3 | kamer | 6:-2 |
| 4 | FelixArg | 4:-3 |
| 5 | WiwiHo | 3:-1 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | bekzhan29 | 0:01 |
| B | LUV | 0:08 |
| C | atU | 0:09 |
| D | duyenn_khong_ngu | 0:32 |
| E | dorijanlendvaj | 0:45 |
| F | bekzhan29 | 0:36 |
| G | Geothermal | 0:59 |
UPD: Разбор опубликован
QueueForces
Please, arrange a testing round before this round. If not, this contest will also have possibility to become a unrated contest. Please...
hahaha, and it has :) !
They must have solved the problem of long queue, so they held the contest. But unfortunately this time website errors made the contest unrated.
So is it rated?
no it's unrated at last. Poor problem writer, two rounds wasted.
*writers :(
have you come from future?
It's a general knowledge. :(
This aged well
@Sol1 He didn't "JINX" it, instead it was a good thought ! Would have saved the hard work of the setters ! Its bad to see their work going waste, as we don't even feel like attempting it in live contest now !
OP be like "They called me a madman"
I wonder how many people are about to wait the LONG queue or to register for tomorrow's contest?
Maybe Mike will postpone the contest if the problem is not solved.
to MikeMirzayanov I think we need to make one unrated round and then run the rated round. Because it might turn out unrated like round #655. it is unfortunate that round #655 has become unrated but I believe the next rounds won't turn out unrated and I think many other competitors have the same thought as mine. please announce before tomorrow's contest about this contest will be rated/unrated. thanks for reading
Seems like we need two unrated rounds before a rated round.
"Hope the contest will not waste efforts of coordinators. Although codeforces is the best platform but sometimes gives problem 'queue'. Thanks for such a wonderful platform mike.
There should be Testing round tomorrow instead of Educational round.
definitely should have... every time we have to cancel a round we should have a testing round to make sure everything's ok
But fewer people will participate in testing round. Because it will not be rated.
It is really sad to know that contest is unrated especially after waiting for a whole week. Let's hope that no such issue occur during educational round.
.
I am just curious to know why in some of the contests, the queue is so long even the participant is nearly equal or less than other contests. The load on the server should be the same! (by the way, it really hearts when you are giving the contest skipping dinner and then contest will be unrated).But I can understand It happens sometimes, we can't do much!
They must have done some upgrading work which turned out to be buggy.
Mike said in announcement, "Sorry, because of the long queue the round is unrated. Probably, the reason is the simultaneous combination of several facts: a lot of participants, 5 pretests in task B, a slight degradation in performance after some recent changes. In any case, I will do an investigation". I think it's more because of the changes they did, as there were too many participants in some other contests too, but there wasn't any long queue at that time.
A,B,C solvers never get to use algo knowledge anymore, just a bunch of constructive/pattern/observation C problems everytime. somebody save us.
The aim is to strengthen your logical and constructive thinking before moving on to advanced Algorithms, that way it would be easier to visualize how algorithms work and build strong concepts in those. Anyway, that's just my opinion and you may be right on your part too.
I get your point. I'm just tired of facing the same things. Given a permutation.... maybe I should focus on getting gud so I'd be able to solve interesting problems.
If a problem starts with "Given a permutation", I become very excited and happy :P
Exactly..i also love permutation problems
Lots of problems which have famous algorithms now, were nothing but constructive, pattern, math, and lots of observations based problems 50 years ago
Make problem A,B,C somewhat harder otherwise there will be same QueueForces tomorrow.
Hope it goes well.
Both unrated :(
Was sad because today's contest got unrated, but Wohoo! we have one more contest tomorrow!
It looks sad to me that problem setters have to go through problems like what happened in previous round (**Submission pending in queue to be judged**). I am sure that setters want to have people competing in contest the way they usually do. But bcz of queue issue their contest is just destroyed.
It definitely takes a lot to write a contest. I really do hope that none of setters contest go through it.
i dont know whether this is correct time to say but despite of long queue problem there is another issue of difference of rating of 3rd and 4th question in recent contests was too large...
That was because many left the contest after Mike's announcement. If queue wouldn't have been in picture then I guess the rating of 4th would be near to 1700
Is it possible to tackle queueforces we can judge submissions of unofficial contestant strictly after submissions of official contestant. So it's priority_queue where official contestant are prioritised
It would be great if all the educational round problems were Algorithm based, take no offense, just my personal opinion. :)
Queueforces xD
Let me tell you a trick to reduce the load. Just midway through the contest make an announcement that the contest is unrated. Then when the contest has ended make it rated. Profit
And like this you will become red and others won't ! :P
I think this time mike will definitely win <3
[Deleted].
I don't understand why people feel this upset about the situation of the long queue. Like what makes people feel that they are entitled to a perfect round when the system is running for the community. You are able to give rounds and practice nice problems without paying a cent. Isn't that enough?
Exactly! and the problems which are there in the contest are all new and original with a very basic and tricky idea behind it for atleast A's, B's and C's and even if some round is unrated (which is rare) and people think that their rating would have been increased a lot, they can do it in future contests as well, as they were able to do it now.
Lezendary_sandwich I completely agree with you. After all this is the best platform someone can get which can handle 20k users at a time. But times like yesterday come very often here. So people should keep patience. Hope today's round will be a good one.
Honestly, it'd be pretty cool if we could pay like an annual subscription to CF that gives access to a judge with a smaller queue. Obviously it doesn't work out, since you get a competitive advantage, but still cool.
sounds like leetcode
Does it work well/badly there? I've never competed on leetcode, but it seems like the competition aspect on leetcode not as prominent as CF's is.
I think that could be nice for when upsolving problems or doing virtuals, but I don't usually have problems with the queue at those times. Otherwise yea the pay2win aspect would be pretty lame.
I feel really bad for problem setters and problem testers!! :(
Another contest, another opportunity to my son to win!
that user name tho :)
Nice username and profile picture. man, this comment was good lmao.
Make Codeforces Great Again
It always great!!
Hoping for no long queues in this contest and I feel unlike the last Div2 ,this contest's B and C will be comparatively on tougher side.
When everybody is talking about queue but no one is talking about stack
Why educational rounds have comparatively very less upvotes than a normal div2 or div1+div2 round.
I too was wondering about this.
Delayed :(
delayed by 10 min (:
And once again history has been repeated. Mike must be trying to fix the queue problem.
Delayed again, by 10 minutes. :(
Codeforces needed to run an unrated round before starting educational round
I think 10 minutes delay is better that that.
If 10 minutes delay solve the problem then sure, but how can they know?
An unrated round before this Educational round ran last day xD Codeforces Round 655 (Div. 2)
not unrated but div 4 maybe,many people won't give an unrated round.
Delayforces into action again! Fucking irritating it is :)
You don't have to use slang to express yourself
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Seems like codeforces is in trouble.
I can already see where its going.
Each time a contest is delayed by 10 minutes, adrenaline of thousands of participants goes straight to the flush. edit: GG codeforces lol.
anyone else facing bad gateway?
Yeah. I am getting. No point of giving contest and taking risk.
Me too
Yes, I guess mike has blocked other pages like profile, etc.
i am getting the same thing too
502 Bad Gateway is coming
why am I getting "502 Bad Gateway" error before the contest
Please delay the contest. Make the server prepared. Don't screw author's efforts
why didn't they delay it if it's clear there's a problem now the round is probably not rated again
Ask Mike
Switch to m1.codeforces.com
Also giving 500 error code
500 Internal Server Error...
quite sad to see it happening again , the problemsetters' hardwork is kinda gone to waste again.
yes , another problemset wasted
If all problem statements (except A) were locked/hidden at the start of the contest, then the problemsetters' work wouldn't necessarily have to go to waste. Even if some technical difficulties were to arise during the round, some problems could still be used in the future, since no contestant would've seen them. We could make it so, that each successive problem becomes visible/unlocked, once at least one of the participants has solved the preceding one.
What do you think of my stupid proposal?
I was able to see first three problems on m2.codeforces . So ,there are definitely more people who did. Btw ,It will be better ,if they publish editorials now .
I wasn't talking about what happened in this specific contest, but rather suggesting a way to change the rules, so that problems only gradually become "unlocked". I was able to see A, B, and C, on m3.codeforces.com too, but there is no way to guarantee, that there wasn't some lucky person who could read all problem statements. Therefore, if a situation like this were to repeat itself in the future, there would be no way of knowing, which problems could still be used in future rounds, unless my proposal was implemented.
Is it still rated?
What's going on?
Codeforces!
My son is crying...
I am so sorry for him :(
Still rated? Cant open anything for 30 mins .
Did they not realise that everyone was facing bad gateway ?
Classic Codeforces
UnratedForces!
I think contest could have delayed bit more or held tomorrow after fixed bug. All the efforts of setter go in vain.
yes,they should have seen this coming and postponed the round,would have saved everybody's time and effort
"Unfortunately, the round is unrated."
Ah shit! Here we go again!
That's why we need daily contests XD
Unrated, right?
Unfortunately, the round is unrated.*Fortunately
Unfortunately for setters and management, fortunately for us
UNRATED
You should have postponed the contest instead of starting. Sad for the author.
...
???
having PTSD..
Monogon be like- First time ?
Lol atleast yours will get postponed.
Let's hope history shall not repeat itself.. Looking forward to your contest!
It's almost like people predicted the round would have been unrated if not postponed. There was no way these issues could have been fixed overnight...
It makes sense to ask "Is is rated?" before contests..
WTF, back to back to unrated contest!
I feel bad for awoo and his efforts :(
I think this is done by rival competitive coding sites like leetcode, atcoder, codechef, they are attacking website.... just opinion.
This even worse than yesterday's round
I disagree with you :-)
Atleast we were able to submit today and get the instant result.
what happened yesterday was worst because u just submitted the code and you dont know weather it is AC or not even after waiting more than 10 min!!
Is it the first time there were two back to back unrated contests? If so, we need to reconsider the direction we are heading to.
A. Yet another wasted problemset
Not for you, just go and submit now :-)
Of course I will do that but solving problems during rated contest gives more fun and it's a chance to change rating
Before July 2020: This contest is unusual to have an unusual starting time.
July 2020: This contest is unusual to be rated.
Sad :(
Wish headquarters can fix it ASAP :)
Unrated again!! :(
No excuse this time, MikeMirzayanov. You knew since yesterday this could've happened and you chose to do nothing about it.
UPD: I did a poor choice of words with this comment, I know it's not true that Mike did nothing about the issues on the platform. I do believe there were a lot of alternatives which could've prevented the round from being ruined, and none of them was taken. I stand by that. But I didn't want to offend Mike, or diminish the efforts he constantly does for the community.
What makes you think he wasn't trying to fix this the whole time? Never assume, and be grateful of their hard work.
Facts:
I've always been grateful to CF, I've even donated so they could keep up and improve, which apparently you haven't done. And I didn't say Mike didn't try to fix this. But he couldn't fix it, and I think there's no excuse this time, considering all the options he had.
You literally said "you chose to do nothing about it".
All your "facts" only make sense with the assumption that yesterday's issue reoccurred and precisely that issue was the cause for today's outage. You also have to assume that it was the same issue as in round 639, then, for some reason it went away, and then reappeared yesterday.
How does this even make any sense? Have you really thought this through before commenting?
What makes you think it was the same issue? You realize that there are multiple things that can go wrong on the website, right? It doesn't even make sense as the first guess:
Facts:
we can somehow make the entire codeforce infrastructure as open source and ask more participant to contribute, optimize, improve its overall quality and performance.
While enjoying the high quality contest, it is also important to maintain the infrastructure itself together.
DeadForces :-)
DeadForces :-)
Please, arrange a testing round. We don't want unrated contest any more.
Sorry For My Bad English
All we need is Hope
Ahh, test 7 killed me.
Any hint regarding test 7 in D ?
Same, can't find anything wrong for 1 hour.
It is sometimes optimal for you to take one Fireball, and all others Berserk
I took care of that, can you give any test-case ?
No I don't have any test case but I have 3 cases which needed you need to solve:
If left or right element from subarray is greater than maximum in subarray:
If length of subbaray is greater or equal than k:
Take as much Fireball as you can
Take one Fireball, and all others Berserk
Take minimum of those 3, if those 3 cannot be achieved, than it's -1
Code: https://www.ideone.com/B1cMcc
Silliset mistake I have made, didn't took care of the garbage values.
Maybe check this TC, ans = 11, to my knowledge
Edit: Ok, sorry my mistake, 11 is the correct answer!
What's the test 7 for D
The problems were good!!!
How to solve D?
In order to reduce array A to B, B first needs do be a subsequence of A. Then, when this condition is checked there is always a solution, and here is how to achieve it with minimal cost. For every consecutive B[i] and B[i+1], we need to delete elements from A in the range [pos[i]+1 , pos[i+1]-1] where pos[i] represents the position of element B[i] in the array A.
It is clear that if pos[i]+1 = pos[i+1] then the cost for this part is 0 otherwise let m be max value of array A over the range [pos[i]+1 , pos[i+1]-1] and nb = pos[i+1]-pos[i]-1 (number of elements in the range).
If nb<k which clearly means we can't use Fireball operation, we have only two options:
else there are two cases:
In order to deal with elements before pos[1] and after pos[m], I've added 0 at the beginning and the end of both array A and B. Here is my submission 86697447.
For the case nb>=k
Can you please explain it in detail , I couldnt thought of how to optimally pick elements as there could be lot of ways. Thanks
yeah, ofc. Well we know that it is more optimal to use one Fireball then to use k Bersek which means k*y < x holds. However, we can't only use Fireballs because nb is not guaranteed to be a multiple of k and we will have some elements left in the end. So instead of directly using Fireballs we will reduce nb to biggest multiple of k smaller than nb using Berseks and then we will employ Fireballs. More formally, the cost will be $$$(nb\mod k)*y + \lfloor{\frac{nb}{k}}\rfloor*x$$$.
Isn't it possible that when you reduce nb to the biggest multiple of k, that you could not use Bersek to destroy the remaining warriors? Namely, you end up with m greater than B[i] and B[i + 1]
when reducing nb to the biggest multiple of k we are only using Berseks to achieve that. Keep in mind that we can always do it by picking an element in the range which has a smaller element adjacent to it. Then, we will use $$$\lfloor{\frac{nb}{k}}\rfloor$$$ fireballs to destroy the remaining warriors.
Problems were really good, infact the difficulty of question B was greater than C until u get the trick. Also D was little tricky if u don't consider all the cases carefully. Lets hope we see a rated round soon.
Pls explain your idea of D.
First check if B is a subsequence of A, if not then we can't produce an answer.
For converting A to B we need(provided B is a subsequence of A) to delete some of the segments/fragments in A which are not there in B, for that you can see the my below comments:
-> https://codeforces.net/blog/entry/79986?#comment-660940
->https://codeforces.net/blog/entry/79986?#comment-660968
Didn't read your explanation(I want to first try on my own) but I got stuck on the test case:
what if array_a = [1,3,4,2], array_b = [1,2], k = 3? I'm stuck there. We can't delete [3,4](since k is 3) and if we delete 3 using 4 then it becomes [1,4,2]. Am I missing something?
For the above test case we won't be able to convert A to B because:
-> size of segment to delete < k so we can't use x mana i.e first type of operation.
-> We can use second operation for completely deleting the fragment only when either of adjacent element > maximum element in fragment, but in ur case max(3,4) > 1 and 2 so we can't completely delete all the elements in the fragment using second operation.
How to solve E?
There must be some way to implement the simulation efficient. Note that the ans foreach move is the number of segments of consecutive rings.
Then, whenever two towers get merged, some of the consecutive segments get merged to one segment, ans is decreased by one for each such merge.
But my solution TLEed.
We can do this by keeping track of the current number of differences between consecutive elements. Every time we merge, some differences will get eliminated. We just need to keep track of how many get eliminated per merge. To do this, keep track for each tower, at what indexes it occurs in the array. For instance in the sample, the array is
Then the sets would be:
Now when you merge two towers, this is equivalent to merging the two sets corresponding to those indices. This can be done in O(log n) amortized by using the small to large merging method. For example, after we merge towers 1 and 3, the sets will become:
You also need to know how many changes between consecutive elements in the original array are eliminated. This can be computed by iterating through the smaller set, and adding 1 for each element in the larger set that is 1 away from this element in the smaller set. In this case the
4fromTower 1and the3fromTower 3are the only ones next to each other. This means we must subtract 1 from the current count of differences.In my first submit I tried to use vectors, and made a new vector out of a and b every time. Then I tried to use sets, but it seems I did buildin some bugs, all TLE.
However, of the solutions I studied so far I like most the one from icecuber, 86686544 which does what you explain above in nice code.
My video editorial for B . I have tried to explain my thought process and why the algorithm worked hope you like it .
What is wrong with this approach for D?
I first checked if B was a subsequence of A. After this, I fragmented A into parts (each fragment was between two such positions, such that the corresponding numbers were the same for A and B, that is to say, where A and B matched. After this, I greedily calculated mana required for each fragment.
To greedily calculate mana required there will be two case:
-> If the maximum element there in the fragment to be deleted is larger than the adjacent elements to that fragment then we must use x mana to delete the k elements in the fragment containing that maximum element also, for the remaining element in the fragment you can than greedily compute the cost. Note: In this case if size of fragment < k then there won't be any possible answer.
-> If the maximum element there in the fragment is smaller than either of the adjacent element then you can greedily compute the cost to delete all the elements in fragment(there won't be restriction like we had above)
I don't understand why my solution for D gives TLE on test 6.
86694208
Never mind, I got AC. It was a stupid variable placement.
Thanks for the contest anyway, I liked the problems.
Now, what about the tutorial? I see no reason to hold it back any longer.
The problemset was really good! kuddos to the problemsetters !!
How to solve Problem E?
I even don't understand the sample:
[[5,1],[2],[7,4,3],[6]] ---> [[2],[7,5,4,3,1],[6]][[5,1],[2],[7,4,3],[6]] ---> [[5],[2],[7,4,3,1],[6]] ---> [[5,4,3,1],[2],[7],[6]] ---> [[],[2],[7,5,4,3,1],[6]]3 steps is ok! why the answer is 5 ?Whenever two consecutive rings lay onto each other they never get separated again. And in the end, it must be one consecutive segment.
So ans is always the number of consecutive segments of rings, minus one.
When towers get merged, some of those segments get merged, too, ans decreases by that number of merges.
It was hard for me to understand that you can reorder the chests in G.
the problems were very nice.Specially problem E.In E i used dsu algorithm.But sad that contest is unrated.
the problems were very nice specially E.In E we can use dsu.But sad that contest is unrated
My video editorial for problem C . I have tried to explain my thought process and the algorithm . Hope you like it .
I have doubt of max and min function. Here is my code for A 86697535. I used one while loop with max function and it gives TLE. As I understand testcases loop is 10**2 while loop is of 10**3 and max function takes 10**3. And 10**8 is valid for 1sec, then why I got TLE. please help, Thank you
You see that such a triple is available at every local maxima, it is in your code.
So just iterate the array once checking every position it if is such a triple. If yes print it and break/return.
Hey spooky, I read your submission after getting WA on D still could not figure out where I am making a mistake. 1. I check if v2 is a subsequence of v1, if not then answer is not possible. 2. I am destroying all segments between the elements. If there is a segment where we have an element which is greater than the starting and ending point of that segment, at least once we should use Power X, else we can use cheaper of Power X or Y. If we are unable to use Power X (segment length is less than K) then answer is not possible. 3. I am destroying all segments from starting to first element in v2, and from ending to last element in v2. Here is a link to my submission: https://codeforces.net/contest/1380/submission/86702514 Any help is much appreciated as always!
Again, as soon as I made this comment I found out my mistake like the last time. Anyway, your solutions are very helpful! Thank you.
Note that p1 is out of bound here, but that seems not to be the reason for WA.
The other code is... well, complecated. Try to simplify. There are so much if and things, one cannot debug this.
Edit: Wrote this parallel to your comment, nevermind.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
On problem G, for the second sample case, can someone explain what configuration of mimic chests gives 7/8 as the expected value for having 6 mimics? I must be misunderstanding some part of the problem but I've read this several times now and I can't see how you can achieve a better EV than 8/8 for 6 chests (by making the chest 3 and either chest 5 or 8 real, and the rest mimic, giving us 1/8*(3+5)). I have a feeling that I could be misunderstanding, and perhaps the optimal strategy is to make chests 2 and 3 real, but from what I understand, this would give an EV of 1/8*((4+3)+3)=10/8.
I don't want to read the editorial or other people's code since I actually want to try solving the problem, but I've been bashing my head about this for quite a while.
EDIT: Oh, I now understand cookiedoth's comment above about reordering the chests. The order that they are given in the problem is NOT the order they have to appear in the circle. That's pretty confusing. I think what makes it particularly confusing is that you refer to rooms using i and then in the next sentence still refer to the chests using i, almost implying that they correspond to the same thing.
You can reorder chests. I also was having problems with understanding the sample tests. But after 20 minutes I finally understood it.
I am not being able to optimize my O(n^2) idea in E. Help?
My idea. For each query, the answer is the number of change of towers from 1 to n. In every query, we can just merge the two sets by iterating the set elements and find out answer by looking through the array.
if yo u merge small set to large set then solution is o(nlog(n))...proof
Wow, didn't know this technique before. Do have any other sources to learn this and practice problems.
you may go to this blog practise ..dsu on tree
Thanks.
Is D based on magic the gathering?
If so what inspired what berserk and fireball do as in the problem statement (they both do something quite different in mtg)?
No, initially there were Lightning Bolt (killing exactly one target) and Berserk (I don't know why Roms chose those spells, probably based on HoMM III). But that problem was considered to be too easy, so we changed the Lightning Bolt to kill several targets at the same moment and chose a random AoE spell to name it
Oh, that's cool.
I have an idea for a problem now that also uses a fireball and berserk spell, but that do something different xD
I am unable to find mistake in my code of div 2 problem D ( code )