299 - Train Swapping

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Wed Mar 06, 2002 3:28 am

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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Wed Mar 06, 2002 5:22 am

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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Wed Mar 06, 2002 6:52 am

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 :wink:

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Wed Mar 06, 2002 1:29 pm

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

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Wed Mar 06, 2002 1:32 pm

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

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sat Mar 16, 2002 2:42 pm

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

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Sun Mar 17, 2002 7:20 am

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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sun Mar 17, 2002 5:00 pm

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
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » Sun Mar 17, 2002 11:58 pm

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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Mon Mar 18, 2002 4:19 am

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? :wink:

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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Mon Mar 18, 2002 8:45 am

Fine, I do have a motive.:smile: 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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Sat Jun 15, 2002 10:13 am

This problem is easy, but I get WA :cry: 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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

299 - Train Swapping

Post by Revenger » Mon Jun 24, 2002 11:41 pm

I can't understand why I get WA :cry:
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
New poster
Posts: 13
Joined: Mon May 05, 2003 4:40 am
Location: Shanghai,China

299 WA

Post by Rene » Sat May 10, 2003 1:27 pm

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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Sun May 11, 2003 7:54 am

input

Code: Select all

1
5
1 3 4 2 5
output

Code: Select all

2

Post Reply

Return to “Volume 2 (200-299)”