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

|

1941 Discussions

|

  • maxfuller5
     + 0 comments

    C++ solution:

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

    for (int i = 0; i < q.size(); i++) {
        if (q[i] - (i + 1) > 2) { // If the difference between an elements' initial position and it's final position is greater than 2,
            // that means it moved to the left more than twice, which means it bribed more than twice. That means the line's Too Chaotic.
            cout << "Too chaotic" << endl;
            return;
        }

        // Start from one position ahead (in the line) of where q[i] *could* have started (i.e at an index of either index 0 or q[i] - 2, whichever is higher). 
        // Count how many people with a higher position than q[i] are in front of q[i] in the queue (i.e behind q[i] in the array), 
        // because each of those people must have bribed their way past q[i].
        for (int j = max(0, q[i] - 2); j < i; j++) {
            if (q[j] > q[i]) { 
                totalBribes++;
            }
        }
    }

    cout << totalBribes << endl;
}

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