Hi!
This round is sponsored by esports team cybercats. The team was founded in October 2021 by me and subscriber.
We currently have a Dota 2 roster, playing in the second division of EEU DPC. Come support us on streams and in the comments!
As a thank you to Codeforces and the competitive programming community, we decided to make this round and give away 100 plush cybercats!
The prizes will be awarded to the first 100 places in the round.
Follow our social networks:
(RU) VK (RU) telegram (RU) youtube (EN) twitter.
The problem set was prepared by subscriber, isaf27, KAN, Catmoonlight, jdurie and BucketPotato.
Round was tested by enot110, izban, qwerty787788, MateoCV, ilyakrasnovv, blobugh, ak2006, Valters07, DiegoGarcia, Chaska, kzyKT, Dan4Life, FedeNQ, alysonNBS, petertromso and jojonicho.
UPD. Scoring distribution: 500 — 1000 — 1500 — (1500 — 750) — 2250 — 2500 — 3000 — 3500.
UPD. editorial
I have got negative delta in div1 or div1+div2 contests for 3 times (and dropped from master to CM twice), but I still decide to take part in next contest (and get another negative delta).
Worst Contest I have Ever Seen!..
Absolutely, only 7k people participated, the problems were too hard so that many did not even submit A
I feel A and B were fine for their spot (considering it isn't a div-2, but a div-1 + div-2). C felt too hard for being C. D1 and D2 were cool problems and I really liked them, and I think they were a little easy for their position. Can't say anything about other problems since I didn't solve them.
So which problems exactly do you feel were hard for their place? (apart from C, I agree with you on that one)
cannot agree with you more.
True
Div1 + Div2, but no Div2 tester.
Ak2006: am i a joke to you?
You forgot to thank Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces
They also forgot to thank X for excellent coordination and help with preparation
cypurr cats!
Hi Vlad, no Rocket League roster yet :p? Did you hit Diamond or higher :D?
diamond 1, finally!
no pro Rocket League roster yet, only the fan one :)
I might end up top1 in this contest
I think and hope the problems are easier than yesterday's #853
853 DIV 1
We also have 3 hours unlike yesterday where we had only 2 hours for that div1. Hope it's gonna be great and educative.
You know, I am something of a cybercat myself
I've read all of your submissions on Codeforces, really really impressive.
Did no one get this? This is the response that Peter gave when Osborn said that.
I am ashamed; I only remembered the initial quote, but now when you mentioned it, I also recall that response!
Hello guys — I am new to codeforces. I just tried my first div 2 virtual contest and solved 2. Is it okay to participate in this one, or should I stick to div2/3/4 contests?
Give all the contests except Div1. This contest has Div2 questions in the beginning so you can participate.
Do participate in all contests. Even if ratings go down, it can be recovered in 2-3 good rounds.
To be really skilled at both gaming and cp. Orz
*cries in hard-stuck Iron [Valorant]
same bro :(
Wow, this is so cool 😄. Never thought professional gamers would sponsor a Codeforces Round. Pro at not only CP but gaming too!! I wish your team all the very best in all your future endeavours.
As a tester, I highly encourage you to read all the tasks!
I liked your old logo more :(
Hope this is my real CM promotion contest ):
what happened in the last round ? you posted the same comment last round right?
+12 , not enough to become a CM ): But yes right
This cat looks kinda sad
I guess the problem statements will not be short and clear and will include some story of the game they are promoting.
cute cat :)
How many problems can we expect in this round ?
I felt something like lol after testing.
The timing is not very friendly to Chinese participants, as they still have classes tomorrow.
It should be obvious by now mate, Codeforces >>>>>>>>>> classes :)
Best wishes for the round ! <3
Auto comment: topic has been updated by enot110 (previous revision, new revision, compare).
Pls no weak tests today.
so cute!
Wow, I saw this team in DPC standings, but had no clue someone known to me is in charge. Can you tell its story?
As a tester, i confirm the round is good :)
I hope after this round I will stop being a prisoner of the cyan
when there will be twitch streams ?
Can't take part today, but the problems look nice.
How to solve D1, D2?
D1: You can do it using a simple O(nk) DP (define state dp[i][j] as the minimum time to do the ith task such that the other machine (the one which doesnt do the ith task) last did the jth task). Transitions will also be quite easy, you need to handle the case wherein (i-1)th task = ith task separately though.
implementation: https://codeforces.net/contest/1799/submission/195167349
D2: If you observe the transitions carefully you will notice that at each i, what happens is that we do a range sum update on some dp values from the dp[i — 1] table and set them to their corresponding values in dp[i] table, and a point update on one dp[i — 1] value and set it to its corresponding dp[i] value, so this can be done easily using a segment/fenwick tree.
implementation (segtree): https://codeforces.net/contest/1799/submission/195178402
I solved both D1 & D2 without segment tree or Fenwick. You can watch my video editorial if you are interested: https://youtu.be/oOyPQL16x1M
Yeeee, i created E of this round 2 years ago
https://www.codechef.com/FEB21C/problems/MEOW1234
Also there is a similar approach here
I really liked the problems but the round was weird for me, I was able to solve D1 and D2 quite easily but I can't for the life of me figure out how to do C. Could anyone give me a hint?
I tried my best and got WA on 4th pretest :'(
I have a quite long solution for problem C although I don't know how to prove it yet: Firstly, create two pointers p1 ( set to 0 ) and p2 (set to n), then save all the strings to a map and then iterate through the map, then for each key in the map, if the frequency of that key is divisible by 2, then simply put the first appearance of the character in p1, the next one to p2, the next one to p1, etc until it ends. If the frequency of that key is odd, do the same process for the n-1 number and then break out of the map. At this time, there are 4 cases : 1. If the map is now completely empty, we can check for the constructed string and reverse version of it to output the larger one out. 2. if the map size is equal to 1, then put the last element in the map in the position string size/2 and printout the larger of the constructed string and its reverse version 3. If the map size is >= 3, then we can put the current element in position of p1 and the other element in the map inside the string in reversed order and output 4. If the map size is equal to 2, then we can put the remaining 1 element in the middle of the string and then put all the other inside it and output it .
Code : https://codeforces.net/contest/1799/submission/195192191 ( sorry for the bad implementation )
I have a pretty similar solution that I proved here
to be honest, I don't like this problem because it is too many cases
I think that the problem by itself is interesting but it's not enjoyable to implement at the beginning of a cf round
I agree, for me too C is harder than D. For me it just came down to considering three cases:
Every frequency is even. Then the answer is just 'abccba'.
Suppose that the smallest symbol whose frequency is odd is symbol 'f'. Then if all symbols greater than 'f 'are the same, then the answer is 'abcfffggfgggfffcba'.
Otherwise, the answer is 'abcfffghijkffffcba'.
seems like it was div 1 only not div1+2
Dislike C and E lol
one of the best Div2B on codeforces
Why? It’s straight forward to get a 2 which is true if you have more than 3 different elements. Otherwise just check if you can make a 2. Whats so good about it
Why problem C are usually harder than normal in div1+div2 rounds? I've consumed much time on it.
Ps: I've lost 50 points for forgot to change array size from 5000 to 300000 when submitting solution of D2, and lost 100 points for forgot to check whether ptr<0 when solving problem A. Why I perform badly on every div1+div2 rounds...
When I started testing, C and D1 were not in the problemset and the order of other problems was A — B — F — E — D2 — G — H. Of course the standing page was funny, and current problemset is even much improvement. This is why I felt lol after testing.
I agree that C was very troublesome to deal with (and I personally had multiple incorrect implementations of a correct idea). I think that kind of messy problem might appear in any kind of round and that it might just be smarter to skip it directly (tbh, after reading the statement, I could guess that I would most likely spend inf time on it).
Don't like ADEG, very boring problems.
In Problem D1, can we create a 3d dp array where the 1st one is for index, 2nd one is for the number of elements which are consecutively used by current CPU and 3rd one is for current CPU ?
Yes, this is one of the correct solutions.
How to solve hairy multiple case problems like C? I was on it for 2:00 hours of thinking different cases and got AC on 2:55
Was this problem kind of pain for everybody? or is it just me not thinking in a good way? Can div.1 contestants solve it easy and without pain thinking???
Skip the problem.
I also wasted 2 hr solving this, and after that when I saw D1 it was direct dp but there was no time to complete the code.......
I agree with every word you said.
C and E are trash problem.
C is really tedious to solve. It’s almost like trial and error. The fact that it has so many submissions means there are tons of cheaters on this round
How to solve (prove) B?
If there's exists some $$$i,j$$$ ($$$i \ne j) \quad a_i = 1 , a_j \ne 1$$$ then we cannot make all the elements equal. because for $$$a_i = 1$$$ you cannot change it. and if you attempt to make the other elements 1 then you are failed also because after making $$$n-1$$$ elements to 1 then you cannot make the last one same because it is now max of the array.
But if you have an array of greater than 1 integers, then you can make all of elements 2 in at most $$$30n$$$ operation. the idea is whenever you found two distinct elements you can divide greater integer by smaller integer. so in this way you make array elements smaller and smaller till you make all elements equal to 2.
Worst case scenario you have to divide 10^9 by 2. then it wouldn't take more than 30 operations (because $$$log(10^9)<30$$$)
Sometimes you don't even reach 2, but rather a bigger number.
Example:
(23, 8, 3)
-->(3, 8, 3)
-->(3, 3, 3)
.Thank you)
Thank you)
E is just a tedious implementation problem. I really enjoyed solving from A to D, but E just simply ruined all my mood.
Please send my thanks to whoever create such an atrocious problem E.
Is it only "Zero IQ" me who found C to be extremely hard? How to solve it :")
Sol:
Let's construct the optimal string in two parts (a left side and a right side which are respectively a prefix and suffix of the final string)
In the first step we will keep the following invariant: left is the same string as right
We consider the chars in lexicographical order
While the current char occurs an even number of times it is clearly optimal to split it evenly on both sides (it is easy to get a contradiction as if you place more a to the left, then you would put some, say, b at the symmetrical position in the right side and you could get better by putting an a instead).
Now we are either done, either facing a char C having odd count.
As earlier, it is optimal to split the even part of the char equally on both sides (so if you have 5 a you will put aa on each side).
(You can do a proof by contradiction exactly like earlier)
There is now only one occurence of C
Consider two cases
1: you have one or less remaining chars greater than c
2: you have more than one remaining chars greater than c
Case 1:
if C is the last char, you just put C as it's the only thing you can do
else, it is basically analog to solving the case abbbb...bb and in this case the best answer is (by casework) to put a in the middle of the group of b
Case 2:
There are more chars so its similar to solving abbccdd... (you can compress adjacent equals chars to make them blocks)
Here we can wlog assume that reading the string starting from the left side will give the lexicographical smallest string.
Assume you don't place a right now, it will be suboptimal as you would add some b on the left and right side (if you add anything greater the string becomes >) and now if you add a on the left side, you can just swap a with the b to get something <= (same on the right side by symmetry).
So you will add some c on both sides but what can make a better answer.
So you should add a to the left. Now it is clearly optimal to sort the remaining chars.
Indeed: we know that reading from the left side gives something strictly smaller than reading from the right side so we are now only interested in making the right as small as possible
Code: 195196709
Constraints in D1 are toooo bad!
n*n*4 memory is not allowed while n*n*2 is allowed
and n*n*2 time is not allowed while n*n is allowed
So do we need to tabulate the solution ?
There's no need for 2D array in D1.
Can you share how did you solved it ?
Let dp[i] = the answer of the problem when consider on range [1, i]. dp[0]=0.
First, let dp[i]=dp[i-1]+cold[a[i]] when a[i]!=a[i-1], or dp[i]=dp[i-1]+hot[a[i]] when a[i]==a[i-1]. That's the situation when we use same cpu for i-1 and i.
Then let j<i-1, a[j]==a[i] and assume we use cpu1 for i and j, cpu2 for [i+1...j-1], we can get dp[i]=min(dp[i], dp[j+1] + cost(j+2, i-1) + hot[a[i]]) where cost(j+2, i-1) is the cost for range [j+2, i-1] if we use only one cpu (we can calculate them in O(n^2)), and for checking all valid j, we can solve D1 in O(n^2).
Hey, your solution seems easy but i do not understand the cost() function. becuase i am confused with the first element of cost(). the first element of the $$$cost()$$$ function contributes $$$cold[j+1]$$$ or $$$hot[j+1]$$$?
can you explain please.
assume we use cpu 1 for j, cpu 2 for j+1, j+2, ... i-1, cpu 1 for i. So each k in [j+2, i-1] contribute hot[k] if a[k]==a[k-1].
but i am asking for the cost of $$$j+1$$$. We are using cpu 2 for $$$j+1$$$? It will take some time to process the $$$j+1$$$ process. But will it take $$$cold[j+1]$$$ or $$$hot[j+1]$$$ ?
Cost of j+1 is contained in dp[j+1].
Yeah, but if one person had n*n time solution, he got AC , but if someone has just extra factor of 2 , it got TLE , this does not seems fair!
My solution for D1 ran for 46 ms, so even a 10* constant factor doesn't matter (if you're using c++).
What is time complexity of your D1 solution
O(n^2) of course
I agree. Lost more than 450 points because of memory.........
You can use the "hidden parameter" technique to only store the current layer of DP, reducing the memory consumption to O(n).
My solution for C (passed pretest but I can't prove it):
Sort string s. Let ptr=0, L=0, R=n-1.
If s[ptr]==s[ptr+1], we must put them on ans[L] and ans[R] in order to minimize t_max[L]. Repeat this while increasing ptr by 2, until we are done or we meet s[ptr]<s[ptr+1].
In the second situation, we check if s[ptr+1]==max(s)==s[n-1]. If not, the answer (for the remained part of ans) is s[ptr+1...n-1] + s[ptr]. Otherwise, the remain part of s is something like "abb...bb", so the answer is 'b'*ceil(k/2) + 'a' + 'b'*floor(k/2), where k = count of remaining 'b'.
How to solve B? ;-;
less / greater = 1
greater / less = [2 , greater]
Also notice that if our array contains a 1 and a greater number x, it will be impossible for x to be reduced to 1 because x / 1 = x
Could we just stop making problem A too hard? Making problem A too hard will scare out most of the contestants, making number of participants too small and are quite unfair for all of real participants, making them very likely to drop rating.
But it's completely trivial ._.
Actually,you can let more pupil or specialist to test, and if any of them cannot finish this problem in 15 minutes, this problem should not appear as problem A.
First, the description of problem A should be simple, can let all participants have idea what this problem is about. If they are confused, they just quit the contest.
Also, the constraint of problem A should be very small to let brute force to pass. As I know from some of my friends, when they do a contest, they will see the constraint of problem A, if the constraint of problem A is more than 10^4, they just know this is a harsh contest and quit.
In my opinion, Problem A should act as a "sign up" problem and should not have any difficulty.
Plus plus, hxu10
So are you proposing to decrease amount of real problems in every contest by one?
Heck, it's competitive programming after all, we are here to solve problems, not to write A+B in every single contest. IMHO, it's fine that today's A is not completely trivial, because that's A of combined round. It should be interesting (despite not hard) to solve for everybody. And there are different types of contests for newbies out here (div3 or even div4) where I don't care if A will be A+B or whatever.
Also, I agree that there is a need for a way to "sign up" for a contest in order to avoid situation when people are reading problems and skipping the round. But let's just add corresponding button and not affect problems quality.
If participants are scared by task A, I think they don't submit any solutions so their rating is not going to drop. However, as average rating is (almost?) constant, this means someone other with higher rating will have to fall, and that's sad)
I am a newbie and I don't think it's hard it you think in the right direction, I immediately had the idea of using deque or set. I think the problem is not the difficulty but their inability to fight hard until they could solve the problem.
Good for you for solving A so quick. However, many of the newbie are not lucky enough like you to think in the right direction. They are frighten by the problem description and just go away.
I think today's A was really an easy A (compared to A requiring some number theory or some ideas, thus pushing beginners to guess the solution and submit random ideas).
The only problem might be the statement which is a bit confusing if you read it too fast but I think that beginners don't try that hard to get AC in less than 10 minutes x)
I don't think you'll lose any single point of rating because of 100 (or even 1000) grays who weren't able to comprehend A.
If 100 user did not attend the contest, that is true. But 1000 user did not attend, that will be different.
Actually, there are at least 4000 users who did not attend, let us see what is the difference.
In round 854, 7800 rated users, if you are rank 1000, your performance is 1851.
In TypeDB Forces 2023, 11000 rated users, if you are rank 1000, your performance 1958.
That's totally a 108 performance difference. Usually, every 4 performance change will cause 1 rating change, which means that will cause 26 rating change.
I'm sure this difference is caused by higher rated users who didn't attend (most likely from objective reasons) and not by hundreds (or even thousands) of grays who was scared by A. Because if we are talking about milestone of top 1000 which you mentioned in your comment — it's very unlikely that many grays in the bottom of standings will really uprise the rating of top-1000 as top-1000 scorers are rated much higher then gray (on average) and grays below them don't affect their expected place much.
Anyone enjoyed the number of sample tests?
Absolutely! And even more their coverage. I was about to start writing wrong solution on C and closer look on pretests really saved my time.
It's good that you add test cases. It will be better if you can make statements more clear.
A-G are all very boring and disgusting.
F is very interesting :)
Why the aim of TL=1s? Seems tighter than usual and I hesitated to implement >100ms (like 1e8 steps) solution.
Nice to see strong pretests :P
could someone please tell the logic of b question
Greedyforces
Auto comment: topic has been updated by enot110 (previous revision, new revision, compare).
this round be like...
Why is F so easy?
I had one red guy in my room who will not agree with you :)
Why are constraints in G so low? I have $$$O(n^2)$$$ solution and it can be optimized to $$$O(nlog^2n)$$$ with FFT
I accidentally solved F in O(n log n) despite N = 5000, though I feel that giving N = 2e5 would make a more interesting problem.
I wanted to make subtask with bigger $$$n$$$ and I noticed such funny solution: in the $$$O(n^2)$$$ solution we can just make ternary search by one of parameters because the function is convex (don't know how to prove, just made a stress test).
I think there are many approaches to make $$$o(n^2)$$$ solution, but we noticed that the problem is enough hard for some reason, so decided not to make the subtask.
F is solveable by simply using the same solution of https://codeforces.net/problemset/problem/739/E.
out of 21K participants only 7K are rated for them, just implement the atcoder system already
Why is this round Div.1? It is definitely not hard enough.
wow, very fast editorial, thanks
If only 2 more minutes were left, I could've solved C. Well glad that at least my idea was correct..
D1 :( :(
long long int dp[5001][5001][3]; gave MLE long long int dp[5001][5001][2]; got AC;
Note that u can drop the first dimension
Why was this contest this difficult the B problem ripped me apart *_*
So low constraint in E led to me implementing a total atrocity of a 5-dimensional dp that works in general case (i.e. arbitrary set of initial cells). After coding it for ~45 minutes it was ~2 times too slow when implemented in $$$O(n^5)$$$, so I needed another ~45 minutes to optimize it to $$$O(n^4)$$$ and then it got WA, so I spent another 30 minutes to write from scratch another solution that works for 2 cities totalling 2 hours for E. I also misread D thinking we got nonconstant number of CPUs and did not finish G on time. My worst performance in a very long time xD (sry for wrong choice of words before the edit xd)
Problem D is a harder version of 1479B2 - Painting the Array II. I actually resorted to copying ecnerwala's solution to that problem (which generalizes easily) because I'm really bad with this type of problem.
I remembered the greedy approach to this problem and used a similar idea where we are assigning the program to the CPU whose latest program is occurring farther in the future than the other. But it gives wrong answer. submission : 195166846
I hate C.
Spent 2 hours and found out it is so fxxking easy.
can u give me a hint ?
try to build a string with min lex so that the leftover pieces can form a reverse string with lower or equal lex. In this case you can make sure the string you build will be selected as answer, and still some implement ation details need to be worked with.
Seriously, It was way past my sleeping time when I worked on this problem.what are your excuses, down voters?
We only recently had a ton of community discussion on how unfun it is for participants to express nonconstructive negative feedback only for this comments section to be flooded with it for not much of a reason ._.
Before systest: NO... I'm in 101st place and I had been resubmitted 951ms E... good bye my cat...
Now: Let's GO!!! I'm in 99th!!! Hello, my cat!!!
upd: Sorry I was just lucky, got uphack on E...
Can anyone tell why my code is failing for Problem D1 as I have declared long long everywhere still ans is coming wrong ?
It is giving correct ans in my IDE but failing when I am submitting Submission Link — https://codeforces.net/contest/1799/submission/195194098
See this, https://codeforces.net/contest/1799/submission/195196346
long long res = LONG_MAX;
or long long res = LLONG_MAX;
Yes I corrected it
Thanks :)
Got stuck in A don't know why!!!!
Got the idea of B in 10 mins and implemented the same, but I didn't get the idea due to pressure that I have to change int to double for both the variables (numerator and denominator) to use ceil and wasn't getting answers as I was only doubling numerator.
Figured out and saw the contest ended:(((((. Submitted after the contest and it got AC! Such a bad day!!
Don't use double for ceil. Ceil(a/b)=(a+b-1)/b
if youre using c++, this will give you WA with negative numbers
a/b + (a%b>0) better
I once saw a website for predicting the difficulty of the problems.
Is it still there?
Link?
I have submitted the same code again and i got Accepted
If there is a way to rejudge the solution again?
195196340 Accepted submission
195171454 TLE submission
subscriber, isaf27, KAN, Catmoonlight, jdurie, BucketPotato, MikeMirzayanov
In Problem B I have a question Can we solve in this way if the number does not contain one then check whelther dividing the no by a[i] with a[j] the value of a[i] will result in two or not If the result is two then we can convert all the number by selecting the ind which get converted to two and the remaining index one by one except the ind index Please answer this Thank You
No. What if there are only 2 numbers, a
3
and a9
? In this case, we divide9
by3
and then the array will have both elements with the same value.Why F is easier than C?
I solved D1 significantly earlier than B, and that really surprised me)
Because current F was originally in C — you and the setter had same thought :P
Feels the same, it took me longer to get the idea of C than F.
Did anyone else solve C recursively?
Hi guys you can check video editorial for
Problem A , Problem B, Problem C, Problem D here — https://youtu.be/AGIrdT_cQuY
Can you tell me what I am doing wrong 195231790
return ans=cc[aa[l]][0] + min(rec(l+1,pre),rec(l+1,aa[l-1]));
here you are directly returning without saving the data into the dp.
Can someone please point me where my solution is leaking memory for Problem B ? — Solution
Try this input: 1 2 9 3
As long as I have more than 2 hours to solve, its good :D
Dear sir, MikeMirzayanov
I recently got message from system that my solution 195163597 is same as others, several names were there. But I did not copied from anyone. You can see I was getting MLE in my initial verdict, then TLE and WA. My initial logic was making all elements 2, which I was trying for atleast 45 min. After getting so many wrong verdict I removed all my code and started again.
I removed all my template in order to not get any TLE( as earlier I have suffered TLE because of my template ), and wrote the basic logic divide by minimum every time, which unfortunately came very late. The question logic is common for everyone. It does not mean that everyone have shared the code. Please correct your plag checker.
I know it was mistake but we who do not cheat and give a lot of time we get plag, just like other cheaters hurts. Please look into this.
Please correct it and improve your plag checker system, and thanks for such great platform for CP
How can I get my cat? haven't received any message yet :(
Be my cat.❤
Normally, you'll have to wait for about a week or so to get a notification. (and wait for a year to have it delivered to your home)
Dear MikeMirzayanov
I received a message from the system that my solution is similar to unordered_map's solution. But only the input part matches and the process of calculating the dp table is different.
Also, problem D1 is similar(the definition of the dp table is exactly the same) to the past problem in KOI(Korean Olympiad of Informatics), which is well-known in Korea. Both I and unordered_map have solved it. So, we were able to solve D1 without copying the code. It seems that it will be faster to implement it alone than to search for the solution code.
I think the system is detecting coincidences only in the LCS of two codes. Please correct this.
My submission : 195156487
Skipped submission : 195164678