Educational Round #9 — Editorial

Divide all the balls into three groups that are as equal in size as possible. If the number $n$ is not divisible by $3$ , the sizes of the groups will differ by at most one ball. Two groups of equal size are placed on the pans of the balance. As a result of one weighing, we determine in which of the three groups the heavy ball is located.

Thus, after one weighing, the problem with $n$ balls is reduced in the worst case to a problem with $⌈ n /3 ⌉$ balls. Therefore, $⌈ l o g_{3} n ⌉$ weighings are sufficient to guarantee the detection of the heavy ball.

Second solution. Let $p$ be the largest exponent for which the inequality $3^{p} < n$ holds. Then the minimum number of weighings required to guarantee the detection of the heavy ball is $p + 1$ .

Example

For $3$ balls, a single weighing is sufficient. If the pans of the balance are in equilibrium, then the heavier ball was not placed on the balance.

In the case of $9$ balls, we divide them into $3$ groups of $3$ balls each. By placing one group on each pan of the balance, a single weighing allows us to determine which group contains the heavy ball.

If there are $8$ balls, divide them into three groups as follows: $3, 3$ , and $2$ balls. In this case, the two groups of $3$ balls are placed on the pans of the balance.

Open problem

Consider a list of integers $L$ . Initially, $L$ contains all integers from $1$ to $n$ , each exactly once (later, the list may contain multiple copies of some numbers). The order of elements in $L$ does not matter. You need to perform the following operation $n - 1$ times:

Select two elements from the list, denoted by $x$ and $y$ . They may be equal.
Remove the selected elements from $L$ .
Add the number $x + y + x \cdot y$ to the list.

As a result, the list will contain exactly one number. Find the maximum possible value of this number. Since the answer can be large, print it modulo $1 0^{9} + 7$ .

Input. The first line contains the number of test cases $t$ . Each of the next $t$ lines contains one integer $n (1 \leq n \leq 1 0^{6})$ .

Output. For each test case, print one integer — the maximum possible value of the last number in the list, computed modulo $1 0^{9} + 7$ .

Open problem

First, transform the expression:

x + y + x \cdot y = y \cdot (x + 1) + (x + 1) - 1 = (x + 1) \cdot (y + 1) - 1

Now, the operation can be seen as multiplying two numbers, each increased by $1$ , and then subtracting $1$ .

If we remove the numbers $x$ and $y$ from the list, the following number will be added to the list:

(x + 1) \cdot (y + 1) - 1

Next, remove from the list the numbers $(x + 1) \cdot (y + 1) - 1$ and $z$ . Then the number added to the list will be

((x + 1) \cdot (y + 1) - 1 + 1) \cdot (z + 1) - 1 = (x + 1) \cdot (y + 1) \cdot (z + 1) - 1

Following this analogy, we can conclude that if initially

L = a_{1}, a_{2}, ..., a_{n},

then at the end the remaining number will be

(a_{1} + 1) \cdot (a_{2} + 1) \cdot ... \cdot (a_{n} + 1) - 1

Since initially $L$ contains all integers from $1$ to $n$ , the final number will be

(1 + 1) \cdot (2 + 1) \cdot ... \cdot (n + 1) -1 = (n + 1)! - 1

The resulting number is uniquely determined and does not depend on the order in which the operations are performed.

Open problem

The input numbers are stored in a multiset $s$ (numbers can repeat). The two smallest numbers are always located at the beginning of the multiset.

multiset<long long> s;

Read the number of elements $n$ .

scanf("%lld",&n);

Read the sequence of numbers and add them to the multiset $s$ .

for (i = 0; i < n; i++)
{
  scanf("%lld",&x);
  s.insert(x);
}

The total cost of adding all numbers is computed in the variable $res$ .

res = 0;

While there is more than one number in the multiset $s$ , extract and add the two smallest elements, then add their sum back into $s$ . The cost of adding numbers $a$ and $b$ is $a + b$ , and this cost is added to $res$ .

while (s.size() > 1)
{
  a = *s.begin(); s.erase(s.begin());
  b = *s.begin(); s.erase(s.begin());
  s.insert(a + b);
  res += a + b;
}

