Pathetic_loser's blog

Bangkok Regional : Problem A, requesting help/hint :(
By Pathetic_loser, 10 years ago, In English

Hi

Could any kind person give me any hint to solve this problem? I am horrible at math :(

Finding unique numbers in N*N multiplication table? :(

Here is the link to the problem

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

»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Because of 7s time limit, so N*N solution could be accepted

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

Is ML big enough for naive solution?

Maximal possible product is 900000000. You need 112.5 millions of bites for such bitset. So if you have at least 128 mb — then solution is straightforward. BTW, even if ML is only 64 mb — you can solve it with 2 runs, storing bitset for first 450000000 at first run and bitset for next 450000000 in second run (using same array both times).

Add rows one by one. Let's store in bitset 0/1 for every number — did we already received this one?

For table (N+1)*(N+1) answer is equal to amount of different numbers in N*N matrix, plus new numbers from row N+1. So you just check every number of form (N+1)*X, with X being less or equal to N+1; if there is 0 in (N+1)*X-th position of bitset — add 1 to answer and set this position to 1.

Now you know answers for all possible values of N, and can say the answer for every query in O(1).

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    We did this during the contest, too. The running time was a bit over 6s when we tested locally (I heard that the judging machine was even faster).

    You can submit a constant array with all possible results though. Some teams actually did this way.

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

      Yes, if source code limit is not 65536 bites, but big enough — constant array is a good idea.

      There are few optimizations to speed up naive solution, if it have problems with passing TL. Simplest one is to do inner loop like this:

      if (i%2==1)L=1;
else L=i/2;
for (int j=L;j<=i;j++)

      because for every even i and j<i/2 you already reached i*j==(i/2)*(j*2) before. This already decreases number of operations by 25%. And one can improve it even more with some other similar tricks

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        You don't need actually big array for naive solution. You can use "sliding window": a buffer with fixed size, for example 65k numbers, and "sieve" this buffer with all prime numbers less than 30K. Code can be actually faster because of CPU cache.

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

      Thanks a lot to all of you :) In my laptop, it ran for 12 seconds and UVA online judge is slower than my laptop and probably also slower than judge computer used at the onsite contest! I can see 3 AC in the UVA though, two of them under 2 seconds and one under 6 seconds.

      Here in CF custom test, it took 4 seconds only!

      → Reply