Connection Status:
Competition Arena > Bribes

Bribes

SRM 483 · 2010-03-12 · by espr1t

SRM 483 · 2010-03-12 · by espr1t · Dynamic Programming
Class Name: Bribes
Return Type: int
Method Name: minBribes
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

The Government in Bulgaria is elected every four years. When an election is held, most people don't vote. They then complain about the new government for the entire time they're in charge, but when the next elections are held four years later, they again don't vote.

Elleonora plans to use this low voter turnout to her advantage. She has found the key to the prime minister's chair: bribes. To ensure that she will win the election, she has decided to bribe all people, who show up on the day of elections, into voting for her. Due to the so called "shurobadjanashtina" (a Bulgarian term meaning that each person is related in some way to all other people), she doesn't even need to pay every voter. For example, if a young couple shows up to vote, bribing just one of them might be sufficient since the other will voluntarily vote for the same candidate.

All voters are lined up in front of the voting place. They are numbered 0 to N-1 from left to right. Each voter has two integer attributes - influence and resistance. They are given in int[]s influence and resistance, the i-th elements of which are the influence and resistance, respectively, of the i-th voter. Influence is a measure of how much a person can affect the decisions of the people surrounding him. Resistance is a measure of a person's will to vote for different candidate. If a person's resistance ever falls to zero or less, he will vote for Elleonora. If Elly bribes the i-th person in line, that person's resistance will be reduced by influence[i]. Since that person affects the people around him, the resistances of the person directly to his left and the person directly to his right (the (i-1)-th and (i+1)-th person, respectively) will each be reduced by influence[i]/2. All division in this problem is integer division, meaning that any fractional parts are discarded. The resistances of the (i-2)-th and (i+2)-th people will be reduced by influence[i]/4, and so on. More formally, when the i-th person is bribed, the resistance of the j-th person is reduced by influence[i]/2^(abs(i-j)), where abs(i-j) is the absolute value of i-j. If, after a number of bribes, everybody's resistance is less than or equal to zero, she has won all the votes, and therefore the election.

Return the minimum number of people she must bribe to win the election. She can't bribe the same person more than once. To win the election, every single person must vote for her. If this is impossible, return -1 instead.

Constraints

  • influence and resistance will each contain between 1 and 50 elements, inclusive.
  • influence and resistance will contain the same number of elements.
  • Each element of influence and resistance will be between 1 and 500, inclusive.
Examples
0)
{ 10, 3, 5, 3, 1 }
{ 11, 2, 7, 3, 1 }
Returns: 2

The influence can be less than, equal or greater than the resistance of a given person. Here the optimal strategy is to bribe the people with indices 0 and 2, decreasing the resistances of the people by {10, 5, 2, 1, 0} and {1, 2, 5, 2, 1}, respectively, making the final resistances {0, -5, 0, 0, 0}.

1)
{ 15, 15, 15 }
{ 13, 42, 13 }
Returns: -1

This one is impossible. Even when bribing all of them, the final resistance is {-12, 13, -12}. The cake is a lie.

2)
{ 10, 16, 4, 7, 1, 1, 13 }
{ 10, 16, 4, 7, 1, 1, 13 }
Returns: 4

After bribing the people with influence 16, 13, and 10, only one person remains with barely positive resistance. She still has to bribe that one person to have full support and win the election.

3)
{ 471, 183, 376, 296, 408, 19, 422, 403, 469, 252, 338, 255, 446, 489, 171, 58, 113, 485 }
{ 232, 270, 172, 261, 15, 380, 276, 151, 403, 48, 90, 215, 457, 231, 277, 269, 202, 336 }
Returns: 7
4)
{ 479, 340, 398, 40, 477, 181, 422, 377, 60, 486, 15, 500, 307, 1, 2, 65, 411, 374, 446, 401 }
{ 402, 87, 20, 76, 468, 493, 252, 98, 216, 58, 89, 500, 89, 26, 8, 125, 269, 116, 426, 81 }
Returns: 7

Submissions are judged against all 131 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Bribes with a public method int minBribes(vector<int> influence, vector<int> resistance) · 131 test cases · 2 s / 256 MB per case

Submitting as anonymous