AlimA's blog

Little Elephant and LCM, WA!
By AlimA, 12 years ago, In English

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 :)

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

if you explain your idea then it will become easier to understand your code then we can help you

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wished you to read and understand it ;)

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like 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))

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    I think your solution gets TLE because of this.

        for (int64 m = 1; m <= a[n - 1]; ++m) {
        memset(f, 0, sizeof(f));
        fill_array(m, n);
    }

    a[n - 1] <= 10^5, and f's size is 10^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 use f.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Let's imagine some fancy code:

        for(int i = 0; i < n; i++) {
  ...
  if(used[k * 28 + 100500 / 9000]) {
    //do something
  }
  ...
  if(!used[j]) {
    //do something
    ...
    //and mark as used:
    used[j] = 1;
  }
  ...
  //now clear 'used' to reuse in next iteration:
  for(int j = 0; j < m; j++) {
    used[j] = 0;
  }
}

        It's kinda long running. Now consider the trick:

        int timestamp = 1;
for(int i = 0; i < n; i++) {
  ...
  if(used[k * 28 + 100500 / 9000] == timestamp) {
    //do something
  }
  ...
  if(used[j] != timestamp) {
    //do something
    ...
    //and mark as used:
    used[j] = timestamp;
  }
  ...
  //now clear 'used' to reuse in next iteration:
  timestamp++;// <---- NO CYCLE HERE
}
        → Reply