11330 - Andy's Shoes

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

Moderator: Board moderators

Post Reply
hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

11330 - Andy's Shoes

Post by hi!man! » Sun Oct 28, 2007 6:45 am

I can't pass this problem. Can anyone check these inputs?
Thanks in advance.

Input1

Code: Select all

25
4 1 2 3 4 4 1 2 3
6 1 2 2 1 3 4 4 5 5 6 6 3
6 1 2 2 3 3 1 4 6 6 5 5 4
6 1 1 2 2 3 4 4 5 5 3 6 6
6 1 2 2 1 3 4 4 3 5 6 6 5
10 2 2 6 5 8 7 4 9 9 4 10 10 1 1 5 3 7 6 3 8
10 4 10 2 1 9 9 3 8 6 7 10 4 5 3 1 6 8 5 7 2
10 9 1 6 5 2 2 1 6 10 9 4 4 5 3 7 8 8 7 3 10
10 6 10 4 7 5 3 1 8 10 5 8 1 9 9 7 4 2 6 3 2
10 10 7 9 8 6 10 3 9 4 4 7 2 8 6 1 5 5 3 2 1
10 9 8 6 7 5 10 7 2 1 5 3 4 10 3 4 6 2 9 8 1
10 9 6 5 5 2 10 1 3 3 4 10 9 8 1 4 7 6 2 7 8
10 5 5 10 10 1 3 3 2 2 6 4 4 8 9 6 8 9 7 7 1
10 8 7 5 1 4 9 3 2 9 4 2 10 6 6 1 8 7 5 10 3
10 6 4 7 8 8 3 10 5 3 10 1 2 5 1 4 9 2 6 9 7
10 2 7 7 2 3 9 9 5 10 10 8 3 4 4 6 1 5 8 1 6
10 5 3 4 8 7 5 8 2 6 6 10 7 1 9 3 10 2 4 9 1
10 9 7 6 4 8 3 10 6 5 5 7 10 1 8 2 1 4 9 3 2
10 10 1 8 4 1 7 4 8 5 5 9 9 2 6 3 3 6 10 7 2
10 10 1 1 2 6 5 9 4 3 9 4 3 5 7 7 10 2 8 8 6
10 9 10 7 8 2 5 10 1 5 2 6 3 4 4 3 6 1 7 8 9
10 9 5 4 7 2 6 8 10 1 9 7 3 10 8 5 4 6 2 3 1
10 10 10 8 3 9 6 3 9 4 4 1 8 2 7 7 1 6 5 5 2
10 5 1 4 7 10 2 6 8 9 3 7 5 2 10 8 9 1 6 3 4
10 4 4 10 3 5 7 1 10 3 6 9 1 8 8 6 5 7 9 2 2
Output1

Code: Select all

3
4
4
2
3
5
6
6
6
8
9
7
6
6
9
5
6
7
5
8
6
7
7
8
6
Input2
http://mercury.cksh.tp.edu.tw/~s4300565/H.txt
Output2

Code: Select all

9991
9986
9992
9988
9992
9989
9990
9989
9993
9987

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

Post by pineapple » Sun Oct 28, 2007 7:03 am

y,my AC program gives the same output.
Actully,It is a bit like the P10020.

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

Post by hi!man! » Sun Oct 28, 2007 7:30 am

strange, my code get TLE..
but I think it is fast enough, which run 2000 times n=10000 test case cost about 4 sec.

Is there any critical input in judge or my code really too slow?

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

Post by pineapple » Sun Oct 28, 2007 8:08 am

One of my friends joined in the contest too,he just used lineary search and got AC in 5.6xxs.
My algorithm used 2 struct for the information of each node and get the index in constant time.my code got AC at 0.510s in the contest.
one for two shoes of each position.
another for two positions of each shoe.
Hope it helps.
Last edited by pineapple on Sun Oct 28, 2007 10:14 am, edited 1 time in total.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Oct 28, 2007 8:28 am

It is possible to get accepted using linear search in C/C++, but not in java.
The proper solution should be constant time per iteration. I guess the judge data is too weak. The bounds should be set at about n=500000.

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

Post by hi!man! » Sun Oct 28, 2007 9:41 am

After I change a bit, I get WA instead.
This is my code. Where is my bug?

Code: Select all

#include<stdio.h>
#include<string.h>
int main(){
   int C,n,i,a[10010],c[10010],x,y,s;
   scanf("%d",&C);
   while(C--){
      scanf("%d",&n);
      for(i=0;i<n;i++){
         scanf("%d%d",&x,&y);
         a[y-1]=x-1;
      }
      for(i=0;i<n;i++)
         c[a[i]]=i;
      for(i=s=0;i<n;i++)
         if(a[i]!=i){
            a[c[i]]=a[i],s++;
            c[a[i]]=c[i];
         }   
      printf("%d\n",s);
   }
   return 0;
}

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

