Problem 1:
You are given a weighted directed graph with N nodes and M edges. Determine whether there exists a path from node 1 to node N such that the sum of the weights on that path is a prime number. If such a path exists, print the minimum achievable prime sum.
Constraints:
N <= 2 * 10^5 M <= 2 * 10^5 Maximum edge weight <= 2 * 10^7
Problem 2:
You are given an array a of N integers and an integer T. You need to choose a subset of numbers from a such that the LCM of the chosen numbers is less than or equal to T.
Print the maximum possible size of such a subset.
Constraints:
N <= 2 * 10^5 T <= 10^9 a[i] <= 60
Nope, they are not easy.
First: looks NP-hard
Second: Observe that there are only 2 141 181 possible LCM values using numbers ≤ 60. We can precompute all such LCMs that are ≤ T.
Let dp[x] = maximum size of a subset whose LCM equals x. Initialize dp[1] = cnt[1], others = 0
Process the LCM values in increasing order. For each current LCM = cur and for each number v from 1 to 60 that appears in the array, compute nxt = lcm(cur, v). If nxt ≠ cur && nxt ≤ T, then: dp[nxt] = max(dp[nxt], dp[cur] + cnt[v]).
Finally, the answer is the maximum dp[x] over all valid x ≤ T.
O(LCM_count * max(a[i]))
Trying to make an actual proof that the first one is hard:
Since you said "path", and not "walk" that makes things easier for me :)
Basically we'll make a gadget to try to reduce to longest path / Hamiltonian path. We'll make all weights 1, and basically reduce "is the longest path from 1 to N exactly N-1 edges long" to this problem.
We need to find a prime gap at least $$$N$$$ in size: we want $$$X$$$ to be a prime, but no numbers in range $$$X...X-N+1$$$ to be prime, because then we can start from vertex "0", make an edge of length $$$X-N+1$$$ to vertex 1, and then the only way to get a prime path is a path $$$N-1$$$ edges long.
To prove that this prime gap exists, consider the sequence:
$$$N!+2, N!+3, ..., N!+N$$$
You can see that all $$$N-1$$$ numbers in this sequence are definitely composite, since $$$N!+x$$$ will be divisible by $$$x$$$ since $$$N!$$$ is divisible by $$$x$$$. So the next prime number after $$$N!+N$$$ can be what we target.
Asymptotically, $$$N!$$$ has roughly $$$N \log N$$$ digits, so this doesn't break polynomial time. Going to the next prime doesn't break the promise either since we know the density of prime numbers scales proportional to 1/$$$digits$$$.