Invitation to Alkhwarizm 2018 (Rated)

priyanshukm · March 14, 2018, 7:55pm

Namaskar Codecheffers,

I would like to invite you all to the flagship coding event [Alkhwarizm 2018][1] organized as a part of annual Techfest of IIIT Allahabad - [Aparoksha 2018][2].

So Get ready to lose yourself in this Algorithmic Extravaganza. It is an individual event. The problem set will comprise of 10 problems of varying difficulty and you will get 5 hours to crack it.

The contest will be an [External rated contest][3]. We are happy to announce that [Alkhwarizm 2017][4] was the first External rated contest in the history of Codechef and this year [Alkhwarizm 2018][5] is the first External rated contest for both Divisions after the [New Rating Division][6] system on Codechef.

Contest link - [Alkhwarizm][7]

The total prize money is worth INR 20K (10K + 6K + 4K). Also top 5 Global winners and top 5 Indian winners will get 300 laddus each.

So be ready to have a nail-biting experience on [Mar 16 - 9 pm to 2 am IST][8].

![alt text][9]

And if you are a Harry Potter fan, you got a good news. The problem statements contains reference from the wizarding world of Hogwarts.

P.S. : If you have at least watched the movies, good for you :P.

Register right now at the link given [here][10] to be eligible for prize money. The contest is open for all but prize money is only for Top 3 college students from the global leader board.

Problem Setters & Testers - [Priyanshu Kumar][11], [Mohammad Ayan Sheikh][12], [Rohan Nayak][13]
(StrokinThreesOnSmokinTrees).

I would like to thank all the Codechef members for their help and support in making the journey of Problem Setting really easy.

Past Alkhwarizm Links : [ALKH2017][14], [ALKH2016][15], [ALKH2013][16], [ALKH2012][17]

Good Luck and Accepto patronum(:P) !!

aryanc403 · March 15, 2018, 12:07am

Thanks Bro. We are comming.

P.S. ask @admin to add this contest link on homepage competitions just above cook-off so that everybody can see and know this is rated.As they did for ICL2018

priyanshukm · March 15, 2018, 2:32pm

Thank You.

priyanshukm · March 17, 2018, 2:31am

Short Hints will be posted within 48 hrs and Full Editorial will be posted within a week.

Thank You for participating and Congratulations to the winners. Some unexpected things happened, like the great deviation of number of submissions for some problems from what we had thought of. But overall it was great seeing such an overwhelming response from the Codechef Community.

Stay tuned for editorails.

priyanshukm · March 19, 2018, 2:11am

SHORT HINTS

HELPVOLD :

Statement’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.

HARRYWND :

Let 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])).

HEDWIG :

The 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).

HARRYPSS :

Break 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

HARRYCOS :

Intended 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.

HARRYGOF :

Sort 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.

HARRYDH2 :

Sort 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).

HARRYDH1 :

This 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 ?)

ROOMOFRM :

Forgetting 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.

HARRYHBP :

We can solve this problem using Centroid Decomposition and BIT.

Find the centroid of tree.

