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

|

1940 Discussions

|

  • pierinazaramella
     + 0 comments

    Hi. I did not understand the input. Are there more than one array and we need to promediate? and the 3rd expected output is just 4. And what happend with the two caothic string? Thanks!

  • manceraaxel
     + 0 comments
    def minimumBribes(q):
    b = 0
    for i in range(len(q)):
        if q[i] - (i + 1) > 2:
            print("Too chaotic")
            return
            
        for j in range(max(0, q[i] - 2), i):
            if q[j] > q[i]:
                b += 1
                
    print(b)

  • 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);
    }