Привет, Codeforces!
В 16.01.2022 17:35 (Московское время) состоится Educational Codeforces Round 121 (рейтинговый для Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
UPD: К сожалению, раунд будет нерейтинговый. Приносим свои извинения за причиненные неудобства. Вы можете дорешать задачи, используя архив Codeforces.
UPD: Разбор опубликован.
First educational round of 2022!
Wish everyone positive delta
2021? funny
Is it possible? Everyone can't have a +ve delta
He wished everyone who reads the comments)
Yes, technically nobody has +ve delta
Most probably everyone will have neither positive nor negative delta :XD
negative
Yes, because its unofficial now. LOL
yeah
first educational round of 2022 and first server down of 2022, looks like 2022 hiding some surprises lol
yeah lol
Aged like milk
everyone had positive (+0) delta :))
Your wish has been granted !
Wish all people who are going to participate in this round good luck!
I hope this will be the best education round in 2022. Wish everyone positive delta
Every educational round is the best,
i really hope this was not the best edu round of 2022
hehe
We always wait for the Educational Round.
feelsstrongman
"why edu round?"
Yes, but its unrated now, unfortunately :(
When I go to register for the contest, it doesn't say that I'm "out of the competition" like it usually does. Is this an error?
UPD: Apparently this is just how edu rounds are, I guess.
The number of problems invented by these guys is more than the number of problems i solved so far. Just wanna say thank you, you guys are genius.
Is rating below 2100 belongs to division 2? If so what is rating range for division 3?
1600
Hope To Be Pupil This Round
hopeforces comeback?
Why Codeforces is lagging when i switch to Wifi ??? Is happening with everyone ???
It happens sometimes,just try to refresh
Yeah but most of the time it hangs and remains hang only |(
first time participating in 2022,and in first educational round of 2022.
and first time power cut in 2022 :(
[deleted]
orz
emmm i'm jced
I wish every green coder becomes cyan
yes, a new contest, can't wait to lose rating again!!!
K0KUSEN, Ahmad_Alzerei Haha
you have to wait a little more for that!
Why haven't they listed the rating of problems ?
because it's edu round and it's in acm-icpc mode
Hope to become pupil.
Better luck next time buddy.
Does anyone else think Problem C statement is unnecessarily complicated?
yes i do think , especially for newbies and pupils like us
And for me too, after solving problem C for 30 mins I realised that I understood the question wrong lol
Is it unrated?
it should be
unrated...
Unrated?
unrated? (due to the breakdown of the website?)
Is it unrated? I hope it is as the site was down for a while.
I want my Delta back >:(
Is it rated?????
un rated？
Is it rated or not?
I wish it still rated :(.
For real
I couldn't submit my solution for C in the last 40 minutes, and I believe others are experiencing a similar situation. Please, unrate this round.
Yeah same situation. Make the round unrated, even temporary sites were not working.
same thing happened to me
I waited about 45 minutes to submit my E, and the site didn't reopen until after the contest ended. Does anyone know how long the site has been down?
yeah last 45 minutes site wasn't working
Can't agree more! Can't submit C (It could just drastically improve my RANK)
yeah, I couldn't submit D...
I haven't solved D so fast in a long time...
It makes me bad
I was not able to submit problem C on time as the website was down.
I was about to submit problem C and the website is down...
What the hell is the power company near Codeforces doing
How to solve E ???
очень печально, что за 3 минуты до конца, когда я засылал D, сайт упал :( не видать прироста рейтинга как своих ушей
он упал у всех на последние минут сорок (
ну я не заметил, увлеченно писал D-шку ладно, не обидно, всё равно WA3
pls dont get rated plssssssssssssssss
Just before I wanted to send a full solution to C, site crashed. If it is rated I am gonna be very very sad.
Same, got B and C, wanted to submit, boom unavailable. 45 min later, website up again
Make it unrated or bring new contest. This is bujdili.
I submitted problem C with two minutes left, but CodeForces was down. I was not able to submit. Did this happen to others?
Any ideas to solve E ???
Brute force
let 2 ^ a, 2 ^ b, 2 ^ c be the partitions
just check whether this partition is possible or not
then the answer:
2 ^ a + 2 ^ b + 2 ^ c — n
The solution I wrote and could not submit due to website being down does the following:
First dfs from any root and determine for each subtree the number of black nodes in that subtree -> now we can determine the number of black nodes of any subtree using any root.
Now we BFS starting from all black nodes going outwards. — If current node u has neighbour v such that v number of black nodes of the subtree v when root is u is bigger than the distance of v to any black tree. Then mark u.
Sorry for bad formatting :/
It should be unrated . Half of the time the server was down...
Obviously it will be unrated. Keep calm everyone.
Where are Codeforces servers hosted?
On clouds
doesn't look like.
I guess it's time to start using cloud like all progressive companies.
give us 30 more minutes
Better to make it unrated. Otherwise, those who have read/downloaded all the problems will have an advantage. (Also a problem for those who are not available anymore)
Due to electrical problems, the site is temporarily unavailable. We expect him to be back in minutes 5-30 minutes.This is there for last half an hour of the contest for me. Anyone else faced same issue?
Will this contest be unrated since the website crashed in the last hour for a lot of people?
guys the contest stopped in between:(
Is it rated or not?
same bro :(
LMAO this guy comment was:
"i wish it was rated :( ..."
but when he saw -13 votes he edit it to:
"is it rated or not?"
I don't get what is wrong for me to wish if it was rated.
As I was going to return to candidate master again and achieve new max rating.
I think it's normal for me to want more than +100 delta and after all it's just a wish it can't change any thing.
I don't get why I get down voted a lot.
and to correct something when I edited the comment it was just -2 not -13
I mean you knew that you are doing something wrong when you edited your comment so why u are asking again? Many people couldn't get +ve delta during the uptime and some of them could have reached +ve delta during the downtime so thats why its not fair for many participants, and btw my delta was 108 +ve but its better for it to be unrated :)
Unfortunately for the authors, the round didn't go smoothly but I enjoyed the problems. Thank you.
I did good. But it should be unrated (: almost 1 hour server probelm :3 Its huge ..
Unrated?
most probably yes
please let me submit!
undo this fuckshit!!
when i want to submit the new code,this contest is stop.So please unrated!
Downforces
.
same shit, my dear...
Will this round be Unrated?
yes it should be ;)
Please make it rated
why？
nope
It will be unrated?
CF everyday bomb.
People are so impatient. I mean, you need to give them some time to announce that it is unrated. Who knows, probably they cannot still access the site : P
edit: there you go
Kindly make this round unrated as the server went down for about 50 minutes. I had written the code for C but was unable to submit it due to the server issues. Many others might have faced similar problems.
I thought I would become CM then the atrocity happened. My disappointment is immeasurable and my day is ruined.
hope it will be unrated
i would become blue，almost
Didn't know electrical issues could screw up a contest. Well the round was supposed to be educational after all XD
Please keep rated...
Does the contest will be unrated due to technical failure?
People should stop down-voting the contest. It's not the fault of the authors, co-ordinators or testers that there was an electrical outage.
Unavailableforces
Probably going be to heavily downvoted but guys it might still be rated. Everyone got the same amount of time to submit their solutions. So effectively only the contest duration got reduced.
And it became unrated just as I commented. Maybe I jinxed it lol.
You said ... "it might still be rated" ...
I wasn't expecting it to be rated but I wouldn't have been surprised if it would have been because effectively only the contest duration was reduced. And I get a feel, I haven't understood your comment.
ig a lot of people want this round unrated because who performed good is a small percentage and that's why they got positive delta
I had 10 minutes left but suddenly the web crashed. When the problem was fixed, I intended to get back to submit my code but the contest is over:((
Half of the people wants it to be rated other half wants it to be unrated. Good Luck awoo
UPD — Round is unrated.
Maybe processing only +ve deltas is a good idea.
This is the best outcome we can have
Does the contest will be unrated now?
i cant submit in the archive, why?
Wait for the system test to end
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
finally NON-NEGATIVE delta in Educational Round.
In my opinion, it should be rated. The server failure has affected equally everybody, and the site has run enough time to be able to submit several problems. It would be a shame to have lost all the time spent. But it is up to Mike of course...
I quite agree, surely because I did well, for once.
This is not how it works. Think about those who solved a question but could not submit and those who could not solve it at all. If the round is rated then it would be unfair to those who could solve it. You can't say it's a shorter version of the round coz the duration announced before the start was 2 hours and that's the duration everyone expected but could not get. So it's fair to everyone that the round gets unrated.
(*￣3￣)╭
From where can I access codeforces archives?
First unrated contest of the year ! :|
It is officially unrated now.
First unrated educational round of 2022! :D
Peoples reaction when codeforces is unavailable during the contest
Why are people downvoting the blog? The authors can do nothing about codeforces's servers
since the contest is stuck at System Testing 100%, it is not completely over and we cant upsolve it in the archive :(
UPD: Now over
Wow! no one's lost any points this round.
Can we add another Educational round by end of Jan to make up this one ??
Why do unrated rounds always happen when I do well :sob:.
Unrated! Thanks UnavailableForces!
Anyway, I loved this round!
Me too. The problems are cool
Any idea how I can submit solutions for contest problems ? I get 'Contest is over' popup message :/
I don't know whether speaking this will affect my contribution to become negative because some people may disagree. But yeah, whatever.
I just wanna "rant". But if the round will be unrated, I will be very upset because after a while, I feel like my performance is quite great in this round. So it feels like making the round unrated is quite unfair (at least for some people did their best for the first 1+ hour (before the electricity went out))
Yes, if I'm at the bottom, probably I will feel different and frustrated.
But when I try to see this objectivically, making the round rated is a fair thing to do. Why? Because in the end, all participants has a fair condition : 1 hour contest (and the electricity go back up after the contest ends anyway)
Yes there's a way of thinking like : "if you're good, you will keep enjoying problem solving — whether the round is rated or not". Yes I do agree with that, but emotionally speaking, it feels like this hits me hard personally (and probably some people might feel the same)
Yeah so that's my point of view. Feel free if you guys want to disagree and downvote for this, but I stand with my thought. And hopefully in the future, there will be some acceptable solution to mitigate this issue
Good luck Codeforces team
This doesn't really make any sense. People choose to participate in the contest with the expectation that the rules/time constraints don't arbitrarily change during the contest. Do you really think someone who can eventually solve 5 problems should be ranked lower than someone who can only solve the first 3 quickly?
In 2 hours contest, I agree with your opinion. And I think this incident is quite an unfortunate event I believe
But I also believe that speed is also important for solving the first X problem quick. So in a way, I think given the equal circumstances to all participants (i.e. electricity went out until the end of the contest), should it still be a fair game?
Unless if in the middle of the contest the server went back up, I think it's another story and when that's the case it's reasonable to make the round unrated
Of course speed is important, that's why it's rewarded on the leaderboard. But in the cp community (in particular these educational rounds), there's a reason why the slowest solver of 4 problems is higher ranked than the fastest person who can only solve 3.
I have to disagree with you — while we all got the same time, changing the duration of the contest can affect people's strategy. Consider the classic example of "I can't wrap my head around problem C, I'll try D and then come back". You'd never do something like this near the end of the contest, but people would consider it when there's plenty of time left. So by suddenly truncating the contest you punish people that are trying harder problems when they really shouldn't be.
It's bad for a round to become unrated, but I think it's the only fair thing to do in this case
I think that extending the contest time is a better way of dealing with server failures. Making a contest unrated is very frustrating and discouraging for those who have performed well. There is a reason why it's called 'competitive' programming. I don't think people here are truly indifferent whether a contest is rated or not :)
Extending contest time is not always feasible. Many people only participate in a contest coz they were able to get free time in that duration. You gotta take care of all time zones.
Hmm I think it's not a best thing because some people might think the contest is unrated and quit before they realize there's an extension :')
1 hour contest is a fair condition, but only if you know the duration beforehand.
Suppose you have written a solution for a problem and you're not so sure that it's correct. It might be due to different reasons — this can be an unproven greedy, the code can just be complex and there might be some bugs in it, etc. Should you submit right away?
If there's a minute until the end of the contest, the correct decision is to go full YOLO, submit (maybe even without checking the samples!) and pray to whomever you worship that both your idea and your implementation of it is correct. But what if you have a considerable amount of time until the end of the contest? Then the better course of action is to wait with submitting the code (because you might get penalty) and test the solution, maybe even let the stress run for several minutes. When you know that you have time, being careful is better than just submitting the code outright.
So, in a situation like today's one (when you assume that it is only the middle of the contest, but in fact it's only a minute), you get punished for doing the correct thing (if you verify your code once again, hoping to submit in 5-10 minutes, you instead can't submit at all). That's why these conditions are unfair, and that's why we chose to make the round unrated.
I see. I think your argument is reasonable. Let's hope this unfortunate incident is minimized in the future :)
It was a terrible contest experience I have had before. Does this kind of problem usually happen during contest HERE?
I don't participate Codeforces contest so frequently, so I'm wondering if it is necessary to consider technical issues on platform.
No, it does not usually happen. Normally the contest experience is smooth except for some minutes at the start of the contest.
happens very rarely
Gotcha. So it seems that it was a rare accident. Unfortunate for authors :(
your profile picture is your reaction
Why did they make it unrated?
cause it's not fair for many contestants, maybe not you, but still worth going unrated
The contest only lasted an hour and twenty minutes when it should have lasted two hours. Even if I don't really agree with this decision, it is clear that it completely changes the competition, and that it may seem reasonable to cancel.
editorial?
haha that actually happened with me XD
Solved 4 problems but unrated.ಥ_ಥ
you should still be proud of yourself
Are there are some thoughts about how to clever implement 1626D - Martial Arts Tournament?
I had for like one hour a more or less clear idea on how it should work (iterate possible group sizes, binary search possible number of partitipants), but was not able to write the code. I tried using lower_bound() for binary search, but did not get it right somehow. What here is the trick to get it right in time?
I bruteforce the size of the small and medium group and check how many people I need to add to form a group with those sizes
After the formation let the Light , Middle and Heavy Section have 2^i , 2^k and 2^j members respectively . Let's form two arrays pref and suff ,
pref[z] number of persons with weight<=z and suff[z] number of persons with weight>=zSo our answer would be 2^i + 2^j + 2^k — n so if we fix i and j to minimize the answer k should be minimized so we should find maximum x such that pref[x-1]<=2^i , minimum y such that suff[y]<= 2^j. We can brute force over all pairs (i,j) and get the result .2^k >= (n-pref[x-1]-suff[y]) thus to minimize k , pref[x-1]+suff[y] should be maximizedWell, it is super obvious how error prone that is. And what you discribe by "get the result" is an additional binary search on the prefix array(s).
The question is, how to make it more clear. Actually I am not able to simply write it down, it is to complecated. I need some kind of abstraction layer or whatever.
I just said what I wrote in my already accepted code . The last statement in my comment is the reason behind why I chose for every i and j max x such that pref[x-1] <= 2^i and minimum y such that suff[y] <= 2^j
Related blog
Was problem C easier than usual? Anyway, good problems.
Yeah i too feel This time C was relatively Easy. Even they allowed N^3 to get passed.
It can be done in O(n) also.
No, we need to sort the monsters by time, that makes it O(nlogn)
Already Sorted
It's sorted. I could come up with TC:O(n), SC:O(1)-- 143027532
Mine is exactly like yours. Damn yeah it not N3.
for problem D, I have a O((log(A))^2 * log(n) + n) solution, is it wrong? submission
problem E was super nice. After a long time, an Edu problem E actually required some thinking. A shame that this was unrated...
I uploaded a screencast solving all problems here: https://youtu.be/XBqrXvMy3Is
I had a pretty clean solution to 1626E - Black and White Tree without any casework, so I'll outline it here.
Hence, we construct the reverse graph of "easily reachable" and multi-source BFS from the black nodes & their neighbors, and we're done!
(The intuition behind "easily reachable" is that we can take a step along this edge regardless of other moves, since we have 2+ black nodes to choose from.)
Full code (including IO/templates) is at 143016277, but the key part is below.
Thank you, this is a brilliant solution, and very well explained!
Thanks! :)
Hmm what do you mean by "reverse graph of easily reachable" ?
Reverse in the sense that in step 1, we would consider the "easily reachable" edge to go from $$$v$$$ to $$$u$$$, but during the BFS we consider it as $$$u$$$ to $$$v$$$ since we are starting from the black nodes.
Exactly, thanks!
Wow that's cool. Thanks
Can someone explains the dp solution for C.
I used greedy
Greedy solution is already O(n)
Can someone explains the dp solution for C. I used ghreedy
Any approach for C ?
merge overlapping intervals
That's really sad that the round was unrated. It's one of the edu rounds that I enjoyed the most
ABCD were all interesting and fun to solve!
For problem C, does a spell stop once it hits a monster, or does it keep going? Edit: nvm, my question was stupid.
Really like the problems in this contest, the problem description is short.
Can someone please help me find the error in my code for problem C. I used a greedy approach of traversing the list in reverse order. Here is my submission
Found and fixed the error
I am sorry for your loss. This Round is, absolutely, good(at least for me).
Looking forward to your future contests!
I figured the idea for the solution of problem F quite quickly after opening it.
Let $$$C := \text{lcm} (1, 2, ..., k-1)$$$. For each value $$$r = a_i \text{ mod } C$$$ there exists an affine function $$$f_r(x) = ax + b$$$ such that the contribution of a value $$$a_i$$$ to the expected value is $$$f_r(a_i)$$$.
These affine functions can be precomputed using DP (hint: compute the operations in reverse order) in $$$O(Ck)$$$ time, where the maximum value of $$$C$$$ is $$$\text{lcm} (1, 2, ..., 16) = 720720$$$.
Problem C what should be the output
45
you are casting 2 spells at 3, which is not allowed. Hence you are forced to cast spells (x + 1) at every second from 2 to 10
is there gonna be an editorial?
https://mirror.codeforces.com/blog/entry/99136
Will the tutorial be available or not?
Can anyone tell what is wrong in my solution 143108028 for problem D where a is size of lightweight, b is size of middleweight and c is size of heavyweight
include <bits/stdc++.h>
using namespace std;
define int long long
// int dp[1000001];
int fun(int a){
}
void solve(){
}
signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; // t=1; while(t--)solve(); }
The only wrong part I could think of is in your code for a you're finding the smallest length bigger than 1<<j while you should be finding the biggest length smaller than 1<<j.
Think of it as such.
In problem it is given that the final partition would be of form $$$2^i$$$ so it would be more sensible to take the maximum number of elements in that partition from the array. So we can say that we take some $$$2^i-k$$$ from array. So we should minimize k right ?
But what you did was, you considered that the number of elements from the array in final partition will be of form $$$2^i+k$$$ and you minimized k. See in that case you would have to add $$$2^i-k$$$ elements to the array. Now minimizing k will actually maximize the answer for a particular i.
Thanks, got it
I am not able to find where am I getting wrong in problem C. Anybody pls help. My submission 143125218 https://mirror.codeforces.com/contest/1626/submission/143125218
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
It's so sad that this round got unrated and i didn't become purple. But i love these carefully-prepared problems :)
It's a shame the round didn't go well, yet I'm glad to have participated.
The problems were all creative and unique, I enjoyed every one of them and loved the round.