OJ Board

I have solved the problem 10338. Sadly i couldnt be in the contest where this problem was posted but i see in the problem description that the time limit was 1 second. I resolve this problem in Java in the easiest way: Calculating the formula of all the permutations of a multiset. To calculate the formula i dont use any trick, i do it straighfoward.

Example: Multiset Size 20. Distinct Elements 2. Multiplicity: 18 2.

To calculate this i make 20! / (18! * 2!) (I calculate all the factorials, i don simplify).

Now my question is, Anyone in C++, Pascal or simply C solved this problem in this way and get accepted with time less than one second. I understand that if anybody make an smart solution that simplify it would be faster than my approach but i just want to know if the same algorithm that i use in Java and potentially it would be rejected for Time Limit Exceded in the contest works well (acording with time) in other language.

PS: my solution works in 1:300 seconds

I solved this problem using the exact same algorithm you
did. I used C and it finished in 0.270 seconds.

Just precalculate and store the factorials in an array. I'm using the same algorithm and get AC in 0.210 seconds.

Thanxs Broderick and Christian for your help.

Maybe it is just me, but i dont like this kind of problems. What's the point of making a problem with so small time tolerance. In contest like acm icpc this doesnt matter (I think that the time is about 30 seconds, but i am not quite sure). My point is whats the benefit for us (the people who want to learn using the online judge) when a problem force us to make an static array of precalculated values.

I believe that people that use this is for learning and apply the algorihtms that they know. I justify the limits on time when you want to filter a "brute solution" from a "smart one" (IE: Using binary search instead of normal search, etc, etc, etc) .

Anyway maybe i am the only one that think this way, i really like to hear another points of views and see why you consider important that we use optimization theniques like the proposed for this problem. To me Optimization makes sense when you are getting an O(n^4) to a O(n^3) or O(n^3*log(n)).

Thanxs for your help.

I think my algorith is right. But it got WA. Maybe i have some input mistakes.

[pascal]
const
name1 = '';
name2 = '';
maxn = 22;
var
cp,w : array[1 .. maxn] of integer;
ck : array[1 .. maxn] of boolean;
n,l,p : integer;
st : string[maxn];

procedure init;
begin
readln(st);
l := length(st);
end;

procedure main;
var i,j,k : integer;
result : longint;
begin
if l = 0 then begin writeln(0); exit; end;
result := 1;
fillchar(cp, sizeof(cp), 0);
fillchar(ck, sizeof(ck), false);
for i := 1 to l do cp := 1;
for i := 1 to l - 1 do
if not ck then begin
k := 1;
for j := i + 1 to l do
if st[j] = st then begin inc(k); ck[j] := true; end;
for j := 2 to k do dec(cp[j]);
end;
for i := l downto 2 do
if (cp > 0) and (w > 0) then begin
inc(cp[w], cp);
inc(cp[i div w], cp);
cp := 0;
end;
for i := 2 to l do
if cp[i] > 0 then
for j := 1 to cp[i] do result := result * i;
writeln('Data set ', p, ': ', result);
end;

procedure get_primes;
var i,j : integer;
begin
fillchar(ck, sizeof(ck), false);
fillchar(w, sizeof(w), 0);
for i := 2 to maxn do
if not ck[i] then begin
j := i * i;
while j <= maxn do begin
ck[j] := true;
w[j] := i;
inc(j, i);
end;
end;
end;

begin
assign(input, name1);
reset(input);
assign(output, name2);
rewrite(output);

get_primes;
readln(n);
for p := 1 to n do begin
init;
main;
dec(n);
end;
close(input);
close(output);
end.

[/pascal]

Hello, I'm not too sure with Pascal data types ... but as far as I know it's maximum value is 2^31 ... I guess you will have problems there if the final answer is greater than 2^31 ... but still less than 2^32 ...

Regards,
LG

So far as I know, Longint is a 64bit integer, it can reach 2^63. Right?

As far as i know, LongInt type is Borland Pascal specific, ant it's a signed 32 bit integer.
There is a Cardinal type in Borland's Object Pascal that is a unsigned 32 bit integer, but i'm not sure if it is supported by the Online Judge

You can find the integer types for GNU-Pascal in the online Programmers Guide http://www.gnu-pascal.de/gpc_104.html#SEC104.

Especially look at paragraph 8.2.3.2 http://www.gnu-pascal.de/gpc_138.html#SEC138
The 64 bits signed integer type is 'LongInt', the unsigned type is 'LongCard'.

I haven't looked at the complete code, but I find the following suspicious:

[pascal] for p := 1 to n do begin
init;
main;
dec(n);
end;
[/pascal]
You change the limiting value within the loop, which can (and will) lead to unpredictable behaviour.

I find my bugs.~~~~~


[pascal]
for i := l downto 2 do
if (cp > 0) and (w > 0) then begin
inc(cp[w], cp);
inc(cp[i div w], cp);
cp := 0;
end;
[/pascal]

cp > 0 should be cp <> 0

are this input and output correct?please reply?
input are from 2 to 20.ouput are follows:
1,
3,
12,
60,
360,
2520,
20160,
181440,
1814400,
19958400,
239500800,
3113510400,
43589145600,
653837184000,
10461394944000,
177843714048000,
3201186852864000,
60822550204416000,
1216451004088320000
thanks in advance.

Whenever a string comes in, I take its length,factorise it and store the result. Then I divide the result by the factorial of number of times any character is repeated. I also sort by selection sort the string to help me do this.

For hhppp for example, the answer is 5!/(2!*3!*) as h is repeated twice and p 3 times. The answer is 10. I get a WA,of course. Any help??!!

Code:
[cpp]
include <iostream.h>
#include <string.h>
#include <stdio.h>

double fac(int x)
{
double temp=1;
for (int i=x;i>1;i--)
{
temp*=i;
}
return temp;
}

int i,j,temp,index,min,count,count2,count3;
char* str;

void main()
{
double num;
str=new char[30];
cin>>count3;
count2=0;
while (count3>0)
{
count3--;
cin>>str;
count2++;
num=fac(strlen(str));
for (i=0;i<strlen(str-1);i++)
{
index=i;
min=str;
for (j=i;j<strlen(str);j++)
{
if (str[j]<min)
index=j;
}
temp=str[index];
str[index]=str;
str=temp;
}
i=0;
while (i<strlen(str))
{
count=1;
j=i;
while (j<strlen(str)-1 && str[j]==str[j+1])
{
count++;
j++;
}
j++;
num=num/fac(count);
i=j;
}
printf("Data set %d: %.0lf\n",count2,num);
}
}
[/cpp]

You must not use double. It may cause precision errors. Remember the result will always fit into an unsigned long int, so all you must do is cancel the factors of the denominator with the ones of the numerator.
Regards!

That's not necessary in this problem, because the maximum length of the string is 20, and 20! fits in a long long. So just replace double with long long and it should work.

No such luck..I replaced all doubles with long long and still nothing but WA..