Hi everyone.
My code for problem Little Elephant and LCM has got WA on test 9. My algorithm is a bit different from the editorial.
Can you help me?
Thx all :)
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
Hi everyone.
My code for problem Little Elephant and LCM has got WA on test 9. My algorithm is a bit different from the editorial.
Can you help me?
Thx all :)
Name |
---|
if you explain your idea then it will become easier to understand your code then we can help you
That's because any deviation from the editorial's version is unorthodox!
jk, :D. Do you expect us to read and try to understand it? :D
I wished you to read and understand it ;)
I found the mistake, but now I got TLE :(
This is My solution:
First, I sort the array a.
then, I iterate over max(b[i]). Suppose that this max equals m. I define f[i] = number of divisors of m which are not greater than a[i] and suppose that T equals the number of a[i]'s which are not less than m. Then, I calculate f[i] with dp. Now the the answer is:
f[1] * f[2] * ... f[n] — f[1] * f[2] * ... f[n — T] * (f[n — T + 1] — 1) * .... * (f[n] — 1)
My algorithm is O(nsqrt(n))
My algorithm is also O(nsqrt(n)) but passed the system test at about 1000ms.. I think for N<=100000 nsqrt(n) is not a large number so you can try to optimize your code more.
I think your solution gets TLE because of this.
a[n - 1] <= 10^5
, andf
's size is10^5
, so the maximum execution time might be too long.You can use timestamps to initialize
f
, this costs O(1) to initialize. 2850964 is the solution. However, there is a solution which doesn't usef
.Thx very much, I changed my code and deleted
f
and got accepted.But I don't know what "timestamps" is. Can you explain it a bit?
Let's imagine some fancy code:
It's kinda long running. Now consider the trick:
Thx very much :)