When only one number remains in the multiset, print the answer — the value of the variable $res$ .

printf("%lld\n",res);

Algorithm implementation — priority queue

Declare a priority queue $pq$ , where the smallest element is always at the front.

priority_queue<long long, vector<long long>, greater<long long> > pq;

Read the number of elements $n$ .

scanf("%lld",&n);

Read the sequence of numbers and add them to the priority queue $pq$ .

scanf("%lld",&n);
for (i = 0; i < n; i++)
{
  scanf("%lld",&x);
  pq.push(x);
}

The total cost of adding all numbers is computed in the variable $res$ .

res = 0;

While there is more than one number in the priority queue $pq$ , extract and add the two smallest elements, then add their sum back into $pq$ . The cost of adding numbers $a$ and $b$ is $a + b$ , and this cost is added to $res$ .

while (pq.size() > 1)
{
  a = pq.top(); pq.pop();
  b = pq.top(); pq.pop();
  pq.push(a + b);
  res += a + b;
}

When only one number remains in the priority queue, print the answer – the value of the variable $res$ .

printf("%lld\n",res);

Open problem

Declare an array $d p$ , where $d p [i] = 1$ , if Bessie can achieve fullness equal to $i$ .

#define MAX 5000001
int dp[MAX];

Read the input data.

scanf("%d %d %d", &t, &a, &b);

Initialize the knapsack: fullness $0$ can be achieved if nothing is eaten.

dp[0] = 1;

Put oranges in the knapsack.

for (i = a; i <= t; i++)
  if (dp[i - a] == 1) dp[i] = 1;

Put lemons in the knapsack.

for (i = b; i <= t; i++)
  if (dp[i - b] == 1) dp[i] = 1;

Bessie drinks water. If fullness $i$ is achieved, then fullness $i /2$ can also be achieved.

for (i = 1; i <= t; i++)
  if (dp[i] == 1) dp[i / 2] = 1;

Solve the knapsack problem again for oranges and lemons.

for (i = a; i <= t; i++)
  if (dp[i - a] == 1) dp[i] = 1;
for (i = b; i <= t; i++)
  if (dp[i - b] == 1) dp[i] = 1;

Find and print the maximum fullness that Bessie can achieve.

for (i = t; i > 0; i--)
  if (dp[i] == 1) break;
printf("%d\n", i);

In Berland, there are $n$ cities connected by $m$ bidirectional roads. Roads cannot connect a city to itself, and there can be at most one road between any pair of cities. It is not guaranteed that it is possible to travel from any city to any other using only the existing roads.

The mayor of one city, Gadji Ibrahim, decided to reform the road system and instructed the Ministry of Transport to carry out the changes. Under the new plan, every road must become one-way, meaning it will connect two cities in only one direction — from one city to another.

To avoid public dissatisfaction, the reform must be carried out so that the number of isolated cities is minimized. A city is considered isolated if there are no roads entering it (outgoing roads from such a city are allowed).

Help Gadji Ibrahim determine the minimum possible number of isolated cities after the reform.

Input. The first line contains two positive integers $n$ and $m (2 \leq n \leq 1 0^{5}, 1 \leq m \leq 1 0^{5})$ — the number of cities and the number of roads in Berland.

Each of the next $m$ lines describes a road: the $i$ -th road is given by two distinct integers $x_{i}$ and $y_{i} (1 \leq x_{i}, y_{i} \leq n, x_{i} \neq = y_{i})$ — the indices of the cities connected by the $i$ -th road.

It is guaranteed that there is at most one road between any pair of cities. However, it is not guaranteed that one can travel from any city to any other using only the existing roads.

Output. Print one integer — the minimum number of isolated cities after the reform.

Open problem

Consider an undirected graph and identify its connected components. If a connected component is a tree (that is, it contains no cycles), its edges can always be oriented so that exactly one vertex has no incoming edges. This means that in a tree component, the minimum possible number of isolated cities after the reform is $1$ (zero is impossible). For example, the root of the tree can be chosen as the isolated city.

