11330 - Andy's Shoes

[hi!man!]

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]

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

[hi!man!]

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]

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.

[sclo]

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!]

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]

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

[shakil]

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.
Input

Code: Select all

1
2 99 199 199 99

[thales]

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]

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]

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.