OJ Board

shaon_cse_cu08 wrote:Hello every1... My code gives Correct answer for every Input i have tested... But I can't understand Why WA... Plz help me...

I can't say why your approach does not work, but try this case:

input: My solution outputs 520, while yours outputs 4680.

@chengouxuan

I tried it with segment tree but got TLE. I don't know how to do the inversion fast.

Can you explain how you solved it with sqrt(n) X sqrt(n) table??

I tried to solve this problem with the state dp[1<<16][5] as proposed, but getting TLE. Maybe some tips on how to solve it with 16X16X5 memo?

EDIT: With the help of Topcoder msg555 I am able to solve this problem now. See here for details.

What exactly do you want explained? Problem statement?
For some tips on how to solve it, take a look at some posts above.

Here are some testcases, hope they help.

input:
23
2 6
32 1760
7 16
59 44132
218 8066
846 192042
469 28609
676 29068
5 2855
458 115874
77 4081
237 68019
697 14637
74 72298
493 340170
732 104676
355 103305
878 179990
357 111384
157 90275
973 2919
28 6188
429 27456

output:
3
55
NO SOLUTION
748
37 ...

Ah, sure, I thought C could be a prime number... but then it cannot be an lcm..

But what do you mean with check it and then forget it. For finding B, I currently use the fact that the lcm of two numbers is always the product of the prime factors which occur more often in the two numbers, so I don't ...

I tried it with only primes. With my current algorithm for finding the value of B, I need the primes from 2 to 10^7.

How can I calculate B if I don't know the factors of A and C.

Now I'm trying to optimize my solution. I currently use trial division and C++ STL map to store how many times each factor occurs.

Some tips or references on how I could optimize would be great. Thanks in advance.

Thanks Angeh, now I could solve it.

I'm not able to come up with a solution...
Obviously, the brute force approach is too slow. My next step was that I tried to come up with a mathematical solution, but without success.

Can anyone help?

How to solve this problem in O(N) ??

I thought the solution should be 2 if n > 3, 0 if n == 1, 1 if n == 2 or n == 3

2 if n > 3: Cut one piece of size 1, another piece of size 2, then we have 3 pieces of size 1,2, n-3
On the first day the miner can give the n-3 size piece, then the 1 size piece and the next n-2 days he can give 2 and ...