RoboElection solution: Facebook hacker cup 2013 Round 2

From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details

This question is the second question(Carried 35 marks out of 100) for the Round 2 of 2013 hacker cup. only top 100 contestants will be moved to Round 3.

Problem Statement

In the not so distant future the world is populated by robots and ruled by an evil robot emperor. Every robot in the world can be identified by a unique numeric ID, and the list of all the existing robot IDs is easily accessible to everyone. One day the emperor decided to call for a general election to preserve an illusion of democracy. He set it up in the following way:

• – Every robot can cast at most one vote per round of voting and the votes are anonymous.
• – The only option on the ballot is the vote for reelection of the emperor.
• – If at least P percent of the population cast votes for the emperor he becomes reelected for the next millennium.
• – Otherwise the emperor declares the vote void, disassembles K robots with the lowest ID numbers (who he finds to be the most rebellious), and then if there are any functional robots left he restarts the whole process.

All the robots are perfectly logical but also rather lazy and prone to procrastination. That’s why after figuring out the plan of the emperor, they will abstain from voting unless they have to vote to survive the election (including this round and all later rounds). If they will die whether or not they vote, they will vote in the hope that the emperor will spare them. (He won’t, because he’s evil!).

Problem

Given N – the initial population size, K – the number of robots disassembled after an unsuccessful vote and P – the required percentage of votes.

Compute the number of times the vote will take place.

Input

The first line contains the number of test cases T, where 1 ≤ T ≤ 100

Each case is a single line with three space-separated integers N K P

0 < K ≤ N ≤ 1’000’000’000’000; 0 < P ≤ 100

Output

For test case i, numbered from 1 to T, output “Case #i: “, followed by a single integer, the number of times the emperor will have to call a vote before getting reelected.

Example

In the first case we have three robots. Two of them are facing disassembly, so they will vote for the emperor. The third robot will survive even if he abstains in the first round, so he doesn’t vote. But two out of three is not enough to reach the 75% minimum, so the election proceeds to a second round. The election ends when the single remaining robot casts a vote for the emperor.

In the second case again two robots are in immediate danger, but the next two robots are forced to vote as well, otherwise they would end up in the same situation as in the first example case. Now with the 4 out of 5 casting the vote the election successfully ends.

Example Input

5
3 2 75
5 2 75
75 8 20
30 15 10
1234 7 44

Example Output

Case #1: 2
Case #2: 1
Case #3: 2
Case #4: 1
Case #5: 60

Solution

From the problem it is clear that all robots who know they will not die will not vote until they know they are safe(means there are k more robots with smaller id’s present). Also all robots who know that they can not escape death will vote in the hope that emperor will spare them.

Lets assume you have n robots in ascending order of id’s, so for every unsuccessful election last k robots will be disassembled. thus finally i= n%k robots will remain(if n%k =0, k robots will remain, i = k). these remaining robots will vote in the favor of the king as they know now it is there turn to die, and remember they will vote only when there are i robots remaining as they know they are safe otherwise.

Now, at any point of time we can calculate v more robots required for the election to be successful such that v = p% of the total robots.

v = (i+v)*p/100;
100v = p*i + p*v;
v*(100 -p) = p*i;
v = p*i/(100-p);
//If this is a decimal we have to take the higher number 
//so we can write it as (p*i -1)/(100 -p) +1; or use a ceiling function by doing calculation on decimal variables.
//also we can say v can even be a multiple of k, thus if(v %k != 0)=> v = v +k -(v%k); 

So, if at any point of time there are x more robots present then i, such that i+x = n. if x < v then number of elections required will be 1(for i robots to decide) + x/k(number of times election should be held to disassemble x extra robots). and if x > v
i = i+v;
x = n-1; or //x-v;
//and then calculate new v and apply same operation.

Here is the java code for the above explanation:-

public class RoboElection {
	
	public long getNumberOfElections(long n, long k, long p){
		long i = n %k;
		if (i ==0)
			i = k;
		long pre = i;
		long v;
		if(p == 100){
			pre = i;
		}else{
			while(i <= n){
				pre = i;
				v= (p*i -1)/(100 -p)  + 1;
				if(v%k != 0){
					v += (k - (v%k));
				}
				i+=v;
			}
		}
		return 1 + (n - pre)/k;
	}
}

Facebook Comments