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

Sort by

recency

|

145 Discussions

|

  • sardodorzi
     + 0 comments

    Inflatable bull rental San Diego

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

  • verifybtc11
     + 0 comments

    Could you please provide more details or clarify your request so I can assist you accurately? If you're referring to a specific book, movie, game, or concept, please provide More info about what you're looking for.

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Nikita and the Game Problem Solution

  • venom1724
     + 0 comments

    10 lines in Python, 100%

    Cool kid solution, have fun with it! 

    cum = []
l = {}

def rec(i,j):
    m = cum[i-1]+((cum[j]-cum[i-1])/2)
    return 0 if m not in l else 1+max(rec(i,l[m]),rec(l[m]+1,j))
        
def arraySplitting(arr):
    global cum, l
    cum = list(accumulate(arr)) + [0]
    l = {cum[i]:i for i in range(len(cum)-1)} # lookup
    return len(arr)-1 if cum[-2]==0 else rec(0,len(arr)-1)

    Using accumulate() from itertools