299 - Train Swapping

[C8H10N4O2]

This should a simple problem, no? I keep getting WA. I don't know what is wrong. Please help!

Code: Select all

#include <stdio.h>

void main()
{
	int i,j,k,m,n,t,A[100],Swaps;

	scanf("%d",&m);
	for(k=0;k<m;k++)
	{
		Swaps=0;
		scanf("%d",&n);

		for(j=0;j<n;j++)
		{
			scanf("%d",&A[j]);
		}

		for(i=0;i<n-1;i++)
		{
			for(j=n-1;j>i;j--)
			{
				if(A[j]<A[j-1])
				{
					t=A[j];
					A[j]=A[j-1];
					A[j-1]=t;
					Swaps++;
				}
			}
		}

		printf("Optimal train swapping takes %d swaps.n",Swaps);
	}
}

[Stefan Pochmann]

Maybe you should sometimes run your programs on your own computer before submitting them. The you would've probably noticed that you output an 'n' instead of a 'n'.

[Stefan Pochmann]

Btw, I just realized that one does not actually has to sort the sequence. Simply determining the "degree of unsortedness" is enough. I'll leave it to you to find out what I mean with that

[C8H10N4O2]

Microsoft Visual C++ babies too much. It automatically fixes memory errors and stuff:o)

[C8H10N4O2]

Wierd, the is definitely there on my computer...

[junjieliang]

I presume your "degree of unsortness" refers to the number of inversions. Is there a way to do this in linear time?

[Stefan Pochmann]

Please define "inversions". But I guess you mean the right thing. Linear time possible? Hmm, maybe. I'll have to think about it. Intuitively, I would say yes.

[junjieliang]

I think I mean it like A > A[j] and i < j. Not very good with this kind of mathematical notations. But actually I don't really need a linear time, just anything that's better than quadratic...

[arnsfelt]

There is a very nice O(n log n) solution, easily derived from mergesort.

Consider returning both the sorted list and the number of inversions and look into how to modify the merge.

[Stefan Pochmann]

junjieliang: So you "need" something that's better than quadratic? Unfortunately, the input cases are so small, that quadratic solutions go through in zero time. What do you need it for? A homework assignment?

I tried to get it down to linear time today, but didn't succeed. Nothing really worked. But I'm not yet ready to give it up.

[junjieliang]

Fine, I do have a motive. It's for solving another problem, where quadratic would be too slow (but that's over at timus). Since this was brought up I decided to ask around...

[Revenger]

This problem is easy, but I get WA Can anybody find an error in this program? Please!

[pascal]Program p299;

Const MaxL = 100;

Var L,Ans : Integer;
Train : Array[1..MaxL]of Integer;
i,j,k : Integer;
t,tt : Integer;

begin
Readln(t);
for tt:=1 to t do begin
Readln(l);
for i:=1 to l do
if i<>l then
Read(Train)
else
Readln(Train);
ans:=0;
for i:=1 to l-1 do
for j:=l downto i+1 do
if Train[j]<Train[j-1] then begin
k:=Train[j];
Train[j]:=Train[j-1];
Train[j-1]:=k;
ans:=ans+1;
end;
Write('Optimal train swapping takes ');
Writeln(ans:0,' swaps.');
end;
end.[/pascal]

[Revenger]

I can't understand why I get WA
Please, help me!

[pascal]Program p299;

Const MaxL = 100;

Var L,Ans : Integer;
Train : Array[1..MaxL]of Integer;
i,j,k : Integer;
t,tt : Integer;

begin
Readln(t);
for tt:=1 to t do begin
Readln(l);
for i:=1 to l do
if i<>l then
Read(Train)
else
Readln(Train);
ans:=0;
for i:=1 to l-1 do
for j:=l downto i+1 do
if Train[j]<Train[j-1] then begin
k:=Train[j];
Train[j]:=Train[j-1];
Train[j-1]:=k;
ans:=ans+1;
end;
Write('Optimal train swapping takes ');
Writeln(ans:0,' swaps.');
end;
end.[/pascal]

[Rene]

Why my code is WA?
Please help me!

[cpp]#include <iostream.h>

struct node
{
int num;
node *next;
};

node *head,*last;

int dele ()
{
node *p;
p = head;
head = head -> next;
delete p;
return 0;
}

int swap ()
{
last -> next = head;
last = head;
head = head -> next;
last -> next = NULL;
return 0;
}

int main()
{
int test,lenth,swaps,i,j;
node *p;
cin >> test;
for (i = 1;i <= test;i++)
{
swaps = 0;
cin >> lenth;
for (j = 1;j <= lenth;j++)
{
last = new node;
if (j == 1) head = last;
else p -> next = last;
cin >> last -> num;
last -> next = NULL;
p = last;
}
j = 1;
while (head -> next)
{
if (head -> num == j)
{
dele ();
j++;
}
else
{
swap ();
swaps++;
}
}
cout << "Optimal train swapping takes " << swaps << " swaps." << endl;
}
return 0;
}[/cpp]

[Hisoka]

input

Code: Select all

1
5
1 3 4 2 5

output

Code: Select all

2