Codeforces Round #831 (Div. 1 + Div. 2, based on COMPFEST 14 Final) Editorial

Pyqe's blog

By Pyqe, history, 3 weeks ago, In English

Tutorial of Codeforces Round #831 (Div. 1 + Div. 2)

3 weeks ago, # |

I solved E it without using dp, if someone could prove why it works that would be great or maybe provide a counter testcase.

Approach

3 weeks ago, # ^ |

Interesting. You constructed the array s,right?

3 weeks ago, # ^ |

can u explain your approach ? I have tried this question in building the array just like you

I noticed the thing that if we take a given node "X" ,then nodes in the longest path from root to a leaf in a subtree where "X" is root can be made to same value.

so I came up with approach something like this For Each level, For Each node in that level lets say Y, I added up the length of longest path from the node Y to the leaf

After getting answer for all levels, I took the max of them but i am missing something.

3 weeks ago, # ^ |

My approach is simply instead of randomly going to a subtree I choose the one with the deepest node and when we have visited all vertices in its subtree I assign a value and push the subtree min in sequence and calculate its LNDS.

3 weeks ago, # ^ |

your explanation is not clear. whose subtree? what do you do with the subtree you choose? what value do you assign?

3 weeks ago, # ^ |

← Rev. 6 →

Sorry if my explanation wasn't clear enough I will explain it more thoroughly. So I'm maintaining a timer variable that will assign a value to each node, it is initialized to 1. Now we start by traversing a tree in dfs order but we assign a value to a node only when we have traversed all nodes in its subtree and the value that gets pushed into s is the subtree minimum of that node then we increment the timer variable. Now for traversal let's say we are at a node x so instead of randomly visiting a node in its subtree, we will start by visiting the subtree with the deepest node(maximum height) first. So for that I just calculated depth of each vertex and took the max depth (height) for each node and just sorted the adjacency list for each node based on their respective height in non increasing order. Finally I just calculate the LNDS of the s sequence that we created.

178446226

3 weeks ago, # ^ |

← Rev. 2 →

It works the same as the dp solution. let a[v] be the lnds of v's subtree. a[v] is either the concatenation of a[c_i] for all children c_i of v, or the path from v to its deepest child, whichever is longer. the length of a[v] is equal to dp[v].

3 weeks ago, # ^ |

Oh got it thank you.

3 weeks ago, # ^ |

How are we deciding the permutation a?

2 weeks ago, # ^ |

Can you please write the full form of LNDS?

2 weeks ago, # ^ |

Longest non-decreasing subsequence.

3 weeks ago, # |

How to prove the first statement in the editorial for problem F?

3 weeks ago, # ^ |

Well, the first thing that helps for this problem is to consider that all multisets have the same size, which is . Simply, add additional zeros representing empty sets until you have numbers in the multiset.

One possible way in which we realize that such a condition is equivalent and can prove it is to note the following: If we are able to createe a multiset we can always move elements from a bigger set to a smaller one and still maintain a valid configuration. The reason is that in there are at most elements that are already in , so the rest, can be moved to if it is necessary.

This implies that if we consider the multisets sorted, which is what makes more sense, we can always move elements from to . Thus, if a configuration is valid, so is any configuration with . And this is the key to the problem. We do not need to consider all multisets, only those that are maximal in this sense. And then we can count how many elements they have below them.

By the way, once we get that formula, it makes no sense to keep considering the multisets in the way we are doing it. Instead, use the sequence of accumulated sums to represent the multiset. Then the condition becomes for all , which reads much better. Hence, our multisets are represented as increasing sequences with decreasing . Or even better, as increasing sequences wiith , and decreasing .

The question is, which multisets are maximal? Two multisets are not comparable if and for some indices and . But... well, this was of little help for me. So, I thought: at the very least I know that the biggest lexicographically is maximal. Which is the biggest lexicographically? Well, if we try to fit as many possible numbers in the first set, we will have . Then, we will substract from every and repeat. In the end, we get the multiset . (And the right hand side is precisely the formula of the statement. This, along with our previous observation, proves that the condition is sufficient.)

However, now that I know the formula I also know that we cannot make another maximal multiset, because for we can only use at most occurences of each number . That means for all multisets . Thus, the lexicographically biggest multiset is, actually, the only maximal.