If a connected component contains a cycle, its edges can always be oriented so that every vertex has at least one incoming edge.

The answer to the problem is the number of connected components that do not contain cycles.

Example

Consider the first example. The graph on the left is the initial one, and the graph on the right is the graph after the reform. Vertex $1$ has no incoming edges.

Let's consider the second example. On the left is the original graph, and on the right is the graph after the reform. Each vertex has exactly one incoming edge.

Declare an adjacency list $g$ to store the structure of the graph, as well as an array $u se d$ to mark already visited vertices.

vector<vector<int> > g;
vector<int> used;

The function dfs performs a depth-first search starting from vertex $v$ . The parent of vertex $v$ is vertex $p$ .

void dfs(int v, int p = -1)
{
  used[v] = 1;
  for (int to : g[v])
  {
    if (to == p) continue;

If a cycle is detected in the current connected component, set $f l a g = 0$ .

    if (used[to] == 1) flag = 0;
    else dfs(to, v);
  }
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &m);
g.resize(n + 1);
used.resize(n + 1);

Read $m$ edges and construct the graph.

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

Perform depth-first search on a disconnected graph. The variable $res$ stores the number of connected components that contain no cycles.

res = 0;
for (i = 1; i <= n; i++)
{
  if (used[i] == 0)
  {

Before processing each component, set $f l a g = 1$ . If a cycle is detected during the traversal, then after the dfs call completes, the value of $f l a g$ will become $0$ .

    flag = 1;
    dfs(i);
    res += flag;
  }
}

Print the answer.

printf("%d\n", res);

Open problem

Merge Tree algorithm. In each vertex of the segment tree store an additional array. The vertex corresponding to the fundamental segment $[i; j]$ contains in its array the sorted sequence of numbers $a_{i}, ..., a_{j}$ .

The construction of such a tree takes $O (n l o g_{2} n)$ time, since when combining two child vertices their sorted arrays are merged in the same way as in the merge step of the merge sort algorithm.

To find the number of elements in the segment $[l, r]$ that are less than $x$ , the segment is decomposed into a set of fundamental segments of the segment tree. For each of these segments, a binary search is performed in the corresponding sorted array to determine how many elements are less than $x$ .

Since the segment $[l, r]$ can be decomposed into at most $O (l o g_{2} n)$ fundamental segments, and a binary search in each of them takes $O (l o g_{2} n)$ time, the processing time for a single query is $O (l o g_{2}^{2} n)$ .

Example

Let's declare a segment tree. In each of its nodes, we'll store an array of numbers.

vector<vector<int> > SegTree;

The input numbers are stored in the array $a$ .

vector<int> a;

The function BuildTree constructs the segment tree based on the array $a$ . The sorted array in each node is formed by merging the arrays of its child nodes in $O (n)$ time using the merge function.

void BuildTree(int v, int lpos, int rpos)
{
  if (lpos == rpos)
    SegTree[v].push_back(a[lpos]);
  else
  {
    int mid = (lpos + rpos) / 2;
    BuildTree(2*v, lpos, mid);
    BuildTree(2*v+1, mid+1, rpos);

    SegTree[v].resize(rpos - lpos + 1);
    merge(SegTree[2*v].begin(), SegTree[2*v].end(), 
          SegTree[2*v+1].begin(), SegTree[2*v+1].end(), 
          SegTree[v].begin());
  }
}

The function Query counts the number of elements in the segment $[l, r]$ that are less than $x$ . For each fundamental segment $[l e f t; r i g h t]$ , the number of elements less than $x$ is determined using the $l o w er_b o u n d$ function.

int Query(int v, int lpos, int rpos, int left, int right, int x)
{
  if (left > right) return 0;
  if ((lpos == left) && (rpos == right))
    return lower_bound(SegTree[v].begin(), SegTree[v].end(), x) – 
           SegTree[v].begin();

  int mid = (lpos + rpos) / 2;
  return Query(2*v, lpos, mid, left, min(mid, right), x) +
         Query(2*v+1, mid+1, rpos, max(left, mid+1), right, x);
}

