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

  • dehaka
     + 0 comments

    i think this works for any number of bribes, not just 2, haven't proved it yet. count the number of pairs of indices (i, j) such that q[i] > q[j].

    O(n log(n)) pass all tests, haven't proved why it works yet, just intuitively works in my head

    void update(vector<long>& fenwick, int i, long value) {
    while (i < fenwick.size()) {
        fenwick[i] = fenwick[i] + value;
        i = i + (i & -i);
    }
}

long access(const vector<long>& fenwick, int i) {
    long sum = 0;
    while (i > 0) {
        sum = sum + fenwick[i];
        i = i - (i & -i);
    }
    return sum;
}

void minimumBribes(int n, const vector<int>& theQueue) {
    vector<long> fenwick(n+1);
    bool flag = true;
    long reversedPairs = 0;
    for (int i=1; i <= n; ++i) {
        if (theQueue[i] - i > 2) flag = false;
        reversedPairs = reversedPairs + i - 1 - access(fenwick, theQueue[i] - 1);
        update(fenwick, theQueue[i], 1);
    }
    cout << ((flag == true) ? to_string(reversedPairs) : "Too chaotic") << '\n';
}

int main()
{
    int t, n, k;
    cin >> t;
    for (int i=1; i <= t; ++i) {
        vector<int> theQueue = {0};
        cin >> n;
        for (int j=1; j <= n; ++j) {
            cin >> k;
            theQueue.push_back(k);
        }
        minimumBribes(n, theQueue);
    }
}