IOI '11 P2 - Race - Olympiads Online Judge

IOI '11 P2 - Race

Points: 17 (partial)

Time limit: 1.4s

Memory limit: 256M

Problem type

Allowed languages

C, C++

In conjunction with the IOI, Pattaya City will host a race: the International Olympiad in Racing (IOR) 2011. As the host, we have to find the best possible course for the race.

In the Pattaya-Chonburi metropolitan area, there are $N$ ~N~ cities connected by a network of $N-1$ ~N-1~ highways. Each highway is bidirectional, connects two different cities, and has an integer length in kilometers. Furthermore, there is exactly one possible path connecting any pair of cities. That is, there is exactly one way to travel from one city to another city by a sequence of highways without visiting any city twice.

The IOR has specific regulations that require the course to be a path whose total length is exactly $K$ ~K~ kilometers, starting and ending in different cities. Obviously, no highway (and therefore also no city) may be used twice on the course to prevent collisions. To minimize traffic disruption, the course must contain as few highways as possible.

Your Task

Write a procedure best_path(N,K,H,L) that takes the following parameters:

$N$ ~N~ – the number of cities. The cities are numbered $0$ ~0~ through $N-1$ ~N-1~.
$K$ ~K~ – the required distance for the race course.
$H$ ~H~ – a two-dimensional array representing highways. For $0 \le i < N-1$ ~0 \le i < N-1~, highway $i$ ~i~ connects the cities $H[i][0]$ ~H[i][0]~ and $H[i][1]$ ~H[i][1]~.
$L$ ~L~ – a one-dimensional array representing the lengths of the highways. For $0 \le i < N-1$ ~0 \le i < N-1~, the length of highway $i$ ~i~ is $L[i]$ ~L[i]~.

You may assume that all values in the array $H$ ~H~ are between $0$ ~0~ and $N-1$ ~N-1~, inclusive, and that the highways described by this array connect all cities as described above. You may also assume that all values in the array $L$ ~L~ are integers between $0$ ~0~ and $1\,000\,000$ ~1\,000\,000~, inclusive.

Your procedure must return the minimum number of highways on a valid race course of length exactly $K$ ~K~. If there is no such course, your procedure must return -1.

Examples

Example 1

Consider the case shown in Figure 1, where $N=4$ ~N=4~, $K=3$ ~K=3~,

$\text{[math]}$

The course can start in city $0$ ~0~, go to city $1$ ~1~, and terminate in city $2$ ~2~. Its length will be exactly $1$ ~1~ km + $2$ ~2~ km = $3$ ~3~ km, and it consists of two highways. This is the best possible course; therefore best_path(N,K,H,L) must return $2$ ~2~.

Example 2

Consider the case shown in Figure 2, where $N=3$ ~N=3~, $K=3$ ~K=3~,

$\text{[math]}$

There is no valid course. In this case, best_path(N,K,H,L) must return -1.

Example 3

Consider the case shown in Figure 3, where $N=11$ ~N=11~, $K=12$ ~K=12~,

$\text{[math]}$

One possible course consists of 3 highways: from city $6$ ~6~ via city $0$ ~0~ and city $2$ ~2~ to city $3$ ~3~. Another course starts in city $10$ ~10~ and goes via city $8$ ~8~ to city $6$ ~6~. Both of these courses have length exactly $12$ ~12~ km, as required. The second one is optimal, as there is no valid course with a single highway. Hence, best_path(N,K,H,L) must return $2$ ~2~.

Subtasks

Subtask 1 (9 points)

$1 \le N \le 100$ ~1 \le N \le 100~
$1 \le K \le 100$ ~1 \le K \le 100~
The network of highways forms the simplest possible line: For $0 \le i < N-1$ ~0 \le i < N-1~, highway $i$ ~i~ connects cities $i$ ~i~ and $i+1$ ~i+1~.

Subtask 2 (12 points)

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~
$1 \le K \le 1\,000\,000$ ~1 \le K \le 1\,000\,000~

Subtask 3 (22 points)

$1 \le N \le 200\,000$ ~1 \le N \le 200\,000~
$1 \le K \le 100$ ~1 \le K \le 100~

Subtask 4 (57 points)

$1 \le N \le 200\,000$ ~1 \le N \le 200\,000~
$1 \le K \le 1\,000\,000$ ~1 \le K \le 1\,000\,000~

Implementation Details

Interface (API)

To be implemented by contestant:

int best_path(int N, int K, int H[][2], int L[]);

Comments

0

HyperGraphJ commented on July 29, 2020, 4:35 p.m.

Underrated problem in my opinion, seems harder than somewhat similar 30p Winter Driving (and for my solutions at least, with slightly worse theoretical time complexity).

8

richardzhang commented on July 29, 2020, 5:45 p.m.

I would argue that Race is much more straightforwards compared to Winter Driving; you simply apply the right algorithm and you're done (your pick of small-to-large merge or centroid decomposition). Winter Driving involves a little more observation and requires a different property of centroids (not just taking advantage of the path decomposition). If you want to try your hand at some slightly more complicated centroid decomposition problems, https://dmoj.ca/problem/dmopc19c7p6 or https://dmoj.ca/problem/dmpg19g5 might be a good place to start.

5

HyperGraphJ commented on July 29, 2020, 6:12 p.m. ← edit 5 →

Wow just after I commented this, it got changed from 20p to 17p, that's the opposite direction I was suggesting damn. In response to your comment I would argue it is harder due to its higher time complexity (at least so far as I know how to do it) $N \log^2 N$ ~N \log^2 N~ vs $N \log N$ ~N \log N~ for Winter Driving, and that the overlapping parts of the problem are slighter harder to implement for this one.

I'm not sure how problems get their pts rating around here, based on timing it seems like someone just read my comment and decided to spite me (or more charitably genuinely examined its difficulty and came to opposite conclusion of mine).

EDIT: I have been informed there is a reasonable $N \log N$ ~N \log N~ solution to this so my claim of difficulty is not objective on complexity grounds, and moreover it is apparently routine to investigate pt values after receiving comments, so I am less scandalised by the change to 17p (despite not really agreeing with it based on IOI performance on problem etc.).