I guess this is one of the most downvoted comments. I wanted someone to nominate me tho :(

Usually, I do not find interactive problems in an educational contest. Have you such an example where it happened recently?

If the contest has an interactive problem they should say in the announcement.

I would like to give you a downvote but because we are in the same community take an upvote.

• in Edu rounds the leaderboard is sorted Depending on how many problems you solve there is no score

• but what if there is 2 people have the same number of problems solve they will sum the times of them and sort it by the person who have less time

• but if person got 2WA on a problem then AC the sum of time will increase by 20 which will give him bad leaderboard place

Doma Umaru?!

because you couldn't solve C?

Isn't C just a standard dp?

what logic you apply while solve d ?

I can not solve c and d !!

How could you solve greedy problem more easily than the DP problem ?

If you don't mind me asking, what was the solution for D?

C was easy DP, maybe a little tricky to implement.

It's hard to use greedy for C, or even impossible (I actually think about a lot of ways to use greedy but I found lots of counter examples either, so just use DP is a better approach).

Hint: Think in reverse operation order. Suppose you include N elements and want to remove one, what's the optimal strategy for Alice?

The model approach is the following one:

If Alice chooses some subset of elements, then Bob will pick the $$$K$$$ elements with the highest values of $$$B_i$$$. If we sort the items by $$$B_i$$$, then this just means Bob will always pick the rightmost $$$K$$$ elements in any subset. Therefore, our array will become split into 2 partitions: the left partition's elements go to Alice, and $$$K$$$ of the elements in the right partition go to Bob (we can choose the ones with lowest $$$B_i$$$).

We can do the following: Iterate over the size of the right partition from size $$$K$$$ to size $$$N$$$, and maintain the sum of the smallest $$$K$$$ values of $$$B_i$$$ using a multiset. We then calculate Alice's profit as $$$\max(0, B_i-A_i)$$$ for all elements $$$i$$$ in the left partition, which we maintain with a prefix sum array.

Let's think of a strategy for Bob. If I take s elements (s>k) then he will choose s-k elements with the minimum b. That's obviously true because sum of a is fixed and to minimize the profit Bob will choose the smallest bs. Now, I'm Alice and I know that. Then I wiill check each b. If I fix some b[i], then for all b[j] such that j>i I will choose minimum k as from them. I know that since they are k and Bob will choose minimum bs, he will not choose from them. So now remains the elements in the prefix of i. Any element I will choose in this prefix, Bob will choose it too. So I want all positive profits in this prefix. I'm not sure if this is kind of a proof, but this was my though process.

I also had WA on 3, does someone have a counter example which I may have overlooked?

"wrong answer 14th numbers differ — expected: '14', found: '13'"

try for this test case:

4 1

1 1 3 9

3 4 5 15

here you will get 0 but answer is 2

Tip (to self, others):
Whenever changing limits like this for debugging purposes — it's probably best to add print statements alongside (so that you remember to fix this as well)
Alternatively, in languages where there is support for compiler-warnings, add those :)

Sigma

simple recursive 258735237

k is less than 10 so you can solve with 2D DP.

E can solve by Monotonic Stack in O(n),so the timelimit is enough. Code

$$$dp[i][j]$$$ = the minimum sum when we only consider the first $$$i$$$ elements, and perform $$$j$$$ operations. We can do $$$dp[i][j] = dp[i-1][j] + A_i$$$ to do nothing. Suppose we perform $$$x$$$ moves: we convert elements $$$A_{i-x}, ..., A_{i}$$$ to the minimum element in this range (call it $$$min$$$), and the new sum of this range is $$$(x+1)*min$$$. The minimum sum for the remaining elements can be obtained with $$$dp[i-1-x][y]$$$, where $$$y$$$ is the # of moves performed beforehand. Therefore, we do $$$dp[i][x+y] = (x+1)*min + dp[i-1-x][y]$$$ for all pairs $$$(x,y)$$$ where $$$x+y \le K$$$.

C is not too hard, but not too easy in this round. If you take a look at previous Edu round, it is something really different, so it doesn't mean high difficulty

Or you could do tmrw's Div. 2 and somehow solve A-D :)

why u lying?? ur 1. edu u solved ABC

sorry man

I believe it's my skill issue:) it was a good problem actually

hard to implement. Not hard to solve.

I'd say both are pretty obvious. Personally, I just found them hard to implement

We'll stay forever this way You are safe in my heart And my heart will go on and on

Pardon me if I'm mistaken, The time complexity of your code is O(t∗n∗n∗O(n)) = O(6∗10⁹). As inner clr(set) takes O(n) in every iteration.