Moderator: Board moderators

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

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

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

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
Contact:

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.

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
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
``````

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
Contact:

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.

To generate the output, i just did this:

Code: Select all

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

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
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
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);
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
Contact:
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
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

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
Contact:
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
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
Contact:
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
That's right!!! Got Accepted, thanks a lot:D

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