PROBLEM LINK:Author: Ankit Srivastava and Uttam Kanodia DIFFICULTY:Medium PREREQUISITES:Matrix Exponentiation PROBLEM:There are $N$ students and the marks awarded to any student should be linear combination of the elements of a given set, while satisfying other constraints as well. Find the minimum average of the marks which can be allotted to the students. In other words, find the minimum possible class average. EXPLANATION:There are various steps in solving the given problem. Let's go through them one by one. Let us call the given set of marks as $S$. First of all, let's make a function $check(x)$ which will tell if a given number $x$ can be awarded as a score to any of the students. Since the score is a linear combination of the elements of $S$, a score $x$ can be allotted iff any of the marks among $xS[0], xS[1], .... , xS[k1]$ can be allotted, or if $x=0$, the base case. Thus, $\forall x>0$, $$check(x) = check(xS[0]) \hspace{2 mm}or\hspace{2 mm} check(xS[1]) \hspace{2 mm}or\hspace{2 mm} ... \hspace{2 mm}or \hspace{2 mm}check(xS[k1]) $$ It is given that the answer to the problem will be at most $2^{52}$, so we need to check up to $2^{52} \times 1000 \approx 2^{62}$, which is a very large number and can be checked using matrix exponentiation technique. This method will take $O(50^3 \times \log{x})$ time. There is another excellent way of computing $check(x)$, which uses Dijkstra's Algorithm. It has been described here in a nice way. See tester's code for this approach. Now, for any given score, we can check if it can be allotted to a student, or not. So, let's make a list which contains all the scores which can be allotted. As we have to find the minimum average, we will try to allot minimum possible marks to each of the students. Minimum marks which can be allotted is $0$. Second minimum marks which can be allotted is the minimum element of the set $S$. Now, suppose someone has received $x$ marks, the guy which is located next to him should be allotted more than $2x$ marks. So, we will keep checking if $2x+1,2x+2,...$ can be allotted and allot the minimum possible marks. Now, we can make a allotment list $L$, which is the list of marks to be allotted to all the students in the class. $L[i]$ can be calculated as follows: $$L[0] = 0, \hspace{2 mm} L[1] = min(S), \hspace{2 mm}L[i] = min(x) \hspace{2 mm} \text{such that} \hspace{2 mm} x \ge 2L[i1] +1 \hspace{2 mm} \& \hspace{2 mm} check(x) = true .$$ Now, final part of the solutions is the calculation of the exact score allotted to each student: Pick each of the local minimum elements of the favorite array one by one. For each local minimum, allot the corresponding student $0$ marks. Keep going to the right of it as long as the favorability is increasing, and keep allotting the next element of the list $L$. Repeat the process in the left of the local minimum. Now, there will be multiple allotments at the same position corresponding to the each of the local minimum. To satisfy all conditions, every student will receive maximum marks among all the marks allotted corresponding to each local minimum of the array. Once every student has received their marks, average calculation is easy. Solution:Setter's solution can be found here
This question is marked "community wiki".
asked 20 Jun '15, 18:18

Can someone explain the matrix expo solution for check(x)? answered 22 Jun '15, 13:54

"So, we will keep checking if 2x+1,2x+2,... can be allotted" I want to know that why this wont give TLE! As regards the matrix exponentiation method, we can define f(x)= f(xS[0]) f(xS1)  ... f(xS[k1]) and 1<=S[i]<=50 So, f(x) = (a1*f(x1))  (a[2]*f[x2])  ...  (a[50]*f[x50]) where a[i] = 1 if S[j]=i for some j < K. Now the matrix form can be written as: Empty entries are also zeroes. And since we have to take the OR operation, we can modify the multiplication by replacing + with . Still my doubt remains whether checking 2x+1, 2x+2, 2x+3 ,... is feasible or not. answered 22 Jun '15, 21:44
1
Hi, I hope you found the problem interesting. First of all, marks of problems are bounded by 50 and K >= 1. So, in every consecutive range of 50 values we will have check(x) true for atleast one value. To solve this problem, you don't need to check for each x using matrix exponentiation. Since, you know answer will be found in at max 50 checks, you can simply exponentiate to 2x + 50. The matrix will contain check() value for all values from 2x+1 to 2x+50. (Why?) Moreover, you should observe that the matrix contains only 0s and 1s, so you should use bitmasks to optimize matrix multiplication.
(22 Jun '15, 23:59)

Can u please help me with a Test Case for WA in the code http://ideone.com/bwqlxq ? answered 22 Jun '15, 00:25

Link for tester's and setter's code is not working answered 23 Jun '15, 12:23

Acess denied to tester's and setter's code. What is happening here? Already there is a comment here and no one is responding. What is this guys?? answered 25 Jun '15, 13:23

@amitpandeykgp tester's and setter's code link not working answered 28 Jun '15, 19:43

@admin Setter's and Tester's solution not visible :( answered 01 Jul '15, 00:30

link http://discuss.codechef.com/questions/71951/zobayer.blogspot.in/2010/11/matrixexponentiation is redirecting to this page.
It has been fixed. Thanks for pointing out.