Hello Codeforces!
On May/12/2023 17:35 (Moscow time) Educational Codeforces Round 148 (Rated for Div. 2) will start.
Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.
This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.
You will be given 6 or 7 problems and 2 hours to solve them.
The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.
Good luck to all the participants!
Our friends at Harbour.Space also have a message for you:
Your Path to Success Starts at Harbour.Space Bangkok
Hello Codeforces!
We are excited to announce that we are offering 10 full scholarships to study Computer Science or Data Science at Harbour.Space, Bangkok Campus!
We invite you to apply to our university in Bangkok, Thailand, where we offer a full scholarship for qualified participants.
Our university has a vibrant and inclusive community, where you'll have the opportunity to learn from and collaborate with some of the brightest minds in your field, such as the one and only Mike MikeMirzayanov Mirzayanov. Additionally, our state-of-the-art University is designed to support your academic success and personal growth.
If you want to pursue higher education, get accreditation and expand your horizons, we encourage you to apply! As members of the Codeforces community, we recognise your talent and dedication to problem-solving, and you would make an excellent candidate for our programme.
Requirements:
Study Commitment: 3 hours/day. You will complete 15 modules (each three weeks long) in one year. The daily class workload is 3 hours, plus homework to complete in your own time.
University requirements
- CV
- High School/Bachelor's Degree
- English proficiency
- Medalist in any Programming competition is a plus!
Make sure to apply before June the 30th, 2023, to be eligible for the scholarship and reduced application fee!
We look forward to hearing from you and welcoming you to our community.
All the best, The Harbour.Space Team
UPD: Editorial is out
Ready to get +DELTA (◠‿◠)
I have seen you commenting things like "Fingers Crossed for +delta (◠‿◠)" on almost every blog but the last time you really participated in a contest is 6 months ago. Is contribution really the whole thing you came to Codeforces for?
At least, I am willing to participate but because of some reasons I am not able to do so. So you better concentrate on your contests rather than checking mine.
I wish that all your problems & issues are resolved ASAP so that you can participate in the contests like you did before =)
Thank You.
awoo's round.
Kindly keep your homoerotic comments about awoo to yourself.
Same to you. Just putting the rude comments in every blog make conflicts.Do participate in any contest.
Bro wtf. It has been a year and you haven't participated with this id. What's the plan?
I definitely do not have CM alt.
As a participant, give me a contribution.
K , but remember you never said negative or positive ;)
Even though I know I am understood by everyone, I should say +DELTA. Hahaha, sure!
Thanks, everyone I got enough contributions. huh
As a cyan tester,I recommend you to see all problems.
As a cyan participant , I recommend you to see all problems.
I am new in codeforces lol hope
If someone Medalist in any programming competition that's why Harbour Space Team reduce some tuition fees for him?
Hope for the _Best_
Give your _Best_.See you in standings!!
You stole my profile picture bro : /
Thank you very much adedalic, BledDest and Neon for the contest and MikeMirzayanov for the Codeforce and Polygon platform! I appreciate your work!
contribute ++
Hoping for a nice contest
It is my first codeforces contest, please say good luck to me.
Good luck, bro ;)
Good luck. Are you a singer?
Are you minion??
yes. I am.
I won't be surprised if he's red alt
I'm ready to get educated.
I have observed the process of your rating change. How were you able to consistently improve your skills like this?
Solve challenging problems
I hope everyone achieves great success.
crazy standing XD,but Why did more people pass E than D
Ay the end — this was not true. Although i saw E getting more sollutions and went for it instead.
bad round :dislike:
I liked it NGL
Editorial for problem C:- Link
How to solve D?
I really enjoyed this round. The dynamic programming idea behind E is so fun!!!
ABCforces
no
is E convolution?
After dealing with all the math it ends up being something like the O(N*R) dp for calculating nCr on steroids.
i tried to understand your code, i understood why we are using pref[k][i] = pref[k-1][i-1]+pref[k][i-1], but i have a silly doubt why the solution getting stored at 1 index more than the original index(eg: pref[1][k] at pref[2][k])?
Yeah, I messed up something with the indexing and saw that as an easy fix. During a competition I don't really care about being exact in my indexing/naming.
Apparently it can be solved using that within the time limit (comment by physics0523), but this is (probably) not the intended solution. There exists a much simpler and (imo) more beautiful solution using properties of the binomial coefficients and dp (and the fact that k is small).
Dynamic programming. If you remember the recursive formula for the f(x, y) = f(x — 1, y — 1) + f(x — 1, y), then the solution is quiet obvious Let dp[i][j] be the solution for the problem find $$$b_j$$$ if k = i, then dp[i][j] = dp[i -1][j — 1] + dp[i][j — 1] Then its just simple optimisations.
E: orz to Nyaan's extremely fast Convolution (Large)
How long the code is! Nyaan must have written the template a long time ago ...
I got thought of the B and C, but I can never pass them... pity! hoping for your next contest!
Can someone explain how in problem B 6 2 15 22 12 10 13 11 got an output of 46 max I could calculate was 40
Apply 2nd operation 2 times.
Yeah. Even i was stuck on it. Then I realize it was just and easy bruteforce problem. Just try every k lol.
Yup even I was thinking the same . Hope I can Upsolve the problem now .
I think there should be an explanation to the sample test in task E
Solved A-E. But it seems that the number of accepted solutions of F is far less than it should be.
A: Let n be the length of string s, then we only need to check first floor(n/2) chars of s. If they are all the same, we can't get any another palindrome. Otherwise we can choose 2 different chars from them and swap them (and chars on the symmetric positions on the right half) to get another palindrome.
B: Sort the array and calculate the prefix-sum. Assume we use the 1-st operation for t times, we will remove 2t elements from the front and t elements from the back of the array. We can try all possible options of t from 0 to k to get the answer.
C: First we can remove all adjacent elements with equal value, and the contrast value will remain the same. Then we only need to remain local maximum and minimum elements of the array (including the first and the last), since if a < b < c or a > b > c we have |a-b|+|b-c|=|a-c|.
D: If k<=n, we can add values from 1 to k on different elements of the array. But if k>n, some values from 1 to k will be subtracted from the array. To make the numbers subtracted be as small as possible, the increments of each operation will be like this: 1, -2, 3, -4, 5, -6, ..., k-2, k-1, k (there are n or n-1 positive values on the back of this sequence, depending on the parity of k-n), then we need to subtract 1 from any values of the array for ceil((k-n)/2) times, and add inc=(k-2*ceil((k-n)/2)) values (from k-inc+1 to k) to different values of the array. To simulate this process, we need to sort the array, and add k+1-i to a[i] for 1<=i<=inc, and find the minimum of the array (we can do this fastly by pre-calculating prefix-minimum of a[i]-i and suffix-minimum of a[i]), then do the subtract operations on some maximum values of the array.
E: The prefix-sum of a[i]:
a[1], a[1]+a[2], a[1]+a[2]+a[3]...
The prefix-sum of the array above:
a[1], 2*a[1]+a[2], 3*a[1]+2*a[2]+a[3]... (which is b[i] when k=1)
The prefix-sum of the array above:
a[1], 3*a[1]+a[2], 6*a[1]+3*a[2]+a[3]... (which is b[i+1] when k=2)
The prefix-sum of the array above:
a[1], 4*a[1]+a[2], 10*a[1]+4*a[2]+a[3]... (which is b[i+2] when k=3)
By this pattern we can solve the problem in O(n*k) by calculating the prefix-sum for k+1 times.
What is the intuition behind coming up with successive prefix sums to replace these complex i choose K operations ? in E ?
C(n , k) = C(n — 1, k) + C(n — 1, k — 1) So b[n][k] = b[n — 1][k] + b[n — 1][k — 1]
Thanks
thank you !
How to solve D with Binary Search?
not trying to be rude but your explanation on problem D is VERY hard to understand. it took me 2 hours to fully comprehend it, anyways thanks for sharing!
wtf is D
Difficulty gap between c and d1 is huge
I think problem E is interesting, even if I didn't solve D or E. Can anyone explain the idea of problem D? Thanks!
First of all, if k <= n the solution is easy, so everything I will say is for k > n.
If you perform an even number of operations on an element you are guaranteed to decrease some value from it, since for each number you add you subtract a bigger number right after, so if you are trying to increase a value (and therefore made an odd number of operations) it's really only the last number you add that is the "deciding factor".
Knowing that, you should try to have the smallest number of your array, let's call it a(0), be added by K and a(1) by K-1, a(2) by K-2, ..., a(n) by K-n.
If (K-n) is an even number you can do it, because for each of the operations before getting to k-n you can just do an even number of operations on each element you change and you are going to end with all elements being ready for an addition.
Also, performing an addition and right after a subtraction, is going to result in decreasing the element by one, so you just have to add each (K-i) to each a(i) and then remove (K-n)/2, in total, from the elements of the resulting array, distributing it the best way to get the biggest minimum value.
If (K-n) is odd you won't be able to increase every element of the array, because to do that you need an odd number of operations on each element, but at least one element will necessarily have an even number of operations on it, so the best you can do is make this element the biggest one, a(n), and not add anything to it (instead of decreasing it) then you can add each value from k-n+1 to k to each element from a(0) to a(n-1) and you are gonna have an even number of operations left. Then again, you will remove (K-n+1)/2 from the resulting array in the best way possible.
If you want to solve D2 you do the same thing, but with some tricks to make it all faster, I can describe them if you want.
Can anyone share their solution for C? My approach was to find increasing/decreasing segements of the array and remove all elements of segment exacept endpoints, either my approach is wrong or i failed to implement it properly. Please someone tell how to solve.
You throw away all elemnts but the 1st, nth, and local minimums and maximums.
The idea. |a — b| + |b -c| == |a — c|.
Only if all values between a and c are >= a and <= c. This can be easily proved using co-ordinates points on a cartesian plane.
|1 — 3| + |3 — 7| = |1 — 7|.(if it is increasing like 1, 3, 7, ....) Similarly for decreasing sequence
you check checkout this video editorial — here
This approach leads to alot of bugs but I did the same thing:
https://codeforces.com/contest/1832/submission/205604237
I had to remove consecutive duplicates for it to work properly
yeah done the same thing maybe u have some error in implementation check out this ac https://codeforces.com/contest/1832/submission/205642721
Here is a concise submission for problem C.
My submission
Spent last 1 hour 54 minutes doing recursive dp . TLE with memo array and MLE with memo map . Some different idea involved in B ?
just sliding window.
How to solve it using sliding window?
check this out -link
Ah , sliding window worked . Thanks a lot . Cool editorial by you
Same hahaha!
Cheers for wasting 2hrs optimizing recursion lol , Someday our recursion will be useful hopefully
I tried it the first time with map + recursion and got TLE. Then, saw the constraints and realized it probably has a greedy solution in O(n). After that made some observations and got AC.
i looked at greedy first , to find whether sum of two minimum was lesser than maximum . It was funny that it failed because of being non greedy for the moment and i could not make my mind to try something other than dp
My main idea was to check for all combinations of including the first and last elements. I used prefix sum so that I don't have to calculate the sum for ranges every time. Check Here
Class 11 combinatorics revise karlo frandss
(Hint: Use (iv) to create a recurrence for b(n, k))
Nice contest! Incase you are stuck on Problem A, Problem B, Problem C. then you can check this video editorial link
Thanks for the such a fast and helpful video editorial ^ ^
Thanks for the video editorial, I will upsolve C. Sure.
Thank you
Thanks for the editorial video. I came up with the solution idea for C, but kept getting WA in test 2. Later realised it had the bug of equal to sign i.e "<=" and ">=". So,I should have ignored duplicate elements.
sed laif.
I think arbitrary $$$MOD(1 \leq MOD \leq 10^9)$$$ would have been a better choice for problem E to cut convolution solution.
Given that Edu rounds weighs all problems equally, it doesn't feel right for there to be a 2-part problem in Edu round unless the two parts are extremely different in difficulty. In the context of today's contest problem D is essentially weighed double that of problems E/F, which clearly should not be the case.
Thought the same about Codeforces Round 855 (Div. 3) but in contrast, I'd come to appreciate how the final problems of before-then div4s were split... so I ended up not posting about either :P
10 minutes after contest, >20 hacks on D :)
even legendary grandmasters are hacked for D1 :(
If anyone facing difficulty understanding D1, Please check Tourist's solution. It is very elegant and easy to understand.
solution link
We can use convolution to solve problem E.
\begin{aligned} b_i &= \sum_{j = 0}^i \binom{i — j + 1}{k} a_j \\ &= \sum_{j = 0}^i \frac{(i — j + 1)!}{k!(i — j + 1 — k)!} a_j \\ \Longrightarrow \sum_{n \geq 0} b_n x^n &= \frac{1}{k!} \sum_{n \geq 0} \sum_{j = 0}^n \frac{(n — j + 1)!}{(n — j + 1 — k)!} x^{n — j} a_j x^j \end{aligned}
We can take $$$f = \sum_{n \geq 0} a_n x^n$$$ and $$$g = \sum_{n \geq 0} \frac{(n + 1)!}{(n + 1 - k)!} x^n$$$ and $$$\frac{1}{k!}(f * g)$$$ is our desired polynomial. Since $$$n$$$ is huge $$$(n \leq 10^7)$$$, we might want to use fast convolution.
What's the hack for D?
Anything with $$$n = 1$$$ that results in a negative answer, for example
Isn't -1 the expected output for this testcase?
Yes it is, I guess you didn't understand my comment. The original commenter asked what test was used to hack probably 100+ submissions on D and I gave an example. The test isn't a directed hack to their solution (I don't know if their solution got hacked or not), it's just the test that I used to hack multiple solutions. The output I mentioned is the correct output, most incorrect solutions give 0 as the answer.
nvm
Thanks.
But I still have no idea what was wrong with my case. Maybe, I have some silly mistake (((
UPD:
O! I've found test case:
4 7
1 1 1 1
1 2 3 4 5 6 7
Really stupid misprint in my solution
Whoever hacked my submission, I hope you have a bad day.
Whoever downvoted my comment, I hope you have a bad day too.
Here goes how I solved A to E
Solution of A New Pallindrome with logic and explanation
https://www.devcp.in/2023/05/ECR-148A.html
my submission for B
can someone tell me in which tc does this code fail.
Problem B.
Your approach itself is wrong. You can't greedily choose whether to delete two min elements or one max element, because you don't know about values in entire array so it may be possible that you don't get the optimal answer finally, hence you can't take that decision just based on 2 mins and one max. This brings us to the solution of checking all possible ways to do the operations, but here dp won't be needed as some dependencies are there, like: 1.You will delete 1st two mins always before next two mins 2. You will delete first max always before 2nd max 3. You will always delete k elements
This brings us to a sliding window protocol solution. At first delete last k elements and find the sum. Then at each iteration, delete two mins and add one max back to the sum and compare with max sum.
I understood that much but still could you give me any tc as i cannot come up with one.
thanks!
ah got it! Sorry for this .
see my code
Thank you Aatma Sir for clarification...
Was it intentional to not keep keep negative answers in test cases of D?
https://codeforces.com/contest/1832/submission/205606471
can someone tell me the problem with my code for c
What if $$$lst[0]$$$ is $$$0$$$ ?
$$$input$$$ :
$$$1$$$
$$$4$$$
$$$1 1 2 1$$$
$$$output$$$ : $$$2$$$
$$$expected$$$ : $$$3$$$
got it . thanks bro!
Why doesn't greedy method work for B?
https://codeforces.com/blog/entry/116396?#comment-1029378
I first misunderstood the statement, I thought that the order of operations did not matter( you could do +5 before +3 so basically could do operation j after i and i > j). Is there any way to solve this problem? I thought about it for about an hour but could not come up with anything.
You can solve it using prefix sums and going through all ways.
Could you elaborate? (to be specific, I thought that you could add -1, n , -2 and n — 1 to the same number in the array)
Almost all fu**ing educational rounds educate me not to give up in contest not cp
The difficulty gap between C and D problems in last 5-6 Div2 Educational rounds is too large imo. It's much more enjoyable to take part in an ordinary Div2 rounds.
Can't say I'll participate in these Educationals anymore.
how far is the Purple id ;)
Why it is unrated though my rating is still under 2100?
Just be patient, rating hasn't been updated for anybody yet.
Editorial please
is system testing is proceded?
how cound D1 and D2 hacked this much ????
I passed D2, but I got a TLE in D1, which is really frustrating. It really affects my experience.
Super strong pretests
Super strong pretests
Very weak pretests for D1 & D2 :( It's not just the negative answers, my submission FST'ed on a tc whose answer is +ve.
PS: I by mistake divided by 2 instead of n at someplace. After changing it, it's AC for D1&2. Frustrating.
From almost getting D2 to FSTing on D1, sigh!!
rating when
I also want to know
AAAAaaaaaaAAAAAAAAAAaaaaaaaaaAAAAAAAAAAAAaaaaaaaaaaaaaAAAAAAAAAAaaaaaaaaa
It always takes ages after Educational rounds. Might wanna check in like 6 hours or so, unfortunately :(
8 hours now,exactly
Ye it's 8 hours since hacking ended, but we had to wait like 6 hours after that to do the system testing and now we'll wait at least 6 more hours for rating. I agree that it's ridiculously slow — it's almost like someone is manually calculating rating changes in Win95 excel spreadsheet.
I've gotten Wa on 44 in D2 because of the corner case
n=1
.It's really a nice problem, but I think it'll be better if the corner cases are included in examples or pretests. It's a part of problem for sure, but isn't it a little cruel for us participants?
Actually, in this round, not only me, but also many other participants are truly educated. As for me, I'll check if there exists a corner case before submitting. From this perspective,it's educational enough as an educational round, I think.
For me, I will check the complexity of my code before the end of the competition.
Well corner cases are different for everyone. When I solved D2 (after the contest ended) n=1 wasn't a problem for me. I don't think it is that cruel having this case, as it is quite logical. What IS cruel is NOT including corner cases in the test cases, for example the possibility of the answers to the queries to be negative numbers, which caused so many hacks in D1 and D2. So in my opinion, it is better to have them no matter how annoying they might be for individuals. It is more educational to come up with what is wrong with your solution during the round rather than after, when you are frustrated because of the hack.
ok, I pull up!!!
I solved E in $$$O(n * k^2)$$$ with polynomials. But I saw that a lot of guys solved it with a much simpler idea in $$$O(n * k)$$$. How to do that?
We use the recursion :-
Given:-
Let us write:-
Now, observe that (use the {n \choose r} recursion to get this):-
This can be solved using DP in O(nk). However, the final solution required some memory optimizations to get accepted.
My Solution -> 205614318.
Solution of B Maximum sum solution with logic and explanation
https://www.devcp.in/2023/05/ecr-148b-maximum-sum-solution-in-cpp.html
At this point I am convinced that they're trolling with rating updates on purpose. I think it takes NASA less time to launch a rocket then it takes for Mike and his crew to update ratings.
As Mike said, they can update ratings at any moment. However, they don't do that because they try to find cheaters and remove them
Same, but me waiting for the editorial*
When will the editorial be released ??
How to solve D?
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
As a person who needs contribution, please give me some.
I wrote the same and got blocked :(
Hello
This contest was just amazing. Waoo :)
Candidate master!
Hello, Div.1! (Though it may send me back to expert.)
great round!
I saw few potential cheaters in this round and they are not skipped, is plag check done?
MikeMirzayanov
Why are the problems unavailable for this match? And the other ones as well..
Hello Codeforces,I just want to know why its always me who rating is been reduced due to same solutions and so on i just checked the submission of given id and i am sure that solution isnt the same please roll back my rating i been having tough time on codeforces this recent contest ..i request.
wtf man please roll back my rating
Got a plagiarism warning for problem A: solution 205553146 for the problem 1832A significantly coincides with solutions sriharsha_2000/205553146, akmalp/205556740.
I use a local environment. This is a coincidence and I can see many other submissions with similar approach (using set).
It took me some time to figure out the dp solution to problem E, and it was fun. I made a video editorial if anyone needs help, you can find it here