QBIT 2015- CONTEST EDITORIAL
Contest Link: www.codechef.com/QBIT15
Problem Setter: Shreyans Sheth (bholagabbar)
NOTE:
First and foremost, I’d like to thank everyone who took part in the contest. Honestly, I was not expecting such participation and it couldn’t have been better. This contest was an initiative from my side to try and bring up the coding culture in my college
We felt that the best time to organize a contest like this would be during the college’s techfest, Technovit, which is currently underway.
I did receive notifications about weak testcases on the 3rd and 5th problems. I really apologize as this was my first attempt at organizing a contest such as this single-handedly. Those who have organized one would know 
Cutting to the chase, here is a short and concise editorial for every problem in the contest. I am aware of the fact that a lot of the external contest holders do not publish editorials and it causes a lot of trouble to those who were eager to learn and took part in the contest. I also did this out of respect for CodeChef and especially Chanukya, who helped me all along the contest. CodeChef really has selflessly uplifted the Competitive Programming scene in India and people like me couldn’t be more grateful 
EXPLANATIONS:
QBIT01: Sudz and Deception
Here, the optimal strategy would be to sort the coins in descending order. Then, Sudz will keep picking coins (large to small) until his sum just exceeds the sum of the remaining coins. This will be the answer.
Setter’s solution: http://ideone.com/Hhoe4i
QBIT02: Santa Banta and Fanta
It seems that this question generated quite a lot of confusion. The basic idea expected is to find list of all numbers reachable from every number in the input. The final answer will be a number reachable by all numbers and the sum of operations taken to reach this number from every number in the input will be minimum.
If there exist multiple numbers with the same number of steps, then we print the minimum number (Asked by @vivekmufc in comments)
Also, a major observation is that since we want the minimum number of steps, all the reachable numbers we find from the input numbers will be <=max number in the input. This is because of the following situation:
Assume that you are multiplying/dividing the maximum number by m. This would require to modify all the numbers accordingly to try and make them equal again, which is not what we have to do.
The best solution was by @karranaggarwal which was absolutely spot on and did the same thing mentioned above. I am using his solution as reference.
Solution link: https://www.codechef.com/viewsolution/8551813
(Another similar problem you can try. You may learn a new approach after reading the editorial which could have been used here): http://codeforces.com/problemset/problem/558/C)
QBIT03: Changing Intervals
The key to this problem is that it is an easy typical dynamic programming problem. To solve it you should make a 2-dimensional boolean array where element i, j indicates if you are able to play song i with sound level j. Initially, you set 0, ‘b’ to true, and then iterate through all songs and sound levels where for each song i you update the values at i+1. Here is a very clear and lucid implementation of the problem.
Setter’s solution:: http://ideone.com/4KaAs3
QBIT04: A Simple Game
The second easiest problem of the contest. Probably got less submission because of the corner case. Here, all we have to check if the sum of the coins in the end if a multiple of the number of people present (n%sum==0). The corner case is when the sum of all the coins is 0 where the answer is -1 (essentially, no one has any coins in the beginning).
Setter’s solution:: http://ideone.com/jSHT8i
QBIT05: Sudz and Marbles
We can treat each string as a binary string, instead of red and blue balls. A string of this type is good only if every maximal contiguous subsequence of “0” has the length divisible by k. We can solve the problem using dynamic programming this way : Nr(i) = the number of good strings of length i. If the i-th character is “1” then we can have any character before and if the i-th character is “0” we must have another k - 1 “0” characters before, so Nr(i) = Nr(i) - 1 + Nr(i - k) for i ≥ k and Nr(i) = 1 for i < k..
Setter’s solution:: http://ideone.com/lsEbgz
QBIT06: Sudz and Cakes
This is a quintessential ‘greedy’ problem. Our main objective is to decorate as many cakes as possible with the given number of candles. A detailed explanation is as follows:
The order of the candles isn’t important, so instead or r, g, b, we’ll call them a0, a1, a2 and sort them in ascending order. We’ll now have a0 <= a1 <= a2.
There’s two case:
• 2*(a0+a1) <= a2. In this case, we can take a0 sets of (1, 0, 2) and a1 sets of (0, 1, 2), so the answer is a0+a1.
• 2*(a0+a1) > a2. In this case, we can continuously take a set of two candle from a2 and a candle from max(a0, a1) until a point that a2 <= max(a0, a1). At this point, max(a0, a1)-a2 <= 1, and since max(a0, a1) - min(a0, a1) <= 1 too, max(a0, a1, a2) - min(a0, a1, a2) <= 1. All we have to do left is take all possible (1, 1, 1) group left. Since we only take the candles in group of 3, (a0+a1+a2) mod 3 doesn’t change, so there will be at most (a0+a1+a2) mod 3 candles wasted. We go back to the beginning now. The answer is (a0+a1+a2)/3
Another way to think about the problem:
assume a0 <= a1 <= a2. and sum = a0 + a1 + a2.
best case would be sum / 3. because no matter what we do we will always be left with sum % 3 balloons. now when can we get sum / 3 cakes and when we can not:
case 1: if 2 * (a0 + a1) <= a2 than it is obvious that we can not get more then a0 + a1 cakes because at each cake at least 1 candle is subtracted from a0 + a1, and by taking 2 from a2 and 1 from a0 + a1 at each turn we can get exactly a0 + a1 cakes.
case 2: if 2 * (a0 + a1) > a2. let’s prove that we can get sum / 3 cakes in such case. By tactic: taking 2 from a2 and one from max(a0, a1), a0 + a1 will not become zero before a2 becomes zero, which means that at some point a2 will become at most max(a0, a1). and at that point difference between a2 and max(a0, a1) will not be more than 2. Now we know that max(a0, a1, a2) — second_max(a0, a1, a2) is not more then 2. we can use this as an invariant. Tactic: taking 2 from max and one from second_max does not change invariant. now suppose we have some choosing tactic, we are stuck when we have situation like this a 0 0 where a >= 0 or 1 1 0. if a <= 2 it means choosing was optimal because no matter what we do we will be left with sum % 3 candles. and second finish(1, 1, 0) is also optimal by same reason. answer in both cases will be sum / 3. according to our invariant we will not be left with a 0 0 with a > 2 because if a > 2 then our invariant does not hold. so we now that our choosing was optimal and answer is sum / 3.
Now what min(sum / 3, a0 + a1) does is exactly checking if 2 * (a0 + a1) <= a2. because if a2 >= 2 * (a0 + a1) (case 1) then sum / 3 = (a0 + a1 + a2) / 3 >= (a0 + a1 + 2 * (a0 + a1)) / 3 = a0 + a1. so min(sum / 3, a0 + a1) will be a0 + a1 (exactly answer to case 1).
if a2 < 2 * (a0 + a1) (case 2) then sum / 3 = (a0 + a1 + a2) / 3 <= (a0 + a1 + 2 * (a0 + a1)) / 3 = a0 + a1 so min(sum / 3, a0 + a1) will be sum / 3 (exactly answer to case 2).
Setter’s solution:: http://ideone.com/Yv0NSj (almost literally 2 lines :))
QBIT07: Sudz and FIFA
This problem requires basic knowledge of combinatorics and probability.
Let’s call Sudz’s team A and Raghav’s team B. The input x represents the skill level of A and y represents the skill level of B. Lets assume we know the probability that team A will score a prime number of goals (lets call this probability Pa) and that team B will score a prime number of goals (Pb). Since those events are independent, the probability that at least one team scores a prime number of goals will be equal to Pa + Pb - Pa * Pb.
Now lets try to compute the probability that a team will score a prime number of goals. A 90-minute game contains only 18 5-minute intervals, and a team can score at most one goal during such interval, therefore a team can score at most 18 goals. Now we need to find all prime numbers Pi not greater than 18, compute the probabilities for each team to score exactly Pi goals, and sum those probabilities to get numbers Pa and Pb. To find primes you may either use the sieve of Eratosthenes, or just pre-code them into an array.
The last but not the least - how to compute the probability for a team with skill S to score exactly K goals during a game? Assume that we’ve selected K intervals and want to compute the probability that the team has scored in each of those K intervals and did not score during any other interval. This probability is equal to Sk * (1 - S)(18 - k) (Sk is the probability to score during k intervals, and (1 - S)(18 - k) is the probability not to score in any of other (18 - k) intervals). And the last step - since there are 18! / (k! * (18 - k)!) ways to select k intervals, the final answer is Pa = (Sum over all primes K) (18! * xk * (1 - x)(18 - k) / (k! * (18 - k)!). Of course, to compute Pb you’ll need to replace Skill Of Team A (x) by Skill Of Team B (y).
Setter’s solution:: http://ideone.com/0Gx5Aa