What is sweet? I don't see any sugar here...

vovuh is the best div.3 problem setter

Fortunately we already had a problem on this algorithm in 2018. KGP18ROL ICPC Regionals 2018 problem SORTALGO.

Btw I like the way of describing the algorithm.

Don't make jokes like that.

.

Don't even do a single pass just make a list with the first element of the original list. A single element list is always sorted.

The last element must be Stalin himself.

But for Chinese,we have to stay up late more night...But it worth that!

Congrats!

No :)

Yes, the round is rated for anyone below 1600 rating, including those who are still unrated/haven't participated in any rated rounds.

Greetings everyone, I, as the writer of this comment and a completely new account that is obviously not an alternate account of another very high rated person on the platform Codeforces, find the website of codeforces.com particularly confusing and novel. Because there seems to absolutely nothing in the statement that tells me if this round has a probability of affecting my rating, I request that one of the more experienced members such as (insert annoying tags of lgm) tell me if the codeforces round of the number 661 variety could possibly have a nonzero probability of affecting my rating

There is no need to worry about anything. In fact, nobody cares if you participate or not, or for your results. Just relax, and enjoy the time.

Register the contest. If you are contestant then you are rated. Unrated if you are Out of Competition.

I think you'll be rated if your presented rating is lower than $$$1600$$$.

is there a way to see your hidden rating?

For any wrong submission you will gain 10 minutes penalty. Penalty is used to rank contestents with same number of solved problems.

My profile picture is a tree :-).

Don't know why it came in the middle of contest. It usually comes at starting.

but it will not let hard word of people be soiled like mine. what else do you expect?

Exactly Same Bro.

I also thought the same

I coded the solution of E1 thinking this was the problem. Then noticed that, the second sample case doesn't match with my "correct" output.

Same here bro, just read the problem again after reading your comment , maybe its high time for me to get glasses

I do not get it. We had to find the minimum number of moves in which we select an edge and divide its weight by 2, such that at the end, path weight from root to all leaves is at most S. Is that not it? Or I misunderstood the question? Because for some reason, I cannot understand why that second TC has answer of 8.

Looking for the solution in the comments and saw this, I feel so dumb...

Same lol, was thinking why is the third hardest problem in a Div3 contest that hard.

i solved D and i couldn't solve C :( , please anyone can help me?

After calculating the value just greedily take the vertex that gives biggest delta(v). delta(v) = (num[v] — num[v] / 2) * leaves[v] where leaves[v] = number of leaves in subtree of v.

Run a DFS to store, how many leaves are there in the subtree of a node

Now store {impact, index} of each edge in priority queue

impact for edge {a,b,w} (a is parent of b) is $$$sub[b] * (w - \frac{w}{2})$$$

Greedily calculate the answer.

you can solve it using std::set

Binary Searcch! IF number of subsequence is k and the answer exist then with k+1 subsequences partition to the answer exist , this was key intuition behind this problem.

Maintain two sets v[0] and v[1](initially both empty). v[x] denotes the set of all those subsequence ids for which the next expected number is x. Iterate through the string. Let's say the current bit is 0, then if v[0] is non-empty, take out one of the element of v[0] and put it into v[1]. If v[0] is empty, create a new subsequence and insert it into v[1].

Time complexity: O(n) using vector.

At any point you should be knowing if a particular sub-sequence is having 0 or 1 as its last element

this can be done with the help of set. Just make 2 sets for 0 and 1

Then when iterating through string if the element we need to work on is 0 than check if there is any sub-sequence with last element 1. Than we can insert 0 in that sub-sequence than update our set of 0 and 1. If no such sub-sequence exist than find the maximum sub-sequence we are having right now and add 1 to it and update our sets one again.

this is O(n) solution https://codeforces.me/contest/1399/submission/89002346

Your code provides WA for this case: 011011

try this test, you will get where you are going wrong

5
11011

Nice English, dude.

The sum of the weights of all paths from the root to the leaves should be at most $$$S$$$.

You're using memset t times which will tle if t=2 * 10^4.

Try this test.

5
11011

