Ready to get +DELTA (◠‿◠)

awoo's round.

As a participant, give me a contribution.

As a cyan tester,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_

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.

I'm ready to get educated.

I hope everyone achieves great success.

crazy standing XD，but Why did more people pass E than D

bad round :dislike:

Editorial for problem C:- Link

How to solve D?

I really enjoyed this round. The dynamic programming idea behind E is so fun!!!

ABCforces

is E convolution?

E: orz to Nyaan's extremely fast Convolution (Large)

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

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.

wtf is D

I think problem E is interesting, even if I didn't solve D or E. Can anyone explain the idea of problem D? Thanks!

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.

Spent last 1 hour 54 minutes doing recursive dp . TLE with memo array and MLE with memo map . Some different idea involved in B ?

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

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.

10 minutes after contest, >20 hacks on D :)

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?

Whoever hacked my submission, I hope you have a bad day.

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.

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

Why doesn't greedy method work for B?

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.

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?

Editorial please

is system testing is proceded?

how cound D1 and D2 hacked this much ????

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'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.

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?

Solution of B Maximum sum solution with logic and explanation

https://www.devcp.in/2023/05/ecr-148b-maximum-sum-solution-in-cpp.html

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.

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.

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