fixed! thanks!

But how to solve F,I guess if a graph has a cycle ,the answer is one of the smallest cycles.

$$$O(2^N\times M)$$$ DP.

For $$$i \lt 2^N$$$ and $$$j \lt M$$$, DP[i][j] should be the minimum cost for having exact treasures corresponding to $$$i$$$.

Edit: using only first j keys of course.

I had an idea but couldn't execute it cuz of time. We create bitmasks for every key based on the boxes it unlocks, for eg: if (j)th key unlocks box 6, turn on the (6)th bit of the (j)th mask. We need to find subset with minimum cost for which bitwise OR of all masks is ((1 << n)-1)<<1 .

1D dp is enough.

No need of 2D dp.

My solution:https://atcoder.jp/contests/abc142/submissions/7762980

Maybe you fail on such testcase:
2 2
1 2
2 1
(Just maybe)

yupp

Count the number of distinct common prime factors + 1

First we make the observation that all common factors of A and B must be a factor of their gcd. The gcd of A and B can be computed very quickly (in about log(A) time) using the following formula: gcd(A, B) = {A if B = 0, gcd(B, A % B) if B != 0} Then, we observe that there is a greedy algorithm. It is always optimal to take all of the prime factors of gcd(A, B) (and 1). This can be proven with exchange argument. Suppose it is optimal to take some K = x * y, where x, y > 1. There exists no other item L we took that have gcd(K, L) > 1, or it would violate the constraints. Thus, gcd(x, L) = gcd(y, L) = 1, and it is more optimal to take x and y instead of K. So just prime factorise gcd(A, B) and add 1 to the number of distinct prime factors. This can be done in roughly O(sqrt(A)) time, which passes.

Sample Code: https://atcoder.jp/contests/abc142/submissions/7751965

the number of divisor of gcd(a,b) + 1

Here is my solution

Can we improve this solution to O(n)??

You have N treasure chests you want to open. There is a shop that sells M keys. Each key has a cost to buy and each may open different chests. What is the minimum cost to buy keys that make it possible to you to open all the chests?

It is a DP solution, where in each state of the DP[K][chests_bitwise] you see if it is cheaper to buy the Kth key and open the chests, or skip the key and check for the next one.

Hope I explained well enough

Here's my solution Edit: updated solution so it has English friendly variables

Try this case:

9 12 1 5 5 2 2 7 7 3 3 8 8 4 4 9 9 1 1 2 2 3 3 4 4 1

In this case your program gives a wrong answer. The case even if its big it is symmetric and easy to understand if you draw it in the paper.

I assume that you are doing wrong what I did initially as well. When you are at node=1, then you are moving at node=5 but from node=5 you can't move to node=2 because node=2 was neighbor of node=1, but your source-code is moving there and its wrong.

So the way I fixed it was to mark as visited all the neighbors of a node, but keep a vector of "goodNeighbors" so as to be possible to go from node=1 to node=2, but not from node=5 to node=2.

This is my submission: https://atcoder.jp/contests/abc142/submissions/7785403

Where can I find this kind of editorial??

It's all my fault, i set int*int to compare with ll and it caused me 1 hours :'(

In the primes vector, you are pushing elements only till 1e3 at max, i.e. in the p*p<=1000000 loop, which goes for p=1e3 at max. Instead of pushing elements in the sieve itself, you can iterate over the bitset and check which elements are set. In this way you will get all primes till 1e6 and not just till 1e3. Below is the accepted code with the required change.

Soln