We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Constructive Algorithms
  4. New Year Chaos
  5. Discussions

New Year Chaos

Sort by

recency

|

1936 Discussions

|

  • LuizHenrique
     + 0 comments

    I've implemented BubbleSort algorithm in C#, to count the swaps.

    OBS; this is not the best solution. O(n^2) time complexity.

    public static void minimumBribes(List<int> q)
    {
        if (q is null || q.Count() < 1)
        {
            Console.WriteLine(0);
            return;
        }
        
        int count = 0;
        int limit = 0;
        long currentValue = 0;
        
        for (int i = 0; i < q.Count(); i++)
        {
            for (int j = 1; j < q.Count() - i; j++)
            {
                if (q[j-1] > q[j])
                {
                    if (currentValue != q[j-1])
                    {
                        limit = 1;
                        currentValue = q[j-1];
                    }
                    else
                        limit++;
                    
                    if (limit > 2)
                    {
                        Console.WriteLine("Too chaotic");
                        return;
                    }
                    
                    (q[j], q[j-1]) = (q[j-1], q[j]);
                    count++;
                }
            }
        }
        
        Console.WriteLine(count);
    }

  • rushikeshchopad1
     + 0 comments

    'Python 3.9' Solution:

     # Making a list compare_arr to incorporate the changes in the initial array and compare the units of displacement

 n=len(q)
compare_arr=[i+1 for i in range(n)]
count=0
chaotic=0
for i in range(n-1):
    if q[i]==compare_arr[i]:
        continue
    elif q[i]==compare_arr[i+1]:
        compare_arr[i], compare_arr[i+1]= compare_arr[i+1], compare_arr[i]
        count+=1
    elif q[i]==compare_arr[i+2]:
        compare_arr[i], compare_arr[i+2]= compare_arr[i+2], compare_arr[i]
        compare_arr[i+2], compare_arr[i+1]= compare_arr[i+1], compare_arr[i+2]
        count+=2
    else:
        chaotic=1
        break
if chaotic==1:
    print('Too chaotic')
else:
    print(count)

  • amatts2002
     + 0 comments

    this is an awful problem

  • princealonte
     + 0 comments

    My C Solution:

    void minimumBribes(int q_count, int* q) {

    unsigned int total = 0;
unsigned int prev;
unsigned int temp;
int arr[q_count];
for(int i = 1; i <= q_count; i++)
    arr[i-1] = i;
for(int i = 0; i < q_count; i++){
    if(q[i] == arr[i])
        continue;
    else if(q[i] == arr[i+1]){
        temp = arr[i+1];
        arr[i+1] = arr[i];
        arr[i] = temp;
        total += 1;
    }
    else if(q[i] == arr[i+2]){
        temp = arr[i+2];
        arr[i + 2] = arr[i + 1];
        arr[i+1] = arr[i];
        arr[i] = temp;
        total += 2;
    }
    else {
        printf("Too chaotic\n");
        return;
    }
}

printf("%d\n", total);

    }

  • g_hamu
     + 0 comments

    My Kotlin solution

    fun minimumBribes(q: Array<Int>): Unit {
    var result = 0
    var list = q.toMutableList()
    for (index in (q.lastIndex) downTo 0){
        val sortedValue = (index +1)
        if (list[index] == sortedValue){
            // make the list smaller so that next iteration would take less time to find the lastIndexOf
            list.removeAt(index)
            continue
        }
        
        // search from tail of list gets the index quicker in this case
        val unSortedIndex = list.lastIndexOf(sortedValue)
        val shift = (index - unSortedIndex)
        if(shift > 2){
            println("Too chaotic")
            return
        }
        
        list.removeAt(unSortedIndex) 
        result += shift
    }
    println(result)    
}