OJ Board

Posted: **Sat Sep 02, 2006 4:50 pm**

Actually, what algorithm should we use to avoid TLE ??? Thx...

Posted: **Sat Sep 02, 2006 7:38 pm**

try to find some formula for this problem ..... no backtracking needed ...

Posted: **Sun Sep 03, 2006 5:58 am**

Riyad wrote:try to find some formula for this problem ..... no backtracking needed ...

Observe that if you look at each column of digit, the numbers in them are the same.

Posted: **Sun Sep 03, 2006 6:25 am**

seriously, this is not my day.
i dont know why i am getting WA

i wrote a brute force code using next_permutation() to test whether my calculated value is correct or not.

using random function i made 120 data and test, all matched the column values, now i have to add them to make it in base 10. i m not sure but i think i am not having overflow. so what else can it be. i have tried a lot.

can anyone tell me the output of this big data?

input:

Code: Select all

2
1 0
10
0 1 2 3 4 5 6 7 8 9
12
0 1 2 3 4 5 6 7 8 9 9 9
0

my column value for the data

Code: Select all

1
16329600
419126400

my final answer

Code: Select all

11
18143999998185600
46569599999953430400

the last value is bigger than 64bit unsigned integer. so i think it is invalid case if my answer is not wrong ofcourse. what about the 2nd one?

thanks

Edit:
some more I/O that i test->

Input:

Code: Select all

1
9
2 
1 9
3 
9 9 9
4 
8 8 2 2 
5
7 7 7 8 9
6
4 5 6 7 8 9
7
1 1 2 2 3 3 9
8 
9 8 7 6 5 4 3 2
9
1 2 3 4 5 6 7 8 9
10
0 1 2 3 4 5 6 7 8 9
11
0 0 1 2 3 4 5 6 7 8 9
12
0 1 2 3 4 5 6 7 8 9 9 9
0

output:

Code: Select all

9
110
999
33330
1688872
519999480
2099999790
2463999975360
201599999798400
18143999998185600
907199999990928000
46569599999953430400

Posted: **Sun Sep 03, 2006 6:58 am**

CodeMaker wrote: my final answer
Code: Select all
11
18143999998185600
46569599999953430400
the last value is bigger than 64bit unsigned integer. so i think it is invalid case if my answer is not wrong ofcourse. what about the 2nd one?

thanks

The 2nd one is right.
I get 9676111852534327168 for the 3nd one, but it might have overflowed.

Your column sums matches mine.
To generate the output, i just did this:

Code: Select all

for(int i=0;i<n;i++) {
  ans*=10;
  ans+=columnsum;
}

Posted: **Sun Sep 03, 2006 8:48 am**

thanks a lot sclo,
doing it in your way gave me Accepted.

then i wondered what was my problem, and found this spoil in my code

3
0 0 0

i was printing
000

where it will be
0

because i was using an array and i forgot to put:
if(sum==0)
{
printf("0\n");
continue;
}

but i should have done it in your way as it is much cleaner.
thanks again.

Posted: **Sun Sep 03, 2006 10:04 am**

I dont know why I am getting TLE

IS my method incorrect??

#include<stdio.h>
#include<string.h>
#include<ctype.h>

#define N 100
//#include<conio.h>

/*
int cmp(char a, char b)
{
char ch1,ch2;
ch1 = tolower(a);
ch2 = tolower(b);

if(ch1>ch2)
return 1;
else if(ch1<ch2)
return -1;
else
{
if( isupper(a) && islower(b) )
return -1;
else if( islower(a) && isupper(b) )
return 1;
else
return 0;
}

}*/

void sum(char res[N], char a[N], char b[N])
{

int len1,len2,len3;
int i,j;
int carry;
int result;
char temp[N];
len1=strlen(a);
len2=strlen(b);

len3=0;
carry=0;
strcpy(res,"");
strcpy(temp,"");
for(i=len1-1,j=len2-1;i>=0||j>=0;i--,j--)
{
if(i>-1 && j>-1)
result = ( (a-'0')+(b[j]-'0') ) + carry;
else if(i<0)
result = b[j]-'0' + carry;
else
result = a-'0' + carry;
if(result>9)
{
carry = result/10;
result %= 10;
}
else
carry = 0;

res[len3++] = result + '0';
}
if(carry)
res[len3++] = carry + '0';

for(i=len3-1,j=0;i>=0;i--,j++)
{
temp[j]=res;
}
temp[j]='\0';

strcpy(res,temp);

//return res;
}

int main()
{

char str[N],a[N];
int len;
int i,j,k,r,s;
int cases;
int num,count;
char res[N];
char str1[N];
//int flag;
char temp;

//scanf("%d",&cases);

while(1)
{

scanf("%d",&num);
gets(str);
if(num==0)
break;

count = 0;
strcpy(res,"");
for(i=0;i<num;i++)
{
scanf("%s",&str);
strcat(res,str);
}

strcpy(str,res);

len = strlen(str);

for(i=len-1;i>0;i--)
{
for(j=0;j<i;j++)
{
if(strcmp(str[j],str[j+1])>0)
{
temp = str[j+1];
str[j+1]=str[j];
str[j]=temp;
}
}

}

strcpy(res,"");
sum(res,str,"0");
strcpy(str1,res);
//printf("%s\n",str);
//permuting & adding
while(1)
{

j = len-2;
while(strcmp(str[j],str[j+1])>=0 && j>=0)
{
j--;

}

if(j<0)
{
//printf("No Successor\n");
break;
}

k = len-1;

while(cmp(str[j],str[k])>=0)
{
k--;
}

temp = str[k];
str[k]=str[j];
str[j]=temp;

r = len-1;
s = j+1;

while(r>=s)
{
temp = str[r];
str[r]=str[s];
str[s]=temp;
r--;
s++;

}

str[len]='\0';

//printf("%s\n",str);
sum(res,str1,str);
strcpy(str1,res);
}

printf("%s\n",res);

}

//getch();

return 0;
}

