alonsomh
BAN USERSupposing that the second output is two, (as only two customers can have both their options satisfied not three)
I would parse the input into a collection of votes, I would also abstract the dogs and the cats into a participant class. Then split all of those into test cases/ballots.
class Vote
{
Participant whoIsLeaving;
Participant whoIsStaying;
///... implementation
}
Class Participant {
ParticipantType type; //struct, or something cached from a DB
int participantId;
}
class TestCase
{
int numberOfDogs;
int numberOfCats;
List<Vote> votes;
}
Then I would parse the votes and keep track of which one is max so I do not have to search on the matrix later.
int ProcessVotes (List<TestCase> testCases)
{
int[] output = new int[testCases.Count];
int i=0;
testCases.ForEach( tc => {
Dictionary<Tuple<Participant,Participant>,int> results = new Dictionary<Tuple<int,int>, int>();
output[i]=0;
tc.Votes.ForEach(v =>{
var tuple = Tuple.Create(v.WhoIsLeaving, v.WhoIsStaying);
if (results.ContainsKey(tuple)) //combination already has a vote
{
results[tuple]++;
if (output[i]<results[tuple])
{
output[i] = results[tuple];
}
continue;
}//end if
results.Add(tuple, 1); //combination has no vote
if (output[i]==0)
{
output[i] = 1;
}
}); //foreach vote
i++;
});//foreach test case
return output;
}
My approach is to move forward until a 0 is found, at that point, see if we can hope over the 0. if we can return false, else keep moving forward. I do not check the last element as we are already there. (C#)
public static bool CanHopeToTheLastElement(int[] array)
{
for (int i = 0; i < array.Length; i++)
{
if (array[i] == 0)
{
int counter = 1;
int j = i - 1;
bool canHop = false;
while (j >= 0 && canHop == false)
{
if (array[j] > counter) //we can hop over i using array[j];
{
canHop = true;
}
--j;
++counter;
}
if (!canHop)
return false;
}
}
return true;
}
The DP formula for calculating any element of the matrix is :
- alonsomh December 26, 2014ResultMatrix[x,y] = ResultMatrix[x-1,y] + ResultMatrix[x,y-1] - ResultMatrix[x-1,y-1] + OriginalMatrix [x,y]
with the exception of the first row and column where:
ResultMatrix [0,0] = OriginalMatrix[0,0]
ResultMatrix [x,0] = ResultMatrix[x-1,0] + OriginalMatrix[x,0]
ResultMatrix [0,y] = ResultMatrix[0, y-1] + OriginalMatrix[0, y]