The main part of the program. Read the input array of integers.

scanf("%d",&n);
a.resize(n + 1);
for(i = 1; i <= n; i++)
  scanf("%d",&a[i]);

Build the segment tree based on the array $a$ .

SegTree.resize(4*n);
build(1,1,n);

Process the $q$ queries sequentially.

scanf("%d",&q);
for(i = 0; i < q; i++)
{
  scanf("%d %d %d",&l,&r,&x);
  printf("%d\n",Query(1,1,n,l,r,x));
}

Chip and Dale help all residents of the country iLandia. One day, after successfully completing their latest missions, they decided to go to the cinema. However, they were in for a surprise! There is only one cinema in the country, and it is located in the capital. Chip finished his adventure in city $x$ , and Dale in city $y$ .

There is very little time left before the movie starts, so both of them decided to order a taxi to arrive before the beginning of the film. Since the rewards of our heroes are rather small, each of them wants to keep their travel expenses as low as possible. Chip can join Dale in a taxi and vice versa if they happen to be in the same city. Since taxi drivers in iLandia charge a fixed price per kilometer, the cost of the part of the journey that the heroes travel together is split equally between them.

You are given several scenarios describing where Chip and Dale finish their adventures in different cities. For each scenario, determine the minimal expenses of the heroes so that they can get to the cinema.

Between any pair of cities there exists exactly one path along which it is possible to travel by car. The distance between any two neighboring cities (connected by a direct road) is $1$ kilometer. The capital always has number $1$ .

Input. The first line contains two integers: the number of cities $n (1 \leq n \leq 1 0^{5})$ in the country iLandia and the price $P r i ce (1 \leq P r i ce \leq 1 0^{4})$ per $1$ km of travel.

Each of the next $n - 1$ lines contains two integers $x$ and $y (1 \leq x, y \leq n)$ describing a road between cities $x$ and $y$ . All roads are bidirectional.

The next line contains the number of scenarios $q (1 \leq q \leq 1 0^{5})$ .

Each of the following $q$ scenarios is described by two integers $c$ and $d (1 \leq c, d \leq n)$ — the cities where Chip and Dale finish their adventures, respectively.

Output. For each scenario print two numbers — the expenses of Chip and Dale for traveling to the capital. The answers should be printed with precision of at least $1 0^{- 5}$ .

Open problem

To find the lowest common ancestor (LCA), the binary lifting method is used. The graph is stored as an adjacency list in the array $g$ . The following global arrays are also declared for the LCA algorithm:

$d [v]$ — the time of entry into vertex $v$ during the depth-first search;
$f [v]$ — the time of exit from vertex $v$ during the depth-first search;
$d i s t [v]$ — the distance from the root to vertex $v$ ;
$u p [v] [k]$ — stores the $2^{k}$ -th ancestor of vertex $v$ ;

#define MAX 100010
#define LOGMAX 18
vector<int> g[MAX];
int timer, d[MAX], f[MAX], dist[MAX];
int up[MAX][LOGMAX];

The dfs function performs a depth-first traversal of the tree starting from vertex $v$ . The vertex $p$ is the parent of vertex $v$ . The distance from the capital (vertex numbered $1$ ) to vertex $v$ is $l e n$ ; this value is stored in the array $d i s t [v]$ . During the traversal, the entry and exit timestamps of the vertex are also computed — $d [v]$ и $f [v]$ .

void dfs (int v, int p = 1, int len = 0) 
{
  d[v] = timer++;

Store the immediate parent of vertex $v$ .

  up[v][0] = p;

Store the distance from the root (the capital) to vertex $v$ .

  dist[v] = len;

Build the table of binary ancestors.

  for (int i = 1; i <= l; i++)
    up[v][i] = up[up[v][i-1]][i-1];

From vertex $v$ , all possible transitions to adjacent vertices are considered. For each vertex $t o$ connected to $v$ by the tree edge $(v, t o)$ , the traversal proceeds to that vertex.

  for (int to : g[v])
    if (to != p) dfs (to, v, len + 1);
  f[v] = timer++;
}

