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.

Hope for the _Best_

I hope after this round I will stop being a prisoner of the blue

Hoping for a nice contest

It is my first codeforces contest, please say good luck to me.

I'm ready to get educated.

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

bad round :dislike:

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

ABCforces

Shiit, needed 1 more second to submitttt

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

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.net/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.

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.

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?

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 gained +74 delta! Good round.

@MikeMirzayanov I'm confused for rejudge system. in last round,my submission status is ac,but become ce after rejudge. at the same time,i submited using the same code,but it passed again

code in the game https://codeforces.net/contest/1832/my same code after rejude https://codeforces.net/contest/1832/submission/205814566

Candidate master!

Hello, Div.1! (Though it may send me back to expert.)

Ok

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