Thank you for everyone who participated in the contest :)
The winners of the contest are:
1. SoMuchDrama
2. achaitanyasai
You both will be getting mail regarding cash prize soon. Please give us time, prizes were also given in the first edition, so will they be given now.
Link to problems Statements: Questions
Please fill the following form if you participated in the contest: https://goo.gl/forms/av1MLDH9A6RJBnB93
Shreyy’s Birthday Gift
There are many ways to solve this problem. Given the solutions submitted by the users, here is an alternate way to think of the problem: For n sized array, the number of modulus operations are n - 1. This implies that you have to divide n - 1 additive and n - 1 negative signs among n items, with each item getting at most of 2 signs, and at least 1 sign each (with some obvious constraints like max value not getting any negative signs and similar).
Now, we just sort the array, and if n is even, we can divide the array into [1: n / 2] and [n / 2 + 1: n] In the first partition, all elements get 2 positive signs each except the last element which gets 1 positive sign. In the second partition, the first element gets a single negative sign, whereas the rest get 2 negative signs. You can find similar distribution when n is odd.
We can find an arrangement for such a division of signs.
Aliens
A simple approach is to hash the possible distances. Then we could check each enemy base in O(N) time. However, this would yield a O(N2) algorithm which is too slow.
Let’s restate the problem and use binary vectors. S[i] is 1 if grenade can reach distance i and H[i] is 1 if there is an enemy base at distance i We want to calculate Possible[i] = S[k] * S[i−k] The Possible vector is actually the discrete convolution of S with itself. We can calculate it the same way we multiply polynomials using a discrete Fast Fourier Transform (FFT).
The discrete FFT of n values can be calculated in O(nlogn).After calculating the Possible vector, we just need to check in how many distances i, Possible[i] > 0 and H[i] = 1 Recall that the distances are up to 200000. Say the maximum distance is D, then the time complexity of this approach is O(N + M + DlogD) which will pass the time limits.
Mario and Browser
First, let's remove all the subtrees which won't have any coins in them, as Mario would never visit them. Following which, we select the shortest path. The shortest path to cover k of n nodes is equal to the totalcost * 2 - costofdiameter So the path Mario chooses would be diameter which starts with smallest possible value and ends with largest possible value.
It is now obvious to see that all the queries are of nodes present on the diameter. A single DFS starting from the endpoint is enough to calculate values of each of those nodes.
Big Mom
The question is as good as asking to find the path with maximum XOR on a tree. We maintain a trie to calculate the maximum values we can get with xor of any new value and previously occurring values.
One way of doing this is by Centroid Decomposition of the tree and calculating subtrees of the centroid and solving for the centroid as we go by.
Abdullah and Fibonacci Cup
The number of divisors of each fib(x) can be found out using sieve of Eranthoses by initializing divisors array to 1. Rather than marking multiples of each prime p as false, multiply the divisor of the multiples(j) with e, where e is the power of p in the factorization of j.
For every even number, decrement divisor by 1 as fib(2) = 1 is an extra count which has already been covered by fib(1) = 1. If we replace the number written on the bag with the number of divisors it has, the game is the same as subtracting fib(x) from it in a single move.
Since the number of divisors for a five digit number is at max 128 and fib(12) = 144. So we only need to calculate Grundy numbers up to 128 and in each move, there are at max 12 moves possible.
Grundy(i) = mex{Grundy(i - fib(1), Grundy(i - fib(2), …….(i - fib(x)) > = 0)}
For each test case, we can use Sprague-grundy theorem to take xor of all Grundy(a[i]). If it is equal to 0, Player 2 would win otherwise Player 1.