The Parent function returns true if vertex $a$ is an ancestor of vertex $b$ .

int Parent(int a, int b)
{
  return (d[a] <= d[b]) && (f[a] >= f[b]);
}

The LCA function computes the lowest common ancestor (LCA) of two vertices $a$ and $b$ in the tree using the binary lifting method and the ancestor table $u p$ .

int LCA (int a, int b) 
{
  if (Parent(a, b)) return a;
  if (Parent(b, a)) return b;
  for (int i = l; i >= 0; i--)
    if (!Parent(up[a][i], b)) a = up[a][i];
  return up[a][0];
}

The main part of the program. Read the input data.

scanf("%d %d",&n,&Price);

Compute the value $l = ⌈ l o g_{2} n ⌉$ .

l = 1;
while ((1 << l) <= n)  l++;

Build an undirected graph that, according to the problem statement, forms a tree.

for(i = 0; i < n - 1; i++)
{
  scanf("%d %d",&x,&y);
  g[x].push_back(y);
  g[y].push_back(x);
}

Run a depth-first search on the tree starting from the capital, where the cinema is located.

dfs(1);

Process the $q$ queries sequentially.

scanf("%d",&q);
for(i = 0; i < q; i++)
{
  scanf("%d %d",&x,&y);
  lca = LCA(x, y);

Before the meeting, Chip travels $d i s t [x] - d i s t [l c a]$ km, and Dale travels $d i s t [y] - d i s t [l c a]$ km. Together they travel exactly $d i s t [l c a]$ km by taxi.

  Chip = dist[x] - dist[lca];
  Deil = dist[y] - dist[lca];

Compute and print the final expenses.

  printf("%.5lf %.5lf\n", (Chip + dist[lca] / 2.0) * Price, 
          (Deil + dist[lca] / 2.0) * Price);
}

Your plane to the ICPC World Finals departs soon, and the only way to reach the airport is by bus. Unfortunately, some drivers are considering going on strike, so you are not sure whether you will arrive on time. Your goal is to plan the trip in such a way as to maximize the probability of catching your flight.

You are given a detailed map of the city showing all bus stations. You are currently at station $0$ , and the airport is located at station $1$ . You have the complete schedule: for each bus you know the departure time from its starting station and the arrival time at its destination. Moreover, for every bus you are given the probability that it will actually operate and that its driver will not go on strike. Assume that all these events are independent. In other words, the probability that a particular bus runs according to the schedule does not depend on whether any other bus is running.

If you arrive at a station strictly before a bus departs, you may try to board it. However, if you arrive exactly at the departure time, you will not have enough time to get on the bus. It is impossible to know in advance whether a bus will operate as scheduled — you will only find out at the moment you attempt to board it. If several buses depart from the station at the same time, you may try to board only one of them.

Consider the schedule shown in the figure. It lists the departure and arrival stations for several routes, as well as their departure and arrival times. Next to some of the routes, the probability that the bus will actually operate is given. For routes where the probability is not specified, it is assumed to be $100%$ .

You may try to take the earliest bus. If it runs, it will bring you directly to the airport, and there is nothing to worry about. Otherwise, the situation becomes more complicated. You can take the second bus to station $2$ . It will certainly depart, but then you will miss the third bus in the list, which would have brought you to the airport in time. The fourth bus you can still catch has a probability of only $0.1$ of operating. This is too risky, so it is better to stay at station $0$ and wait for the fifth bus. If you manage to board it, you can then try to transfer to the sixth bus to the airport; if it does not run, you will still have a chance to return to station $0$ and catch the last bus going directly to the airport.

Input. The first line contains two integers $m (1 \leq m \leq 1 0^{6})$ and $n (2 \leq n \leq 1 0^{6})$ — the number of bus routes and the number of stations in the city. The next line contains one integer $k (1 \leq k \leq 1 0^{18})$ — the time by which you must arrive at the airport.

