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 =)
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 ;)
As a cyan tester,I recommend you to see all problems.
As a cyan participant , I recommend you to see all problems.
Hope for the _Best_
Give your _Best_.See you in standings!!
You stole my profile picture bro : /
Hoping for a nice contest
It is my first codeforces contest, please say good luck to me.
Good luck. Are you a singer?
Are you minion??
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
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
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.
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
How to solve D with Binary Search?
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.net/contest/1832/submission/205604237
I had to remove consecutive duplicates for it to work properly
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
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
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.
Was it intentional to not keep keep negative answers in test cases of D?
https://codeforces.net/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$$$
Why doesn't greedy method work for B?
https://codeforces.net/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)
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.
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.
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 :(
Candidate master!
Hello, Div.1! (Though it may send me back to expert.)
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