# CLMARKS EDITORIAL

Author and Editorialist: Avijit Agarwal

Medium

### PREREQUISITES

Observation and pattern recognition

### PROBLEM

M marks needs to be distributed among N students standing in a line. Every K^{\text{th}} student from the last student gets to be the leader and can determine the distribution of the marks. The leaders distribution is approved if at least 50\% of the present students vote for it. Otherwise last K students (including the leader) are expelled from the school and the new last student gets to be the leader. This process stops when a distribution is approved and the leader becomes the deciding student.

• Every student wants to maximize his/her marks or try not to get expelled if possible.
• They would expel any other student if he/she can get the same marks.
• If there are multiple distribution proposals maximizing the leaderâ€™s marks that would be accepted then he will propose the lexicographically smallest such distribution.

Find out who will be the deciding student and what maximum marks can the he get.

### EXPLANATION

The problem was inspired by the Pirate Riddle

Observation 1 \to N<=2*K

• N<=K,
Then the N^{\text{th}} student will become the deciding student and can get the full M marks as all of the present students will vote for the N^{\text{th}} student as otherwise they would be expelled

• N>K and N<=2*K,
Then also N^{\text{th}} student will be the deciding student and can get the full M marks as the last K students will vote for the N^{\text{th}} student unconditionally which is at least 50\% of the total students present.

Observation 2 \to N<=2*(M+K)

• N>2K and N<=2K+2*M,
Here too the N^{\text{th}} student will become the deciding student as he will get K votes unconditionally and can get the required number of votes by giving 1 mark to those students who would otherwise get 0 marks if the N^{\text{th}} students distribution is not approved. It can be proved that sufficient numbers of such students always exist. He would need to give 1 mark to at least \lceil ( N-2*K )/2 \rceil students. So the N^{\text{th}} student can get a maximum of M-\lceil ( N-2*K )/2 \rceil marks.

Observation 3 \to N >2*(M+K)

• N is in [2M+2K+1, 2M+3K],
Here no matter what the N^{\text{th}} student will never get the required votes and would get expelled. So the (N-K)^{\text{th}} student which will have index \leq 2M+2K will be the deciding student.

• N is in [2M+3K+1, 2M+4K],
Here the N^{\text{th}} student will be the deciding student. The N^{\text{th}} student gets 2*K votes unconditionally because if his/her distribution is not approved, then 2*K students would get expelled as the next leader would also get expelled as the next leader would belong in the above group of range [2M+2K+1, 2M+3K]. Moreover he can always get at least 50\% of votes by giving 1 mark to those students who would otherwise get 0 marks if the distribution of N^{\text{th}} student is not approved.

• N is in [2M+4K+1, 2M+7K]
Here no matter what, the N^{\text{th}} student will never be the deciding student and would get expelled. So here (N-x*k)^{\text{th}} student will be the deciding student, where x is the least value for which (N-x*k) belongs to the above group.

• N is in [2M+7K+1, 2M+8K]
Here the N^{\text{th}} student will be the deciding student as he get 4*K votes unconditionally and he can get the remaining required votes by giving 1 mark to those students who would otherwise get 0 marks if his approval was rejected.

• N is in [2M+8K+1, 2M+15K]
Here no matter what, the N^{\text{th}} student will never be the deciding student and would get expelled. The deciding student will be the [N-x*k]^{\text{th}} student, where x is the least value for which [N-x*K] belongs to the above group.

• N is in [2M+15K+1, 2M+16K]
Here the N^{\text{th}} student will always be the deciding student as he gets 8*K votes unconditionally and gets the remaining required votes using the marks.

Can you find a pattern here?
We can see that always a continuous group of K students can be the deciding student which ranges from
[ 2*M+ (2^i-1)*K +1] to [ 2*M+ 2^i*K], where i\geq2
Let z=2*M+ (2^i-1)*K +1
Then the continuous group ranges from z to (z+K-1).

• If N \geq z and N=(z+K-1-i), then the N^{\text{th}} student can get marks upto min(i/2,M)
• Otherwise if N belongs to outside these ranges, then [N-x*K]^{\text{th}} student will be the deciding student, where x is the least value for which [N-x*K] lies among one of the above ranges.

Let us take an example ->
K=3, M=2. Then the following values of N will be the deciding students.

• {1,2,3,4,5,6} can all get 2 marks. [1 - 2*K]
• {7,8,9,10} can get {1,1,0,0} marks respectively. [2K+1 - 2M+2*K]
• {14,15,16} can get {1,0,0} marks respectively. [2M+3K+1 - 2M+4K]
• {26,27,28} can get {1,0,0} marks respectively. [2M+7K+1 - 2M+8K]
• {50,51,52} can get {1,0,0} marks respectively. [2M+15K+1- 2M+16K]
and so onâ€¦

The required time complexity is \mathcal{O}(log{N})

The characteristic of the leader that he will always propose the lexicographically smallest distribution is only given to make the entire game deterministic such that for a given N, M, K all the moves can be deterministically pre-planned.

Moreover even without this characteristic the solution would be the same if all the leaders take absolutely no risk in proposing a distribution. Can you think why?

### SOLUTIONS

C++ solution can be found here.
Java solution can be found here.
Python solution can be found here.

4 Likes

I think this type of analysis is good for long challengeâ€¦

1 Like