In problem B tutorial, it should be "odd positions in alphabet ("aceg…") and even positions in alphabet ("bdfh…")", instead of "odd positions in alphabet ("acef…") and even positions in alphabet ("bdgi…")"

in problem c we dont need to binary search the result, just make $$$2$$$ pointers $$$l=0$$$ and &r=n/2& and always try to match the current $$$l$$$ value with the next valid $$$r$$$ value? code

wonderful tutorial thank you awoo, we appreciate your effort

Problem C. Why does my java code fail? https://mirror.codeforces.com/contest/1156/submission/53668587

I love the solution for E, great task ^^

In B, complexity is not O(n), it is O(n log n) for sorting.

can someone please explain the proof of the problem C a little bit more? I didn't get it from the editorial.

Problem E

In fact this problem can be solved using Divide and Conquer. :)

Let's consider all the subsegments $$$[l',r']$$$ whose left bound $$$l'$$$ is in $$$[l,mid]$$$ and whose right bound $$$r'$$$ is in $$$(mid,r]$$$ ($$$l,r$$$ and $$$mid$$$ are known in this part of the Divide and Conquer) . When $$$l'$$$ moves from $$$mid$$$ down to $$$l$$$, we can know the rightest pos satisfying $$$\max_{i=mid+1}^{pos}p_i<\max_{i=l'}^{mid}p_i$$$ (it is certain that they cannot be equal) using a pointer $$$rpos$$$. And we are now looking for those $$$r'$$$s. When $$$mid<r'\leq rpos$$$, the maximum value is in $$$[l',mid]$$$. Now $$$l'$$$ and the maximum value (let's call it $$$maxn$$$) are fixed, so we check if the $$$j$$$ whose $$$p_j$$$ is $$$maxn-p_{l'}$$$ is in the range of $$$(mid,rpos]$$$ and update the answer. When $$$rpos<r'\leq r$$$, the maximum value is in $$$(mid,r']$$$. Let's solve this part of the problem offline. When we enumerate $$$i$$$ from $$$r$$$ down to $$$mid+1$$$, we put $$$maxn-p_i$$$ (where $$$maxn=\max_{j=mid+1}^i p_j$$$, which can be got very quickly) into a bin and for an $$$l'$$$ whose $$$rmax+1$$$ is just $$$i$$$ we calculate how many times we put the value of $$$w_{l'}$$$ into the bin.

The time complexity is $$$O(n\log n)$$$.

Code: 53674474

I don't quite get why the mentioned solution for problem E is O(n(log(n)). Can someone explain more ?

here is my solution for D that uses DP on Trees. The implementation is extremely simple, but the transitions are more complex to come up with. 53644201

I think problem C doesn't need a binary search. A single loop solves the task. Look at my submission 53648314

could anyone help me to understand "if(siz[w][x] < siz[w][y]) swap(x, y);" what mean this code ?

i found that just like Union Find's rank unite, when i delete this code , i got ac too(even faster).

But if i delete this code, i think it will change the size of siz[0][i] or siz[1][i], maybe when i calculate the root "if(par[0][i] == i) ans += (siz[0][i] — 1) * 1LL * siz[0][i];"

and got wrong answer.

In B why do we have to check whole list cant we check only at junction of odd and even array?

Problem E,you can use Sparse-Table and Union-Find. https://codeforc.es/contest/1156/submission/53700970

Two things need to be proved are missing in C's editorial:

Q1) For a fixed $$$k$$$, why does matching the $$$ith$$$ element from the first $$$k$$$ elements with the $$$ith$$$ element from the last $$$k$$$ elements maximize the minimum distance across all pairs?

A1) Consider the two pairs $$$(L1, R1)$$$ and $$$(L2, R2)$$$, where $$$L2>=L1$$$ and $$$R2 \leq R1$$$. The minimum distance here is $$$R2-L2$$$. We can swap $$$R1$$$ and $$$R2$$$ producing the pairs $$$(L1, R2)$$$ and $$$(L2, R1)$$$. Where $$$R1-L2 \geq R2-L2$$$ and $$$R2-L1 \geq R2-L2$$$. So the minimum distance now is $$$>=$$$ the previous minimum distance. This implies that for any two pairs, the pair with less $$$L$$$ should have the less $$$R$$$. In other words, the $$$ith$$$ elements of the first and last $$$k$$$ elements should be matched.

Q2) Why does binary search work for this problem?

