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

nlogn is intended, nlog^2 or nsqrt can pass if written carefully enough but I highly doubt sqrtlog can pass.

Just make Aho-Corasic, and calculate link2(v) = link(v) but only with ends of strings. Now u just go left-to-right in some string of query. After adding some char, you have node V, u must check every suffix, that's end of some string, of this node. U can do it with link2(v). It works O(q * sqrt(5*10^5)), bcs u have only sqrt(5*10^5) different lengths of strings;

Please put code in spoiler tags

code looks very dirty... plz polish up

whats the solution of D???

• We may assume the array is circular.
• An alternating array has no monochromatic adjacent pair (like 00 or 11).
• If the array is not alternating, there are always two adjacent pairs 00 and 11. We can remove both of them in one operation.
• Every operation removes at most two adjacent monochromatic pairs.

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

O(NlogN)

I solved it in $$$O(n log(n))$$$, if LIS is required to solve it I don't think it can be any better.

Your approach is correct Maybe you glitched your code or failed maintaining the height ?

Here is my code which AC https://mirror.codeforces.com/contest/1437/submission/96920232

For this test case-

8 1 2 3 8 7 6 5 4

Answer should be 3 your code is giving 1 . I might be wrong

1 as root

2 3 5 6 can all be childrens of root

4 can be a child of 2

so overall the height is $$$2$$$

The easy way to describe the answer is to calculate the number of increasing sequences, and in each sequence count the number of elements in it.

In each node, you can put an entire increasing sequence as the children of it. and now the number of nodes for the next level increases by the number of elements in the increasing sequence.

for example this: $$$1, 7, 8, 5, 6, 2, 3, 4$$$

$$$[7, 8]$$$ $$$[5, 6]$$$ $$$[2, 3, 4]$$$

so $$$[5, 6]$$$ will be a child of $$$7$$$ , and $$$[2, 3, 4]$$$ will be a child of $$$8$$$. and now for the next level you have $$$5$$$ nodes namely $$$[5, 6, 2, 3, 4]$$$.

I hacked my solution, ez.

If there are at least $$$2$$$ positions to fix, there are always indices $$$x, y$$$ such that $$$s_x = s_{x+1} = 0$$$ and $$$s_y = s_{y+1} = 1$$$.

Proof by contradiction: suppose wlog that $$$s_i = s_{i+1} = 0$$$ is false for each $$$i$$$.
Let $$$z_i$$$ be the position of the $$$i$$$-th $$$0$$$. Then, the inequality $$$2(j - i) \leq z_j - z_i \leq 2(j - i) + 1$$$ holds.

But there are two positions to fix, so $$$z_{i+1} - z_i = 3$$$ should hold for two indices $$$i = a, b$$$, $$$a < b$$$.

Then $$$z_{b+1} - z_a = (z_{a+1} - z_a) + (z_b - z_{a+1}) + (z_{b+1} - z_b) \geq 3 + 2(a + b - 1) + 3 = 2a + 2b + 4$$$.

But $$$z_{b+1} - z_a \leq 2(a + b + 1) + 1 = 2a + 2b + 3$$$ (contradiction).

So $$$x, y$$$ exist, and you can fix $$$2$$$ positions by reversing either $$$[x + 1, y]$$$ or $$$[y + 1, x]$$$.

My solution was also intuitive , although I didn't consider it as a cycle. I counted positions where $$$s_{i}=s_{i+1}$$$ and $$$ans = (cnt+1)/2$$$. No idea why this works either but it just seemed right and it passed. Was able to solve B in just 4 mins. Felt really good after failing terribly in the Techno Cup :)

Hey I didn't participate in the round, so don't know if this solution is correct. But maybe can help with intuition.

Keep a count of number of chunks of 1s(c1) and number of chunks of 0s(c0). When we reach n/2 chunks each of 0s and 1s, we are done. In one operation if you reverse a sub-array starting and ending in different bits you can increase both c0 and c1 by 1 potentially (potentially coz that won't happen on the ends). It can be proved that while there are more breakable chunks of 0s and 1s there are sub-arrays ending in opposite bits that break these chunks, incrementing both c0 and c1 by 1. You may need one extra operation if you have an almost alternating sequence but with just c1 = n/2 — 1 and c0 = n/2 or vice versa. With this you can see that you will need max(n/2 — c0, n/2 — c1) reversal operations.