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

BIO prime problem
Автор fmoeran, история, 13 месяцев назад, По-английски

Hi guys,

Here's a problem from the 2016 British Informatics Olympiad round 1.

Problem statement

A prime number is a whole number, greater than 1, that can only be divided by itself and the number 1. Two prime numbers are connected if the difference between them is 2n for some whole number n ≥ 0; e.g. possible differences are 1, 2, 4, 8, 16, 32, … A path is a sequence of (at least two) prime numbers, without repetition, where adjacent numbers in the sequence are connected. If the first number in the sequence is p and the last number is q then we say the path is between p and q. The length of a path is the total number of prime numbers used. There may be multiple paths between two prime numbers; the lengths of these paths may be different. For example:

• 13 is connected to 5 (13 — 5 = 8 = 23), 5 is connected to 3 (5 — 3 = 2 = 21) and 3 is connected to 2 (3 — 2 = 1 = 20);

• As 13 and 5 are connected there is a path between them (13—5) whose length is 2;

• There is a path from 13 to 2 (13—5—3—2) whose length is 4;

• There is a longer path from 13 to 2 (13—17—19—3—2) whose length is 5.

You will be given an upper limit on the primes you are allowed to use. For example, if the limit was 18 then the path 13—17—19—3—2 would not be permitted as it includes a prime above this limit.

Write a program to determine the length of the shortest path between two primes. Your program should input three integers in order: l (4 ≤ l ≤ $$$2^{24}$$$) indicating the highest value you are allowed to use, followed by the primes p then q (2 ≤ p < q < l). You will only be given input where there is a path between p and q using values below l. You should output the length of the shortest path.

My question

It should be an easy question, just breadth first search from p to q with a few tweaks.

My issue is the "(4 ≤ l ≤ $$$2^{24}$$$)". For my search to work it needs to be able to calculate which values are prime and which are not. My solution was to just use a sieve to pre-calculate them all. However, that obviously wont work for $$$l=2^{24}$$$ as the mark scheme only gives points to solutions that finish in under 1 second.

One thing to note is that the actual largest value in the test cases was l=1,000,000 so it could be that a solution for larger l doesn't exist. What do you think?

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

»
13 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

No, I think you can comfortably sieve primes up to 2^24 in under a second quite easily. After that it's as you said, a simple BFS.

This code is around 500ms on my laptop(probably could be faster elsewhere) with 2^24

#define int long long

bool isPrime[20000000];

void sOE(int maxN) {
    memset(isPrime, 1, sizeof isPrime);
    for (int i = 2; i <= maxN; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= maxN; j += i) 
                isPrime[j] = false;
        }
    }
}
→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yeah fair enough, I was using python (my school doesn't support c++). I'm not sure if the question supported all language speeds.

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

      Well, I think in Round 2 you must use C++, so they probably didn't have different languages in mind.

      → Ответить
»
13 месяцев назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

You can do this problem in $$$O(maxpathlength^2 \log^2 n)$$$ There is a primality test algorithm which works in $$$O(\log n)$$$, with a bit of constant factor, so you can just run a BFS and connect a prime with every prime whose difference with the prime is $$$2^n$$$.

Depending on how large the $$$maxpathlength^2$$$ is, this problem can also be done for $$$4 \leq l \leq 10^{18}$$$.

Edit: After doing some tests the $$$maxpathlength$$$ seems to be only $$$15$$$ for $$$10000$$$, $$$10$$$ for $$$1000$$$ and $$$7$$$ for $$$100$$$. Since it probably grows at a $$$\log n$$$ pace the algorithm should work in $$$O(\log^4 n)$$$ which is about $$$2 \cdot 10^8$$$ for $$$n = 10^{18}$$$.

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

    Wh ywas i downvoted im sad

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

      I'm not really sure? I liked the fix and you don't deserve to be downvoted for a good response that was well researched and correct!

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

        I made a minor mistake, the primality test I mentioned works in about $$$12 \cdot \log n$$$. So for $$$l \leq 10^{18}$$$ this might TLE in the absolute worst case

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

    How did you get $$$O(maxpathlength^2)$$$? Shouldn't it be $$$O(k^{maxpathlength})$$$ for some $$$k$$$? The logic is that if after $$$s$$$ steps BFS have reached $$$t$$$ nodes, then after $$$s+1$$$ it will reach $$$kt$$$ nodes. For example, in complete BST we will have $$$k=2$$$.

    → Ответить