A2) After sorting the array $$$arr$$$, denote $$$least[i]$$$ to be $$$j-i$$$ where $$$j$$$ is the least index such that $$$arr[j]-arr[i] \geq z$$$, or $$$+\infty$$$ if no such $$$j$$$ exists. For a valid $$$k$$$, $$$max_{i=1}^{i=k}\ least[i] \leq n-k$$$ (Assuming $$$1$$$-based indexing). If the previous inequality doesn't hold, we won't be able to match some $$$ith$$$ elements of the first and last $$$k$$$ elements. Denote $$$k\_inv$$$ to be the least invalid $$$k$$$, $$$max_{i=1}^{i=k\_inv}\ least[i]>n-k\_inv$$$. So any $$$k'$$$ where $$$k'>k\_inv$$$ will be invalid also, because $$$max_{i=1}^{i=k'}\ least[i] \geq max_{i=1}^{i=k\_inv}\ least[i]$$$ and $$$n-k'<n-k\_inv$$$.

[Problem B]

I am thinking about pretty straight forward, yet quite interesting solution to this problem. It is random shuffling till we get good arrangement or terminating and saying "No answer" after 1000 iterations.

I reckon that many people did it this way. Wonder if it is 100% correct and provable.

Solution: 53719836

Another solution for problem E. First, you need to build a tree representing the whole permutation. Choose the largest element n as the root of tree, then elements on the left side of n in the permutation form the left subtree of root, elements on the right side of n in the permutation form the right subtree of root.

The question is about how many pairs of (u, v) for each node x, where u locates in the left subtree of x and v locates in the right subtree of x.

After building the tree, do dsu on the tree. The total time complexity is O(nlogn).

In problem E. Why did solutions like these https://mirror.codeforces.com/contest/1156/submission/53741778 pass on time? For example test is [1, n, 2, n-1, 3, n-2, ...]

I can't understand: "we should match the leftmost L-point with the leftmost R-point, the second L-point with the second R-point, and so on, in order to maximize the minimum distance in a pair". Can someone explain me with?

Can anyone please explain these words with some examples? I haven't a clear idea about that.

nice problems

Can anyone help me with problem C ! I've used two pointers to make pairs Here is my submission

Edit: Sorry i figured the problem!

I think I have got a simple explanation of D. No dsu, no dp, just simple bfs + combinatorics. Here we go. 1. split the tree into two graphs, one containing only 0-edges and other containing only 1-edges. 2. count the number of nodes in each components for both graphs. 3. to find the number of only 0-containing paths and 1-containing paths, we can just count the paths inside all components(a path belonging to only a single component). 3. let's assume 1, 3, 4, 20 lies in a component. now, for this component, valid path is 20. let's face it. for a valid path, we need to pick two nodes and then we need to do permutation of two nodes. picking two nodes take p*(p — 1)/2 ways and ways of permutation of two nodes is only two. so, the number of valid paths is p*(p — 1)[p is the number of nodes in a component]. also, in a component, the number of ways you can go to a node belonging to a component is (p — 1).(going to node from all other p — 1 nodes of the component.) 4. thus, we can count only the answers that belongs to only a component of a graph. that is only 0-containing paths and 1-containing paths. 5. now, we have to face the paths that contains 0-edges at first and then 1-edges later. to do this let's define a vertex v. for paths going through v, we have to come into v through 0-edges and go out of v through 1-edges. as, we have found the number of ways to go into v in a 0-containing component and a 1-containing component, we can easily do this work just using multiplication law of permutation.

finally, here is the code(if needs). https://mirror.codeforces.com/contest/1156/submission/54551825

Ohh... I solved a 2300 ranked problem! without seeing tutorial! how? how?

Better late than never. Problem E was really nice!

For 1156C, why doesn't the greedy solution work. Like matching a point with another point on its right which is nearest to it, provided the distance is greater than or equal to z ?

Can someone tell me what is wrong with my solution for D. I used dp on trees to find the no.of invalid pairs and remove it from the total no. of possible pairs ( i.e n*(n-1) ).
Please find my submission here.

How to do Div2C using DP?

How to do Div2C using DP?

Thank you problem setters, who made this contest for us. And thanks for the tutorial ^^

https://mirror.codeforces.com/contest/1156/submission/81658673 Div2C.Its showing error in test 7. Someone pls explain.

For problem 1156B - Ugly Pairs, I used kind of an ad-hoc case-by-case solution.

Let, n = number of different characters in string s.

1. If n is odd and greater than 3, then there is always an answer. The answer is constructed like this. eg: abcdefg ==> ce, bf, ag, d. (Notice the pattern)
2. If n is even and greater than 2, then there is always an answer. The answer is constructed like this. eg: abcdef ==> cf, be, ad (Notice the pattern)
3. If n is 2, then just have to check whether those 2 are neighbors or not.
4. And if n is 3 and all 3 are consecutive, then there is no answer. Else, the answer is always possible.

Solution: 86424440

Problem D can be solved by simple re-rooting. 87430433

Can someone help why the multiset approach for the problem 1156C - Match Points is not working??

int n, d;
  cin >> n >> d;
  multiset<int> s;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    s.insert(a);
  }
  int ans = 0;
  while (s.size() >= 2) {
    int left = *s.begin();
    auto it = s.lower_bound(left + d);
    if (it == s.end())
      break;
    ++ans;
    s.erase(s.begin());
    s.erase(it);
  }
  cout << ans << endl;

I feel the editorial to Problem C is very unclear. I still don't get what is meant by "swap" them. Swap whom ? L? R? the one behind L ? idk.

Here's my attempt for an editorial.

1. It is clear to use Binary search. If we can make 'mid' pairs, we can surely make 'mid-1' pairs, we may/may not be to make 'mid+1' pairs.
2. Therefore, l (Minimum Pairs Possible) =0 and r (Maximum Pairs Possible)=n/2.
3. So applying binary search , mid=(l+r)/2. Now the main tricky part is to check whether we can form mid pairs or not ?
4. For an array [a1 , a2 ... an], what is the best/surest way to make 'mid' pairs?
5. It is to take {a[1],a[n-mid]} , {a[2],a[n-mid+1]} .... {a[mid],a[n]}. But why? Simply because these would have the maximum possible diference.

93012535

Can there be any possible solution to solve F that use expected value like expected value of remaining elements when iterating to the ith element ?

Can anyone tell me in Card Bag problem (F) for the test case 4 1 3 4 3 how the answer is 1/4? awoo