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:
Prashant Shishodia
Based on the leaderboards following people have qualified for prizes:
Overall top 3:
Top 5 Indians:
Top 2 from IIT Patna(presently studying):
Editorals!
Is It Some Space Cakewalk?
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
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 the answer.
1-2-3 Subsequence
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://mirror.codeforces.com/blog/entry/71357?#comment-558146 Thanks to fugazi
Universe is random, but is it?
Divide the Country
Will You Win The Prize?
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.