WR WR WR WR...

Post by sapnil » Sun Oct 28, 2007 3:07 pm

I get too many WR
Can any one help me,plz.................

Here my code.

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<stdlib.h>

#define CSE 10090

struct SS
{
	long x,y;
};

SS Loc[CSE];

bool Flag[CSE];

long a[CSE*2];

void Init(long n)
{
	long i;

	for(i=0;i<=n;i++)
	{
		Flag[i]=1;
	}

	return;
}

int main()
{
  //freopen("Shoe.out","w",stdout);
	long T,i,R,Temp,n,t;

	scanf("%ld",&T);
	while(T--)
	{
		scanf("%ld",&n);

		Init(n);

		for(i=1;i<=2*n;i++)
		{
			scanf("%ld",&a[i]);

			if(Flag[a[i]])
			{
				Loc[a[i]].x=i;
				Flag[a[i]]=0;
			}
			else
			{
				Loc[a[i]].y=i;
			}
		}
		R=0;
		for(i=1;i<2*n;i+=2)
		{
			if(a[i]!=a[i+1])
			{
				R++;
				Temp=a[i];

				if(Loc[a[i]].x == i)
				{
					t=a[i+1];
					a[i+1]=a[Loc[a[i]].y];
					a[Loc[a[i]].y]=t;

					if(Loc[t].x==i+1)
					{
						Loc[t].x=Loc[Temp].y;
					}
					else
					{
						Loc[t].y=Loc[Temp].y;
					}

				
				}
				else
				{
					t=a[i+1];
					a[i+1]=a[Loc[a[i]].x];
					a[Loc[a[i]].x]=t;

					if(Loc[t].x==i+1)
					{
						Loc[t].x=Loc[Temp].x;
					}
					else
					{
						Loc[t].y=Loc[Temp].x;
					}

				}
				
			}
		}
		printf("%ld\n",R);
	}

	return 0;
}
Thanks
Keep posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Post by shakil » Sun Nov 04, 2007 3:21 am

Sapnil, The identity of the shoes are not in 1 to n and i think it will be less than 10000. I think your tracnic is right. :D
Input

Code: Select all

1
2 99 199 199 99
SHAKIL

thales
New poster
Posts: 2
Joined: Sat Sep 20, 2008 11:44 pm

TLE in 11330 - Andy's Shoes

Post by thales » Tue Oct 21, 2008 2:11 pm

This problem will drive me crazy.
Can somebody help me with my algorithm?
I am received many TLE's with a linear algorithm.
I translate in the array col the colors of the left shoes so, I will have as a left shoe in the i-th pair the i color.
After that I calculate the right-shoes permutation with its inverse, and in O(n) time I sort the permutation.
My code gives correct answer for all the sample input posted here.

Code: Select all

got accepted


Thanks in advance for any help.

Ty4
New poster
Posts: 7
Joined: Sun Jan 19, 2014 1:58 am

Re: 11330 - Andy's Shoes

Post by Ty4 » Sun Feb 16, 2014 7:43 am

I'm getting TLE on this no matter what, and I refactored and changed a lot before posting here. Anyone have any insight?

Code: Select all

#include <climits>
#include <cstdio>
#include <unordered_map>

using namespace std;

int cases, pairs;

int main()
{
	scanf("%d", &cases);

	while (cases-- > 0){
		scanf("%d", &pairs);
		unordered_map<int, int> mixedPairs;

		for (int i = 0; i < pairs; ++i){
			int leftShoe; int rightShoe;
			scanf("%d %d", &leftShoe, &rightShoe);
			mixedPairs.insert(pair<int,int>(leftShoe, rightShoe));
		}

		int min = INT_MAX;
		for (unordered_map<int,int>::iterator it = mixedPairs.begin(); it != mixedPairs.end(); ++it){
			int n = it->second;
			int len = 0;
			while (n != it->first){
				n = mixedPairs[n];
				len += 1;
			}
			if (len <= min)
				min = len;
		}

		printf("%d\n", min);;
	}

	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11330 - Andy's Shoes

Post by brianfry713 » Tue Feb 18, 2014 11:29 pm

You can solve this in a greedy manner. I just used two int[10000] arrays to track which shoes are in each location and two int[10000] arrays to track where each shoe is.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 113 (11300-11399)”