Ending note: Yes, we can prove necessity from the very beginning and sufficiency if we consider the lexicographically biggest multiset and the first observation, without any notion of maximal elements. However, I am not sure one would get there magically. Instead, I believe the first observation must lead us to think of maximal elements and then we can either guess that there is just one or simply deduce it as it has been shown.

9 days ago, # ^ |

Why do we get in the formula for ? I get the part of , but not the reason for the i. Is like we're telling we are repeating an element in one of the set we built right? but this should then be invalid

9 days ago, # ^ |

Well, if you want to make each element the largest possible each time, you take one element from each set with one element, which is why . Then, you substract one from each set and get

because you took at least $i$ elements from each set already.

Then, by induction, if you suppose , you get

which equals

9 days ago, # ^ |

I see, I think what I didn't get is that is cumulative

Thanks

3 weeks ago, # ^ |

You can conclude and prove this lemma with mincut maxflow — if you try to find a maximum matching between a chosen multiset of sizes, and the frequencies of the elements, then try to find the condition by which all cuts are of size at least .

It's pretty lengthy (I can elaborate if you want), but you can arrive at this condition without magically guessing it (the magic here comes from the magic of MCMF).

3 weeks ago, # |

My logic is exactly the same as the editorial but giving WA at tc 2

sol link: https://codeforces.com/contest/1740/submission/178662191

can someone please help me... thanks

3 weeks ago, # ^ |

I think it should be > as even if we have filled all slots we can remove some in next iteration and if we don't we will report that ans don't exist

3 weeks ago, # ^ |

is right. try it and I'll explain it to you.

3 weeks ago, # ^ |

okay okay , i got it i am so dumb(the reason i am pupil)

Thanks a lot :)

3 weeks ago, # ^ |

Take a look at Ticket 16402 from CF Stress for a counter example.

3 weeks ago, # |

What is and in the first statement in the editorial for problem F?

3 weeks ago, # ^ |

Now edited to make it clearer.

3 weeks ago, # |

In Problem E, can anyone explain why we would ever do this? ->If card i is used in the longest non-decreasing subsequence, then the maximum answer is the maximum value of dist(j,i) for all j∈Di.

Can someone give a small counter example where doing just this (->If card i is not used in the longest non-decreasing subsequence, then the maximum answer is the sum of dp values of all of the children of i.) will fail.

3 weeks ago, # ^ |

you can consider a stick tree. where 1->2->3->4 here it always makes sense to select a root node as we can never get the better answer by excluding the root.

3 weeks ago, # ^ |

← Rev. 3 →

I did consider this case in my dp. I did this. My code failed anyways.

if(adjList[u].size() == 1) dp[u] += 1(Below is the dfs)

void dfs(int u, vector<vector<int>> &adjList, vector<int> &dp){
    int answer = 0;
    if(adjList[u].size() == 0){
        dp[u] = 1;
        return;
    }

    for(int v: adjList[u]){
        dfs(v, adjList, dp);
        answer += dp[v];
    }
    dp[u] = answer;
    if(adjList[u].size() == 1) dp[u] += 1;
}

Thanks

3 weeks ago, # ^ |

Take a look at Ticket 16403 from CF Stress for a counter example.

3 weeks ago, # ^ |

Thanks! Got it. I made a mistake with my reasoning.

3 weeks ago, # |

In my opinion, the editorial gives the conclusions more than proof or explanation for them, with many sentences like "We can observe/see/obtain/ that ...".

3 weeks ago, # ^ |

Agreed. Now, some of the editorials have been edited to give more explanations about the claims and conclusions. I hope they are more helpful now <3

2 weeks ago, # ^ |

Thanks! Truly more helpful.

3 weeks ago, # |

I think the time complexity in C problem would be O(nlogn) the writer forgot that he assumed that the elements are sorted . ( Though nlogn will do the work but still )

3 weeks ago, # ^ |

It is fixed now. Thanks for pointing it out! <3

3 weeks ago, # |

Imho, complexity of problem D is O(n). There is just iteration over an array.

3 weeks ago, # ^ |

Yea, my solution also runs in O(n). However, I think the priority queue solution is more intuitive to explain and understand. Thanks for mentioning that!

3 weeks ago, # |

Problem E is inclusion-exclusion question which is cleverly written

3 weeks ago, # |

← Rev. 4 →

+25

In D, let's say we have the grid:

where x are empty cells. If we can move any card to any cell, as long as there is an empty cell, could someone explain how we could move 4 to the cell where 5 currently is — cell with coordinates (3,1) ?

