hello_its_me's blog

Third Permutation CSES confusion
By hello_its_me, 3 months ago, In English

Problem Link : Third Permutation
Here how is this code not giving a TLE ?

I got this code from an LLM (i modified it afterwards) but the reason why this is working is not cleared any how. If anyone has solved this in any other way plz do share. Thanks in advance. 

    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    if (n == 2) {
        cout << "IMPOSSIBLE\n";
        return;
    }
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        c[i] = a[(i + 1) % n];
    }
    for (int i = 0; i < n; i++) {
        label: 
        if (c[i] == b[i]) {
            for(int j = 0; j < n; j++) {
                if(c[i] != a[j] and c[i] != b[j] and c[j] != a[i] and c[j] != b[i]) {
                    swap(c[i], c[j]);
                    goto label;
                }
            }
            cout << "IMPOSSIBLE\n";
            return;
        }
    }
    
    for (int i = 0; i < n; i++) {
        cout << c[i] << " ";
    }
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Why it made more sense to you to ask an LLM for the code and asking Human to explain the code?

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

    Firstly, I can't go on asking Human for every problem I can't solve. So I took LLM's help. Secondly, the explanation seemed a bit confusing to me. Since many people have solved this problem that's why I am asking if they have solved this way or in any other way. I hope it is clear to you.

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

      Yep. Got it. Sorry for being rude from my side. Being penitent, I thought of looking into the problem but failed.

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

        No it's totally fine. I think the server is OK now.

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

          Yep and Here is My solution Link

          I have solved the problem in the following way:

          1) Firstly I have gone through the arrays and checked how many times a value has occurred. Whenever, a value has occurred for two times, we have pushed that value into a queue.

          2) When I am iterating the array for the first time, and found my queue not empty-> That means, the value has already occurred twice beforehand and won't be present in the future so,I can pop the value from the queue and place it in the available spot.

          3) In the first pass, We have iterated but haven't placed all the values in the answer array. So, We will iterate again.

          4) In the second iteration, whenever, we will found any empty place in the answer array, that means we need to fulfill this value. We will try to fill this place by iterating over our queue once and checking whether this value fulfills our condition or not. -> If we have iterated over the whole queue and haven't found any suitable value to be placed, then we will print Impossible.

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

I solved this problem using a really simple idea.

Basically, we can just randomly shuffle until the answer is valid, except when $$$n = 2$$$.

For each position $$$i$$$, only $$$2$$$ values out of $$$n$$$ are forbidden ($$$a_i$$$ and $$$b_i$$$), so a random permutation has roughly $$$\left(1 - \frac{2}{n}\right)^n \approx \frac{1}{e^2} \approx 13.5\%$$$ chance of being valid. This means on average only $$$\sim 7\text{-}8$$$ shuffles are needed to find a valid solution. The expected complexity is $$$O(n)$$$ since each shuffle takes $$$O(n)$$$ time and the expected number of attempts is constant.

Here is the code:

Solution code

I hope this explanation helps! :)

→ Reply