11182 - Zeroes III

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

Moderator: Board moderators

Post Reply
suhendry
New poster
Posts: 14
Joined: Sat Aug 31, 2002 6:55 am

11182 - Zeroes III

Post by suhendry » Tue Feb 27, 2007 6:06 am

Is there any 'advance' number theory involved in this problem?

O(n) is not fast enough. I've tested the judge with O(n) dummy code (input and loop), and it run for 5s :o . My best algorithm was O(nlog b) using prime factorization, which is obviously give me TLE.

I use this formula:
F2(n) = 1^S(n) . 2^S(n-1) . 3^S(n-2) . ...... . n^S(1)
where S(n) is accumulated sum from 1 to n -> n * (n+1) / 2
Suhendry Effendy

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Feb 27, 2007 8:03 am

O(n) is waaay too slow.
F2(n) = 1^S(n) . 2^S(n-1) . 3^S(n-2) . ...... . n^S(1)
Yes, but since we are only interested in the factors of F2(n) related to input b, many of the terms aren't necessary. Think about it. We got accepted during contest, and NO hard number theory is required.

Try also the case:
1000000 2
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

deepesh
New poster
Posts: 13
Joined: Sat Dec 23, 2006 5:57 am

Post by deepesh » Tue Feb 27, 2007 12:44 pm

Can you give the answer for :
1000000 2

Also can you give a few more test cases. I am getting a wrong answer.


[Edit] -> I have got accepted on this problem

suhendry
New poster
Posts: 14
Joined: Sat Aug 31, 2002 6:55 am

Post by suhendry » Thu Mar 01, 2007 6:16 am

At last, I got accepted using O(log n . log b). Thank you for your hint :)

input:

Code: Select all

8191 8192
1000000 2
1000000 2310
1000000 6720
1 2
2 864
5 10
10 10000
48 219
100 5
2133 504
2610 30
3248 219
4511 888
8950 66
42610 3000
84511 7323
63702 864
63702 1431
244080 67
955467 6
958356 496
958356 3502
984673 9973
999999 9999
1000000 10
1000000 10000
0 0
output:

Code: Select all

7032662488
166662438307705929
16665402729127869
27776193671899116
0
0
1
5
0
36924
266003535
734253290
75718500
415423766
11886657412
1073649906316
39445538957
7177687067852
826272808535
36682693786847
72686052960360603
4889164417770575
1437645574232012
15713577274647
1666006641512399
41664788608656248
10416197152164062
Edit: (add more random testcases). I don't think there's any tricky case in this problem..
Last edited by suhendry on Mon Mar 26, 2007 7:50 am, edited 1 time in total.
Suhendry Effendy

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

Post by erdos » Thu Mar 22, 2007 3:55 am

Hi,

My program outputs the same results but judge returns WA. Could you please provide some additional sample input and output?

Thanks,

Jos

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Mon Apr 02, 2007 9:35 am

Hello ,
Could you give me some hint about how to reduce the complexity from O(nlogb) to O(lognlogb) ?

since we are only interested in the factors of F2(n) related to input b
What does it mean?
Could you please give me some hints?

Thx in advance! :D

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik » Mon Apr 02, 2007 9:55 am

Hello,

by calculating the sums on paper you can find a formula to compute the number of occurences of a given prime in F2(n). But for each prime p you have to sum these occurences for p, p^2, p^3, ...
(Just as you do to determine the number of occurences of a prime p in n!)

These are less then log(n) steps required (stop at p^x>n). As b has less than log(b) distinct prime factors, you are done.

Cu, Erik :)

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Thu Apr 05, 2007 4:10 am

Erik wrote:Hello,

by calculating the sums on paper you can find a formula to compute the number of occurences of a given prime in F2(n). But for each prime p you have to sum these occurences for p, p^2, p^3, ...
(Just as you do to determine the number of occurences of a prime p in n!)

These are less then log(n) steps required (stop at p^x>n). As b has less than log(b) distinct prime factors, you are done.

Cu, Erik :)
Hi , Erik
Thanks a lot!! I got in 0.346 sec.
:P

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

Post by erdos » Sat Apr 07, 2007 4:46 pm

It is quite weird...
I spent a while thinking on this problem to get to the right formula. My program gives the same output for the extended input provided a few posts below. Even so I get WA.

Probably, for some extreme inputs, in some intermediate calculation the int64 limit is exceeded and that causes an error?

Could you please provide border cases like that?

Thanks,

Jose Carlos

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Sun Apr 08, 2007 4:59 am

I think there's no such tricky cases. I use unsigned long long and get accepted.

try this cases also

Code: Select all

999999 2
1000000 997
999999 991
0 0
Output
166661938317090928
166919023725621
167930784422985

Hope it helps.

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

Post by erdos » Mon Apr 09, 2007 12:44 am

Thanks for the input but my program also gives the same output. So I still have no clue what may be wrong as I've tried many different inputs and the output is correct. I'm posting my source code below if someone is kind enough to spend sometime trying to figure out what might be the problem.

Code: Select all

//Removed
Thanks,
Last edited by erdos on Mon Apr 09, 2007 1:51 pm, edited 1 time in total.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Mon Apr 09, 2007 9:46 am

I change this portion of u'r code and get AC.

Code: Select all

if(countFactors[i]/bases[i]<min) 
{ 
     min=countFactors[i]/powers[i]; 
}

after change

if(countFactors[i]/powers[i]<min) 
{ 
     min=countFactors[i]/powers[i]; 
}

remove u'r code after AC.

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

Post by erdos » Mon Apr 09, 2007 1:58 pm

Hi,

Thank you so much. I've submitted and got accepted.

When I looked at your correction it was immediately obvious. It was a typo, but what's more amazing is that even with that typo the program was giving correct results for any test case posted here!

If it were giving some wrong results it would have been much easier to spot it.

Thank you again,

Post Reply

Return to “Volume 111 (11100-11199)”