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
10338 - Mischievous Children
Moderator: Board moderators
-
Christian Schuster
- Learning poster
- Posts: 63
- Joined: Thu Apr 04, 2002 2:00 am
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.
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.
10338 WA
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]
[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]
-
easton2048
- New poster
- Posts: 3
- Joined: Fri Jun 28, 2002 11:27 pm
- Location: California
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.
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.
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.
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.
10338 help!!
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]
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]
-
uzioriluzan
- New poster
- Posts: 27
- Joined: Thu Feb 14, 2002 2:00 am
