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

I done a and b , have you done c ?

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 ?

do you know how to find the testcase which went wrong? as if there are many testcases it is not shown in the submission

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

I tried difference (Greedy) too, in quite different ways, making array of differences, modifying original array and difference array on each iteration, counting max difference and keep on deleting from the sum. But there is one thing greedy doesn't account for ie repetition in similar differences. Example --> n = 4 k = 2, a = [4, 8, 5, 1] the differences are 4, 3, 4. You chose the first 4 to change, new array is [4, 4, 5, 1] next you choose last 4. final array --> [4, 4, 1, 1], sum = 10 Now in case you choose last 4 to change --> [4, 8, 1, 1] now you choose the difference 7 which gives --> [4, 1, 1, 1], sum = 7.

I haven't practiced DP but as far as I can see from solutions, people tend to be doing similar thing using DP ie a 2D array to keep track of all changes. (I might be wrong on the DP logic since idk how to use DP). But the problem in greedy you faced is same as mine and I presume many more got stuck here.

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.

I did the same but got WA 5 times

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

do dp range and the cost is the min element in range * length of range

$$$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

we pretty much used the same approach , but the problem meant to be solved using DP and not greedy

are you using greedy? well, this case doesn't work for greedy

5 4
999 999 2 3 1

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.

std::set has a lot of overhead as it uses a tree structure, so you end up using a lot of time allocating and deallocating memory, rebalancing the tree, etc.

My solution is the same, but the only difference is that you clear the set, I define a new one each time. I think this is the reason why you take more time on the original tests and got hacked.

It's a RTE

A generator must be deterministic, that is, it must produce the same output every time it's run. If you use RNG, you must set a random seed.

Just think about test case 1 3 2 1 2 6

U will get your answer

T= 1 N= 3 K =2 Arr: [1 2 6]

You are applying a greedy algorithm, i.e. merging the immediate best, rather than doing a deeper search.

For example,

1 5 2 20 10 19 28

Your algorithm will see the largest difference (20-10) and merge them, and then merge 19 together, totaling 10+10+10+28 = 58. but the optimal solution would be 20+10+10+10 = 50

reject memoization, embrace tabulation

It's a stack.

let st[i] be the largest j so that j < i and the subarray [j, i] is not unique (if j doesnt exist, st[i] = inf).

Now, if st[i] < i (for i = 1 -> n), we have a segment [st[i], i], now the problem becomes: calculate the minimum number of black points so that each segment contains at least 1 black point. It's easy to solve using deque and dp.

made a mistake, but set has a high overhead for each operation.