Each of the following $m$ lines describes one route. Each line contains integers $a$ and $b (0 \leq a, b < n, a \neq = b)$ — the starting and ending stations. Then follow integers $s$ and $t (0 \leq s < t \leq k)$ — the departure time from station $a$ and the arrival time at station $b$ . The last value in the line is a number $p (0 \leq p \leq 1$ , with at most $10$ digits after the decimal point), denoting the probability that the bus will operate according to the schedule.

Output. Print the probability that you will catch your plane if you act optimally. Your answer must have an absolute or relative error of at most $1 0^{- 6}$ .

Open problem

To solve the problem, we use a dynamic programming approach where routes are considered in decreasing order of departure time.

Let's consider the following state:

The passenger is at station $x$ at time $t im e$ .

What is the maximum probability of reaching the airport on time from $x$ under an optimal strategy? We denote this quantity as $b es t (x, t im e)$ . The parameter $t im e$ can take values up to $1 0^{18}$ , so the number of states is effectively infinite. If we are standing at a station waiting, the situation only changes at moments when a bus departs. Therefore, we'll consider only bus departure times.

When we compute $b es t (B, S)$ for a given route, transitions are possible only to states with later times:

If the bus runs, we move to the point $(E, T)$ ,
If the bus does not run, we stay at $(B, S)$ and wait for the next route.

In both cases, the next moment in time is strictly later than the current one. Thus, if we process the routes in decreasing order of departure time, all the necessary future values will already have been computed.

Dynamic Programming Transitions

Consider the following route:

$B \to E$ , departure $S$ , arrival $T$ , probability of running $p$

Then there are two possible actions:

$1$ . We try to take the bus. If the bus runs, the probability of this event is $p$ . In this case, we move to the state $(E, T)$ and then continue acting optimally:

p \cdot b es t (E, n e x t ro u t e > T)

If you arrive exactly at the departure time, there is no time left to board the bus. Therefore, we look for the next departure from station $E$ that is strictly greater than $T$ .

If the bus is canceled, the probability of this event is $1 - p$ . In this case, we remain at station $B$ and wait for the next route:

(1 - p) \cdot b es t (B, n e x t ro u t e > S)

If several buses depart from the station at the same time, you can attempt to board only one of them. If that bus is canceled, you cannot board another bus from station $B$ at time $S$ . You must wait for a route whose departure time is strictly greater than $S$ .

$2$ . We do not try to take the bus at all. In that case, we move to the next bus at the same station:

b es t (B, n e x t ro u t e \geq S)

Thus, the transition has the following form:

b es t (B, S) = ma x (p \cdot b es t (E, n e x t ro u t e > T) + (1 - p) \cdot b es t (B, n e x t ro u t e > S), b es t (B, n e x t ro u t e \geq S))

Example

Sort the routes in the first example by station number and departure time. On the right, list the pairs (departure time, route number) sorted by departure time.

Route number	Departure station	Arrival station	Departure time	Arrival time	Probability	Pair
0	0	1	0	900	0.2	(0, 0)
1	0	2	100	500	1.0	(100, 1)
2	0	3	200	400	0.5	(200, 2)
3	0	1	700	900	0.1	(500, 5)
4	1	1	1001	1001	1.0	(500, 7)
5	2	1	500	700	1.0	(501, 6)
6	2	1	501	701	0.1	(550, 8)
7	3	1	500	800	0.1	(700, 3)
8	3	0	550	650	0.9	(1001, 4)

Compute the probabilities of arriving at the airport in decreasing order of bus route departure times. The notation $t im e^{+}$ denotes a time strictly greater than $t im e$ .

b es t (1, 1001) = 1.0;

b es t (0, 700) = 0.1 \cdot b es t (1, 90 0^{+}) = 0.1 \cdot 1 = 0.1;

b es t (3, 550) = 0.9 \cdot b es t (0, 65 0^{+}) + 0.1 \cdot b es t (3, 55 0^{+}) = 0.9 \cdot 0.1 = 0.09;

b es t (2, 501) = 0.1 \cdot b es t (1, 70 1^{+}) + 0.9 \cdot b es t (2, 50 1^{+}) = 0.1 \cdot 1.0 + 0.9 \cdot 0 = 0.1;

