AlimA's blog

By AlimA, 11 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

»
11 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

»
11 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

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

    I wished you to read and understand it ;)

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

  • »
    »
    11 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.

  • »
    »
    11 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.

    • »
      »
      »
      11 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?

      • »
        »
        »
        »
        11 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
        }