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 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
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 :)