b es t (3, 500) = 0.1 \cdot b es t (1, 80 0^{+}) + 0.9 \cdot b es t (3, 50 0^{+}) = 0.1 \cdot 1.0 + 0.9 \cdot 0.09 = 0.181; b es t (3, 500) = ma x (b es t (3, 500), b es t (3, 550)) = ma x (0.181, 0.09) = 0.181;

b es t (2, 500) = 1.0 \cdot b es t (1, 70 0^{+}) + 0.0 \cdot b es t (2, 50 0^{+}) = 1.0; b es t (2, 500) = ma x (b es t (2, 500), b es t (2, 501)) = ma x (1.0, 0.1) = 1.0;

b es t (0, 200) = 0.5 \cdot b es t (3, 40 0^{+}) + 0.5 \cdot b es t (0, 20 0^{+}) = 0.5 \cdot 0.181 + 0.5 \cdot 0.1 = 0.0905 + 0.05 = 0.1405; b es t (0, 200) = ma x (b es t (0, 200), b es t (0, 700)) = ma x (0.1405, 0.1) = 0.1405;

b es t (0, 100) = 1.0 \cdot b es t (2, 50 0^{+}) + 0.0 \cdot b es t (0, 10 0^{+}) = 1.0 \cdot 0.1 = 0.1; b es t (0, 100) = ma x (b es t (0, 100), b es t (0, 200)) = ma x (0.1405, 0.1) = 0.1405;

b es t (0, 0) = 0.2 \cdot b es t (1, 90 0^{+}) + 0.8 \cdot b es t (0, 0^{+}) = 0.2 \cdot 1.0 + 0.8 \cdot 0.1405 = 0.2 + 0.1124 = 0.3124; b es t (0, 0) = ma x (b es t (0, 0), b es t (0, 100)) = ma x (0.3124, 0.1405) = 0.3124;

Define the structure of a bus route, $R o u t e$ . It contains:

$B$ — the starting station (where the bus departs from);
$E$ — the destination station (where the bus arrives);
$S$ — the departure time from the starting station;
$T$ — the arrival time at the destination station;
$P$ — the probability that the bus will run on the route;
$v a l u e$ — the maximum probability of reaching the airport (station $1$ ) if the journey starts with this bus and the remaining route is chosen optimally.

struct Route
{
  int B, E;
  long long S, T;
  double P, value;

Bus routes are sorted:

by departure time $S$

  bool operator<(const Route& r) const
  {
    return S < r.S;
  }
};

The main part of the program. Read the input data.

scanf("%d %d %lld", &m, &n, &k);

Create a list of all routes grouped by departure station. The vector $v$ has size $n$ , which is the number of stations. Thus,

$v [i]$ contains the list of all bus routes departing from station $i$ .

vector<vector<Route>> v(n);
for (int i = 0; i < m; i++)
{
  scanf("%d %d %lld %lld %lf", &r.B, &r.E, &r.S, &r.T, &r.P);

The maximum probability of reaching the airport from this route is initially unknown, so we initialize it to $0$ .

  r.value = 0.0;

Add route $r$ to the list of routes that start from $r . B$ .

  v[r.B].push_back(r);
}

Now we create a dummy route that represents the moment when the passenger is already at the airport (station $1$ ). Both the starting and ending stations are the airport.

r.B = 1;
r.E = 1;

The probability that this route succeeds is $100%$ .

r.value = 1.0;
r.P = 1.0;

The departure time and arrival time are later than all others.

r.S = k + 1;
r.T = k + 1;

Add this dummy route to the list of routes departing from the airport.

v[1].push_back(r);

For each station $i$ , sort all routes departing from that station $(v [i])$ by departure time $S$ . This is necessary to efficiently find the next route later using $u pp er_b o u n d$ .

for (int i = 0; i < n; i++)
  sort(v[i].begin(), v[i].end());

Create a single processing order for all routes based on departure time so that the dynamic programming can proceed from later routes to earlier ones.

Declare a vector of pairs, $or d$ , which stores for each route:

$1$ . Departure time $S$ .

$2$ . Route indices: $i, j$

$i$ — station number
$j$ — route number in $v [i]$