Posted: **Sun Sep 03, 2006 10:08 am**

you WILL TLE if you try to add each permutation of the numbers by actually generating the permutations. 12! is huge.

Posted: **Sun Sep 03, 2006 10:28 am**

THEN I HAVE TO THINK ANOTHER POSSIBLE WAY !!!!!!!!!!!!!!!!!!!!

HOPE I COULD FIND IT

Posted: **Sun Sep 03, 2006 2:34 pm**

Hi, I keep getting WA for my solution of this problem. I have used the same algorithm as explained by some of the posters(obviously not quite the same as i can't get it accepted:D) but basically, I am using the trick with looking at the digits in columns and all the inputs provided here as well as sample input work correctly. I hope someone who got this problem accepted could provide me with some tricky input cases... Thx.

Posted: **Sun Sep 03, 2006 3:52 pm**

You may try this inputs

Code: Select all

Posted: **Sun Sep 03, 2006 4:29 pm**

Thanks, mamun. For the inputs you provided, my program outputs:

3333
0

That should be correct, right? I really don't know what the problem is... Here's my code. If someone feels like looking for a bug:D

Code: Select all

#include<iostream>
#include<algorithm>
#include<map>
typedef unsigned long long int big;
using namespace std;

big factorial_minimize(big n, big duplicates)
{
 	big sum=1;
 	for(big i=duplicates+2;i<=n;i++)
 	{
	 		sum*=i;
    };
    return sum;
};
bool duplicates(big array[],big n)
{
 	 	map<big,big>mapa;
 	for(big i=0;i<n;i++)
 	{
	 		mapa[array[i]]++;
    };
    big duplicates=0;
    for(map<big,big>::const_iterator iter=mapa.begin();iter!=mapa.end();iter++)
    {
	        duplicates+=(iter->second-1);
    };
    return duplicates;
};

big permutations(big array[],big n)
{
 	map<big,big>mapa;
 	for(big i=0;i<n;i++)
 	{
	 		mapa[array[i]]++;
    };
    big duplicates=0;
    for(map<big,big>::const_iterator iter=mapa.begin();iter!=mapa.end();iter++)
    {
	        duplicates+=(iter->second-1);
    };
    return (factorial_minimize(n,duplicates));
};

 void finish (big the, big n)
  {
     big counter=0;
     big multiplier=1;
     big result=0;
     while(counter<n)
     {
		 result+=(the*multiplier);
		 multiplier=multiplier*10;
		 counter++;
     };
     cout<<result<<endl;
  };
  
void handle_duplicates(big array[],big n)
{
 	 big the=0;
 	 big counter;
 	 bool valid[n];
 	 for(big i=0;i<n;i++)
 	 valid[i]=true;
 	 for(big i=0;i<n;i++)
 	 {
	  		 if(valid[i])
	  		 {
              big nova[n-1];
			  counter=0;
	  		 for(big j=0;j<n;j++)
	  		 {
			  		 if(i!=j)
			  		 {
					  		nova[counter]=array[j];
							  counter++; 
			  		 };
		     };
		     for(big u=0;u<n;u++)
		     {
			  		 if(array[u]==array[i])
					   valid[u]=false;
	  		 };
		     the+=(array[i]* permutations(nova,counter));
			 };
     };
     finish(the,n);
 };
 
 void handle_regular(big array[],big n)
 {
  	  big the=0;
 	  big counter1;
 	  for(big ik=0;ik<n;ik++)
 	  {   
             counter1=0;
	         big nova[n-1]; 
             for(big i=0;i<n;i++)
 	         {
	 		       if(array[ik]!=array[i])
	 		       {
			 	    	nova[counter1]=array[i];
			 		    counter1++;
	               };
	 		};
	
          the+=(array[ik]* permutations(nova,counter1));
     };
     finish(the,n);  	  
};
  
 
void handle(big array[],big n)
{
 	 bool dup=duplicates(array,n);
     if(dup)
     {
		   handle_duplicates(array,n);
     }else
     {
    		handle_regular(array,n);
  	 };
};	 

int main()
{
            big n;
			while(cin>>n && n!=0)
			{
		        big array[n];
		        for(big i=0;i<n;i++)
			    {
 		                cin>>array[i];
 		        };
 		        
			    handle(array,n);
    		 }; 	
};

Posted: **Sun Sep 03, 2006 11:23 pm**

A SPOILER:
The number of ways to rearrange n digits, where we have C occurences of digit i is:

Code: Select all

n!/product(C[i]!)

Posted: **Mon Sep 04, 2006 10:26 am**

That's right!!! Got Accepted, thanks a lot:D

Posted: **Mon Sep 11, 2006 6:59 am**

The number will fit into a signed 64-bit integer. Java doesn't have unsigned ones (except 16-bit one), and my solution w/o BigInt passed.

OJ Board

11076 - Add Again

11076 - Add Again

about 11076

Re: about 11076

11076 WA