Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### pk842's blog

By pk842, history, 5 months ago, ,

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.

• +4

By pk842, history, 5 months ago, ,

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.

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

Thanks!

• -9

By pk842, history, 10 months ago, ,

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$

• +7

By pk842, history, 10 months ago, ,

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 :(

• 0

By pk842, history, 20 months ago, ,

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 :)

• 0