I made the same mistake, at this line: PriorityQueue<long[]> pq = new PriorityQueue<>((o1, o2) -> (int) (o2[1] * o2[0] - o1[1] * o1[0]));, your comparator should maximize the amount reduced per operation, (weight of edge + 1) / 2 * number of leaves in subtree, not the amount the edge is currently contributing to the sum. There's a difference between the two.

My Submission

Yeah! the rating change will be more or less the same as shown by that predictor. Kudos! you did a great job today!

https://github.com/actium/cf/blob/master/1300/90/1399d.cpp

I used two queues, very short implementation

Here is your accepted code 89057458

I am not sure but I think for set lower_bound(a.begin(),a.end(),x) works in linear time.

you need to use a.lower_bound(x);

Idk what ur approach is but it's supposed to be pure dp. Maybe you are allowing segments to intersect inside of one?

I can try to explain and prove my solution ^_^

Let's define impact of an edge as $$$(w-\left\lfloor\frac{w}{2}\right\rfloor)*l$$$, where $$$w$$$ is the current weight of that edge, and $$$l$$$ is the number of leaves in the subtree of that edge. So $$$w$$$ occurs in sum $$$l$$$ times.

Now let's find out, after performing, say, $$$i$$$ moves on edges with $$$c==1$$$ and $$$c==2$$$, the maximum sum of impact we can obtain. The resultant sum obviously decreases by sum of impact.

Now, we do dp. $$$dp[i].first=max(dp[i-1].first+b1[dp[i-1].second.first+1], dp[i-2].first+b2[dp[i-2].second.second+1)$$$

where, $$$dp[i]=$$$ {maximum sum of impact for cost $$$i$$$, {number of moves with $$$c==1$$$ type edges, number of moves with $$$c==2$$$ type edges}}

$$$b1[j]=$$$ maximum sum of impact with $$$j$$$ moves of $$$c==1$$$ type. Similar for $$$b2[j]$$$.

Now an insight: The number of moves is bounded above by $$$nlog(nW_{max})\leq50n$$$ for the given constraints.

So now we can just do linear search and output the answer just when sum$$$-dp[i].first$$$ becomes less than or equal to $$$S$$$.

Even though DP relation is intuitive, here is the proof:

Obviously, the $$$j^{th}$$$ move can either be $$$1$$$ or $$$2$$$ type, so we max over those. Now, lets say for $$$1$$$ type, we do not take the $$$(dp[j-1].second.first+1)^{th}$$$ $$$1$$$-type move:

UPD: A part of the previous proof was wrong. Here is the complete correct proof for the DP recurrence.

Structure theorem: Let number of $$$1$$$ and $$$2$$$-type moves $$$(n_1[i], n_2[i])$$$. Then for adjacent elements

$$$|n_1[i]-n_1[i-1]|\leq1$$$

$$$0<=n_2[i]-n_2[i-1]<=1$$$

(can be proved by easy induction)

From here, we can easily compare the optimal solution and the solution of our DP+Greedy.

This proof took me very long (almost all night) so please upvote if you found it useful ^_^ 89052626

1
8
5 5 1 5 1 5 8 2

Your code give 2, but it should give 3.

Yes

You do same solution as same E1 except with two different priority queues, one for each cost, storing amount in vector after x turns, then just do 2 pointers.

My messy solution for E2 using just greedy approach with 2 priority queues 89027488. Not sure if it really works though.

E1 and E2 can be solved using the same approach, with some extra work in E2. I didn't use priority queue though. In E1, I sorted all the contribution of all edges. Now the problem is what length of prefix of this sorted list you need to take to make the total weight $$$\leq S$$$.

In E2, I made two different sorted list, each for one of the two cost types. Now for each prefix length $$$k$$$ of the first list, find out the cost of taking $$$k$$$ moves from this list and remaining from the other list. The minimum cost is the answer.

My approach was as follows: possible values of s are 2 to 100 for each possible value of s I tried to find the possible pair count based on the given weights and finally took the maximum.

https://codeforces.me/contest/1399/submission/89041975 Hope it helps!