Thus, each entry in $or d$ indicates: "Route $v [i] [j]$ departs at time $S$ ".

vector<pair<long long, pair<int, int>>> ord;
for (int i = 0; i < v.size(); i++)
  for (int j = 0; j < v[i].size(); j++)
    ord.push_back({ v[i][j].S, {i, j} });

Sort the vector $or d$ in ascending order of departure times for all routes, regardless of the station.

sort(ord.begin(), ord.end());

The variable $re t$ computes the maximum probability of catching the flight when starting from station $0$ at time $0$ .

double ret = 0.0;

Iterate through the routes in decreasing order of departure time, so that for the current route, the value of all future routes (those departing later) has already been computed, allowing us to correctly compute the optimal probability.

for (int itOrd = m; itOrd >= 0; itOrd--)
{

Let us store the departure time of the current route in the variable $s t a r tT im e$ .

  long long startTime = ord[itOrd].first;

$p$ is a pair of indices that allows us to locate the current route in the array of routes $v$ : the route itself is stored in $v [p . f i rs t] [p . seco n d]$ .

  auto p = ord[itOrd].second;

If the departure time $s t a r tT im e > k$ (meaning it is impossible to catch the plane), we simply skip this route.

  if (startTime > k) continue;

$s t$ is the index of the departure station for the current route.

  int st = p.first;

$r$ is the current route for which we compute the $v a l u e$ .

  Route& r = v[p.first][p.second];

Initialize the $v a l u e$ for the current route to zero.

  r.value = 0.0;

$q u ery$ is a temporary object of type $R o u t e$ that is used to find the next route using $u pp er_b o u n d$ . We do not use all its fields — only $B$ and $S$ , which are needed for comparison during the search.

  Route query;

Configure $q u ery$ for the following scenario: we want to find the first bus from the same station that departs strictly later than the current time $S$ , if the current bus is canceled (does not run).

  query.B = r.B;
  query.S = r.S;

We look for the first bus from the same station that departs later.

  auto it = upper_bound(v[st].begin() + p.second, v[st].end(), query);
  if (it != v[st].end())

If such a route exists, increase $r . v a l u e$ by the probability of success through it.

    r.value += (1.0 - r.P) * it->value;

Consider the scenario where the bus actually runs. In this case, at time $T$ we arrive at station $E$ . We prepare the object $q u ery$ to search for the next route. We formulate the query: "Find a bus that departs from station $E$ later than time $T$ ".

  query.B = r.E;
  query.S = r.T;

The variable $d$ stores the index of station $E$ , where we have arrived.

  int d = r.E;

Search for the next bus after arriving at $E$ in the list of routes $v [d]$ using binary search. Its departure time from $E$ must be strictly greater than $T$ , because according to the problem statement, if you arrive exactly at the departure time, you cannot board the bus.

  it = upper_bound(v[d].begin(), v[d].end(), query);
  if (it != v[d].end())

If such a route is found, it means we can transfer to it. Add the contribution of the probability $p \cdot b es t (E, n e x t ro u t e > T)$ .

    r.value += r.P * it->value;

The next option we consider is to skip the current bus. That is, we do not even consider the option of boarding it or not. We wait for the next bus at the same station.

Check if the next bus exists at this station. Recall that the current route $r$ is stored in $v [p . f i rs t] [p . seco n d]$ .

  if (p.second + 1 < v[p.first].size())

If the bus exists and the probability of successfully reaching the airport using it is higher, we update $v a l u e$ . Here:

$r . v a l u e$ is the probability of success if we try to board the current bus;
$v [p . f i rs t] [p . seco n d + 1] . v a l u e$ is the probability of success if we skip the current bus and wait for the next one.

    r.value = max(r.value, v[p.first][p.second + 1].value);

Update the overall answer. We select the best option only among the buses that depart from the initial (zero) station

  if (r.B == 0) ret = max(ret, r.value);
}

Print the answer.

printf("%.6lf\n", ret);

Comments

Nothing yet

Be the first one to start the conversation!

Loading

Just a moment, getting data from the server