Old Polish problem about bridge crossing

Revision en2, by ko_osaga, 2023-05-26 09:03:03

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.

Spoiler

The problem is almost 20 years old, but it's really hard. Anyone knows how to solve this?

#### History

Revisions

Rev. Lang. By When Δ Comment
en2 ko_osaga 2023-05-26 09:03:03 169
en1 ko_osaga 2023-05-25 14:55:43 1534 Initial revision (published)