Right now we are finding the value of (minimum In path) * (maximumInpath) 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 (minimum IN path) * (maximum 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.

vagesh_verma · March 24, 2018, 2:21pm

Any idea when will we get laddus of this contest?

priyanshukm · March 25, 2018, 2:12pm

I think laddus are credited really late. You have to wait for may be about 3-4 months at max.

harrycoda · March 27, 2018, 11:41am

I am not sure if the Codechef policy doesn’t allow copied problems in a rated round, but I think it’s quite unfair if people can just take codes off another website and paste them here and then get a huge rating increase.

P2 was obviously classic, P3: [HEDWIG][1]
The only difference is instead of exactly X vertices the original problem had ‘atleast’. 100% Same approach.

I didn’t solve more problems, but who knows if they were copied as well and half of the solvers didn’t even have to actually ‘solve’ them in contest.
[1]: http://codeforces.com/problemset/problem/375/D

aryanc403 · March 28, 2018, 2:49am

@harrycoda But the irony here is this question was done by 52 participants out of ~800. I’m not taking stand for anyone on this. Just wanted to point this out. And yes I strongly believe that questions should not be copied. And codechef have policy which does not allow question to be copied. You can refer here https://www.codechef.com/FEB18 a question was removed just because they got to know that this question was available on internet. And in this case also if they got to know about this then thay would have responded timely and removed that question. Plz, mail them at [email protected]

aryanc403 · March 28, 2018, 2:50am

Just running out of words so continuing here.
@admin @vijju123 Plz, look into this. And if anything can be done now then do the needful.

vijju123 · March 28, 2018, 1:44pm

Frankly, I see nothing wrong if the easier questions seem-classic, or are based on standard ones. They are easy for a reason. So p2 being classic is no problem to me.

Case with P3 was a bit more concerning, since that was a bit more on Medium side in difficulty scale than P2. Its hard to tell if its a case of copying, because its a Div1-D v/s P3 of a contest, combined with the fact that theres a huge database of problems on the internet, it can be hard to check if your problem is already there or not. In fact, for P3, we did a check on that particular setter- to see if any other problem of his in the contest “highly resembles” some other problem on internet- because of course, 1 or perhaps even 2 problems may resemble, but if multiple are resembling then its fishy of course. We did not find any other such problem after best of our efforts, if you found elsewise, please report so.

That being said, I really dont see why people even have a “doubt” that codechef allows for copied problems in rated rounds- despite us cancelling several external contests and banning institutes in past- that too in unrated ones.

Regarding what actions we might take/have taken- I really don’t get it why @harrycoda instead of reporting the problem then and there either via mails (*preferable means) or appropriate thread resorted to “I didn’t solve more problems”. I will take that line as he went offline after that, or anyways after finding a copied one he didnt report it to us then. Either way, reporting such instance after more than 10 days of contest and expecting an action from our side cannot be entertained because its simply unfeasible for us. Please report such instances quickly and at apt time. You can yourself judge, what can we do 10 days after the contest when ratings are updated and another rated round has also taken place? Rolling back ratings isnt a good choice either. If it were reported during contest, we would have had people from @admin panel look up and verify other problems as well and would have made a decision (eg- removing a problem) and compensated it via increased time or any similar means. Its not possible now.

harrycoda · March 28, 2018, 2:19pm

I found that the problem was copied only recently when I fell upon it via a very popular CF post on the trick that was used in the problem. In contest I just thought it was a very crude application of the trick and implemented it not bothering to check whether it was copy. I was a little surprised at the number of subs but then I let it be. And no, I did not leave the contest, I just couldn’t solve more. I feel being such a popular problem, with hundreds of subs on CF someone should have got to know on time. I know nothing can be done now, except taking care in the future.

rj25 · March 28, 2018, 3:18pm

Has been more than a week still no editorials posted.

vijju123 · March 28, 2018, 6:39pm

Ok. Usually when people say they found copied, they mean it “They found it during the contest.”.

with hundreds of subs on CF someone should have got to know on time.

I get your intuition, but thinking in @admin 's shoes, we just cannot rely on such a thought. The figures can vary vastly from what we estimate. Thats why we dismissed possibility of that problem having made contest “Very unfair” , except the fact that it was a lottery ticket if one could find it online. Then again, in my opinion, if he used google that aptly, let it be. I cant find any shit in google even in long contests.

priyanshukm · March 29, 2018, 6:54pm

@harrycoda

Apologies !!

First of all, I would like to inform you that we have been working on the problem set since December 2017 so that the problems are new and fun to solve.

About Problem 2 being classic. Yes, I agree as it was added to the contest during the last few minutes in order to balance the difficulty level. And I don’t think there is any problem with an easy problem being classic. It was kind of intended that more people are able to solve it that’s why we made it classic.
I guess you already know this still, I want you to know that when a contest is rated all the problems are checked by the moderators, problem setters, and testers for them being similar to any other problems. Unfortunately, we were not able to find any such problem which was similar to HEDWIG before the contest.

I would like to emphasize the point that I am not encouraging copying of problems, neither defending this unfortunate accident by the next statement. But, as the question was not easily found on googling and the number of submissions for this problem were really low, I would say it hasn’t affected the rating of anyone in a severe manner. And as suggested by @vijju rolling back ratings is not a solution.

Apologies again.

priyanshukm · March 29, 2018, 7:00pm

I am sorry but all three of us are super busy with the placement season on our head. You can ask for a detailed explanation of any of the problems right here or on the codeforces blog post. We are happy to help in any way possible.

rj25 · March 29, 2018, 7:33pm

I wanted help in hashing question. How hashing of entire matrix of k*k is done ?

priyanshukm · March 29, 2018, 8:06pm

Go through both of these submissions :

Hash used here for k * k matrix is :

p^(kk - 1) * a[1][1] + p^(kk - 2) * a[1][2] … p^(k*k - k) * a[1][k] + … + p^(1) * a[k][k-1] + a[k][k].
Write the above formula on paper in matrix form and you will quickly understand.

First one is O(nnk) solution.

Second one is basically optimized version of first one in whivh O(k) factor is removed.

rj25 · March 30, 2018, 3:13am

I did hashing by modifying value of matrix i.e. a[i][j] was changed to :
[a[i][j] | its row in kk matrix | its column in kk matrix] then after getting this value I calculated hash and used the same map method, it passes time limit but gives WA. Is it because of collision in hashing ?
Solution : https://www.codechef.com/viewsolution/17984694

harrypotter0 · March 30, 2018, 7:28am

I strongly agree with @aryan403 , this type of copy paste is not allowed and should be strongly discouraged. BTW, I messed this problem completely. But the point here is that solution should not be available on net, actions need to be taken.Can someone provide a solution to this?