+1

I know it would be controversial, coming from a newbie, however adding a point system in Educational rounds similar to Div2 rounds, but in a compressed manner, would have fared better. Experts would have focused on harder problems upto their level, while the newbie/pupils start from the easier ones and gradually peaking up...

The current system follows the number of solved problems and time penalty. While it's not bad, but why not something similar to Div2 round point system?

Apology in advance, if I am missing some obvious reasons.

I don't know why but it turns out that the people are desperate to make my situation as the meme guy lol!

The comment is deleleted)))

this is not youtube comment section.

You can always not participate if you do not like it.

If the customer wants 3 cans 5 // 3 is 0 3 % 5 is 3 so the customer will buy 3 cans one by one which is smaller than 5/2 = 2.5

(same thing if the customer wants 4 cans)

If you did greedy, it wont work.

Submission

it's dp. look at constraints, they gives hint in itself.

You can solve using Dynamic Programming . Sort the given array . The corresponding array of times will be also sorted and will be of size n .

$$$dp[i][j]$$$ — min answer having placed the first $$$i$$$ dishes in the first $$$j$$$ minutes.

First lets sort the dishes in non-decreasing order of $$$t_{i}$$$ so we can iterate on time in ascending order.

$$$dp[0][0]$$$ is clearly $$$0$$$.

Clearly at any state (where $$$i \lt n$$$) we can place the dish now, in which case $$$dp[i + 1][j + 1]$$$ = $$$min$$$($$$dp[i + 1][j + 1]$$$, $$$dp[i][j]$$$ + unpleasantness), where unpleasantness is of removing the $$$i$$$-th dish at the instant j or $$$abs(j - t_{i})$$$.

Or we can just not place it, in which case, $$$dp[i][j + 1]$$$ = min($$$dp[i][j + 1]$$$, $$$dp[i][j]$$$)

Dynamic Programming!

Sort the intitial oven times

Try giving time t to current index i note their absolute difference move forward for the remaining suffix and find the minimum sum of absolute difference of timings it can be done using bottom up dp easily.

Here

.

https://github.com/actium/cf/blob/master/1400/30/1437b.cpp

Another way is to count number of consecutive ones. Let this be K. Therefore, add K — 1 to the answer. Do same for zeroes. Answer is max of answer for one and answer of zero. 96876793

This is mainly because when we solve for 111000, we see that we actually need 2 moves.

First move => 100110.
Second move => 101010.

Try for higher strings like 11110000, you will notice the answer is always K — 1 for K consecutive ones.

I found D way easier than B (maybe because I'm more familiar with graph theory) Basically just give the nodes greedly and maintain the height (because if you try to store the tree you'll mle)

just count consecutive zeroes and ones and ans is max of both ,I learned the hard way :(

same feeling, couldnt solve B even after thinking more than 1.5 hr

Maybe B's time limit is a fact. I have tried a brute-force approach at the last moment and it passed with 1700+ ms timing. Now I am waiting to see if it can get a TLE in the system-test or someone hacks it.

B seems easier: https://github.com/actium/cf/blob/master/1400/30/1437b.cpp https://github.com/actium/cf/blob/master/1400/30/1437d.cpp

Here is an intuitive solution that worked for me.

For each consecutive pair of 1s, u have to insert a 0 between them and u will always have a "smart way" to do that in a single move(considering the fact that we have equal zeroes and ones). The same holds for pair of zeroes as well.

Doing it for a single pair of 1s, also do the job for a single pair of 0s. So count the consecutive 0s(00)-> cnt0 and 1s(11) -> cnt1, then max(cnt0, cnt1) will be the answer.

Hope it helps.

At this kinds of problems, you usually want to search for alternative statements that are more helpful. We can see that we could reframe it as: given a string s consisting of n/2 0's and n/2 1's, lets define f(s) = the number of i for which s[i] = s[i + 1], 1 <= i < n.

To make s alternating, we want to make f(s)=0.

A reverse operation changes f(s) with at best 2. So f(s) can be decreased with at most 2 in one operation. A lower bound for the answer to this problem is ceil(f(s)/2).

Now we only have to prove that you can always decrease f(s) by 2, excepting the case where f(s) = 1.

if f(s) > 1, then we will always have at least a pair of consecutive 0's and at least a pair of consecutive 1's. So we can just reverse the substring cotaining one of this 1's and one of this 0's and decrease f(s) by 2.

For example s = 01001011,f(s) = 2. we have the 0 pair (3,4) and the 1 pair (7,8). So if we reverse (4,7) we get 01010101.

If f(s) = 1, than the string will have to be either 0101..0110101...1010 or 1010....1001...0101. So you can reverse a prefix/suffix and decrease f(s) by 1, arriving at f(s)=0.

Educational rounds do not have the same hacking feature as div2 or div1. You can hack after the contest, but you'll not get any points for that.