PROBLEM LINK
Author and Editorialist: Avijit Agarwal
Tester: Sarthak Manna, Jatin Yadav
DIFFICULTY
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.