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

Bangkok Regional : Problem A, requesting help/hint :(
Автор Pathetic_loser, 10 лет назад, По-английски

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

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

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

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

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

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

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

    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.

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

      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

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

        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.

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

      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!

      → Ответить