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

|

1938 Discussions

|

  • sandeepgarg
     + 0 comments
    void minimumBribes(vector<int> q) {
    int bride=0;
    int i=0;
    for(i=0;i<q.size()-1;i++){
        int temp=0;
        for(int j=i+1;j<q.size();j++)
        {
            
            if(q[i] > q[j]){
                temp++;
            }
            if(temp > 2)
            {
                cout<<"Too chaotic"<<endl;
                break;
            }
        }
        if(temp > 2)
        {
            break;
        }
        bride=bride+temp;
    }
    if(i==q.size()-1)
        cout<<bride<<endl;

  • alexis_deruelle
     + 0 comments

    I've implemented a simple lookahead building upon @princealonte solution after noticing you only need contextual information from 3 adjacent values that you compare from the current index.

     q = 2  1  5  6  3  4  9  8  11 7  10 
 v = 1  2  3  4  5  6  7  8   9 10 11
 
 1 : 1  2  3  .. .. .. .. .. .. .. .. 
 2 : .. 1  3  4  .. .. .. .. .. .. .. 
 3 : .. .. 3  4  5  .. .. .. .. .. .. 
 4 : .. .. .. 3  4  6  .. .. .. .. .. 
 5 : .. .. .. .. 3  4  7  .. .. .. .. 
 6 : .. .. .. .. .. 4  7  8  .. .. .. 
 7 : .. .. .. .. .. .. 7  8  9  .. .. 
 8 : .. .. .. .. .. .. .. 7  8  10 .. 
 9 : .. .. .. .. .. .. .. .. 7  10 11 
10 : .. .. .. .. .. .. .. .. .. 7  10 
11 : .. .. .. .. .. .. .. .. .. .. 10

    We just have to update the lookahead values depeding on three cases.

    Here the corresponding c++ solution :

    void minimumBribes(vector<int> q) {
  unsigned int bribes = 0;

  int u = 1, v = 2;
  for (size_t i = 0; i < q.size(); ++i) {
    int w = i + 3;

    if (q[i] > w) {
      cout << "Too chaotic" << endl;
      return;
    }

    if (q[i] == w) {
      bribes += 2;
    } else if (q[i] == v) {
      bribes += 1;
      v = w;
    } else if (q[i] == u) {
      u = v;
      v = w;
    }
  }

  cout << bribes << endl;
}

  • 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