As the round is over, the links are disabled by them.

I can only come up with a very basic brute force solution of $$$(2*N)!$$$ where for each of the order of visiting I calculate the cost and then update the answer accordingly. But as expected this even didn't pass even a single test.

Can someone please help me with some spoilers on how to proceed further with it?

Thanks!

Edit: Hello all! Why everyone is downvoting the post? Is there something wrong with it or I asked the question in a wrong way ? I find the problem difficult so I asked for help and if someone find it easy then instead of directly downvoting please explain the solution (or atleast a step towards it) and then downvote if you think it's irrelevant.

Hello I recently learned DCP trick. I had tried implementing it but my implementation give WA on DYNACON1 of SPOJ and MLE on CF 100551.

• DYNACON1 implementation
• 100551A solution

Can someone please suggest what is wrong in the solution or can give any better implementations?

Thanks!

N cities are connected using bidirectional roads (there may be multiple roads between two cities and the graph may not be fully connected).

There is a value associated with each nodes ($$$A[i]$$$) and with each edges. The cost of entering a city is $$$A[i]$$$.

We have to find the minimum cost of entering any city starting from every possible element $$$i$$$.

Example : 4 cities having value (5, 7, 100, 11) and roads are (u, v, w) where (u, v) are nodes and w is the weight of the edge.

(1, 2, 5), (3, 4, 50)

Answer is (5, 7, 61, 11)

Explanation : starting from 1 we can enter city 1 (cost 5)

starting from 2 we can enter city 2 (cost 7)

starting from 3 we can enter city 4 (cost: (3 -> 4)edge + value_of_entering_4(11) = 61)

starting from 4 we can enter city 4 (cost: 11)

Constraints: All the edge values and cost of entering a city is $$$<= 10^9$$$ Number of cities and number of roads $$$<= 10^5$$$

Given an array of integers $$$(A[i] <= 10^5)$$$. We have to find number of unordered pairs (i, j) such that their GCD is greater than B.

All value <= $$$10^5$$$

Can someone give me a general idea how to approach such kinds of problems? Because this type of question appears frequently in programming contests and every time I devote much time solving this but failed each time :(

prob : http://codeforces.net/contest/351/problem/C

I've read the editorial but didn't understand the matrix exponentiation part. I've also read the comments but didn't get it. can someone please explain that concept.

Thanks in advance :)