Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Here is my Dynamic Programming solution.
It comes up with 6 since it counts the first point score as a lead change (no one is in the lead to someone being in the lead).
static void Main(string[] args)
{
int S1 = 10;
int S2 = 6;
int[] a = { 2, 3 };
int[,] max = new int[S1+1,S2+1];
for (int i = 0; i <= S1; i++)
for (int j = 0; j <= S2; j++)
max[i,j] = -1;
max[0,0] = 0;
// Loop through each array element
for (int j = 0; j <= S2; j++)
{
for (int i = 0; i <= S1; i++)
{
// Loop through each possible scoring increment at each array element
for (int x = 0; x < a.Length; x++)
{
int t1 = i - a[x];
int t2 = j - a[x];
// Case where team 1 scores these points
if (t1 >= 0)
{
// The max number of lead changes from before these points happened
int lastMax = max[t1, j];
// The max changes at this score should be at least the max from before this score happened
if (lastMax != -1 &&
lastMax > max[i,j])
max[i, j] = lastMax; ;
// If a lead change happened and that gets a new max number of changes, store that number
if( t1 <= j &&
i > j &&
lastMax >= max[i,j])
max[i,j] = lastMax + 1;
}
// Case where team 2 scores these points
if (t2 >= 0)
{
int lastMax = max[i, t2];
if (lastMax != -1 &&
lastMax > max[i, j])
max[i, j] = lastMax;
if( t2 <= i &&
j > i &&
lastMax >= max[i,j])
max[i, j] = lastMax + 1;
}
}
}
}
for (int i = 0; i <= S1; i++)
{
for (int j = 0; j <= S2; j++)
{
Console.Write(max[i, j].ToString() + " ");
}
Console.WriteLine("\n");
}
Hi, ChristmasDonkey,
I agree with you that it's a definitely dynamic programming question. And the dp function should be:
dp[i][j] = Math.max(dp[p][q]), if (i - j) * (p - q) > 0, here no lead change
Math.max(dp[p][q]) + 1, if(i - j) * (p - q) < 0, here lead changes
where p < i and p < j;
Couple of points
#1 : for (int i = 0; i <= S1; i++)
for (int j = 0; j <= S2; j++)
max[i,j] = -1;
max[0,0] = 0;
Now of Rows : S1
// Loop through each array element
for (int j = 0; j <= S2; j++)
{
Number of Rows : S2 .
These two are inconsistent .
#2 : In loops if (t1 >= 0)
{} and
if (t2 >= 0)
{}
You are considering maximum number of ways to get the score , Not maximum number of ways with lead change to get the score.
why do u start writing code like an idiot. Just tell your algo, and we will find out if its correct or not. I'm not going to read through your crap code and try to understand.
1:0, 1:2, 3:2, 3:4, 5:4, 5:6, 10:6. At least the lead could change 6 times, not 4. This is a math question, not a programming question, though.
The question is asking for finding the maximum number of changes. 4 is just an example.
Agree, this is a maths question, not programming question, every change lead to 1 minus among a,b
given 10, 6, it will be 6
given 5, 6, it will be 5, always the smaller number
shouldn't it be just min[S, S']. The losing team at most can lead maximum of the team score times. So does the wining team,
thanks for the pointer! after going through other possible examples, it makes sense.
if S!=S' :
min(S,S') is the max opportunities for losing team
return min(S,S')
else if S==S':
both teams have equal chance of winning
return S or S'
This works only if a single point can be scored; does not work if the minimum number of points that can be scores id 2 or greater
This solution definitely works, but as @Asonibare pointed out, it works for scores that increment by 1.
Again, the question is not clear if scores can increment in a range, that is if score increase can vary between certain values.
But if you think scores can increase by 2 or greater, then the maximum number of leads would be
min(S,S')/score increment value
Here is my algorithm to check if the scores can increment variably within a given range.
1. consider the least possible value in given range
2. min(S,S')/least possible value in given range
This will give me the maximum number of lead changes possible
Indeed one only need to recurse on the last step, ie, A[-1]
if finalA > finalB, then the last scoring should go to finalA to increase the chance of maximal exchanges of leads, if finalA - A[-1] < finalB, then the exchanges should be 1 + numberOfChanges(A[:-1], finalA-A[-1], finalB), otherwise it is numberOfChanges(A[:-1], finalA-A[-1], finalB).
Similarly, we can conclude for the case finalA < finalB. It needs discussion that if there is a tie, whether the original leader still considered to be leading or not.
My first thought of a solution was to use a graph of all the possible solutions and then simply to do BFS distance on the final score node. I think this is the best solution from a optimal perspective as it can achieve linear time. However, it does take quite a bit of code.
You can always do a recursive solution but this isn't efficient, heres my go. Note: I count a tie breaker as a leader change.
public static int getMax(int s1, int s2, int[] plays, int c) {
if (s1 == 0 && s2 == 0) return c;
int max = -1;
for (int i=0; i<plays.length; i++) {
for (int j=0; j<plays.length; j++) {
int s1_play = s1 - plays[i];
int s2_play = s2 - plays[j];
if ((s1_play < 0 || s2_play < 0) || (plays[i] == 0 && plays[j] == 0)) continue;
if ((s1 > s2) && (s2_play >= s1_play)) {
c++;
System.out.println(s1+":"+s2+"->"+s1_play+":"+s2_play+" "+c);
} else if ((s2 > s1) && (s1_play >= s2_play)) {
c++;
System.out.println(s1+":"+s2+"->"+s1_play+":"+s2_play+" "+c);
}
int x = getMax(s1_play, s2_play, plays, c);
if (x > max) {
max = x;
}
}
}
return max;
}
Here is my solution in ruby. I assume that it is always possible for a team to not score (ie, get 0). If that assumption is correct we start with the winning team (if the end is a tie it doesn't matter which team) and figure out the minimum amount they can score to get ahead of the losing team or get to the their final score. Then we switch teams and do it again.
scores = [ 0, 1, 2, 3 ]
final = [6, 10]
# find the minimum amount the team can score to
# trigger a score change or get to the final score
def find_min_score(team, actual, final, scores)
minscore = (actual[0] - actual[1]).abs
score = scores.select { |i| i > minscore }.first
if score and (actual[team] + score <= final[team])
score
else
minscore = final[team] - actual[team]
score = scores.select { |i| i >= minscore }.first
if score and (actual[team] + score <= final[team])
score
else
raise "error"
end
end
end
def team_play(team, actual, final, scores, inlead)
score = find_min_score(team, actual, final, scores)
actual[team] += score
puts "score is: #{actual[0]} : #{actual[1]}"
if (actual[0] != actual[1])
tmp = (actual.max == actual[team]) ? team : ((team == 0) ? 1 : 0)
if (tmp != inlead)
puts "change! team #{team} in lead"
true
else
false
end
else
false
end
end
scores.sort!
changes = 0
inlead = -1
inplay = (final[0] > final[1]) ? 0 : 1
actual = [0, 0]
puts "score is: #{actual[0]} : #{actual[1]}"
while actual[0] < final[0] or actual[1] < final[1]
if team_play(inplay, actual, final, scores, inlead)
changes += 1
inlead = inplay
end
inplay = (inplay + 1) % 2
end
puts "total changes: #{changes}"
Here is java code
key is you have to minus from final score ,
minus options are 0,2,3
e.g: 10-3 vs 6-0 --> 7-2 vs 6-0 (lead change)
public static void main(String[] args){
int _s1=10;
int _s2=6;
int[] _A={0,2,3};
int _c=0;
int max=solve(_s1,_s2,_A,_c);
System.out.println(max);
}
public static int solve(int s1, int s2, int[] A, int c)
{
if (s1 == 0 && s2 == 0) return c;
else if (s1 < 0 || s2 < 0) return -1;
int max = -1;
for (int i = 0; i < A.length; i++)
{
for (int j = 0; j < A.length; j++)
{
int sc1 = A[i];
int sc2 = A[j];
if (sc1 == 0 && sc2 == 0) continue;
boolean change = (s1 > s2 && s1 - sc1 < s2 - sc2 ||
(s1 < s2 && s1 - sc1 > s2 - sc2 ));
int x = solve(s1-sc1, s2-sc2, A, c + (change ? 1 : 0));
if (x > max) max = x;
}
}
return max;
}
4 times correct
public static void main(String[] args){
int _s1=10;
int _s2=6;
int[] _A={0,2,3};
int _c=0;
int max=solve(_s1,_s2,_A,_c);
System.out.println(max);
}
public static int solve(int s1, int s2, int[] A, int c)
{
if(s1==0 && s2==0) return c;
else if (s1<0 || s2<0 ) return -1;
int max=-1;
for(int i=0;i<A.length;i++){
for(int j=0;j<A.length;j++){
int sc1=A[i];
int sc2=A[j];
if(sc1==0 && sc2==0) continue;
boolean change=false;
if(
(s1>s2 && (s1-sc1 <s2-sc2) &&s1-sc1>0 && s2-sc2>0 && (s1-sc1!=1) && (s2-sc2!=1) )
||
(s1<s2 && (s1-sc1 >s2-sc2) &&s1-sc1>0 && s2-sc2>0 && (s1-sc1!=1) && (s2-sc2!=1))
){
change=true;
System.out.println("(+"+sc1 +")----> " +s1 +" : " +s2 + "<---(+" + sc2 +")");
}
int x=solve(s1-sc1,s2-sc2,A,c+(change==true?1:0));
if(x>max) max=x;
}
}
return max;
}
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+2)----> 4 : 3<---(+0)
(+3)----> 5 : 3<---(+0)
(+3)----> 5 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+2)----> 4 : 3<---(+0)
(+3)----> 5 : 3<---(+0)
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 4 : 3<---(+0)
(+0)----> 4 : 6<---(+3)
(+2)----> 4 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
(+0)----> 3 : 4<---(+2)
(+0)----> 3 : 4<---(+2)
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 4 : 3<---(+0)
(+3)----> 8 : 6<---(+0)
(+0)----> 5 : 6<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+0)----> 5 : 6<---(+3)
(+3)----> 5 : 3<---(+0)
(+0)----> 3 : 4<---(+2)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+3)----> 5 : 3<---(+0)
(+3)----> 6 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+2)----> 4 : 3<---(+0)
(+3)----> 5 : 3<---(+0)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+3)----> 5 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
(+2)----> 7 : 6<---(+0)
(+0)----> 5 : 6<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+0)----> 5 : 6<---(+3)
(+3)----> 5 : 3<---(+0)
(+0)----> 3 : 4<---(+2)
(+0)----> 3 : 4<---(+2)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+3)----> 5 : 3<---(+0)
(+3)----> 7 : 6<---(+0)
(+0)----> 4 : 6<---(+3)
(+2)----> 4 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
(+2)----> 5 : 4<---(+0)
(+0)----> 3 : 4<---(+2)
(+3)----> 5 : 4<---(+0)
(+3)----> 5 : 3<---(+0)
(+2)----> 4 : 3<---(+0)
4
A team is said to lead if in an individual game, it scores higher than the other team and a change in the lead happens if it overtakes the score of the other team. If the score is calculated as positive integer(as mentioned in the question), the minimum number required to overtake the other teams score is by adding 1 over the other team.
A B
0 0 --> initial values.
1 0 --> teamA lead by 1. (A = B + 1)
1 2 --> teamA's score is same, teamB lead by 1. (B = A + 1)
3 2 --> ..... (A = B + 1)
3 4 --> ... (B = A + 1)
5 4 --> ... (A = B + 1)
5 6 -->... (B = A + 1)
7 6 --> (A = B + 1); We should stop our algorithm here.
8 6 -->No change in the lead. Highest(TeamA) = 10, Highest(TeamB) = 6.
9 6 --> No change
10 6 --> No change
We can solve this by going from initial scores (0, 0) to (10, 6) or we can trace back (10, 6) --> (0, 0) and I chose to trace back the scores. Also, we don't care about any scores where the lead does not change.
/**
*
Given an array of positive integers that represents possible points a team could score in an individual play.
Now there are two teams play against each other. Their final scores are S and S'.
How would you compute the maximum number of times the team that leads could have changed?
*/
public class MaxLeadChangeCalculator {
public static void main(String[] args) {
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(0, 0));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(10, 6));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(6, 10));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(1, 2));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(2, 1));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(5, 6));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(5, 5));
System.out.println("----------------------");
}
public int calculate(int firstTeamScore, int secondTeamScore) {
// If it's a tie we need to decrease change count by 1 as the algorithm below considers that there was initially a change.
boolean decreaseLeadChangeByOne = firstTeamScore == secondTeamScore && firstTeamScore != 0;
System.out.println("Final scores are : firstTeamScore: " + firstTeamScore + "; secondTeamScore: " + secondTeamScore);
int leadChangeCount = 0;
while(true) {
if(firstTeamScore == 0 && secondTeamScore == 0) {
// As we're tracing back, if both scores reached initial values, we break.
break;
}
if((firstTeamScore > secondTeamScore) || (firstTeamScore == secondTeamScore && firstTeamScore != 0)) {
// Handles the iteration where teamA's score is higher also
// Handles equal final scores situation.
firstTeamScore = (secondTeamScore - 1) < 0 ? 0 : (secondTeamScore - 1);
printLeadChange(firstTeamScore, secondTeamScore);
leadChangeCount++;
} else if(firstTeamScore < secondTeamScore) {
// Handles iteration where teamB's score is higher.
secondTeamScore = (firstTeamScore - 1) < 0 ? 0 : (firstTeamScore - 1);
printLeadChange(firstTeamScore, secondTeamScore);
leadChangeCount++;
}
}
return decreaseLeadChangeByOne ? leadChangeCount - 1 : leadChangeCount;
}
private void printLeadChange(int firstTeamScore, int secondTeamScore) {
System.out.println("Lead changed decreasing order: firstTeamScore: " + firstTeamScore + "; secondTeamScore: " + secondTeamScore);
}
}
I misunderstood the question above. Right solution is as follows:
/**
*
Given an array of positive integers that represents possible points a team could score in an individual play.
Now there are two teams play against each other. Their final scores are S and S'.
How would you compute the maximum number of times the team that leads could have changed?
*/
public class MaxLeadChangeCalculator {
public static void main(String[] args) {
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(10, 6, new int[]{1, 2, 4, 6, 7, 9, 10}));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(6, 10, new int[]{1, 2, 4, 6, 7, 9, 10}));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(1, 2, new int[] {1, 2}));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(5, 5, new int[]{1,2,3,4,5}));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(5, 5, new int[]{1, 5}));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(5, 5, new int[]{1, 5, 10}));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(2, 1, new int[]{1, 2}));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(9, 1, new int[]{1, 2, 6, 7, 8, 9}));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(120, 200, new int[]{1, 2, 6, 7, 8, 9, 10, 20, 30, 40, 45, 60, 76, 80, 90, 100, 120, 160, 180, 190, 200}));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(120, 120, new int[]{1, 2, 6, 7, 8, 9, 10, 20, 30, 40, 45, 60, 76, 80, 90, 100, 120, 160, 180, 190, 200}));
System.out.println("----------------------");
System.out.println("Max Lead change: "
+ new MaxLeadChangeCalculator().calculate(3, 10, new int[]{10, 10, 10, 2, 3, 1, 1})); // Duplicate scores added.
System.out.println("----------------------");
}
public int calculate(final int firstTeamFinalScore, final int secondTeamFinalScore, int[] possibleScores) {
int firstTeamScore = 0, secondTeamScore = 0;
int possibleScoreIndex = -1;
possibleScores = removeDuplicatesAndSort(possibleScores);
int leadChangeCount = 0;
while(true) {
if(possibleScoreIndex + 1 > possibleScores.length
|| (firstTeamScore == firstTeamFinalScore && secondTeamScore == secondTeamFinalScore)
||(firstTeamScore == firstTeamFinalScore && secondTeamScore > firstTeamScore)
|| (secondTeamScore == secondTeamFinalScore && firstTeamScore > secondTeamScore)) {
break;
}
if(firstTeamScore == secondTeamScore) {
if(possibleScores[possibleScoreIndex + 1] <= firstTeamFinalScore) {
firstTeamScore = possibleScores[possibleScoreIndex + 1];
possibleScoreIndex++;
leadChangeCount++;
printLeadChange(firstTeamScore, secondTeamScore);
} else if(possibleScores[possibleScoreIndex + 1] <= secondTeamFinalScore) {
secondTeamScore = possibleScores[possibleScoreIndex + 1];
possibleScoreIndex++;
leadChangeCount++;
printLeadChange(firstTeamScore, secondTeamScore);
}
} else if(firstTeamScore > secondTeamScore) {
if(possibleScores[possibleScoreIndex] == secondTeamFinalScore) { // Equating values.
secondTeamScore = possibleScores[possibleScoreIndex];
continue;
} else if(possibleScores[possibleScoreIndex + 1] <= secondTeamFinalScore) {
secondTeamScore = possibleScores[possibleScoreIndex + 1];
possibleScoreIndex++;
leadChangeCount++;
printLeadChange(firstTeamScore, secondTeamScore);
}
} else if(firstTeamScore < secondTeamScore) {
if(possibleScores[possibleScoreIndex] == firstTeamFinalScore) { // Equating values.
firstTeamScore = possibleScores[possibleScoreIndex];
continue;
}
if(possibleScores[possibleScoreIndex + 1] <= firstTeamFinalScore) {
firstTeamScore = possibleScores[possibleScoreIndex + 1];
possibleScoreIndex++;
leadChangeCount++;
printLeadChange(firstTeamScore, secondTeamScore);
}
}
}
return leadChangeCount;
}
private int[] removeDuplicatesAndSort(int[] possibleScores) {
Set<Integer> sortedSet = new TreeSet<Integer>();
for(int i : possibleScores) {
sortedSet.add(i);
}
int[] retArr = new int[sortedSet.size()];
int index = 0;
for(int i : sortedSet) {
retArr[index] = i;
index++;
}
return retArr;
}
private void printLeadChange(int firstTeamScore, int secondTeamScore) {
System.out.println("Lead changed increasing order: firstTeamScore: " + firstTeamScore + "; secondTeamScore: " + secondTeamScore);
}
}
Why is everyone's code so over complicated? I feel like I'm misunderstanding the question. From my interpretation the array of scores are given. No need to find all of the scenarios.
so something like:
public Integer calculateLeads(scores)
{
scores.sort();
int count = 0;
while(!scores.isEmpty()){
Integer curr = scores.get(0);
scores.remove(0);
for(int i = 0; i < scores.size(); i++){
if(scores.get(i)> curr)
{
scores.remove(i);
count = count + 1;
break;
}
}
}
Take the min of S' and S if they are not equal. Then add 1 to the min and then divide that min by the min of the array holding the possible points that can be scored on any given play that is not 0.
Pseudocode :
For example if S'=10 and S=6:
possible_points_per_play = [0,1,2,3]
min(10, 6) = 6
6 + 1 = 7
min(possible_points_per_play) = 1 //min thats not 0
then divide 7 by the min and you'll get the maximum lead changes.
I know this is not perfect but it seems the a step in the right direction.
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
class CUtil
{
public:
int GetMaxTransitions(vector<int>& pts, int SWin, int SLose)
{
//prepare the pairs
vector<PTPAIR> ptpairs;
for (int i = 0; i < pts.size()-1; i++)
{
for (int j = i + 1; j < pts.size(); j++)
{
PTPAIR pt1, pt2;
pt1.first = pts[i];
pt1.second = pts[j];
pt2.first = pts[j];
pt2.second = pts[i];
ptpairs.push_back(pt1);
ptpairs.push_back(pt2);
}
}
//pass the pairs and sum goals to recursive procedure
int max_trans;
if (GetMaxTransitions_Pvt(ptpairs, SWin, SLose, max_trans))
{
return max_trans;
}
return -1;
}
private:
typedef pair<int, int> PTPAIR;
typedef pair<int, int> CACHEKEY;
typedef pair<int, bool> CACHEVALUE;
map<CACHEKEY, CACHEVALUE> m_cache;
struct GOALPAIR
{
int goal1;
int goal2;
int max_trans;
bool fValid;
};
bool GetMaxTransitions_Pvt(vector<PTPAIR>& ptpairs, int Goal1, int Goal2, int& max_transition)
{
CACHEKEY key;
key.first = Goal1;
key.second = Goal2;
if (m_cache.count(key) > 0)
{
CACHEVALUE cval = m_cache[key];
max_transition = cval.first;
return cval.second;
}
vector<GOALPAIR> goalpairs;
goalpairs.resize(ptpairs.size());
for (int i = 0; i < ptpairs.size(); i++)
{
//compute the goal1 and goal2
int gnew1 = Goal1 - ptpairs[i].first;
int gnew2 = Goal2 - ptpairs[i].second;
GOALPAIR& gp = goalpairs[i];
gp.fValid = false;
gp.goal1 = gnew1;
gp.goal2 = gnew2;
gp.max_trans = 0;
if (gnew1 == 0 && gnew2 == 0)
{
gp.fValid = true;
}
else if (gnew1 < 0 || gnew2 < 0)
{
continue;
}
else
{
gp.fValid = GetMaxTransitions_Pvt(ptpairs, gnew1, gnew2, gp.max_trans);
}
}
//now decide the max_transition from each pair
max_transition = 0;
bool fValid = false;
for (int i = 0; i < goalpairs.size(); i++)
{
GOALPAIR& gp = goalpairs[i];
if (!gp.fValid)
{
continue;
}
fValid = true;
RESDIRECTIONS prevDir = GetDirection(gp.goal1, gp.goal2);
RESDIRECTIONS newDir = GetDirection(gp.goal1 + ptpairs[i].first, gp.goal2 + ptpairs[i].second);
int local_max_trans = gp.max_trans;
if (prevDir != newDir && !(gp.goal1 == 0 && gp.goal2 == 0))
{
local_max_trans++;
}
if (max_transition < local_max_trans)
{
max_transition = local_max_trans;
}
}
CACHEVALUE cval;
cval.first = max_transition;
cval.second = fValid;
return fValid;
}
enum RESDIRECTIONS
{
FIRST, SECOND,
};
RESDIRECTIONS GetDirection(int SFirst, int SSecond)
{
if (SFirst < SSecond)
{
return SECOND;
}
return FIRST;
}
};
#define ARRAYSIZE(a) (sizeof(a)/sizeof(a[0]))
int main()
{
int a[] = { 0, 10};
vector<int> nums(a, a + ARRAYSIZE(a));
CUtil utl;
cout << utl.GetMaxTransitions(nums, 100, 60) << endl;
}
import java.util.LinkedList;
import java.util.List;
public class MaxFluctuationsInTournament {
int[] a;
int s1,s2;
int[][] b;
public MaxFluctuationsInTournament(int[] a, int s1, int s2) {
this.a = a;
this.s1 = s1;
this.s2 = s2;
}
/**
* assume scores non negative, assume only one team scores in a game
* assume a sorted
*/
public int getMaxFlips(){
if(s1<0 || s2 < 0 || (s1==0 && s2==0) || a==null || a.length == 0){
return 0;
}
int k = a.length;
int m = Math.max(a[k-1], s1)+1;
int n = Math.max(a[k-1], s2)+1;
b = new int[m][n];
// base cases
for(int i = 0; i < k; i++){
b[0][a[i]] = 1;
b[a[i]][0] = 1;
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int max = b[i][j];
for(int l = 0; l < k; l++){
int c = 0;
if(a[l] > 0 && a[l] <= i){
c = b[i-a[l]][j];
boolean winnerFlipped = ((i>j)&&(i-a[l]<j));
if(winnerFlipped){
c = c+1;
}
}
if(c > max){
max = c;
}
if(a[l] > 0 && a[l] <= j){
c = b[i][j-a[l]];
boolean winnerFlipped = ((i<j)&&(i>j-a[l]));
if(winnerFlipped){
c = c+1;
}
}
if(c > max){
max = c;
}
}
b[i][j] = max;
}
}
// find maximizer
System.out.println("DEBUG max(#flips)=" + (b[s1][s2]-1));
return b[s1][s2]-1;
}
public List<List<Integer>> getMaximizer(){
int k = a.length;
return findMaximizer(a,k,s1,s2,b);
}
List<List<Integer>> findMaximizer(int[] a, int k, int i, int j, int[][] b){
List<List<Integer>> res = new LinkedList<List<Integer>>();
if(b[i][j] > 0){
List<Integer> prevState = new LinkedList<Integer>();
for(int l = 0; l < k; l++){
int c = 0;
if(a[l] > 0 && a[l] <= i){
c = b[i-a[l]][j];
boolean winnerFlipped = ((i>j)&&(i-a[l]<j));
if(winnerFlipped){
c = c+1;
}
}
if(c == b[i][j]){
// found maximizer
prevState.add(i-a[l]);
prevState.add(j);
break;
}
if(a[l] > 0 && a[l] <= j){
c = b[i][j-a[l]];
boolean winnerFlipped = ((i<j)&&(i>j-a[l]));
if(winnerFlipped){
c = c+1;
}
}
if(c == b[i][j]){
// found maximizer
prevState.add(i);
prevState.add(j-a[l]);
break;
}
}
if(prevState.size() > 0){
res = findMaximizer(a,k,prevState.get(0),prevState.get(1),b);
List<Integer> currState = new LinkedList<Integer>();
currState.add(i);
currState.add(j);
res.add(currState);
}
}
return res;
}
public static void main(String[] args) {
int a[] = { 0 , 1 , 2 , 3 };
int s1 = 10, s2 = 6;
MaxFluctuationsInTournament wrapper = new MaxFluctuationsInTournament(a,s1,s2);
int maxFlips = wrapper.getMaxFlips();
List<List<Integer>> res = wrapper.getMaximizer();
int n = res.size();
System.out.println("Result " + maxFlips);
for(int i = 0; i < n; i++){
List<Integer> state = res.get(i);
System.out.println("State " + (i+1) + "\t(" + state.get(0) + "," + state.get(1) + ")");
}
}
}
I write a DP solution and found one interesting thing. That is, the maximum lead change count is always min(S1, S2). So I guess there should be some math proof that can lead to this result. Can anyone give a math proof? Thanks.
These are some test results:
Max changes of 83 and 86 is 83
Max changes of 77 and 15 is 15
Max changes of 93 and 35 is 35
Max changes of 86 and 92 is 86
Max changes of 49 and 21 is 21
Max changes of 62 and 27 is 27
Max changes of 90 and 59 is 59
......
Max changes of 34 and 64 is 34
Max changes of 43 and 50 is 43
Simple recursion should work, however I am not sure if a more optimized solution is expected.
The only thing to be careful here is that you should not make a recursive call when both teams score 0 as it will call forever. Here is a C# code.
Returns 5 with 10, 6, and {0,2,3} (0:0 0:2 3:2 3:4 5:4 5:6 8:6 10:6)
- Anon August 18, 2014