Hi guys,
I would like to thank all participants for making this event a grand success and specially thank ck98, darklight13, LightYear, kunj017, scameeer, leviOosa and hackcyborg for the problem setting and testing efforts and specially for actively managing the queries during contest!!
So, without wasting more time I'd like to congratulate our winners:
Based on the leaderboards following people have qualified for prizes:
Overall top 3:
Top 5 Indians:
Top 2 from IIT Patna(presently studying):
Winner from 1st year IIT Patna
Editorals!
Is It Some Space Cakewalk?
Problem Author: darklight13
The main idea for problem was pigeon-hole principle i.e in worst case we pick all the different type of cakes first and then any additional cake would make a pair repeat. So the answer to the problem was number of different types of cake in the list + 1.
Time Complexity O(n+max(T)).
Kunj Destroys Asteroids in 13th Dimension
Problem Author: darklight13
This problem can be solved in many ways like prefix sum , window sliding or even binary search.
I will discuss one with partial sum. The equation of the rhombus can be represented by |x| + |y| = X. Thus we only need the manhattan distance of the points. We make a prefix array that will store number of points less than or equal to manhattan distance i for each i. We calculate the points lying between X and X+K using prefix sum for each X where X is prime which can be computed by sieve. For each X the number of points lying between the rhombi would be pre[X+k] — pre[X-1]. Maximum of all such iterations will be the answer.
1-2-3 Subsequence
Problem Author: scameeer
The naive solution of iterating from l to r for each query will give TLE. Thus we use segment tree. At each node in the segment tree we store 6 values. 1. Length of maximum subsequnce strating from 1 and containing only 1. 2. Length of maximum subsequnce strating from 2 and containing only 2. 3. Length of maximum subsequnce strating from 3 and containing only 3. 4. Length of maximum subsequnce strating from 1 and containing only 1 and 2. 5. Length of maximum subsequnce strating from 2 and containing only 2 and 3. 6. Length of maximum subsequnce strating from 1 and containing only 1, 2 and 3. Now when building the segment tree you can maximize these values at each node to get the answer. At each node combine when with possible combinations like 1+(2-3), (1-2)+3, 1+(1-2), (1), (2), (3), (1-3)+3, 1+(1-3). The answer to each query will be the maximum of the above values. This can be better understood in editorial code. A much clean solution can be: https://codeforces.net/blog/entry/71357?#comment-558146 Thanks to fugazi
Universe is random, but is it?
Problem Author: Nightmare05
First off, we begin by observing that since average of a child is his average over all exams he appears in, the expected score of a child is independent of E (the number of exams he appears in) and by a similar argument the answer is independent of N (number of students) as well. So, we know that answer is a function of M (maximum marks) and K (number of re-evaluations only) f(K,M). And now observe, a child would go for re-evaluation only if he scores less than or equal to f(K-1,M) else he won't go for further re-evaluations.
Divide the Country
Problem Author: LightYear
For this problem in particular we saw a lot of creative solutions. But still for the sake of editorials, here is the solution we thought.
First, check if the given graph is a tree. If yes, then output n — 1. If not then there exists at least one cycle. Choose any vertex which is part of a cycle. Let's call it u. Run dfs from u. Now suppose you are currently at vertex v. If there is a non-bridge vertex in the dfs subtree of v then you obviously cannot remove the edge between v and its parent and it is no longer a candidate for the answer. After checking that condition if the edge between v and parent of v is still a candidate then it means that the dfs subtree of v consists only of bridges. Keep track of the diameter of the subtree. If diameter is same as the current maximum diameter then check for the number of nodes in the subtrees.
Will You Win The Prize?
Problem Author: leviOosa
The question is given as if it has to be solved online, but actually it is an offline question. Take all the characters given in all queries in sequence to make a string (S1). The given string is named as (S). Make string (T)=S1+#+S. Now apply “KMP” on this string (T). In the array obtained by KMP take the answer from (n+1)th index to (2n)th index. This is our required l(i). So, ans(i)=l(i)*2^i. It’s easy to calculate the binary representation of ∑(i=1 to i=n) ans(i). Refer to the solution code for better understanding.
Yet Another Permutation Array!
Problem Author: scameeer
With the given cumulative sum array A, find out the elements in the array P. This can be easily done by knowing how cumulative array get build. The first element of the cumulative array will also be present the array P. The rest elements can be found using A[i]-A[i-1] for all i>=1 to n-1 (0-based indexing). Now in these conditions answer will be -1: 1. The number of distinct elements in P are not n. 2. If the distinct elements are n, all integers from 1 to n are not present. This can be done by storing the above made P array elements in set data structure and iterating them. In all other cases answer exists. Print the array P formed.
Binary Matching
Problem Author: Nightmare05
Since a lot of people were interested in the proof of this problem specially, I decided to write a complete rigorous proof and well since some stuff is mathematical I am writing on paper and uploading pics. Pic 1 Pic 2
