Permutations

[adina0822]

Please help me to solve this.

John has n songs that he wants to listen to, but he can't do that anyway, because some songs can't be played one after another.

In the input file playlist.in there is the integer number n that represents the number of songs, the integer number m that represents the number of pairs of songs that can't be played one after another and then m pairs of integer numbers that represent the songs that can't be played one after another.

In the output file playlist.out there will be n integer numbers that represent the right order to listen the songs.

1 < n <= 13
1 < m <= 30
There is always a solution. If there are more solutions in the output file there will be only the first one in lexicographic order.

e.g.
playlist.in
5
4
2 3
1 5
1 4
2 4

playlist.out
1 2 5 3 4


This is what I did, but I only get 60 out of 100 because the time limit is exceeded.

using namespace std;
#include <fstream>
ifstream f ("player.in");
ofstream g ("player.out");
int n,m,v[61],x[14],i,j, use[14],ok,pos[14];



int verif ( )
{
ok=1;

for (j=1; j<2*m && ok==1; j=j+2)
{
if (pos[v[j]]-pos[v[j+1]]==1 || pos[v[j]]-pos[v[j+1]]==-1) ok=0;
}

if (ok==1) for (i=1; i<=n; i++) g<<x[i]<<" ";
return ok;
}

int aranj(int k)

{
int i;
if(k==n+1)
ok=verif();
else if (!ok) for(i=1;i<=n;i++)
if(!use[i])
{
x[k]=i;
pos[i]=k;
use[i]=1;
aranj(k+1);
use[i]=0;
}
}

int main ()
{


fscanf (f,"%d%d",&n,&m);

for (i=1; i<=2*m; i++) fscanf (f, "%d", &v[i]);


aranj (1);
f.close ();
g.close ();
return 0;
}

[Smac89]

This is not a permutations question(which explains your TLE), look up topological sorting.

EDIT:
For the given example, these are the possible songs that can be played after each other:
1 - 2, 3, 5
2 - 1, 5
3 - 1, 4, 5
4 - 3, 5
5 - 2, 3, 4

To get the first one in lexicographic order, start at 1 and pick the smallest unvisited vertex in each row until you have picked n songs:
1, 2, 1, 5, 2, 3, 1, 4

1, 2, 5, 3, 4

[adina0822]

Yes, but that will not work on each example.
Try this one:

playlist.in
12
18
4 2
4 5
4 6
4 7
4 9
4 10
4 11
1 7
1 3
1 5
6 7
10 11
11 12
11 7
11 5
11 4
12 5
12 6

[Duthomhas]

Oh? What goes wrong?

[adina0822]

Well, if you choose the smallest unvisited number you will get 1 2 3 4 8 5 6 9 7 10 12 and there will be no possible choice for the last place, because 11 can't be placed after 12.
I'm very sure that I have to use permutations here, but I'm looking for a more efficient way.

[Duthomhas]

Uh, according to your list, 11 is not forbidden after 12.

Have we misunderstood that list to mean that "11 12" indicates that neither (11 12) nor (12 11) are valid?

All that does is require an additional adjustment to your adjacency graph.
Why not do as Smac89 suggests and google "topological sort".
It is the algorithm designed to answer problems like yours.

[adina0822]

11 can't be after 12 and 12 can't be after 11.
I'll google that. Thank you for your time.

[Duthomhas]

Your question was confusing, so I cannot be sure you are looking at it right yet... sorry.

If "11 12" indicates both "12 11" and "11 12" are invalid, then the listing in your penultimate post lists "11 4" twice: once as "11 4" and once as "4 11". This makes no difference in running the algorithm, of course, but it does make a difference in terms of what was intended.

A topological sort is a modified Depth First Search. What level class is this? I presume this is a university class? (I'd be surprised if it were for High School.)

Using your criteria and the last thing, a proper topological sort produces
1 2 3 4 8 5 6 9 11 7 10 12
which is correct.

The greedy algorithm Smac89 suggested isn't a proper DFS, so it failed in your case.

[adina0822]

I'm in high school and I'm preparing for a contest, and I have this site with exercises where I can send my solution and it would give me a score and the first example that doesn't work if it's the case. It also shows me what should I obtain for that example.
And for that one before I have to obtain 1 2 3 4 8 5 6 10 7 12 9 11, so I guess 4 11 and 11 4 mean the same thing.
But there's no need to write that twice so I am so confused now.

[Duthomhas]

Wait, you're supposed to get 1 2 3 4 8 5 6 10 7 12 9 11 for the list seven posts up?
There's something wrong, then, because given that list and the constraints you gave us, that is not the first lexicographic answer.

And... I really don't want to take the time to reverse-engineer the input. Can you link us to the actual contest rules that you are working from?

[adina0822]

Well I could, but they are in Romanian language.

But I think it is the first lexicographic answer, but again 4 11 and 11 4 have to mean the same thing.

It's okay, I'll figure it out after all. I understand everyone has his/her own limited time, so don't worry about it.