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?

I really don't mean to bother anyone, this has just been annoying me for a good amount of time.

The problem is 835G. I seem to have a working solution but it's timing out at test 38.

I thought my solution worked in O(n) but it clearly either doesn't or something else is very wrong. My thought process was that both makeWanted and dfs should work in O(n) since there are no loops in a tree, so solve() should be O(n) as well.

I'd be incredibly thankful if you could have a look and see where I'm wrong :)

Hi, I hope you're having a good day.

There seems to be two very distinct types of competitions. A competition will either have a few problems that scale in difficulty very quickly, or have more accessible problems and a slightly less punishing gradient. The first type leads to large numbers of contestants reaching specific problems and then their ranks being decided mainly on speed which I see as a bad thing, however it does allow the contestants to stretch their skills to the limit which allows some to really shine. One example of one of these contests is the most recent(873 D2) where almost 70% completed the first 3 problems. The second type leads to more even distributions of the rankings but it doesn't really allow for contestants to be challenged as they have less time to do each problem.

I'd be interested to hear your thoughts on which type you tend to prefer!