11076 - Add Again

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

Moderator: Board moderators

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

11076 - Add Again

Post by jan_holmes » Sat Sep 02, 2006 4:50 pm

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

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

about 11076

Post by Riyad » Sat Sep 02, 2006 7:38 pm

try to find some formula for this problem ..... no backtracking needed ...
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

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

Re: about 11076

Post by sclo » 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.

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » 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
Last edited by CodeMaker on Sun Sep 03, 2006 7:46 am, edited 1 time in total.
Jalal : AIUB SPARKS

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

Post by sclo » 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;
}

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » 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.
Jalal : AIUB SPARKS

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » 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;
}

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

Post by sclo » 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.

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Sun Sep 03, 2006 10:28 am

THEN I HAVE TO THINK ANOTHER POSSIBLE WAY !!!!!!!!!!!!!!!!!!!!
:(
HOPE I COULD FIND IT

Dzejla
New poster
Posts: 3
Joined: Mon Jul 17, 2006 7:55 pm
Location: Bosnia and Herzegowina

11076 WA

Post by Dzejla » 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.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sun Sep 03, 2006 3:52 pm

You may try this inputs

Code: Select all

4
1 1 0 0
3
0 0 0

Dzejla
New poster
Posts: 3
Joined: Mon Jul 17, 2006 7:55 pm
Location: Bosnia and Herzegowina

Post by Dzejla » 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);
    		 }; 	
};

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

Post by sclo » 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]!)

Dzejla
New poster
Posts: 3
Joined: Mon Jul 17, 2006 7:55 pm
Location: Bosnia and Herzegowina

Post by Dzejla » Mon Sep 04, 2006 10:26 am

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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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.

Post Reply

Return to “Volume 110 (11000-11099)”