3 weeks ago, # ^ |

You can't but you don't need too. Cards only move if they are the current next card going to the exit or as part of a rotation to let another card past (so you'd never need to move from one 2x2 square into the other). As long as there is an empty square any card can reach the exit which is all that matters.

3 weeks ago, # ^ |

Nice catch! We actually did not realise the possibility of that. The tutorial has been edited to have a more correct claim.

3 weeks ago, # |

← Rev. 2 →

+20

Very pleasant round to participate in. Liked E and F a lot. C and B were also pretty nice. Looking forward to see more rounds from you!

3 weeks ago, # |

← Rev. 2 →

Can somebody explain C in a some other way ? Greatly appreciated <3

2 weeks ago, # ^ |

← Rev. 2 →

Q: What is the maximum difference you can get?
A:

Let's call this difference . You can get for by placing all elements with value in one of the first two slots, then placing all elements with value in the other. Now iterate through the array and find the minimum value of . Let's call this value . Now iterate through the array and find the minimum value of . Let's call this value . The answer is then .

Why? For the second difference (), to achieve , you can place all elements with value in the second slot, all elements with value in the first slot, and the rest of the array elements in the third slot. To achieve , just interchange the elements in the first two slots.

Edit: there is one case that is not handled — if after selecting the elements for the first two slots, there are no more elements left for the third slot. In this case, for the third slot, we select one of the elements in either the first or second slot, whichever maximizes the second difference. The answer in this case is .

In fact, this solution works in but the one in the editorial is probably faster in practice.

11 days ago, # ^ |

← Rev. 2 →

Hii [user:@WaisKamal], I try to solve this with same approach u mentioned above but still i'm getting WA in test case2. Can you please look into my code.

10 days ago, # ^ |

applied the same approach got the same WA similar to yours even though the approach looks correct acc to me

10 days ago, # ^ |

hey got the issue check code for 1 2 52 53 72 hope you can spot the error in the logic :)

9 days ago, # ^ |

Hii yogendra, i found error in my logic. Thanku for helping me. And i still thinks above approach explained by @WaisKamal is wrong. is it?

9 days ago, # ^ |

Yes as according to above logic this example should give diff answer(lesser).

3 weeks ago, # |

← Rev. 3 →

+10

Did anyone solve problem I like this?

Start from editorial's O(nm^2) knapsack

Lets say you have dp[i] after considering . divide into line segments. let the kth segment is for

Then can be calculated in O(mK) using deque or something to find range minimum

so in total it will be O(mn)

3 weeks ago, # ^ |

Yes, it can be done in .

3 weeks ago, # |

← Rev. 2 →

In problem E, why is ai>maxj∈Di(aj) true in the optimal solution?

Edit: Its clear now, thanks for editing the editorial

3 weeks ago, # |

For que 5 I thought of a solution where the answer will be (no of nodes — no of nodes with more then one children). It fails on test case 6. Can anyone please provide a counter example, I am unable to think of one.

2 weeks ago, # ^ |

6 1 2 2 2 2

2 weeks ago, # |

Animations like in D helps understand better

2 weeks ago, # |

In problem F, I got AC by (Though it can be optimized to easily).

Too weak system test or too high efficiency?

Submission

11 days ago, # |

Only by using nuclear weapon to inflict pain and suffering on Ukrainian people and their leaders, Ukraine as a country will be able to remember things!

29 hours ago, # |

181379852 Can anyone tell me what is the problem with my submission, it seems to be working fine to me, but is unable to pass test case 2

5 hours ago, # ^ |

Take a look at Ticket 16435 from CF Stress for a counter example.

Pyqe's blog

Recommend

乔思伯发布新款N2 NAS机箱：5盘位NAS迷你铝机箱 - 超能网

京东徐雷：推动实体经济实现‘质’的有效提升和‘量’的合理增长

Upcoming tactical RPG Fire Emblem Engage turns its back on its predecessor

Samsung is bringing Xbox and Nvidia cloud gaming to more of its TVs

6 weeks with Apple Watch Ultra: What's great and what needs work

消息称英伟达RTX 4090显卡已卖出 13 万块，比4080更好卖

SAP Tech Night Bengaluru – First edition November 25th 2022 #sitBLR

Change Dimension Values of Restricted Measure via Script

京东集团公布2022年三季度财报携手厂商共推趋势家电助推行业持续增长

SAP CustomerCheckout Table Service Menu

About Joyk