why your profile have negative rating?

+121? :o (btw i wanna get back to specialist after this contest, or at least stay at P)

Your already a blue.

1665 points to LGM, i can't wait :clown:

Hopes should be realistic bro

All the best bro

Even the number of colors you have may change! (By becoming lgm)

Thanks, anymore I don`t need your help, I have solved it

The score distribution will be published later.

Very good Question actually. Someone please answer this.

Read the statement.

same

from experience, they are aaround the same in difficulty. Div1+2A ~ Div2A.

yes

that means i have to rank about 1000 a little bit tricky..

I am also waiting for it

You can do it.

your hopes should be realistic

It's not about what others think it's about what you think.

It means Problem 6 is divided into two subtasks, where first one is worth 2000 points and second one 500 points. Second one is worth less because if you solve the first one, second one may be a bit easy after the knowledge you gain from the first. OR you may start second one directly as solving it will solve both of them at the same time.

Some observations I made:

Alice's strategy should be greedy

Bob must take all of the occurrences of a cake for his actions to be useful

Can we memoize based on position/turns?

solved using memoization (dp) ,logic is if bob has to remove any number than he remove all occurences of the number, calculate frequency of all element then store in a vector and do o(n^2) memoization (knapsack) you can see the memoization dp solution 268191223

I had the same idea but it failed on pretest 2 :(

What could be the problem? 268218168

Don't know what to do in CP, just try DP.

• Alice will eat one of each cake tastiness in ascending order except for those tastiness values where Bob can eat all the cakes before Alice reaches it.

• So for Bob the strategy is simple, he wants to pick the maximum number of tastiness values $$$t_1, t_2, ... t_k$$$ such that he can eat all of their cakes BEFORE Alice reaches the corresponding tastiness values.

• Since it is only optimal for Alice to eat them in ascending order, we can sort the tastienss values in ascending order and do a knapsack like dp on their counts. Let $$$dp_{i, j}$$$ mean that Alice has managed to eat $$$j$$$ of the $$$i$$$ smallest cakes and Bob has $$$dp_{i, j}$$$ remaining turns for which we haven't decided what cake he ate. Then the transititions just become:

  $$$1$$$. Alice eats a cake of the current tastiness and Bob gains another turn — $$$dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)$$$

  $$$2$$$. We use Bob's remaining previous turns to eat the remaining cakes (if possible) — $$$dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - cakecnt[i])$$$ (iff $$$dp[i][j] >= cnts[i]$$$).

Then the maximum $$$j$$$ for which $$$dp[n][j]$$$ is $$$\geq 0$$$ is clearly the answer.

I thought D felt similar to a priority queue simulation problem like this one, https://codeforces.com/contest/1974/problem/G , but I found doing take-not-take DP to be an easier approach

If $$$a_v \gt \sum a_{child}$$$, then we clearly need to increment $$$a_{child}$$$ for some child.

Notice that incrementing a node $$$v$$$ by $$$1$$$ means that we will need to increment some chain of nodes $$$x_1, x_2, \cdots x_k$$$ where $$$x_1 = v$$$, $$$x_i$$$ is a child of $$$x_{i - 1}$$$ and one of the following conditions is satisfied for $$$x_k$$$:

1. $$$a_{x_K} \lt \sum a_{child}$$$
2. $$$x_k$$$ is a leaf

Also observe that a given node can be used as $$$x_k$$$ by the first condition at most $$$\sum a_{child} - a_{x_K}$$$ times, while a leaf node can be used an unlimited number of times.

Moreover, such a chain results in a cost of $$$k$$$. So at any instant, we want to pick the shortest chain possible, i.e, pick a node least depth first among nodes in the subtree of $$$v$$$ which satisfy the above condition.

So we can just store the number of possible contributions at each depth for the subtree of each $$$v$$$ while iterating using dfs and use the above approach to fix cases where $$$a_v \gt \sum a_{child}$$$.

Code — 268172990

congratulations in advance

Congrats!!! DuongForeverAlone, But u were always the "Master"! and Best of Luck! for System Testing.

Great job, congrats

try debugging it on custom invocation

Maybe. Although I used O(n^2) approach, there possibly has an O(n) IMO.

Assume there's an array {t[1], t[2], ..., t[r]} and Bob need to let Alice can't eat cakes with tastiness t[i]. Then for each tastiness t of cakes, let f[t]=1 is Alice can eat it, f[t]=-cnt[t] if Alice can't eat it, then every prefix sum of f[t] must be non-negative. You need to find the maximum array size by DP.

Lets take frequency array F = {4, 4, 4, 3, 5, 5, 2}

Now, according to your approach :

• Alice {3, 4, 4, 3, 5, 5, 2}
• Bob {3, 4, 4, 3, 5, 5, 1}
• Alice {3, 3, 4, 3, 5, 5, 1}
• Bob {3, 3, 4, 3, 5, 5, 0}
• Alice {3, 3, 3, 3, 5, 5, 0}

now no matter what Bob does, Alice can choose 3 more cakes. So total 6 cakes. But, if Bob started with 4th cake type then he can also complete last cake type before Alice reach there. So, Alice only can take 5 cakes.

Simulate the process.

Try to find how the answer increase from [i+1....n] to [i....n].

If a_i is smaller than a_i+1, it means there must be some point where a_i equals a_i+1, and when a_i+1 becomes 0, the work is done between[i+1....n], and more importantly a_i is now 1.so ans++. If equal, ans++.

If bigger, it depends on what the current answer is. If current answer is bigger or equal than a_i, it still means there must be some point where a_i equals a_i+1, thus ans++. And if current answer is less, ans+=a_i-ans,which i guessed out.

Since h>0, it is enough with:

for (int j=0;j<n;j++) m=max(m,h[j]+j);

(find the height which is the most costly)

I just bashed it with brute force until it passed pretests (still can FST tho). I also considered small-to-large merging, but at the time I thought it was not going to work.

yes (at least the way I solved it)

solved D using simple memoization (just think if bob has to remove any element then he should have to remove all occurrences of that element and just do dp[submission:268191223]

For D:

Observation 1: Order does not matter, so move things around however we want

Observation 2: It is always optimal for Alice to eat the smallest cake, so we should sort the cakes

Observation 3: Bob should only eat a cake if he intends to eat all of those cakes of that level of tastiness

So with that, we can reduce this problem down to: for each type of cake (so we aggregate into tastiness, frequency pairs) in sorted order of tastiness, will Bob eat all of this type of cake or will Alice eat one of the cakes?

Let's think about the consequences of each action

Alice eats the cake: +1 to Alice's score, but Bob can eat 1 more cake

Bob eats the cake: Bob can eat $$$count[cake]$$$ fewer cakes, but Alice's score does not change.

Let $$$dp[i, j]$$$ represent the minimum number of cakes Alice can eat, starting with the $$$i^{th}$$$ least tastiest cake with Bob being able to eat $$$j$$$ cakes.

This leads to recurrences:

many problems are easy... once you know the solution

BTW, E could be solved easily in $$$O(n \log n)$$$ with small to large merging, just curious why was the constraint $$$5000$$$?

I suspect its to prevent irritating issues with overflows. Like, you need a leaf to contribute at least $$$n \cdot \max(a)$$$, but a node can sum to upto $$$n \cdot n \cdot max(a)$$$ which will overflow int64 for $$$n = 2 \cdot 10^5$$$ and $$$a_i \leq 10^9$$$. This is fairly easy to fix by capping the sum to $$$n \cdot \max(a)$$$ but its also irritating for no real reason.

Also, I personally feel that adding small to large merging doesn't make the problem any better, its a bog standard implementation of it.

I actually was convinced the greedy idea was wrong but it passed ~500 rounds / 2 mins of stress testing at $$$N = 16$$$ so I submitted the code, only for it to find a countercase 2 seconds after submission T_T

Sorry this might be dumb but what is random stress tester, is it different from stress testing we do?

What is the counterexample for that? I wasn't able to come up with or generate a counterexample and I still don't know why it isn't working :P

also curious if it is possible to implement G2 quickly and clean

For me, the number of cases was the same for G1 and G2. For G2 all I needed to add was if statements before some of the cases from the G1 solution.

When a contestant realizes there is a bug in their submission, and have not yet locked it, they should be able to resubmit. Naturally, the last such attempt will be tested.

If you want to submit an optimized version that shouldn't affect the standings, you can do it after the contest.

orz

I'm not first solve for A, sstrong submitted 2 seconds earlier: https://codeforces.com/contest/1987/standings/participant/185369380#p185369380

Found them by sorting by submission time.