KFIB
Prerequisites : Prefix Sums.
A naive brute force of this algorithm would be O(N*K) because calculating each term will take K calculations. To calculate the ith we will have to add a[i-k], a[i-k+1] …a[i-2], a[i-1] terms. So if we use a prefix sum, then we can do this computation in O(1). a[i-k] + a[i-k+1] …a[i-2] + a[i-1] = prefix[i-1] - prefix[i-k-1].
a[0] = 0;
for(i from 1 to k)
pref[i] = 1 + pref[i-1];
for(i from k+1 to n){
pref[i] = (pref[i-1] + (pref[i-1] - pref[i-k-1]))%mod;
}
print (pref[i] - pref[i-1])%mod
This reduces the complexity to O(n) and is fast enough to get full points!
BRKTREE
Prerequisites: DFS, Tree
When we remove an edge, the tree breaks into two parts with sum W1 and W2. Also W_1 + W_2 = W(the original tree).
If we know the sum of all nodes in one tree, then we can also find the other one in O(1)
Whenever, we remove an edge, one of the complete subtree gets removes. So if we know the sum of all subtrees(which we can calculate using a DFS in O(n)), then we can easily find the answer in O(N) by iterating through all the subtrees and checking if the answer matches for each query.
Since, all queries are independent we can calculate all the possible difference and store it in a set. Then whenever we get a query we can just check whether the value exists in the set.
We are very sorry for the fault in the second subtask
LNGHW
Each element has a specific remainder when divided by M. Lets make an 2d array, vector b[M].
Then we can push all the elements to their specific array depending on their remainder. After that sort all the arrays depending on its a[i] value. Then we can easily answer the queries.
for(i from 0 to n-1){
int inp; read inp
b[inp%M].push_back(make_pair(inp, i));
}
for(i from 0 to M-1){
sort(b[i].begin(), b[i].end());
}
for(q--){
int i, R; read i and R
if(i <= b[R].size()) print( b[R][i-1].second + 1)
else print (-1)
}
PIZPAR
The problem can be solved using a greedy approach. By induction we can prove that for a single pizza, if we make n cuts in it, the maximum number of slices we get is (n*n + n + 2)/2.
Now with this formula we can prove that it’s always optimal to make the maximum possible number of cuts on a single pizza, rather than dividing the total cuts among the pizzas.
Let’s suppose we have a total of x+y cuts. Now, if we divide the cuts (ie. make cuts in two separate pizzas) the total slices we get is (x*x + x + 2)/2 + (y*y + y + 2)/2. Where as if we make the x+y cuts on a single pizza, we get (x*x + y*y + x + y + 2*x*y)/2 slices.
We can clearly notice that the latter provides more slices. This means that it is always more optimal to make as many cuts as possible in one of the pizzas. This gives us our greedy solution.
