Halo, Codeforces! Ape kabar kitak? Nyi deu sit bau maang? 😍 😍
COMPFEST 16 is happy to invite you to participate in Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round) on Oct/06/2024 09:05 (Moscow time). The round will be rated. You will be given 2 hours to solve 5 problems, 2 of them will have subtasks.
Note the unusual time of the round.
The problems are written by ArvinCiu, CyberSleeper, athin, and joelgun14.
We would like to thank:
- KAN for helping to host the round;
- errorgorn for the based coordination;
- gansixeneh, CyberSleeper, joelgun14, and icebear30 for helping with the problem preparation;
- gansixeneh again for the sigma helps;
- Alexdat2000 for writing the Russian translations;
- A_G, Dominater069, efishel, Error_Yuan, fishy15, Sk0rlupka, Umi and valeriu for testing the contest and providing us very useful feedback;
- Universitas Indonesia, all the local committees, administrators, and managers of the whole COMPFEST event;
- MikeMirzayanov for the amazing Codeforces and Polygon platform!
COMPFEST itself is an annual event hosted by Universitas Indonesia. It is the largest student-run IT event in Indonesia and competitive programming contest is one of the competitions hosted.
We hope you will enjoy and have fun in the contest. Muga-muga beja lan isa entuk biji apik!! 💪💪🔥🔥
Edit 1: Score distribution is $$$500 - 750 - (750+1000) - 2500 - (1750 + 750 + 1000)$$$
Edit 2:
Congratulations to the winners!
Div.2 :
Div.1 + Div.2:
Congratulations also to the first solvers!
A: _MASSIMO_
C1: ksun48
C2: 2mato_pota2
D: ecnerwala
E1: vlt0824
E2: nifeshe
E3: xuanxuan001
On behalf of the COMPFEST committees, we are glad that our Codeforces Round ran quite smoothly and we hope that you all enjoyed our problems. See you next year! 😍 😍
Edit 3: The editorial is up!
Pyqe will win COMPFEST 16!
Pyqe will win COMPFEST 16!
Pyqe will win COMPFEST 16!
Pyqe will win COMPFEST 16!
who won?
Kinon will win COMPFEST 16!
Pyqe will win COMPFEST 16!
Pyqe will win COMPFEST 16!
Pyqe will win COMPFEST 16!
Pyqe will win COMPFEST 16!
Pyqe will win COMPFEST 16!
Here comes The Pyqe
who?
Pyqe will win COMPFEST 16!
Congratulations to Pyqe as the on-site champion! Also congratulations to Zanite as the 1st runner-up!
Please highlight the unusual starting time
Tomorrow:
weirdest one ever
school at 4:30?
China is very big country, but they use only one timeline. So if they live far from beijing, their time goes weird.
It's a boarding school, so we have to go back on Sunday afternoon
You don't have National Day Holiday?(In fact,I already went to school yesterday afternoon.I'm in the computer lab now.)
As far as I know,the holiday in high school is always shorter than usual.
We senior high school students hardly have time to relax on holidays.
based sleeping schedule
Could you tell where to participate in Hacker Cup?
Register Here, check the faq page for more info
Never seen such a good contest time and duration for Chinese!
Never seen such a good contest time and duration for Chinese!
I wasn't so excited by contest. Thanks to everyone who had contributed in this contest
As a participant, I registered.
As a Participant, I am also registered;
Looking forward to the contest :DDD. Thank you everyone, especially errorgorn and ArvinCiu for the sigma helps!
Halo Codeforces! Muga muga kowe kabeh sehat.
Maturnuwun karo KAN, errorgorn, ArvinCiu lan juru susun acara liyane uwis isa ngadano mirror COMPFEST nang Codeforces. Muga muga kowe kabeh seneng karo soale, Muga muga kowe kabeh bedja, enthuk biji sing apik, lan aja lali seneng-seneng ngelakoni ujiane.
Hi Codeforces! Hope you're all doing well.
Thank you to KAN, errorgorn, ArvinCiu, and all the other people involved in making this round possible. Hope you all enjoy the problems, GLHF!
can someone please translate this one?
It's in the spoilers mate.
lol for a second I thought that it was a real language, but, upon closer inspection, it is clearly just a bunch of gibberish. You got me.
It's Javanese...
IT'S JAVANESE :V
it's the real java language :D
krama alus
aku wong suroboyo ora ngerti krama alus
I just learned some javanese. Muga muga means hope.
That's right!
I am unable to attend this contest just because of the start time. Many Bangladeshi students won't be able to attend in the contest
class miss diya den
School e exam ache vai
Damn... Kun class e poro, ar kun school?
School chinben na. But Class 9
Same! But, half diya aisha contest korbo.
What is the score distribution?
Never seen such a bad contest time and duration for Bangladeshi!
Never seen such a good contest time and duration for Chinese!
An odd times may change anyone's rating oddly.
Good contest time for me.Normal contest time is "unfriendly" for boarding high school students.
Wow
Good
Looking forward to it.It is a CF Round which I have a time to register(which hardly ever happen).
Hope to reach Cyan if i managed to participate in this contest....
The time of the contest is so wonderful for Chinese!
Nice time for Chinese!
Hello (Codeforces) 2021 :)
Cristiano Ronaldo nan paliang rancak.
good
Hope the unusual time make more people can't register, so that I can get higher rating. Hope ususual time rounds can be more and more.
Bruh moment if you think less people means it's easier to get higher rating (News flash: It does not).
But the unusual time makes more Chinese people register (Maybe).
hopefully this contest will be the start of a great journey ahead
when the contest will start tomorrow and how to join the contest?
Score distribution?
Score distribution?
plz no mistakes LIKE last time...
Hoping for a great contest, especially with the 1am start time! Also please release the scoring distribution for the problems.
What about the score distribution?
GL & HF, and upvote for the time of the round :)
This is stupid, why can I only comment once in ten minutes
where is score distribution?
scoring distribution when?
score dist ??
Finally the score distribution is out!
AHHHHHHHHHH, continue getting TTTTtle... (4 times)
6 times now :(
7 times...
Is it just me or A is actually harder than B/C1 without the score distribution presented?
The real order was C1 < B < A
i solved A,B in the first 16 mins. and coudn't solve C1 :(
you did better than me in first 15 minutes cheer up !!!!. It took me 12 minutes to just wrap A.
I just made some predictions and... BOOM.
Pretty much dislike guessing for a problem like this, it could have been a nice 1000-1125 point problem instead.
agreed, A >>>>> C1 >> B. imo
C1 seemed too easy for a C, B atleast had some implementation.(just my opinion)
B is actually the easiest to implement imo, 10 lines and done.
Oh then I messed up lol
This comment gave me a heart attack!
emm... why do I think A is easy (solved in ~16 minutes) and B is VERY hard (spend ~1h 40 min to figure out why it continues getting TLE)
(and didn't take any look to C2)
Felt the same thing
+1
ya i actually find a and b much more harder than c1
Why E3 only worth 1000 point? Isn't E1 and E2 just knapsack? Why 2500 point on them
E1 could be enough for Floyd Warshall to pass. By the way, I'm surprised to hear that this is some kind of Knapsack problem.
E2 => Knapsack
E3 => Use Minkowski to optimize that knapsack
What the hell is minkowski?
I solved A with just a hunch using priority queue, can anyone provide proof for the solution?
If you do it in non-sorted order then basically, you would be making the average smaller, like if the average is non-intger then it gets rounded off. Now this rounded off number would be used for calculating the mean again and again, this way you would be affecting the largest number possible hence reducing the average by at minimum by 1. On the other hand if you via sorted order the maximum is never affected
D looked simple but was legit confusing once I tried solving it lol. Even E looked interesting. Welp :")
E1 is brutefurce. ( considering pretests passing for me ) .
Couldn't try E :")
understood the issue. :)
My Disappointment Is Immeasurable and My Day Is Ruined! gg
Is it just me, or someone else also felt like E1 is much much easier than C2 ?
( hopefully I won't get FST , my comment is based on the pretests results. May be I might be missing something which is not covered in pretest) .
Probably... In fact coming up with idea in C1 is harder than C2 imo.
really?? Imo A is harder than C1, but I found C2 much harder than both.
Problem A, I just had some senses that if I prioritize to take those smallest numbers to do the operation, then the answer will be maximum because the larger numbers won't be halved too early. Well, you're right. Actually it's hard to prove A that way so not everyone could do it smoothly.
I also thought same as you can't prove the solution of A though but I think its greedy to always just chose smaller elements and that way it will be maximum
Speedrun.
E1 << D.
I guess it was kinda obvious from score distribution
So it is useful to see the score distribution. (For most contests)
Obviously, yes
How did C2, I got the intution that we need to find inversion_count on each update but was not able to code further don't know how to find it , plz help .
The sufficient condition for the order to be valid is, if you denote min_pos[i] be the minimum position the $$$i^{th}$$$ person in this order, then you need to have min_pos[a[i]] < min_pos[a[i + 1]] for all $$$1 \leq i \leq n - 1$$$. So what we can do here is maintain the number of position $$$i$$$ such that min_pos[a[i]] < min_pos[a[i + 1]]. If this number equals to $$$n - 1$$$, then the answer the Yes, or No otherwise. Submission: 284562164
Thanks, this was the first intution before i got to inversion count , Weep :)
im so tilted, i came up with this with like 1 hour and 15 minutes left, and i just couldnt debug in time. thank you for the explanation
Omg bro, you're so good, it's really unfortunate that you couldn't solve the problem
Why so mad?
sorted <=> no of inversions = 0 (neccessary and sufficient) , here because of permutation , we need lesser than inversions
an alternative for so much if statements: 284600395
What was the approach for C1 kept staring at it thought it as easy question and made two wrong submission then realized it's not my cup of tea. Can anyone please explain me what was the trick in the question and also share your approach. Thanks in advance.
The condition for the array to be good is that for every $$$a_i$$$'s first appearance in $$$b$$$, all elements that come before it in $$$a$$$ have appeared in $$$b$$$ before it.
see My solution I did the same but why it didn't worked
you should not break before taking all input
Silly me
Basically first process all b in sequence which are unique wrt previous one, now basically you wanna check if it's elements are present in a in that order. But when there is a mismatch, this can only be fixed if that element which is now present in b has been processed sometime ago, so keep a set to keep track of all the unique elements that have been processed, if its there in set then we can rearrange it and make it feasible.
Build an array C which only keeps first appearances, for example if b= 1 1 1 2 3 2 1, then C = 1 2 3. Then the answer is YA iff C is a prefix of the array a. After the first appearance of a student you can move him as you whish, so it only matter to compare first time of each one.
Just check, In what sequence members are appearing, and then check whether the members who should present each section are appearing in same order? example : 3->4->1->2 are members who will be presenting slides then, 3->3->4->1->4->3->2 is valid whereas 3->1->4->3->2 is invalid (since 1 is appearing before 4)
For an array $$$b$$$ to be valid, for all $$$1 \leq j \leq m$$$, the index of $$$b[j]$$$ in $$$a$$$ must be lower or equal to the number of distinct elements in $$$b[1:j]$$$.
I thought of if initial b order is same as a then yes else no
Good contest overall. Love how it requires coding knowledge to solve problems, rather than relying on obscure mathematical concepts.
It seems difficult to make up for the remaining questions.
sortforces
Can someone explain why this submission to B fails?284540617
Is the frec array cleared correctly?
You modify $$$freq[i]$$$ for values of $$$i$$$ that are not in $$$a$$$, but only reset if for values in $$$a$$$.
This input fails :
2
3 1
0 0 2
2 10
0 2
You should rather define
vector<int> freq(n+1)in thewhileloop, this way you won't have to think of reseting your array.Thank you! For some reason even after realizing only the first n values mattered I still made a global freq array. I did eventually solve it, but I didn't figure out what the mistake with this submission was.
Can anyone tell me why I got wrong answer in this code ??
Is there any edge case I was missing ??
https://codeforces.me/contest/2021/submission/284596509
Good round, thanks.
Good round!!!
Thanks!!!
any sqrt decomp solution for C2 ?
My solution used hashes. I noticed that if we leave only first occurence of each number in $$$b$$$, it must a prefix of $$$a$$$, that is both necessary and sufficient. I wanted to be able to calculate the hash of this transformation of $$$b$$$. It can be done with segment tree
284558525 code
nice approach
Can you check my blog about this same solution? https://codeforces.me/blog/entry/134809
Beautiful solution bro, I was able to boil down the problem but wasn't able to implement it.
Done the same thing with hashing and seg tree
I was trying to understand your code and had a few questions, in the initializer list for the parametrized constructor of the struct
node, you have passed one argument to h, i.e.h(x). Looking at the constructor of thehintstructure, this would mean that onlyh1is set toxandh2andh3are still 0 right. But when you create theprefarray, I believe all ofh1,h2andh3are being set. Am I getting something wrong here?Either c++ magic or I was actually using only one hash lol. I copied this structure from one of my previous codes and didn't give it much thought
Right, I checked locally, you're using only one hash. I really liked your idea btw, I was thinking of coming up with a hashing solution initially but I couldn't figure out how do I handle the zeros. Your idea of treating zeros as a length 0 object so that it doesn't contribute to the hash is really interesting.
Too tight memory limit for E2. Maybe 512MB or more would be better?
You need only one $$$n \times n$$$ array and some $$$n$$$ arrays, what's the need?
I built a Kruskal reconstruction tree which has $$$2n-1$$$ vertices, so I need one $$$2n\times n$$$ array which is too large for the memory limit.
Instead of making dp on subtrees you can merge dps of two components when Kruskal merges them
it was my first contest just happy to give :')
Thank you for this round! So far my only rating loss was on COMPFEST 15, but today I got my revenge and became CM on COMPFEST 16!
I submitted by mistake the solution for C2 in C1 and it got accepted for C1 obviously, but the previous submission for C1 (which also passed all the test cases) was skipped and as a result my ranking declined and also my rating (seddddddd) please make the first submission for C1 only count...... ArvinCiu
284567403 got skipped and 284580672 got accepted. I want 284567403 this to be accepted instead as it was submitted well before in time than 284580672.
Thank you in advance.
It is the contest rule that only the final submission counts and resub gets -50
I didn't know it. So made the mistake. Please do some abracadabra
This round A is the same of Luogu Simulation Game
Picture:
link to the problem in luogu site?
It belonged to a source.So we can't share the full PDF with you.
The source's link: The fall camp
i see thanks
I finally became an expert this round!
What's wrong with my idea in B ? My idea is to increase the frequency of $$$a[i] + x$$$ whenever the frequency of $$$a[i]$$$ is greater than 1, keep the frequency of $$$a[i]$$$ at 1, and then calculate the MEX.
WA Link: 284609466
Consider
0 0 0 0Thanks, I should've read the task more clearly on "after every operation we can increment any $$$a_i$$$ by $$$x$$$. I misread as we should only able to change the original $$$a_i$$$ s. Just iterating up to $$$n$$$ would be suffice rather than iterating on
freq.keys()consider freq map has values [1,2] and [2,1] and x=1
so nfreq will be same as [1,2] and [2,1] now when you are looping in freq , when 1 comes , it will inc the count of 2 in nfreq , but in freq, the count of 2 will remain same as it was previous.....so you just need to change freq to nfreq in that loop
I became a specialist in this round.
congratulations
Hello guys.When will the solution be released? I think I need to add some ideas for learning how to solve problems.
Hi Mike, I would like to know why you have banned so many Chinese coders, I think you have mistakenly banned some of them in the same server room, and some of them have had their numbers banned but others have not, is this a mistake on your part?
They all used secondary accounts to participate in today's round. Such behavior is unacceptable and violates the rules. I think this could be a good lesson. I spent the entire two hours of the round investigating and analyzing the situation because of these "jokers".
So they got their solutions skipped or did you just remove them from official standings?
But you only banned a few people, there are still a lot of people who weren't banned, isn't that a mistake on your part?
No, it isn't Mike's fault. It's the owner of those accounts to blame. Also, don't make these meaningless accusations, especially when you don't have any contribution to the community. If you think there are other accounts that should be banned, you could tell Mike kindly.
For those who can neither speak English nor show their courtesy in their comments, I feel sorry for their country for having such a group of low-quality coders. (FYI: This is not for ChatgptMini, it's to the commenter of the abusive words in Chinese which got removed afterward)
You can not show your courtesy,too.
Yes, and yet it has nothing to do with what I said.
Why don't you think about why you've got 16 down? Think about what you're saying.
They criticised Chinese alters and got downvoted, wow. Seriously, why do Chinese give alters a pass? I'm also a Chinese and I don't condone such behaviour.
Firstly, I don't think it's embarrassing to not know English. Secondly, when you do not have enough community contribution, you should not use community contribution to evaluate this matter.
Firstly, I don't think it's embarrassing for not knowing English, either. But I think it's improper to use Chinese to post comments (especially abusive ones) when the only allowed languages are English and Russian.
Secondly, I don't see there's a connection between my own contribution and the matter I'm talking about.
What I mean is, you shouldn't differentiate people based on community contributions. Moreover, I believe that Mike's behavior also contains certain errors, and the punishment for opening a small account should not be imposed on a large account, which is extremely unreasonable.
What I wanted to say is if he thought there are some accounts Mike forgot to block/unblock, he could tell Mike. I believe this is the better way to contribute to the community instead of blaming Mike. Sorry if I caused any confusion.
Are you supposing that the owners of your alts are not you? The one to be punished is you instead of your account, although the sudden ban without any warning is somehow annoying and unreasonable.
But the punishment should correspond to the behavior, not the owner of the account. The act of registering a small account has nothing to do with a large account.
There is some stupid mass attack from Chinese users. All comments opposing their cheating are getting downvoted. Maybe they should try following the rules next time.
That's not true. We're not cheating.
Chinese are not cheating but you're not Chinese……
Fox dung to that. Do you really believe your community, whatever it is,have no cheaters? Think of that before you speak
The cheaters cheated. Not the mass Chinese users.
We are not cheating!Most of Chinese users are really strong.The cheaters cheated.Just like rapists rape women.But not all Indians rape women.
This blog were deleted...
I think you are the biggest joker.
No, it isn't Mike's fault. It's Mike's and your fault.
Will these people's accounts be unblocked after a period of time?
If you don't have an idea how to reconcile with the remote judge of Luogu or to solve the cloudflare and DDOS problems of codeforces, then you don't have an idea how to go home.
MikeMirzayanov
Healthy humans are supposed to break out of the solar system.
The goal should be clear.
You can go home if you have no idea.
Agreeing with the rules, but I would like to see if random people with multiple accounts are investigated, analyzed and banned, but not only the tops of the rank list. Otherwise, it is still unfair and amusing. Let alone if the rule is set reasonably.
Thanks to Mike, we now have a great CP site with bad connection (for all the users) but more importantly, good discipline (for some of the alt users)! Which is the most important is obvious for everyone! sto MikeMirzayanov orz
Lets cheer, for today is the day Mike spent 2h dedicated on such meaningful work!
why use alt got banned but cheaters just got skipped?
true dude
Then you shouldn't ban large accounts either, as it will make the efforts of many users in vain.
Man, what can I say?
74traktor and mike out!
Maybe remove them from the rating is better. Disabling them is an insulting action.
the observation on alts in div2
I agree with the rule, but I want to see more proof of it.
I think some people have been wronged.
Hey! Why giving mike downvotes? Has he done anything wrong? Let's upvote!
Whether we downvote or upvote is decided by the content of the text, not by the sender.
⛵
no fishing.
i agree with the rule, but i think you maybe wrongly banned some of them because in China there are few IPs and many people are using the same IP to surf the Internet.
to MikeMirzayanov
Could you please show the method to tell whether the accounts are of the same person?
That is to say, you should also ban orzdevinwang because he used zh0ukangyang account before. MikeMirzayanov
MikeMirzayanov
麦克 蜜耳炸压懦夫
You are joker.
你是小丑。
qijianci said.
萎哥说。
Your biggest mistake is to ban wo_shi_wei_ge during the game!
你最大的错误就是在赛时封禁了”我是萎哥“！
You will regret it for the rest of your life!
你会后悔一辈子的！
Rev. 22？
Always update.
Laugh track analysis: laugh track analysis deleted
Hey Mike, it's obvious that Limie and zxwlimie is owned by the same person. Could you please ban one of them?
May eimil and Limie is owned by the same person?
Yeah some people have violated the rules.But they are not "jokers" at all.
About the impolite comments the other people said,I feel sorry and ashamed.
In China, if someone cheating in competitions, there will be a ban about only accounts which participate in cheating. It can be fifty or more people who using the same IP, so you should not punish by banning IP addresses, as this may affect many innocent people Others are not obligated to take responsibility for cheating, even if their IP addresses are the same
Why Why Why,Why Why Why，Why is the punishment for people with trumpets worse than people who cheat, do you have any ideas, if you don't you can just go home
Don't think you're an administrator you can just slander people, don't talk shit about people because you can't do it. You have no evidence! !!! codeforces, that is the administrator enjoys the highest power, you think I am copying, you brown it, you can even block my number. But the eyes of the masses are bright ！！！！
If you block me, it will let the oiers of the whole world know that codeforces admins are rotten!!!! codeforces will be infamous!
Unknown_Error lol
Your recent complaint has been reviewed and found to be clearly unjustified. Submitting such complaints violates the Codeforces rules—this is clearly stated right in the complaint submission form. As a punishment, you are barred from submitting complaints for 7 days. Repeat violations will lead to more severe measures, up to and including the blocking of your account. Please do not submit any more unjustified complaints.
How do you know? If a lot of classmates participate in their school's special computer room, they would have the same IP.
Can somebody please explain the solution of E1?
You can use Floyd- Warshall to create a distance matrix of the maximum of all edges used to reach that node and then greedily pick the server that gives the lowest sum across all houses that need internet because constant is small.
But how do you pick 2 optimal servers, then 3 optimal servers efficiently?
Run 3 nested loops : one for each additional server, then on all nodes, then for houses that need internet. You also need a visited array for servers chosen already.
Why is it true that if we pick a server for k, it will be choosen for a bigger k?
Greedily, it always makes sense to select one of the p nodes as the server ... Hence, when a node is chosen for k it remains.
Seems to me that it doesn't work that easily, guys. Sometimes it's hard to prove greediness, and I didn't see proof in your answers. Maybe, I'm missing something so answer, plz, to the following question.
For example, if we install server in vertex 3 for k=1, then why it's not possible for k=2 to have set of vertices (1, 2) as an optimal solution with latency less than (3, 1) or (3, 2) or any other (3, *)?
It's easy to prove that it's always optimal to choose one of the p nodes (if we have solution with server in node v which is not in one of the p nodes, we can choose node w which is p node and minimalizes maximum on the path from v to w, then move server from node v to node w and we have solution equal or better), but i don't know why do nodes remain when they're choosen
Exactly.
Can anyone help me with problem a , I wasted a lot time but couldn't come up with some with good logic
my idea was that the last element will be max, if the previous two elements that make it are max. so how would you pair so that this happens?
1.pairing anything with the max element only decreases the max element. so not advisable. 2. pair min with min? yes! it increases the overall min of the array without hurting the max.
so, sort the array and pair min with min.
284608545
I used priority queue (min heap) & kept taking floored average of 2 smallest nos., popping those 2 from the queue, & pushing back the floored average, until just a single number was left in the queue. You can view my solution.
As an official contestant, I just wanna say that "Boss, Thirsty" and "Digital Village" are very cool problems! Congrats to the problemsetters!
Can you tell the solution for Boss, thirsty?
Can anybody help me find what's wrong with my solution for B ? 284594624
Try
> 1instead of> 0Unfortunately it didn't work,
repstores the number of repetitions in my case not the number of instances.okay so after a lot of headache i figured it out.
the problem with my code was that it basically was only checking for "gaps" between numbers within the array. but it didn't try to fill the gaps after the largest array element.
adding a while loop that tries to complete the array after the largest element using the same idea in the previous loop seemed to work.
When will the editorial come out? I would like to see the solution for problem D and E3.
Tutorial when? QwQ
QwQ
Joker, don't use another account to comment on yourself!!
Anybody else missed the round?
How C2?
3 2 1 4 — array a
1 3 3 2 1 2 4 1 4 — array b
so positions in sorted order in array b for each integer :
3 : 2 3
2 : 4 6
1 : 1 5 8
4 : 7 9
If and only if bold letters are sorted from top to bottom then YA otherwise TIDAK
Try to think from here
I had this exact idea and 40 min left in the contest. But couldn't figure out at all how to check if they are sorted or not in O(logn). Any hints or ideas?
segment tree? I could not think other solution.
no heavy data structure is required
after each update only two bold letter's values get changed , so it's sufficient to only check those two bold letters and the ones immediately after that total 4 , keep a $$$track[i]$$$ which says whether bold letter in $$$i$$$ > bold letter in $$$i - 1$$$ and also keep count of no of $$$track[i]=1$$$ on the flow
You can use a heap to store the slides for each member. After any change, it's easy to pick the new earliest slide the user needs to present(it's just the top of the heap). This can be used to maintain an array of first slide, each member in the queue needs to present. If that array is sorted, the slides are presentable. We can keep track of number of indices where
a[i+1] < a[i]after each query, for a sorted array, this would ofc be zero.Code(Python), fairly readable - https://codeforces.me/contest/2021/submission/284731038
I sort of understand the solution of B. But I keep getting TLE and I don't know how to optimize it. Can someone help me look at my code? It is 284575211. It should be pretty readable and it is basically brute force. Thanks a lot!
Switch unordered set to a vector with size n and it should work.
Thank you for the suggestion. I have tried to implement it with vector using the same idea and it did pass a few more test case. But still got TLE at testcase 9 284649489. I would appreciate any more suggestions.
Edit: Actually I changed a few long long int to int and it passed but barely rt: 0.9(s). Is there a better way of tackling this problem?
try inputting all numbers before actually doing any operations, it should be much faster that way
Thanks it worked!! Is there an explaintion for that? Or should I just avoid doing operations while inputting?
this way youre iterating n times exactly, so it cant TLE, in your previous approach for some inputs, you sometimes iterate over numbers redundantly,which leads to tle
In your solution, the value is pushed forward until it becomes unique.
Then consider the following test.
1
200000 1
99999 99998 99997 ... 0 0 0 ... 0
In this case, there will be no pushing until the first zero appears, but the remaining $$$10^5$$$ zeros will pass through all values greater than 0, which are also $$$10^5$$$ at the very beginning.
Thus, at least $$$10^{10}$$$ operations will be performed in total, which is why TLE occurs, and the asymptotics of this solution is $$$O(n^2)$$$
Thank you I understand. How should I optimize the solution? Basically how would I skip those numbers for a faster run time?
Edit: I have a new solution that passed but the runtime wasn't great. Maybe there is a better way of dealing with this problem? 284650265
I wrote my own editorial for this problem in this comment, the asymptotics of the solution is O(n)
Why still no editorial
getting wrong ans on test case 2(C1) please point out the error in my code 284584744
someone explain B
Let A be the initial array. Note that the maximum MEX cannot be greater than n, since there are n total elements in the array. Let the array C contain the number of elements with the value Y in the array C[Y] = k, where Y is the value of the element, k is the number of Y in A (Since MEX is not greater than n, then it makes no sense to store Y > n values in C).
Initially, we will go through the array A and for each of its elements $$$Z < n$$$ we will make C[Z] += 1.
Now let's see which element we can't get in A. Let it be the element $$$el$$$
Initially, $$$el = 0$$$. Next, we will use the following algorithm.
If $$$el \ge x$$$ and $$$C[el - x] > 0$$$, then C[el] += C[el-x]-1. If we have several identical values, then it is optimal to change all but one, because MEX will not became lower from this. Using the C array, we push the elements further, leaving only unique values behind.
If $$$C[el] > 0$$$, then el += 1, otherwise we will not be able to get the value of $$$el$$$ in the array A, which means the maximum MEX will be equal to $$$el$$$
The asymptotics of such a solution is O(n)
Edit: Code of this solution — 284652327
I understand now thank you. I am supposed to move all duplicates at once instead of one by one.
Just woke up from my long slumber(my brain crashed while giving my worse possible Hacker cup, so I had to) and was looking for the Codeforces contest, and realizing only now, I have already missed it
anyone solved C2 with merge tree ?
nvm
Can somebody help me with my code for B? Why does it fail. Cannot seem to find any counter test case on my own — Link to code
Thanks for pointing the test case my code gives 4. It should have been 5. Can you please guide what am I missing.
You don't consider case when after moving elements there is number x that wasn't in the initial array and freq[x] > 1. You should move this element too, in your loop you only check elements that were in initial array.
Hey Thanks. Got the problem solved it by replacing vec[i] with just i. After your explanation.
We are still waiting for the Editorial :(
upvoted
Mike,please tell me,why do cheaters only get skipped while using multi accounts is getting banned?(plz forgive my poor English.)
Ask yourself,
1) How many Voter cards you have ?
2) How many LinkedIn Profile you have ?
3) How many Students Profile you have at your college / school ?
Now, one may argue, codeforces is neither voting platform, nor hiring platform or may be school. But, this is some other platform, we want to keep fairness. We want to keep single identity for one person.
4) What do we achieve by keeping one account ?
TRANSPARANCY and FAIRNESS.
So many of the Chinese CP-athelets are ORZ. Only a fool would doubt that. Now, these ORZ-Chienese CP-athelets are already in Div-1 at codeforces. They create ALT accounts and gets higher ranks and the person who should get rank below 200, actually gets rank above 500-700 ( considering 400-500 alt accounts ).
Now, coming to CHEATERS. They suck. They don't have brains. Some people cheat because they are looking for job opportunities. In India, if you are college student, one of the criteria for getting interview opportunity is, you have good rating on coding platforms.
Cheaters suck, so do ALT account users.
You are right, but I think cheating is more severe than having alt accounts.
I see.However,skipping is in order to warn the cheaters before banning them,but alt accounts users DON'T get warned before they get banned.
So why don't just ban accounts that were rigistered later but ban their all?
Definitely cheating is more terrible than using alt accounts,but what mike is doing is like alt is more terrible.
What do you suggest to do here ?
Should we warn the ALT account user ? How do we do it ? How does codeforces know, which two accounts are owned by same user ?
If your government knows, you have two passports, then government will invalid one of the passports. Either you get notice or default. In case of codeforces, we don't have any other option to send notice or anything.
I simply fail to understand, WHY DO YOU NEED ALT ACCOUNT ????
are you trying to hide from others that you are still coding ? ( may be the solution to this problem is, codeforces provide some hide-profile mode )
Then why do codeforces warn cheaters(by skipping) but not just ban them?
You can ban them. Lack of awareness, or lack of knowledge, or may be pressure to get job makes people cheat.
But literally everyone makes mistake. If the mistake is repeated multiple times, then of course you should get banned.
Forgiveness is your answer !!!
I don't know about others, but I believe in second chances.
You give the second chance to cheaters,then why not give it to alt users?
I assume cheaters are not insta-banned in case of misdetection by the system because it's half automated, not because they want to give cheaters a second chance. Catching alts is a more manual work and therefore the decisions are likely to be directly made by admins, so there is no reason to forgive them.
explain the process to me, how can I give you second chance !!!
I blocked your Div2 account, which was kind of useless. Your main account, where you are actually RED coder, is still active. what is wrong here !!!!
I SIMPLY DON"T UNDERSTAND, WHAT EXACTLY YOU ARE FIGHTING FOR ?
You like giving examples in passports, and you are radical.
And the opinion you give once and again is, cheating is ok to forgive, while alt accounts are not. Using your strategy, its like using another person's passport is ok.
I'll state why I think alt accounts are not as severe as cheating. Cheating is, you are not doing the problems on your own, but alt accounts on the other hand, to speak only on solving, legit.
Now I'm going to answer some of your questions.
Yes, we should warn the user just like the scenario in cheating. How? By sending private messages.
One thing is to notice is that the problem with passworts is political, and in no case can represent alt accounts, as they were absolutely the different matter.
Because you are not in a country in which competitions are very severe. If I create an account for training, but not competitions, it is only because you want to secretly solve problems and not to be noticed by other people or other orginizations.
Another use is giving the sense of real competition. A master enters a Div2 contest, and he/she will not feel the atmosphere as before. However, this training is critical.
And a another aspect is that codeforces has not implemented throughly "unrated register".
Hide-profile mode is strange.
And in your words, sir, I sense a high level of superiority. The internet isn't a place for quarrels, a problem should be discussed politely.
You never explained one thing to me...
WHY EXACTLY DO YOU NEED ALT ACCOUNT ?
As a moderator, if I know, somebody is fake, and I know somebody is actually RED coder, pretending to be div2 participant,,, WHY SHOULD I LET that someone TAKE PART IN DIV2 another time ?
explain this !!!
Passport is radical, how about LinkedinProfile ? does that sound radical ? School/college profile, is that also radical ?
This is my last comment on this topic, Please don't expect any revert back on these comments.
I am deeply distrubed by these point less debate going on for "ALT USERS". I just fail to understand, WHY SHOULD A RED CODER BE ALLOWED TO TAKE PART IN DIV-2 contest pretending to be DIV-2 coder ? just for EGO BOOST ? . WHY NOT REACH LGM and boost your EGO ?
Ask yourself,
1) How many times can you lie before trust is broken?
2) How long at most can you delay your credit card debt?
3) How much can you hide before it all comes to light?
Now, one may argue, codeforces is not a real-life platform. But, this is some other platform, we want to keep honesty. We want to keep pure integrity for one person.
4) What do we achieve by prohibiting cheating?
SINCERITY AND FRANKNESS.
So many of the Indian CP-athletes are normal guys without any intellectual disabilities. Only a fool would doubt that. Now, these normal-Indian CP-athletes are still in Div-2 at codeforces. They create telegram groups and gets almost same ranks by transmitting their codes, and steal codes from the same room, and the person who should get rank below 200, actually gets rank above 500-700 (considering 400-500 cheaters).
Now, coming to ALT ACCOUNT USERS. They suck. They don't have brains. Some people use multiple accounts because they are boring when Div1 contests are fewer and fewer. In China, if you are high school student, one of the criteria for getting a gold-medal opportunity is, you have good racing condition, in which you participate in real contests as much as you can.
In a word, I think you are making NONSENSE COMMENTS (so was my imitation). You just SHOUT OUT, cheaters are bad, and alt accounts are bad, so we should ban alt accounts. What? For completely no reason. You have explained nothing but just done some simile tricks. I'm wondering why are you getting so many upvotes. Rediculous.
In reply to your further comments:
why can't registering an alt account be considered as a mistake? Registering an alt account, and cheating, are all banned in the contest rule, without any difference in severity level. If one can be forgave, so is the other. Let alone the ways Mike treats the two behaviors are completely different: a skip, with no rating decrease; and bans in both accounts.
Since, not having open mind, THINGS WILL NOT MAKE ANY SENSE TO YOU.
What "second chance" do you need in ALT account ? huh ? You create completely new account, and get into top 10 of div2. Just after participating in 3 Div-2 contests, you reach CM level. And then codeforces realises, nobody is this good, this must be some ALT account user. So, they will simply block your ALT account. Where is the problem in that !!!!! ( HOW DO I GIVE YOU SECOND CHANCE, EXPLAIN BRO !!! )
Nobody knows, what is your ORIGINAL account, UNLESS, there is huge similarities between your code. You can change your coding style for ALT account.
NOW, I SENSE LOT OF PERSONAL ANGER IN YOUR COMMENT. AND THIS ANGER IS COMING FROM EITHER OF TWO THINGS...
1) YOU ARE USING ALT ACCOUNTS, AND YOU WANT TO KEEP DOING IT,
2) YOUR CLOSE FRIENDS ARE USING ALT ACCOUNTS. YOU WANT TO SUPPORT THEM AND THAT'S WHY YOU ARE TAKING A STAND.
You mentioned above...
"""I AM EXPLAINING NOTHING !!!"""
what part of my comments don't make sense to you ???
above comments are asking WHY NOT BAN CHEATERS, THEN WHY BAN ALTS. Cheating is worse than creating ALT account.
I asked them counter question, WHY DO YOU NEED ALT ACCOUNT ? EXPLAIN IT TO ME !!! You already have one account, WHY NOT USE THE SAME ACCOUNT ? Are you trying to hide from someone, that you took part in the contest ???
Cheater account still has an identity of its own, but ALT account doesn't have identity of its own. that's why ALT accounts should be immediately banned. In my opinoin, if cheater is caught cheating 3 times or 5 times, He also deserves BAN.
Yes I am INDIAN, and YES I am NORMAL GUY. It took me 7-8 years with my inconsistent persistence just to reach CM level. I have been plagiarised on CodeChef for sharing my code with my Juniors during college time, just because I wanted to help them getting placements. But I never cheated on CodeForces, to get higher ranks. So yeah, I am average guy.
NOT EVERY INDIAN IS CHEATER, AND NOT EVERY CHINESE CP-ATHELET IS ALT USER.
ok do you play Genshin Impart?
it is really a good game which fits Indians.
One can learn from you, how not to take things personally.
do you know why you has got 12 downvotes?
Editorial pls
When the editorial will be uploaded?
I want Tutorial for E3 so bad!!!
Notice that the answer in samples is convex (meaning $$$a_i - a_{i+1} \ge a_{i+1} - a_{i+2}$$$). You can store dp as its first element and difference array. Since dif array is sorted, you can store it as multiset. When merging two dps, it's basically merging two multisets. You also need to count first element, but that's trivial
Could someone explain submission D of ecnerwala . I think we somehow need to store two dp arrays , but he has used only 1.
Not too sure which two arrays you have in mind. Each row needs to (strictly) include one of the endpoints of the previous row, so our dp array just stores the min cost for each row assuming that this point is an endpoint; we don't care whether it's a left endpoint or a right endpoint. We do a left->right and a right->left pass to update these, in each pass we store 2 variables, one is the best value assuming we have included the previous row's endpoint, one is the best value assuming we haven't. Maybe that answers your question?
But how does that satisfies the second constraint i.e. a new element is there in the current row? I think in that case left or right endpoints matters.
When I say it includes and endpoint, I actually mean it includes the "point between the no day and the yes day". Equivalently, it must include a particular consecutive pair of days: either l-1,l or r,r+1
I must truly commend your brilliance. Upon reviewing the details more carefully, if I understand correctly, you've stored the DP array in such a way that allows the use of indices $$$j$$$ and $$$j + 1$$$ from $$$dp[j]$$$ to compute $$$ndp[j + 1]$$$ (Left pass) , $$$dp[j]$$$ holds the optimal solution when the previous row covers the interval $$$[l, j]$$$ or $$$[j + 1, r]$$$, which enables the use of the interval that $$$[l, j + 1]$$$ in the new row where $$$l <= j$$$ and it doesn't matters whether it was left endpoint or right.
ArvinCiu Editorial please
Pyqe will win COMPFEST 16!
wasted 2 hours on A and can't solve codeforces div 2 A guessing style are harder than 3000 rated problems for me
my very first solution which I guessed after 16 minutes of the virtual participating was correct but I used set instead of multiset
but even though this is a very bad problem the author at least should have allowed the formula solution to pass by lowering the Ai range
unusual time -> meanwhile me = only get accepted a
Why is the editorial not pblished yet?
Explain to me, plz, algorithm for E1. Most of the solutions use Floyd-Warshall algorithm to calculate distances between vertices. Then for each k they greedily find next vertex to install server, and this vertex should reduce current latency the most. So if we have set of vertices-servers on the step k, then solution for k+1 contains all these vertices plus another one that have met the criteria I've described above. While it's clear for me that we should install servers in vertices where we need servers (and do not consider other vertices as candidates), it's more complicated to prove optimality of greediness on each step for k. Can you explain me, why greedy solution would be globally optimal?
For example, for k=1 I have to put server in vertex, say, 3. Why it's not possible for k=2 to have set of vertices (1, 2) as optimal solution so that latency of (1, 2) solution is less than (3, 1) or (3, 2) or any other (3, *) solutions?
Exactly, otherwise it would become a NP-hard problem i guess.If you got to know the answer to this doubt, please let me know!
so we're not sure whether we will use codeforces for the next time.
In some ways, codeforces has been disabled too.
Compared to banning small accounts, Mike should pay more attention to user experience, such as the lengthy evaluation times (often taking several minutes to get results after submitting a problem during contests), the various negative impacts caused by Cloudflare (which can take nearly 10 minutes before a contest), and the frequently crashing website (especially in China, where Codeforces is very slow to access and sometimes inaccessible for hours). As a well-known platform, Codeforces should work on improving its servers.
——This is ChatGPT 4o's opinion on the matter.
why dont you give your own opinion instead of gpt lmao
A small piece of advice: next time, it's better to ask ChatGPT in English, so that it will generate English contexts for you, and you don't have to do stupid (and wrong) translations from Chinese to English.
Another piece of advice: you should reply to Mike instead of replying to the whole post.
Anyway, if you want to tell me that your comment is generated by ChatGPT, I think it shows that you do not understand / support your comment, right?
Why hasn't the official solution been made public yet?
When will the editorial be out? Seems to be taking longer than usual..
orz
Dear YocyCraft, we heartily miss you, and your small editorial. We didn't get any editorial for last context from almost 1.5 days.
When will the editorials for this round be published?
When can we expect the editorial to be published?
Hello! The editorial is currently in progress. Thanks for your patience, stay tuned, it’ll be ready soon! 😍 😍
Editorial Please!!
Editorials?
Editorial When?
Can someone tell me why this contest doesn't have a editorial?
Editorial pls!
So why isn't the editorial added?
ArvinCiu Editorial Plsss
editorial where :(
Hunting Editorial
Still waiting for the editorial.
editorial waiting room
solution to C2 really seems dirty with no exception.. even jiangly's
is there any easier way to implement?
Not really. You don't need to use segment trees at all as mentioned in the editorial. I am using sets to store all occurrences of each element and calculating the no. of correct alignments for each query dynamically. You can refer my solution here.
https://codeforces.me/contest/2021/submission/284565329
hello , recently i received a message from system stating that my submission https://codeforces.me/contest/2021/submission/284556726 matched with https://codeforces.me/contest/2021/submission/284580743 this submission.
I have used my local machine for code compilation and not any online compilers but still our codes matched to a very great extent. My submission was made quite before the another one. His submissions are marked SKIPPED .
can someone please tell me what should i do, clearly its a coincidence. Will my submission will also get skipped? ArvinCiu please look into it. Thankyou.
hello , recently i received a message from system stating that my submissions coincided with others solution. This is my solution for 2021A https://codeforces.me/contest/2021/submission/284537400 and it shows skipped even though i didn't receive any message for this one. My solution for 2021B was this Java solution https://codeforces.me/contest/2021/submission/284580891 which also shows skipped. And my solution for 2021C1 https://codeforces.me/contest/2021/submission/284591253 coincided with other solutions, i really have no idea how it coincided with others solution and i just use vs code for solving and don't use any online compilers. Thank you for your patience and i hope this misunderstanding gets resolved.
I hope someone can help me in this.ArvinCiu please look into this.
Hello , recently i received a message from system stating that my submissions coincided with others solution. I have been told that many others have found solutions similar to mine. But I really don't know how to match it. I write code in vs code and I don't use any online compiler. I try my best to solve the whole contest by myself... hope i was able understand, even i have solved two problems both are doing skipped show. my submission link : A. https://codeforces.me/contest/2021/submission/284545259 B. https://codeforces.me/contest/2021/submission/284600769
ArvinCiu
ArvinCiu
OMG YES FINALLY CONTEST IN 1PM
Hello , recently i received a message from system stating that my submission 284588336 for the problem 2021C1 coincided with others solution. I have been told that many others have found solutions similar to mine. But I really don't know how to match it. I wrote my solution on my local computer and didnt use any online ecompiler. It so happens that i took idea from a a similar question to solve this and this might have been the reason of solution being matched with other. But it definitely isnt copied and was written by myself.
ArvinCiu please look into it.
hello my submission of 284585378 got skipped for problem B. but i used the idea and code from one youtube video which was already posted before the contest so please review it and make my submission valid. I write code in vs code and I don't use any online compiler. I try my best to solve the whole contest by myself... my code is definately not copied from someone else you are mistaken please go through it once this is the link of that video that contains the idea and is already published much before the contest. so please review it.. https://www.youtube.com/watch?v=q2UYu3TS78E
ArvinCiu Thanks! [user:joelgun14][user:athin]
I'm not black!!!
Regarding someone[user:Shivansh_24] with the same code as me for question B during the competition.
I want to say, I did not cheat.
reason:His submission time is longer than mine,Obviously, he plagiarized my code.
Please be informed.
Hello organizing team, First of all competition was awesome, so thank you for that. My submission 284580743 was detected to be similar to subsmission 284556726 by codeforces model.
I received mail as this:-
"Attention!
Your solution 284580743 for the problem 2021C1 significantly coincides with solutions Garvit_Goyal/284556726, clerisyutsav47/284580743. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked."
My submissions has been skipped and it's first time it happened, I didn't even coded in any online platform nor copied code from anywhere. I request organizers to please look at this regard, My code template is same everywhere.I believe human reviewer would be able to distinguish it. I did copied my template from internet and our template do match slightly. But that happened coincidentally, none of the other solutions are matching. You can even look at the solutions from other competitions, none of them are similar to anypoint. Please look at it ArvinCiu
Can someone please take their time out to explain me why in the question E1, the nodes we choose for any value of K-1 , will also be included in the optimal list of servers for K ?
What is the limit of your Laziness ? You guys are still unable to come up with the Editorial of E ?
Confirmed
I can't read the source codes. When I click on the code it shows me N/A