You are not logged in. Please login at www.codechef.com to post your questions!

×

ANKMARKS - Editorials

PROBLEM LINK:

Practice
Contest

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$,

$$check(x) = check(x-S[0]) \hspace{2 mm}or\hspace{2 mm} check(x-S[1]) \hspace{2 mm}or\hspace{2 mm} ... \hspace{2 mm}or \hspace{2 mm}check(x-S[k-1]) $$

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[i-1] +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
Tester's solution can be found here

This question is marked "community wiki".

asked 20 Jun '15, 18:18

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

edited 09 Feb '16, 20:02

admin's gravatar image

0★admin ♦♦
19.8k350498541

It has been fixed. Thanks for pointing out.

(22 Jun '15, 00:26) amitpandeykgp4★

Can someone explain the matrix expo solution for check(x)?

link

answered 22 Jun '15, 13:54

venkatnani82's gravatar image

2★venkatnani82
211
accept rate: 0%

"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(x-S[0])|| f(x-S1) || ...|| f(x-S[k-1]) and 1<=S[i]<=50

So, f(x) = (a1*f(x-1)) || (a[2]*f[x-2]) || ... || (a[50]*f[x-50]) where a[i] = 1 if S[j]=i for some j < K.

Now the matrix form can be written as:

Matrix Exponentiation 50x50

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.

link

answered 22 Jun '15, 21:44

yash_15's gravatar image

5★yash_15
5181716
accept rate: 2%

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) code_master015★

Can u please help me with a Test Case for WA in the code http://ideone.com/bwqlxq ?

link

answered 22 Jun '15, 00:25

ravi_rk's gravatar image

2★ravi_rk
11
accept rate: 0%

edited 22 Jun '15, 14:55

Link for tester's and setter's code is not working

link

answered 23 Jun '15, 12:23

evil999man's gravatar image

7★evil999man
513
accept rate: 0%

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

link

answered 25 Jun '15, 13:23

worm4's gravatar image

2★worm4
1
accept rate: 0%

@amitpandeykgp tester's and setter's code link not working

link

answered 28 Jun '15, 19:43

achilles1993's gravatar image

4★achilles1993
112
accept rate: 0%

@admin Setter's and Tester's solution not visible :-(

link

answered 01 Jul '15, 00:30

ankurverma1994's gravatar image

4★ankurverma1994
415114
accept rate: 8%

edited 01 Jul '15, 00:31

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,299
×303
×81
×1

question asked: 20 Jun '15, 18:18

question was seen: 2,616 times

last updated: 09 Feb '16, 20:02