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

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