Problem link (The problem is originally from ONTAK 2007, but I can't find it from szkopul.edu.pl)
Statement: $$$N$$$ people wants to cross the river with a boat. In each step, two people will take the boat to cross the river, and if necessary, one of those two will come back with a boat to salvage the remaining people. Each people have a time factor $$$t_i$$$, and the time boat needs to cross the river is equal to the maximum time factor of all people on the boat. Additionally, there are $$$M$$$ pairs of people, who don't want to be in the boat at the same time. What is the minimum time needed for all people to cross the river? Print NIE if this is impossible at all. ($$$2 \le N \le 100\,000, 0 \le M \le 100\,000$$$)
I can solve this problem in polynomial time, but I don't think this approach can be optimized, nor have I found any alternative approach.
The problem is almost 20 years old, but it's really hard. Anyone knows how to solve this?
I'm curious about your strategy with no restrictions at all.
I believe the optimal solution is combining these two algorithms: $$$\newline$$$ Let $$$t_1$$$ $$$\le$$$ $$$t_2$$$ $$$\le$$$ $$$t_3$$$ $$$\le$$$ $$$t_4$$$, and let's try to move 3 and 4.$$$\newline$$$ First algorithm:$$$\newline$$$ Move (1,3), return (1), move (1, 4), return (1): This has a cost of $$$t_3$$$+$$$t_4$$$+2 $$$t_1$$$.$$$\newline$$$ Second algorithm:$$$\newline$$$ Move (1, 2), return (1), move (3, 4), return (2): This has a cost of $$$t_4$$$+2 $$$t_2$$$+$$$t_1$$$.
I think if you add $$$t_1 + … + t_n$$$ to the solution to the original problem, you get the solution to the reduced problem mentioned above. And it makes sense, as the reduced problem considers that we move pairs across the river and we move them back.
You can think of the reduced problem as such:
What is the minimum cost to move all people to shore B and back, such that we move two people at a time from shore A to shore B, and one person at a time from shore B to shore A? And there is no one boat a time.
It makes sense that an optimal solution to the original problem is also an optimal solution to this problem, modulo sum of $$$t$$$ s.
The case $$$K=0$$$ admits the greedy solution similar to what you mentioned. I remember I prepared this exact problem for a Uni contest last year or so.
OP: What is the exact reduction from the reduced problem to the general weighted matching?
I used a rather naive reduction. We find a min-weight perfect matching in the following graph with $$$2n$$$ vertices:
and subtract $$$\min_e w(e)$$$ from the answer.
Anyway, I read the statement incorrectly, so this problem now looks much less like a matching.
Without restrictions it is https://acm.timus.ru/problem.aspx?space=1&num=1826
I guess you are misreading the statement. The statement on the Baekjeon says that after two swimmers A and B cross the river either A or B returns, while your explanation says anyone on the goal side can swim back. If my reading is correct, the problem is about MST in the complement graph and we can solve it in $$$O((N+M) \log N)$$$ time.
That being said, I'm getting WA (my submission) and I have no idea why it doesn't work. I even wrote brute-force and checked that it correctly calculates MST, so I must be overlooking something.
That makes a little more sense (this change in the statement), although I don't see how MST solves the problem.
Let $$$G$$$($$$V$$$, $$$E$$$) be the MST of the graph, $$$V$$$ = {1, 2, 3, 4, 5, 6, 7}, $$$E$$$ = {(1, 2), (2, 3), (3, 4), (4, 5), (3, 6), (6, 7)}, how do you use this tree? I mean, you should go through an edge more than once.
Root the MST per the vertex with minimum $$$a_i$$$. Repeatedly take any edge $$$e = (i, j)$$$ adjacent to leaf $$$i$$$, take both to the opposite side, and take the non-leaf $$$j$$$ back. This incurs the cost $$$\max(a_i, a_j) + a_j$$$. But the leaf is removed, so we can make the cost function symmetric: $$$\max(a_i, a_j) + a_i + a_j$$$ and remove the cost for the leaf later on. So the structure of MST doesn't matter.
Not every tree is okay, is it? It seems that only caterpillar trees can be achieved through this process (a long chain downward plus some leaves attached to all nodes). Am I right?
Very sorry, I also checked my reading several times, but I couldn't find that.
I feel that this is not an MST but an arborescence.It can be reduced into MST, I think. I can't see your code, so I'm not sure if this is the reduction you've doneSolve for each connected component. Compute min spanning tree wrt weight $$$a_i + a_j + \max(a_i, a_j)$$$ and add $$$-\sum a_i$$$.
That is precisely the same as my reduction, which got WA. I wonder if it's indeed wrong or if the judge has some mistakes. I'm waiting for someone to solve the problem with this strategy.
Also have WA in 25% with the same strategy: code
I will check the tests with Baekjoon.
The output is
IMPOSSIBLEinstead ofNIE-_-Baekjoon added a SPJ that accepts both outputs and rejudged the problem. You will soon get AC.