Hello, Codeforces!
I would like to invite you all to Alkhwarizm 2018, the flagship coding event of Aparoksha — The Annual tech fest of IIIT-Allahabad.
It will contain 10 tasks of varying difficulty and you will get 5 hours of time to fight this fierce battle of Codditch(another version of Quidditch).
The contest will be an External rated contest. We are happy to announce that Alkhwarizm 2017 was the first External rated contest in the history of Codechef and this year Alkhwarizm 2018 is the first External rated contest for both Divisions after the New Rating Division system on Codechef.
The problem setters and testers are me(alooochaat1998), blake_786 and priyanshupkm. Buckle up for an adventure ride through the wizarding world of Harry Potter once again. Each problem you solve will score a goal. Score all goals in this fierce battle of Codditch and we'll make sure that you get the lion's share in Monex Melicis (the money potion, another version of Felix Felicis).
The contest starts at 9:00PM (IST) on 16th March,2018. Check your timezone here.
Prizes:
The best wizard/witch will get a lion's share of 10K INR.
The 2nd best wizard/witch will get a panther's share of 6K INR.
The 3rd best wizard/witch will get a wolf's share of 4K INR.
Top 5 global winners and top 5 Indian winners will get 300 laddus each straight from the kitchen of Honeydukes.
Register right now at the link to be eligible for getting Monex Melicis. The contest is open for all but prize money is only for Top 3 college students from the global leader board.
Past Alkwarizm links : ALKH2017, ALKH2016, ALKH2013, ALKH2012.
Good luck everyone! Hope to see all wizards and witches on the leaderboard.
Reminder : Contest starts in 1 hour.
Update : It was great seeing so many submissions. Thank you for participating. Short Hints will be provided within 2 days since we are quite busy in tech-fest events. Also, detailed editorial will be announced within a week. Congratulations to all the winners. Thank you all for participating.
Update 2 : Sorry for removing the blog suddenly. I had forgotten to repost after saving the draft. Rest of the short hints will be updated within tomorrow.
Update 3 : All the short hints are given. Editorial will be posted within a week.
Short Hints:
HELPVOLDStatement's second paragraph shows that Voldemort has to go from room having lowest energy(to which he arrived) to room having highest energy in a sorted manner. Hence first sort the energies in increasing order and take the sum of pairwise adjacent energies to get the answer.
HARRYWNDLet f(i,x) be the maximum number of wands using which we can make a stick of length x using the types of sticks from type 1 to type i.Our answer is f(K,N). The recurrence can be written, f(i,x) = max(f(i-1,x), f(i-1,x-len[i])). Similarly for minimum g(i,x)=min(g(i-1,x),g(i-1,x-len[i])).
HEDWIGThe intended solution was using Small to Large trick. We can maintain 2 maps for each vertex, one for storing the frequency of colors in its subtree, and second for storing the counts of colors that appear specific times. While merging the maps, we can use the Small to Large trick to reduce the complexity to O(n*log n).
ROOMOFRMForgetting about the constraints, we can use binary search to find answer to 1st type of query. Applying binary search to each query won't pass the time limit. We can use Parallel Binary Search for this. Solution of second query can be found out by traversing the operations backwards and using disjoint set union.
HARRYHBPWe can solve this problem using Centroid Decomposition and BIT.
Find the centroid of tree.
Right now we are finding the value of min_in_path * max_in_path for all the paths passing through given centroid.(this can be done using BIT). Add this value to your final answer.
Remove the current centroid and recursively calculate the value of P for all the decomposed trees and add them to your answer.
[As simple as divide and conquer]
Now how to calculate the value of min_in_path * max_in_path for all the the paths passing through given centroid. Run a dfs from the centroid and store the minimum and maximum value from root node(centroid) to current node in a vector of pair.
Now the problem is reduced to :
Given a vector of pair find the summation of min(A[i].first, A[j].first) * max(A[i].second, A[j].second) for all pair i,j in the index of array. Think about it.
Hint : This is the right place to use BIT.
HARRYDH1This was a game theory problem with range queries and use of trie to build a tree on which game will be played. The game is known as Hackenbush which is pretty famous.
Basically we have to build a forest of trees using given strings on which the game will be played. Each move is nothing but removing an edge from a tree which leads to removing its subtree which is not connected to the root anymore.
Each game is played on a range of trees where number of string used to construct it is less than k.
Step to proceed:
Build trie for all the strings with a particular id.
Build tree from each trie on which game is played.(Redundant)
Find grundy number for each each tree.
For each query construct a set S of grundy values of all trees where number of strings used to construct it is less than k in range l to r.
Let the xor of all the values in set S be g. Find the frequency of g in S.
Step 4 and 5 can be done using merge sort tree.(How ?)
HARRYCOSIntended solution is to use Hashing. For Hash you can either use two primes or it can even be done using one prime(How ?).
Find the Hash for each K * K submatrix of matrix A save the count of each hash in map A.
Find the Hash for each K * K submatrix of matrix B save the count of each hash in map B.
Now to count total number of equal submatrix pairs iterate on each hash value and add the product of count of this hash in map A and map B to your final answer.
Solutions with a complexity of O(n * n * log(n*n)) , appropriate optimization and strong hash can pass all the test cases.
HARRYPSSBreak the summation into 2 parts.
1st part :- consider 2 cases :-
when N is odd ==> 2^(N - 1)
when N is even ==> 2^(N - 1) + C(N, N/2)/2
C(N,N/2) can be easily calculated using Lucas Theorem
2nd part :- Fibonacci(n) using matrix expo
HARRYGOFSort the queries in reverse order. Store pairs of (A[i], i) in vector and sort the vector. Maintain a segment tree to answer queries of L to R (Refer to the problem http://www.spoj.com/problems/GSS1/). Initially Update all points of segment tree with K. For each query update only those points for which A[i] > Q[i].P. In this way only N updates will occur.
HARRYDH2Sort the values on the basis of age . For each index a range is needed which can be calculated using binary search. For finding answer for a range construct a segment tree where each node contains 2 matrix M^S[i] and M^(S[i] — 2) where M represents the matrix constructed from recurrence for F(N). Merge operation can be find easily using these 2 matrix. The intended solution was to use diagonalization of matrix to find M^S[i] and M^(S[i] — 2).
Auto comment: topic has been updated by alooochaat1998 (previous revision, new revision, compare).
Note: you can participate in Alkhwarizm contest only if you have Alzheimer.
Did the intended solution of HARRYHBP involve Centroid Decomposition + Implicit 2D segment tree?
I have a solution using these two DS. Complexity — O(N*(LogN)^3). But I thought it was an overkill. Also, TL was too strict for this complexity.
The intended solution was using centroid decomposition and fenwick tree with a complexity of O(n * logn * logn).
We will be posting detailed solutions soon.
EDIT : Hint for the problem is posted.