Largest permutation of elements in the range 1,....,N

[SlurrerOfSpeech]

with at most k swaps. (In other words, like the largest number formed by swapping k digits.)

Example. A=[4,2,3,5,1], k = 1 ---> [5,2,3,4,1]

I'm wondering why my algorithm is failing the test cases which I'm unable to see.

using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
    public static void Swap(int[] A, int i1, int i2)
    {
        int temp = A[i1];
        A[i1] = A[i2];
        A[i2] = temp;
    }
    static void Main(String[] args)
    {
        int[] parameters = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        int n = parameters[0];
        int k = parameters[1];
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        for(int i = 0; i < arr.Length && k > 0; ++i)
        {
           if(arr[i] == n) 
               continue;
           int j = arr.Length - 1;
           for(; j > i && arr[j] != n; --j);
            Swap(arr,i,j);
            --n;
            --k;
        }
        Console.WriteLine(string.Join(" ", arr));
    }
}

 

[D H]

Your algorithm is O(N²). You need to find an O(N) algorithm.

 

[Ibix]

I think things go wrong when you try to skip a swap.

Edit: no, never mind. I misunderstood.

 

[D H]

Your algorithm is O(N²). You need to find an O(N) algorithm.

To make this clear, this is a hacker rank problem. Problem sites such as this focus solely on efficiency in the small, and in the process create rather artificial problems. This is an artificial problem.

As an alternative to beating yourself over the head on those artificial hacker rank problems, try looking into contributing to an existing open source project. There are many active open source projects at github and bitbucket, some of which are begging for help. So help. Along the way, you'll learn about version control, about the project, how to understand a large codebase, how to contribute to it, and how to test your contributions. This is much more worthwhile than solving one dynamic programming problem after another.

That said, dynamic programming comes into play in this problem. (This is an important concept you should learn.) DP oftentimes uses memoization. You haven't done that. You instead have that inner loop, which can be done away with by memoization. You haven't taken full advantage of the artificial nature of the problem, which is that the input sequence is a permutation of the integers between 1 and N (inclusive). Keep track of the indices of the values between 1 to N in an easily build array. Now when you swap, you need to swap index array elements as well as value array elements so that the index array always keeps in sync with the value array.Aside: DYAC, "memoization" is a word! Stop trying to change it to "memorization!"

 

[SlurrerOfSpeech]

That said, dynamic programming comes into play in this problem. (This is an important concept you should learn.) DP oftentimes uses memoization. You haven't done that. You instead have that inner loop, which can be done away with by memoization. You haven't taken full advantage of the artificial nature of the problem, which is that the input sequence is a permutation of the integers between 1 and N (inclusive). Keep track of the indices of the values between 1 to N in an easily build array. Now when you swap, you need to swap index array elements as well as value array elements so that the index array always keeps in sync with the value array.

Ah, I see.

Lemme try this.

 

[SlurrerOfSpeech]

Hmm, this is still failing some of the test cases.

using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
    public static void Swap(int[] A, int i1, int i2)
    {
        int temp = A[i1];
        A[i1] = A[i2];
        A[i2] = temp;
    }
    static void Main(String[] args)
    {
        int[] parameters = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        int n = parameters[0];
        int k = parameters[1];
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        int[] pos = new int[n]; // pos[m-1] is the index of the value m in arr
        for(int i = 0; i < arr.Length; ++i)
        {
            pos[arr[i] - 1] = i;
        }
        for(int i = 0; i < arr.Length && k > 0; ++i, --n)
        {
           if(arr[i] == n)
               continue;
           int j = pos[n - 1];
           Swap(pos,arr[i]-1,n-1);
           Swap(arr,i,j);
           --k;
        }
        Console.WriteLine(string.Join(" ", arr));
    }
}

 

[Pepper Mint]

Hmm, this is still failing some of the test cases.

using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
    public static void Swap(int[] A, int i1, int i2)
    {
        int temp = A[i1];
        A[i1] = A[i2];
        A[i2] = temp;
    }
    static void Main(String[] args)
    {
        int[] parameters = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        int n = parameters[0];
        int k = parameters[1];
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        int[] pos = new int[n]; // pos[m-1] is the index of the value m in arr
        for(int i = 0; i < arr.Length; ++i)
        {
            pos[arr[i] - 1] = i;
        }
        for(int i = 0; i < arr.Length && k > 0; ++i, --n)
        {
           if(arr[i] == n)
               continue;
           int j = pos[n - 1];
           Swap(pos,arr[i]-1,n-1);
           Swap(arr,i,j);
           --k;
        }
        Console.WriteLine(string.Join(" ", arr));
    }
}

1. validate inputs
2. validate returned values from all methods

 

[SlurrerOfSpeech]

The input would be valid. The specs of the problem guarantee that. All the test cases expect for the 3 last ones are passing, and sometimes the failing ones fail with a Runtime Error and other times a Wrong Answer. I think HackerRank's C# engine is screwed up. I changed to Int64 and still getting errors.

 

[Pepper Mint]

The input would be valid. The specs of the problem guarantee that.

The specs might state so but the written code above I mean clearly isn't "guaranteed" to be bug-free.

All the test cases expect for the 3 last ones are passing, and sometimes the failing ones fail with a Runtime Error and other times a Wrong Answer. I think HackerRank's C# engine is screwed up. I changed to Int64 and still getting errors.

A lot of unknown errors related to runtime, it could be your code is accessing an invalid array object, for example. "Wrong Answer" is probably due to an incorrect implementation of your algorithm.
The probability that HackerRank system fails is also present but at least your code needs to be reworked with more guarding snippets to check all methods' returned values. Best practice is for the long road ahead in coding not for passing a pretty simple exercise of likely a test interview with a man-made system.

 

[Jarvis323]

If you are assuming no gaps or duplicates, then this seams to be the problem:

        for(int i = 0; i < arr.Length && k > 0; ++i)
        {
           // if this happens, then n is not decremented
           if(arr[i] == n)
               continue;
           int j = arr.Length - 1;

           // and then if n was not decremented last iteration
           // then n is at arr[i-1], so this loop will not find n, and will only result in j=i
           // so you will waste a swap, swapping arr[i] with itself
           for(; j > i && arr[j] != n; --j);
            Swap(arr,i,j);
            --n;
            --k;
        }

Otherwise, if gaps or duplicates are allowed, then there are more problems