Блог пользователя AlimA

Little Elephant and LCM, WA!
Автор AlimA, 12 лет назад, По-английски

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

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    → Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        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
}
        → Ответить