Chef War II Discussion

Let me share my method first. My method is very simple. I use the ring as the answer directly. Then this question is similar to a special TSP question.

Firstly, Floyd algorithm is used to preprocess the path length between K special points.

Then the hill climbing algorithm is used to optimize the answer.

The hill climbing algorithm is looking for an arrangement of a_1, a_2... a_k, so that Cost (a_1a_2)+Cost (a_2a_3) +...+ Cost(a_ka_1) is as small as possible.

There are two types of edges in the title, but these two types of edges can be considered as the same edge, which can be reduced to the form of A * day + B .

The final question is how to determine the order of the repaired or constructed paths that have been identified. You can use any method you want. The ranking comparison function I use is A_1*day_2>A_2*day_1.

Finally, my method scored 26131769.
https://www.codechef.com/viewsolution/25241792

If you have some different ideas, please share it, We will be happy. :yum::yum:

2 Likes

Unfortunately I never made it past the trivial solutions for this problems because I always got WA for my more interesting approaches. A trivial solution is: repair all existing roads in sequential order (for something like 0.00001 points).

In general, if the cost were with respect to the day when some work is finished, then it would be optimal to sort roads by the linear part of their cost divided by their number of days. I think it is still pretty good to do it that way.

What I wanted to do is: Compute a spanning tree on K and link all leaves in a cycle.

But somehow the following did not give a correct answer for me. Take any cycle on K and add an arbitrary edge. After some debugging where I did not find the bug I gave up on this :frowning:

I’ve thought about spanning trees, but spanning trees can only be used when the edges satisfy triangular inequalities. When the edges don’t satisfy triangular inequalities, your method may be terrible, believe me.

Spanning trees should work, I think, if you have a good estimate of the day when you will start working on something. Anyway, I failed before I had trees … will definitely check out other solutions to find out what I did wrong.