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. Dynamic Programming
  4. Nikita and the Game
  5. Discussions

Nikita and the Game

  • dehaka
     + 0 comments

    there cannot be more than n leaves, and hence cannot be more than 2n nodes in a full binary tree, and n is of order 10^4 so it can be brute forced

    simple BFS, no dynamic programming, O(n*log(n))

    int decision(int i, int j, const vector<long>& sum) {
    if (i == j or (sum[j] - sum[i-1])%2 == 1) return -1;
    auto it = lower_bound(sum.begin()+i, sum.begin()+j+1, (sum[j]+sum[i-1])/2);
    if (*it == (sum[j]+sum[i-1])/2) return it - sum.begin();
    else return -1;
}

int arraySplitting(vector<int> arr) {
    int score = 0;
    queue<vector<int>> Q;
    vector<long> sum = {0};
    Q.push({1, (int)arr.size(), 0});
    for (int i=0; i < arr.size(); i++) sum.push_back(sum.back()+arr[i]);
    while (!Q.empty()) {
        int index = decision(Q.front()[0], Q.front()[1], sum);
        if (index != -1) {
            Q.push({Q.front()[0], index, Q.front()[2]+1});
            Q.push({index+1, Q.front()[1], Q.front()[2]+1});
            score = max(score, Q.front()[2]+1);
        }
        Q.pop();
    }
    return score;
}