CareerCup

For each person, store lists of everyone they beat.

Backtrack:
- Fill first position with people who have had wins (iterate over all these of course)
- Then: At every position thereafter: Fill every person who has lost to the person in the previous position of the filled array but is not in result array.

Typed this directly in here, so could be buggy

// denote the people by integers 0, 1, ...., N-1
//global for convenience
static i=0;   //position of result[] current invocation fills

_function(prev)  //function gets previous person (filled into result)
{
    int j; //iterate over losers of 'prev'

    if( i == N) { //do whatever with result[ ] as it is full }

    //fill current spot of result array
    for( j = every person 'prev' has beaten and not in result)  
    {
        result[++i] = j;    
        _function(j);   //fill next spot in result with people j beat
        i--;
    }
}

// fills first spot with winners (wrapper for _function)
function() 
{
    int j; //iterate over all people who have at least one win

    for (j = every person that has a win)
    {    
        result[0]=j;
        _function(j)
    }
}

// PRUNE this as you desire.

Can we try this using Graph?
Lets create a graph where Nodes represent people (N nodes).
A directed edge from A to B means that A has defeated B.
After such a graph is created, apply Topological sort.

This also raises a concern for the last element to be added to the queue. Does it mean that last element of the queue hasn't defeated anyone?

HI Guys I have found a dynamic programming solution to this problem.

I will first discuss the algorithm and then I will give the program for solution.
So to start with this. We will manipulate the array that is we have to start by checkin each and every combination of all the numbers.

So input for me would be a square matrix of size nXn which will have value 1 if i has one over j and 0 if i has lost from j . we can also assume a function which return one if i wins over j and o if i loses over j.

1. Instialize an array of size n with a[i]=1 which will represent our final exam.
2.The base case for our algorithm will be when the array contains only one element that is there is only one student in class. in that case the answer will be only that student.
So out base case for our function name findSequence(a,l) will be

if(l==n-1)
			return a[l];

3. Now we have to break our problem in small problem s of one size and then combine results form the sub problems to get the solution of higher problem for example.

if there are two classes with one people each 3 and 4 the answer will be 3 and 4 but if we have a class with these two students 3 and 4 and 3 wins over 4 then we can check after find the lower level that if win(4,3) = 1 then subsequence will be 4,3 else 3,4

in the same way if there is a class with these two people 3 and 4 and the sequence return is 4,3 from this and there is an individual class with 2 which the answer tot his individual class will be 2 but if these three are in same class answer will be 2,4,3 if win(2,4) = 1 else this sequence wont exist.

4. now the problem is how to break the array in to smaller problems . this i will show with the help of a tree

[1,2,3,4]
								/    |     |      \
							      /     /      \         \
						    [234] [134] [214] [231]
						/     |    \
					[34] [24] [32]
					/   \   /   \   /   \
				     [3] [4] [2][ 4][3][2]

the problem can be broken in the above way now the original programme

findSequence(a,l)
	{
		if(l==a.length-1)
			return ;
		else
		{
			for(int i=l;i<n;i++)
			{
				swap(a[l],a[i])
				findSequence(a,l+1);
				if(wins(a[l],a[l+1])==1)
					return;
			}
		}
	}
	main()
	{
		int[] a = new int[n];
		for(int i=0;i<n;i++)
			a[i]=i
		findSequence(a,0)
		for(int i=0;i<n;i++)
			System.out.print(a[i]+" ");
	}

Backtracking will work, only first we have to form the mapping as to who was defeat by how many people. eg d - { b, c } (d was defeated by b and c} etc... Person who didn;t win against anyone, forms array[0] (there may be more than one such persons). Start backtracking on this map.

how about sorting payers based on number of times he won?
ex:
2 lost to 4
2 lost to 5
5 lost to 4
[player, won]
[2, 0]
[5, 1]
[4, 2] -- sort them based on number of times they won....so final order will be 2,5,4

I think its O(n) solution, the question do not demand all possible solutions, it wants any one.
Algo:
Linklist l = new Linklist()

for each element in N people:
insert(element,l)

insert(element, l)
-- if l is empty:
l.root = element
return
root = l.root
while(root is not null):
if element has won against root:
insert element before root:
break;return
root = root.next

root.next = element