rivalq's blog

Codeforces Round #793 (Div. 2) Editorial
By rivalq, 3 years ago, In English

I hope you all liked the round. Please share your feedback in the comments section.

1682A — Palindromic Indices

Hint
Tutorial
Solution

1682B — AND Sorting

Hints
Tutorial
Solution

1682C — LIS or Reverse LIS?

Hint
Tutorial
Solution

1682D — Circular Spanning Tree

Hints
Tutorial
Solution

1682E — Unordered Swaps

Tutorial
Solution

1682F — MCMF?

Tutorial
Solution
  • Vote: I like it
  • +147
  • Vote: I do not like it

Comments Comments (93)
| Write comment?
»
3 years ago, # |
  Vote: I like it -37 Vote: I do not like it

:holyfrick: That was lightining fast .. Thnx for the hinted editorial !! helps a lot in upsolving :)

→ Reply
»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

great problems, fast editorial, quick rating changes, and becoming specialist.
thanks alot :D

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Missed C by just "+1", took single/2 instead of (single+1)/2. :(

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I wish authors who put an anti-hash test in C a very pleasant evening.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

Rating change is faster than editorial :D thanks

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is E related to something like toposort(finding indegree = 0)?

Can someone give hint please

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it
    hint
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Can you elloborate on the idea ? I can't get how to construct a tree form permutation Thanks!

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +22 Vote: I do not like it

        If we connect $$$i$$$ and $$$p_i$$$ in a graph, you will see that the graph is some loops. So for one loop with length $$$k$$$, the minimal number of swap must be $$$k-1$$$ and the swap must connect all node in the loop. So you will see that if you connet all swap $$$(a_i,b_i)$$$, it will look like a forest.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, but I have no idea how to solve it on the tree

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            ← Rev. 3   Vote: I like it +15 Vote: I do not like it

            OK. For an element in position $$$i$$$, we need to move it to position $$$p_i$$$. We will see that we can only use a series of swaps to move $$$p_i$$$, and two node have only one path in a tree. So if the edges in the path from $$$i$$$ to $$$p_i$$$ is represented as $$$x_1,x_2,\dots$$$, they must be used in such an order in the final. So we can make a new graph to describe the order for the swaps, and then use a topo sort can slove it.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              But it seems that the number of edges is $$$O(n^2)$$$..?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                ← Rev. 4   Vote: I like it +15 Vote: I do not like it

                Oh, I forgot it. A good observation in this problem is that one edge may appear at most twice in all paths. Because A swap edge can only change two position, so it can be proved that if three or more paths through an edge, there must have no solution. So there are at most $$$2n$$$ visit for all the edges. Finally, the time will be $$$O(n)$$$.

                → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I only have an $$$O(n^2)$$$ algorithm. For each loop, choose one node as the starting point, then judge whether the dfs order on the tree is same as the loop's order.

          → Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Awesome round. Fast Editorial. Quick Rating Changes. rivalq, CoderAnshu supremacy.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what is wrong with my code idea for B https://codeforces.me/contest/1682/my

→ Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Just gonna share my construction for D here (no clue whether it's the same as the editorial):

Spoiler

Submission: 158082919 (the code isn't very neat)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What do you do when there are two ones at the end?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      If the upper or lower segments of even degree vertices do not exist, it is fine to connect them to the next available point.

      You may be thinking that the previous 1 will have even degree, but it will be compensated by a blue edge.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        For example, this is what I get when I try to follow the intuition from the picture to construct the tree on string 10001100 (crosses are vertices with odd degrees, circles — vertices with even degrees)

        Screenshot-from-2022-05-24-12-57-54

        If I follow the intuition from the picture, I end up with a 1 with an even degree.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Well actually the answer is NO for this testcase since the number of 1s is odd.

          → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For question C an input like 1,2,9,8,10,11,11 should have 3 as an answer right but the code will give 4 as the answer. Can someone tell me what am i missing?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the round was lucky for me; I just became specialist ;)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Another easy to see proof for A:

Number of element equal to the middle element has the same parity as that of N. So decrease N by 1, the parity of the middle elements should be changed

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

Here's a pictorial solution to D which is very similar to the one in the editorial.

Spoiler
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -43 Vote: I do not like it

I think C solution is not correct, as it doesn't contemplate all possible cases. The one concretely isn't ok on the pretests 2 is the input num 22:

1 1 2 3 3

Where it says answer is 3. If it was the 1 or the 3 the number that had a single appearance it would be right, as it could be put in the middle of the array, but when is the 2 there is no way to order it that gives result 3.

I made this awful code just to test it and it seems that the max increasing substring is in fact 2

// C++ program to display all permutations
// of an array using STL in C++
  
#include <bits/stdc++.h>
using namespace std;

int maxSubsequence(int a[], int n);
  
// Function to display the array
void display(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        cout << a[i] << "  ";
    }
    
    cout << endl;
    cout << maxSubsequence(a, n) << "\n";
}

int maxSubsequence(int a[], int n){
    int rl = 1;
    int lr = 1;
    int aux = 1;
    for(int i = 0; i < n; i++){
        aux = 1;
        int j = i + 1;
        while(j < n && a[j-1] < a[j]){
            aux++;
            j++;
            
        }
        rl = max(aux, rl);
    }

    for(int i = n-1; i >= 0 ; i--){
        aux = 1;
        int j = i;
        while(j > 0 && a[j-1] > a[j]){
            aux++;
            j--;
        
        }
        lr = max(aux, lr);
    }

    return min(rl, lr);

}
  
// Function to find the permutations
void findPermutations(int a[], int n)
{
  
    // Sort the given array
    sort(a, a + n);
  
    // Find all possible permutations
    cout << "Possible permutations are:\n";
    do {
        display(a, n);
    } while (next_permutation(a, a + n));
}
  
// Driver code
int main()
{
  
    int a[] = { 1, 1, 2, 3, 3 };
  
    int n = sizeof(a) / sizeof(a[0]);
  
    findPermutations(a, n);
  
    return 0;
}

Am I missing something?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    The answer is 1 3 2 3 1. Your testing code is just not corrected in finding LIS.

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what if the sequence given is : 2 2 3 5 5 7 7

      how do you get 4?

      what arrangements?

      → Reply
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

I liked problem F, but I feel like it would've been better to not add the artificial complexity from the bipartite flow graph stuff.

I'd prefer something like "there is a wall of stacked 1 by 1 blocks along the number line. for most of the infinite number line the height is average, but unfortunately there are some positions where there are more or fewer than average blocks in a single column. can you figure out how many steps to the left and right in total the boxes need to be moved? The non-average heights are given in this format with queries..."

→ Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

A shameful round for me only solved A-C ): :(

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Great Round, enjoyed it a lot!!!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem B, with the input:

1

8

0 1 2 7 4 5 3 6

it seems like the answer is not correct, if im wrong, pls point out my mistakes.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Man the solution for D blew my mind :D Great Round!

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

please add the problem rating in the tags of the problems.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

sometimes map is faster than unordered_map

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It was not intuitive or provable in the contest that maximum X would be the AND of all misplaced elements of the array. Bad day for me:)

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Changing just one line in my problem C code gave AC after the contest :(

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

For problem B, why the upper bound of the answer is the bitwise AND of all elements which are not at their correct positions.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Because X must be a submask of all such elements and bitwise AND is maximum of those X.

    → Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

In question C , on using unordered_map<int,int> , I am getting TLE whereas using map<int,int> accepts the solution. Can anyone please tell why it is so? My both submissions : Accepted Solution using map [problem:C][TLE submission using unordered_map](https://codeforces.me/contest/1682/submission/158110821)

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    unordered map answers its queries(add, get) in amortized O(1) time. The key word is amortized, which means that there are cases when it's not that fast. The worst case is O(n) in time for these operations, which you've probably dealt with in tc 28.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

speedforces

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Video: A very interesting Multiset Hashing Solution to Problem E

Posting this because the Editorial to problem E is not posted yet (and I talked to the problemsetters and their solution is different from mine)

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

For A, don't you mean $$$s_i = s_{n - i + 1}$$$ instead of $$$s_i = {n - i + 1}$$$?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In second problem ,AND SORTING i am confuse in why it is taking 'and(&)' of all elements present at not correct position, please help

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We don't need to move the elements at the right places. Hence only the elements at wrong places should be eligible for swapping. Thus X should be & of all those values.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In part C https://codeforces.me/contest/1682/submission/158147851 if I don't write i<n-1 in the while loop, one of the test case fails on CF but passes in my device. Could someone explain why?

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I'm afraid that I didn't catch the point of problem C.

Why don't we just make the subsequence in a monotonically increasing order?

Like this:[2 2 4 4 5 5].

By this way,LIS(a')=0.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Oh, I made such a stupid mistake. :( Neglect it.

    → Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Good Problem E!
Maybe Better for having a sooner editorial XD

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why not use Hash to solve the 1682A?

And why do you Hack unordered_map in 1682C?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why not use Hash to solve the 1682A?

    Because its an overkill. Simpler easy to implement solns exist.

    And why do you Hack unordered_map in 1682C?

    Because it's hackable.

    → Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I have added editorial of problem E. It's really long and detailed. Hope you would like it.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For problem E, how to understand the phrase "because we have to sort the permutation in a minimum number of moves which isn't possible if two cycles are merged at any instant".

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem 1682C — LIS or Reverse LIS?, how do we have the answer 3 for this input: 1 1 2 3 3?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explan the problem F?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really good problem D and E! But why the editorial of problem F is really late......

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys I have a question regarding C :

Consider the test case :

1
3
1 2 2

Now, there are three arrangements of $$$[1, 2, 2]$$$ :

  1. $$$[1, 2, 2]$$$ : here, $$$LIS(a) = 2$$$ and $$$LIS(a') = 1$$$ so beauty is $$$1$$$.
  2. $$$[2, 1, 2]$$$ : here, $$$LIS(a) = 1$$$ and $$$LIS(a') = 1$$$ so beauty is $$$1$$$.
  3. $$$[2, 2, 1]$$$ : here, $$$LIS(a) = 1$$$ and $$$LIS(a') = 2$$$ so beauty is $$$1$$$.

So beauty in every case is $$$1$$$. My code outputs $$$1$$$ as well. However, the output and the formula from the editorial suggest the answer should be $$$2$$$. Can anybody point out where the flaw in my reasoning is?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Nevermind I made a mistake in case $$$[2, 1, 2]$$$ got it

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm getting TLE at testcase #28 in Problem C. Here's my submission. Can anyone help me why I'm getting TLE.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hey, I am trying to understand why in problem C the solution is said to be NlogN? We simply add to the map and then traverse it, isn't it just N? what am I missing here?

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Alternate solution for problem E:

Firstly, observe that the edges corresponding to swaps required to sort one cycle form a tree which has all the nodes in the cycle (this is also present in the editorial, so I won't elaborate on it).

Now, let's consider how we can solve this subproblem:
There exists a tree of $$$n$$$ vertices, and an additional value $$$p_u$$$ for each node $$$u$$$. Now, some hidden order of edges was chosen, and then for each edge $$$(u, v)$$$, we swap the values of $$$p_u$$$ and $$$p_v$$$. You are given the final value of $$$p_u \quad \forall u \in [1, n]$$$. You need to recover any order of edges which would lead to the same values of $$$p$$$.

Note: For an edge $$$(u, v)$$$ when we remove this edge, the tree is split into two components, I will be calling the one containing $$$u$$$ as the $$$u$$$-component and the one containing $$$v$$$ as the $$$v$$$-component.

Claim 1: After all swaps, for every edge $$$(u, v)$$$, there exists exactly one node $$$x$$$ in the $$$u$$$-component, such that $$$p_y = x$$$ for some node $$$y$$$ in the $$$v$$$-component after all swaps (note that $$$(u, v)$$$ is an unordered pair for no loss of generality).

Proof

Now, to restore a valid order of swaps if any exists, we can simply do the following:
For any edge $$$(u, v)$$$ such that in the current state, the node $$$p_u$$$ is in the $$$v$$$-component and the node $$$p_v$$$ is in the $$$u$$$-component, add the swap of $$$(u, v)$$$ to the beginning of currently found order, and then swap $$$p_u$$$ and $$$p_v$$$.

Proof of correctness:

This can be implemented pretty simply, by using some euler tour stuff.

Implementation: link

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C what will be the answer or how to sort this array

10 10 15 15 1 2 3 4 5

→ Reply