Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# Largest permutation of elements in the range 1,...,N

Tags:
  1. Aug 16, 2016 #1
    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.

    Code (Text):

    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));
        }
    }
     
     
  2. jcsd
  3. Aug 16, 2016 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Your algorithm is O(N2). You need to find an O(N) algorithm.
     
  4. Aug 16, 2016 #3

    Ibix

    User Avatar
    Science Advisor

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

    Edit: no, never mind. I misunderstood.
     
    Last edited: Aug 16, 2016
  5. Aug 16, 2016 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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!"
     
  6. Aug 16, 2016 #5
    Ah, I see.

    Lemme try this.
     
  7. Aug 16, 2016 #6
    Hmm, this is still failing some of the test cases.

    Code (Text):

    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));
        }
    }
     
     
  8. Aug 16, 2016 #7
    1. validate inputs
    2. validate returned values from all methods
     
  9. Aug 17, 2016 #8
    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.
     
  10. Aug 17, 2016 #9
    The specs might state so but the written code above I mean clearly isn't "guaranteed" to be bug-free.
    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.
     
  11. Aug 27, 2016 #10
    If you are assuming no gaps or duplicates, then this seams to be the problem:
    Code (Java):

            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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Largest permutation of elements in the range 1,...,N
  1. Multiset Permutations (Replies: 3)

  2. Largest number in f90 (Replies: 13)

  3. Permutations with BFS (Replies: 4)

Loading...