10338 - Mischievous Children

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

Moderator: Board moderators

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

10338 - Mischievous Children

Post by ithamar » Mon Jul 29, 2002 11:50 pm

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

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada

Post by broderic » Tue Jul 30, 2002 5:18 am

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

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Tue Jul 30, 2002 8:41 am

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

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

Post by ithamar » Tue Jul 30, 2002 10:47 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.

Rivaldo
New poster
Posts: 19
Joined: Sun Jul 07, 2002 3:59 pm

10338 WA

Post by Rivaldo » Tue Jul 30, 2002 4:21 pm

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]

easton2048
New poster
Posts: 3
Joined: Fri Jun 28, 2002 11:27 pm
Location: California

Post by easton2048 » Wed Jul 31, 2002 2:05 am

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

Rivaldo
New poster
Posts: 19
Joined: Sun Jul 07, 2002 3:59 pm

Post by Rivaldo » Wed Jul 31, 2002 5:27 am

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

sweko
New poster
Posts: 7
Joined: Fri Apr 19, 2002 4:05 pm

Post by sweko » Wed Jul 31, 2002 10:20 am

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
SWeko has spoken

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon » Wed Jul 31, 2002 11:49 am

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.

Rivaldo
New poster
Posts: 19
Joined: Sun Jul 07, 2002 3:59 pm

Post by Rivaldo » Wed Jul 31, 2002 12:11 pm

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

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo » Sat Aug 03, 2002 7:43 pm

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.

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

10338 help!!

Post by mido » Tue Sep 17, 2002 1:55 pm

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]

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

Post by uzioriluzan » Tue Sep 17, 2002 3:41 pm

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!

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Tue Sep 17, 2002 4:05 pm

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.

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Wed Sep 18, 2002 11:16 am

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

Post Reply

Return to “Volume 103 (10300-10399)”