11076 - Add Again

[jan_holmes]

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

[Riyad]

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

[sclo]

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.

[CodeMaker]

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

[sclo]

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;
}

[CodeMaker]

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.

[sakhassan]

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;
}

[sclo]

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

[sakhassan]

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

HOPE I COULD FIND IT

[Dzejla]

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.

[mamun]

You may try this inputs

Code: Select all

4
1 1 0 0
3
0 0 0

[Dzejla]

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);
    		 }; 	
};

[sclo]

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

[Dzejla]

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

[Darko]

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.