11014 - Make a Crystal

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

nafi
New poster
Posts: 11
Joined: Sat Jul 31, 2004 10:35 pm
Location: Dhaka, Bangladesh
Contact:

11014 - Make a Crystal

Post by nafi »

I am getting WA for this problem. Can anyone tell me what are the correct output for 6, 8 & 10? I get 290, 530 & 1010 respectively. Are these results right?

Nafi

nafi
New poster
Posts: 11
Joined: Sat Jul 31, 2004 10:35 pm
Location: Dhaka, Bangladesh
Contact:

Post by nafi »

My results are wrong for N = 8 & 10. I have found a mistake in my derivation.

Nafi

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

Post by QulinXao »

my prog(wich judge think wrong) for:
2
4
6
8
10
100
1000
10000
100000
200000
0
return :
Crystal 1: 26
Crystal 2: 98
Crystal 3: 290
Crystal 4: 578
Crystal 5: 1154
Crystal 6: 854786
Crystal 7: 834185090
Crystal 8: 832136021570
Crystal 9: 831930692993858
Crystal 10: 6655340768473154

It's correct? wich case wrong?pls help
PS. in sol I use eratosfen sieve

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

Strange. Your output is correct.

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

Post by QulinXao »

now all ok (I get accepted)
but i think exist some bug in fpc
cose my 1 try(wrong) use var r:comp; and writeln(r:0:0)
and 2 try(accepted) use var r:int64; and writeln(r);

in home i use:
for 1try bp(turbo/borland pascal)
for 2 try dcc( delphi )
for all value they get same result
but on judge under fpc they difrent

PS.HELLO ADMIN! AM I right?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

If my information is correct, the type Comp is a 64 bit signed integer type that is handled by the Floating Point Unit of an Intel type processor, instead of being implemented as a true 64 bit integer type, so it might be possible that it suffers from rounding errors. (The type is not defined for other than Intel architectures).
I think it is safest to use Int64 (signed) or QWord (unsigned) if you use 64 bit integers. They are either directly handled by the CPU (Athlon 64) or split by the compiler into two 32 bit integers. I think the judge runs on a 32 bits machine, so the latter might be the case.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam »

I need a hint to solve this problem (I will be very happy if a complete illustration is posted).

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

(Assuming you know about Euler's Phi function.)

My approach starts from thinking about a two dimensional version of Phi function.
Let A(n) be | { (x,y) : 1<=x,y<=n and gcd(x,y,n)=1 } |
What's A(n) when n is prime? power of prime?
What's A(ab) if a and b are co-prime?

Then the final solution could be built up from this function A.

kalinov
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia

Post by kalinov »

I used principle of inclusion-exclusion.

To solve 3D problem (x>0, y>0, z>0) I do this:

Let f(k) be the number points (x,y,z) such that 0<x<=N, 0<y<=N, 0<z<=N and such that x, y, and z are multiples of k.

f(k) = (N/k)*(N/k)*(N/k) (it's integer division)

First, let's count total number of points. It's f(1).

Now we have to subtract f(2) because gcd for those points is not 1 (it is at least 2), so those points are not valid.
Also we subtract f(3), f(5), f(7)... because of same reason...
But then we subtracted points like (6,6,6) twice (once with f(2) and once with f(3)). So we have to add them once more. So we add f(2*3), f(2*5), f(3*5)...
And so on...

So we end up with something like this:
f(1) - f(2) - f(3) - f(5) - f(7) - ... + f(2*3) + f(2*5) + f(3*5) + ... - f(2*3*5) - f(2*3*7)...

Obviously, f(k)=0 for k > N, so there will be at most N (nonzero) terms to add (subtract).


You can use the same approach to solve 2D problem (to count the number of points like (x,y,0), (x,0,z) and (0,y,z) )

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

Post by QulinXao »

1. cho can you explain?(your sol very fast-0.064sec)
2. my sol is(0.152sec more then 2 time slow :( ) :
w=(2*i+1)^3
s=w-w[i-1];
p=s-sum(p[j]| i mod j=0, 0<j<i);
r=sum(p,1..i);
where w- all atoms in cube 2i
s-new atoms (|x| or |y| or |z| ==i)
p-atoms in level i from wich can view center (0,0,0) or as same gsd(x,y,z)==1
r[i] - that us ask

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam »

Thank you very much Mr. Cho and Mr. Kalinov for your explanations.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

The bottle neck of my algorithm is the sieve, afterwards, everything can be done in linear time. Since our approaches are different, it's not surprised that there is a constant factor difference in the running times.

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam »

Mr. Kalinov. Can you describe how to make this effitiently?
(I am sorry for annoyance, but I am not very good at these tricks of discrete math)

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

Post by QulinXao »

Cho wrote:The bottle neck of my algorithm is the sieve,
my too (for j:=2 to m div i do dec(p[i*j],p);
Cho wrote: afterwards, everything can be done in linear time.

yep!
Cho wrote:Since our approaches are different, it's not surprised that there is a constant factor difference in the running times.

I think not so dif.
Cho can you more detail about your sol
ps. by the way if s:=i than p -euler phi function

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

1. Run sieve so that factor[n] store the max prime factor of n
2. Compute all phi[n] by making use of factor[n], O(n)
3. Compute all A[n] by making use of factor[n], O(n)
4. Compute all sumphi[n] to be phi[1]+...+phi[n], O(n)
5. Compute all sumA[n] to be A[1]+...+A[n], O(n)
6. Finally, for each query, the answer can be computed in O(1).
So, the bottle neck is phase 1.

>> p=s-sum(p[j]| i mod j=0, 0<j<i);
Is this part O(n sqrt(n))?

Post Reply

Return to “Volume 110 (11000-11099)”