PROBLEM LINK:
Author: Ankit Srivastava and Uttam Kanodia
Tester: Roman Rubanenko
Editorialist: Amit Pandey
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 x-S[0], x-S[1], .... , x-S[k-1] can be allotted, or if x=0, the base case. Thus, \forall x>0,
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:
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
Tester’s solution can be found here
