Educational Round #4 — Editorial

If $n = 0$ , the answer is $0$ .

If the number of toasts $n$ does not exceed the pan's capacity $k (n \leq k)$ , then toasting all the toasts on both sides will take $4$ minutes.

Since each toast must be toasted on both sides, a total of $⌈ 2 n / k ⌉$ toasting rounds is required. Each toasting round (placing up to $k$ toasts on the pan at the same time) takes $2$ minutes.

Therefore, if $n > k$ , the minimum time required to toast all the toasts is $2 \cdot ⌈ 2 n / k ⌉$ minutes.

Example

Suppose there are $n = 3$ toasts, and the pan can hold $k = 2$ toasts at a time. Let us label the sides of the toasts as $1 a, 1 b, 2 a, 2 b, 3 a, 3 b$ .

Then all $6$ sides can be toasted in $6$ minutes as follows:

First toasting: $1 a$ and $2 a - 2$ minutes;
Second toasting: $1 b$ and $3 a - 2$ minutes;
Third toasting: $2 b$ and $3 b - 2$ minutes;

Total: $3$ toasting rounds of $2$ minutes each, which makes $6$ minutes.

Open problem

Agent Johnny English is back in action!

This time, the fearless agent and his assistant Bof have been tasked with maintaining order at a charity event. Upon entering the hall and surveying the scene, English realized that to get a complete picture of what was happening, he would need to take a stroll around the room, chat with the guests, and observe the waiters. After completing his reconnaissance, English, confident in his success, decided to meet up with Bof and impress him with his incredible analytical skills. Unfortunately, poor Bof completely loses his way at social events, so he just slowly follows the instructions of the senior agent.

The hall is a square on the coordinate plane with sides of length $1 0^{6}$ , parallel to the coordinate axes. The entrance is located in the lower left corner of the square, at point $O (0, 0)$ . Agent English plans to select several guests positioned at points with integer coordinates and greet each of them in turn. He will not greet the same guest consecutively, but he might occasionally make a mistake and return to a guest he has already greeted. The trained agent moves at a speed of $p$ and greets guests instantly. Meanwhile, Bof, moving at a speed of $q$ , is heading directly to the final point of the route planned by English.

To avoid raising suspicions, Agent English wants to find a route where he and Bof will arrive at the meeting point simultaneously. Unfortunately, the agent does not have time to think through the details of his brilliant plan, so it is up to you to handle that.

Given the speeds $q$ and $p$ , find any route that starts at point $(0, 0)$ and consists of points with non-negative coordinates not exceeding $1 0^{6}$ . Moreover, the time taken to traverse the route at speed $q$ must equal the time taken to traverse the same route at speed $p$ .

Input. Two positive integers $q$ and $p (1 \leq q \leq p \leq 1 0^{5})$ — the speeds of Bof and Agent English, respectively.

Output. In the first line, print the number $n (2 \leq n \leq 100)$ of points in the route. In the following $n$ lines, print pairs of integers $x$ and $y (0 \leq x, y \leq 1 0^{6})$ — the coordinates of the points in the order of traversal. The first point must be $(0, 0)$ . Points may repeat, but there must not be two identical points in a row.

Open problem

Johnny English and Bof reach the final point simultaneously in time $t$ . Johnny English covers a distance $s_{1} = p \cdot t$ , while Bof covers a distance $s_{2} = q \cdot t$ . The ratio of the distances traveled is equal to the ratio of the speeds: $s_{1} / s_{2} = p / q$ .

Let's construct such paths constructively. For example, consider a route consisting of $4$ points: $(0, 0) \to (2 q, 0) \to (2 q, p - q) \to (2 q, 0)$ . Here, the coordinate $p - q$ is chosen to ensure that its value is non-negative (according to the problem's conditions, $q \leq p$ ).

The length of Johnny English's path is $2 q + 2 * (p - q) = 2 p$ .
The length of Bof's path is $2 q$ .

If the speeds of Johnny English and Bof are the same, then the points $(2 q, 0)$ and $(2 q, p - q)$ coincide, and according to the problem's conditions, there cannot be two identical points in a row on the route. In this case, as a solution, one could choose, for example, the following route: $(0, 0) \to (1, 0)$ .

Farmer John is not good at multitasking. He often gets distracted, which makes it difficult for him to work on long-term projects. Right now, he is trying to paint one side of his barn but constantly gets distracted by tending to his cows. As a result, some parts of the wall end up with multiple layers of paint, while others remain less covered.

The side of the barn can be represented as a two-dimensional plane of size $x \times y$ , where Farmer John sequentially applies paint in the form of $n$ rectangular areas with sides parallel to the coordinate axes. Each rectangle is defined by the coordinates of its bottom-left and top-right corners.

Farmer John wants to achieve an even coating of the wall so that he does not have to repaint it anytime soon. However, he also does not want to waste extra paint. The optimal number of layers is considered to be $k$ . Your task is to determine the area of the wall that is covered with exactly $k$ layers of paint after all rectangles have been applied.

Input. The first line contains two integers $n$ and $k (1 \leq k \leq n \leq 1 0^{5})$ — the number of rectangles and the required number of paint layers.

Each of the following $n$ lines contains four integers $x_{1}, y_{1}, x_{2}, y_{2}$ , defining a rectangle with its bottom-left corner at $(x_{1}, y_{1})$ and top-right corner at $(x_{2}, y_{2})$ .

All coordinates $x$ and $y$ are in the range from $0$ to $1000$ . All given rectangles have a positive area.

Output. Print one integer — the area of the wall covered with exactly $k$ layers of paint.

Open problem

First, let's consider the one-dimensional version of the problem. Suppose we have $n$ segments $[a_{i}, b_{i}]$ on a number line, where $0 \leq a_{i}, b_{i} \leq 1000$ . The goal is to determine how many segments cover each integer on this line.

We declare an integer array dp and initialize it with zeros. Then, for each segment $[a_{i}, b_{i}]$ , perform two operations:

d p [a_{i}] + +; d p [b_{i} + 1] - -;

Next, compute the prefix sums of the $d p$ array. The value of $d p [i]$ represents the number of segments that cover the number $i$ .

For example, consider the following set of segments: $[3; 7], [6; 9], [1; 4], [3; 8], [2; 5]$ . Initialize the $d p$ array:

For each segment $[a_{i}, b_{i}]$ , perform the following two operations: $d p [a_{i}] + +; d p [b_{i} + 1] - -$ .

Now let's consider the two-dimensional version of the problem. Suppose we have $n$ rectangles on a plane, each defined by coordinates $(x_{1}, y_{1}) - (x_{2}, y_{2}) (0 \leq x_{1}, y_{1}, x_{2}, y_{2} \leq 1000)$ . The goal is to determine how many rectangles cover each cell of the plane.

Declare a two-dimensional integer array $d p$ and initialize it with zeros. Then, for each rectangle $(x_{1}, y_{1}) - (x_{2}, y_{2})$ , perform the following four operations:

d p [x_{1}] [y_{1}] + +; d p [x_{1}] [y_{2} + 1] - -; d p [x_{2} + 1] [y_{1}] - -; d p [x_{2} + 1] [y_{2} + 1] + +;

After that, compute the prefix sums in the $d p$ array. The value of $d p [i] [j]$ represents the number of rectangles that contain the cell $(i, j)$ .

For example, consider the rectangle $(2, 2) - (4, 5)$ .

Example

Let's consider the given example containing three rectangles.

$8$ squares are covered with exactly $2$ layers of paint.

A string partition is called a palindromic partition if every substring in this partition is a palindrome. For example, the string "ababbbabbababa" can be partitioned as "aba|b|bbabb|a|b|aba" — this is an example of a palindromic partition.

Determine the minimum number of cuts required for the palindromic partitioning of a given string. For example:

for the string " $ababbbabbababa$ " a minimum of $3$ cuts are needed to create the partition " $a ∣ babbbab ∣ b ∣ ababa$ ";
if the string is already a palindrome, $0$ cuts are needed;
if all the characters of a string of length $n$ are different, the minimum number of cuts required is $n - 1$ .

Input. One string $s$ of length no more than $1000$ .

Output. Print the minimum number of cuts needed for the palindromic partitioning of the string $s$ .

Open problem

Let $s$ be the input string. The substring $s_{i} ... s_{j}$ is a palindrome if one of the following conditions is satisfied:

$i \geq j$ (the substring is empty or consists of a single character);
$s_{i} = s_{j}$ and the substring $s_{i + 1} ... s_{j - 1}$ is a palindrome;

Let the function $I s P a l (i, j)$ return $1$ if $s_{i} ... s_{j}$ is a palindrome, and $0$ otherwise. The values of $I s P a l (i, j)$ are stored in the cells $p a l [i] [j]$ .

Let the function $f (i, j)$ return the minimum number of cuts required to partition the substring $s_{i} ... s_{j}$ into palindromes. The values of this function will be stored in the cells of the array $d p [i] [j]$ . Therefore, the solution to the problem will be $f (0, s . s i ze () - 1)$ .

Note that $f (i, i) = 0$ , as a string consisting of a single character is already a palindrome.

To compute $f (i, j)$ , cut the substring $s_{i} ... s_{j}$ into two parts: $s_{i} ... s_{k}$ and $s_{k + 1} ... s_{j} (i \leq k < j)$ . Recursively solve the problems on the strings $s_{i} ... s_{k}$ and $s_{k + 1} ... s_{j}$ . Look for the value of $k (i \leq k < j)$ that minimizes the sum $f (i, k) + f (k + 1, j) + 1$ . The term $+ 1$ in the sum represents the single cut made between the characters $s_{k}$ and $s_{k + 1}$ . Thus, we obtain the following recurrence relation:

f (i, j) = i \leq k < j min (f (i, k) + f (k + 1, j) + 1)

Example

For example, for the string " $abab cc b$ " consisting of $7$ characters, we have:

f (1, 7) = 1 \leq k < 7 min (f (1, k) + f (k + 1, 7) + 1)

The sum takes its minimum value at $k = 3$ :

f (1, 7) = f (1, 3) + f (4, 7) + 1 = 0 + 0 + 1 = 1

Since the substrings " $aba$ " and " $b cc b$ " are palindromes, $f (1, 3) = f (4, 7) = 0$ .

Define the constants, the input string $s$ , and the arrays.

#define MAX 1001
#define INF 0x3F3F3F3F
int dp[MAX][MAX], pal[MAX][MAX];
string s;

The function $I s P a l (i, j)$ checks whether the substring $s_{i} ... s_{j}$ is a palindrome. The substring $s_{i} ... s_{j}$ is a palindrome if $s_{i} = s_{j}$ and $s_{i + 1} ... s_{j - 1}$ is a palindrome. The values of $I s P a l (i, j)$ are stored in the cells of the array $p a l [i] [j]$ .

int IsPal(int i, int j)
{
  if (i >= j) return pal[i][j] = 1;
  if (pal[i][j] != -1) return pal[i][j];
  return pal[i][j] = (s[i] == s[j]) && IsPal(i + 1, j - 1);
}

The function $f (i, j)$ returns the minimum number of cuts required to partition the substring $s_{i} ... s_{j}$ into palindromes.

int f(int i, int j)
{

If $i = j$ , the substring $s_{i} ... s_{j}$ consists of a single character, and no cuts are needed. If $i > j$ , the substring $s_{i} ... s_{j}$ is considered empty, and no cuts are required.

  if (i >= j) return 0;

If the value $f (i, j)$ is already computed, return the stored value from the $d p [i] [j]$ .

  if (dp[i][j] != INF) return dp[i][j];

If the substring $s_{i} ... s_{j} (i < j)$ is a palindrome, there is no need to make any cuts. In this case, the minimum number of cuts is $0$ .

  if (IsPal(i, j)) return dp[i][j] = 0;

Cut the substring $s_{i} ... s_{j}$ into two parts: $s_{i} ... s_{k} (i \leq k)$ and $s_{k + 1} ... s_{j} (k + 1 \leq j)$ . Then, recursively solve the problems for both parts: $s_{i} ... s_{k}$ and $s_{k + 1} ... s_{j}$ . Find the value of $k (i \leq k < j)$ for which the sum $f (i, k) + f (k + 1, j) + 1$ is minimized.

  for (int k = i; k < j; k++)
    dp[i][j] = min(dp[i][j], f(i, k) + f(k + 1, j) + 1);

Return the answer $d p [i] [j] = f (i, j)$ .

  return dp[i][j];
}

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

cin >> s;

Initialize the arrays.

memset(dp, 0x3F, sizeof(dp));
memset(pal, -1, sizeof(pal));

Compute and print the answer.

res = f(0, s.size() - 1);
cout << res << endl;

You are given $n$ buildings with heights $h_{1}, h_{2}, \dots, h_{n}$ . Your task is to make all buildings have the same height. You are allowed to either remove bricks from buildings or add bricks to them. Adding or removing one brick has a certain cost, which is specified individually for each building.

Find the minimum total reconstruction cost required to make all buildings have the same height $k$ (where $k$ is any non-negative integer), that is, to satisfy the condition $h_{1} = h_{2} = \dots = h_{n} = k$ .

For simplicity, assume that each building is a vertical column made of identical bricks.

Input. The first line contains a single integer $n (n \leq 1 0^{5})$ — the number of buildings.

The second line contains $n$ integers — the heights of the buildings $h_{1}, h_{2}, \dots, h_{n} (0 \leq h_{i} \leq 1 0^{4})$ .

The third line contains $n$ integers $c_{1}, c_{2}, \dots, c_{n} (0 \leq c_{i} \leq 1 0^{4})$ — the cost of adding or removing one brick for the corresponding building.

Output. Print a single integer — the minimum total cost required to make all buildings have the same height.

Open problem

Sort the buildings by height so that $h_{1} \leq h_{2} \leq ... \leq h_{n}$ . Buildings with the same heights are sorted by increasing cost of adding / removing.

Find the cost for which we can make the height of all houses equal to $h_{x} (1 \leq x \leq n)$ . It is equal

f (x) = i = 1 \sum n ∣ h_{i} - h_{x} ∣ \cdot c_{i}

The function $f (x)$ is concave and has a global minimum, that can be found with a ternary search.

Example

Consider the first example. Sort buildings by height:

Find the value of the function $f (x)$ for all heights:

$f (1) = (1 - 1) \cdot 30 + (2 - 1) \cdot 10 + (3 - 1) \cdot 20 + (4 - 1) \cdot 40 = 170$ ,
$f (2) = (2 - 1) \cdot 30 + (2 - 2) \cdot 10 + (3 - 2) \cdot 20 + (4 - 2) \cdot 40 = 130$ ,
$f (3) = (3 - 1) \cdot 30 + (3 - 2) \cdot 10 + (3 - 3) \cdot 20 + (4 - 3) \cdot 40 = 110$ ,
$f (4) = (4 - 1) \cdot 30 + (4 - 2) \cdot 10 + (4 - 3) \cdot 20 + (4 - 4) \cdot 40 = 130$

The minimum of the function $f (x)$ is achieved at $x = 3$ , while $f (3) = 110$ .

Each building has a height $h$ and the cost $cos t$ of adding or removing a floor. The information about all buildings is stored in the array $b$ .

#define MAX 100001
struct Building
{
  int h, cost;
};
Building b[MAX];

The function cmp is a comparator for sorting buildings. Buildings are sorted by increasing height. If the heights of the buildings are the same, then sort them by increasing cost.

int cmp(Building a, Building b)
{
  if (a.h == b.h)
    return a.cost < b.cost;
  return a.h < b.h;
}

The function f computes the cost to make all buildings equal to the height of the building number $x$ .

long long f(int x)
{
  long long ret = 0;
  for (int i = 1; i <= n; i++)
    ret += 1LL * abs(b[x].h - b[i].h) * b[i].cost;
  return ret;
}

The function ternary_search uses the ternary search to find the value of $x \in [l e f t; r i g h t]$ for which $f (x)$ is minimal. Initially, the search range is $[l e f t; r i g h t] = [1; n]$ .

long long ternarySearch(int left, int right)
{
  while (right - left >= 3)
  {
    int a = left + (right - left) / 3;
    int b = left + 2 * (right - left) / 3;
    if (f(a) > f(b))
      left = a;
    else
     right = b;
  }

The difference between $l e f t$ and $r i g h t$ does not exceed $3$ . In this case, the minimum of $f (x)$ on the interval $[l e f t; r i g h t]$ is found by exhaustive search.

  long long res = f(left++);
  while (left <= right)
    res = min(res, f(left++));
  return res;
}

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

scanf("%d", &n);
for (i = 1; i <= n; i++)
  scanf("%d", &b[i].h);
for (i = 1; i <= n; i++)
  scanf("%d", &b[i].cost);

Sort the buildings.

sort(b + 1, b + n + 1, cmp);

Find and print the answer. Buildings are numbered from $1$ to $n$ .

printf("%lld\n", ternarySearch(1, n));

Dominoes can inspire a variety of entertaining activities. For example, children enjoy arranging domino tiles in a line, placing them side by side. If you push one tile, it falls and knocks down the next one, which in turn knocks down the following one, and so on, until the chain reaction stops. However, there might be setups where not all tiles fall. In such cases, you need to push an additional tile to keep the chain reaction going.

Given a specific arrangement of dominoes, determine the minimum number of tiles that need to be pushed by hand to make all the dominoes fall.

Input. The first line contains two integers $n$ and $m (1 \leq n, m \leq 1 0^{5})$ , where $n$ is the number of domino tiles, and $m$ is the number of lines describing their interactions. The dominoes are numbered from $1$ to $n$ .

Each of the following $m$ lines contains two integers $x$ and $y$ , indicating that if the domino numbered $x$ falls, it will knock over the domino numbered $y$ .

Output. Print one integer — the minimum number of domino tiles that need to be pushed to make all the dominoes fall.

Open problem

Let us consider the problem of finding strongly connected components in a directed graph. Each vertex in one strongly connected component will be assigned the same color. Let $co l or [i]$ denote the color of the $i$ -th vertex. The number of distinct colors will equal the number of strongly connected components.

It is obvious that if one domino tile is pushed, all tiles belonging to the same strongly connected component will inevitably fall. Let $c n t$ represent the number of strongly connected components.

We'll define an array $u se d$ of length $c n t$ , where $u se d [i] = 1$ if it is necessary to push a domino in the $i$ -th component. Now, let us determine for which values of $u se d [i]$ we should set it to $0$ .

Iterate through all edges of the graph. We are interested only in the edges that connect different strongly connected components. If such an edge is of the form $i \to j$ (where $co l or [i] \neq = co l or [j]$ ), then set $u se d [co l or [j]] = 0$ . This means there is no need to push a domino from the component with color $co l or [j]$ , because by pushing a domino from the component with color $co l or [i]$ , we'll guaranteedly topple all dominoes in the component with color $co l or [j]$ .

After processing all edges, count the number of ones in the array $u se d$ . This will be the minimum number of domino tiles that need to be pushed.

Example

The graphs from the examples have the following form:

In the first example, it is enough to push domino number $1$ .
In the second example, it is necessary to push dominoes numbered $1$ and $5$ .

The graph in the first example has $3$ strongly connected components.

Since there is an edge $(1, 2)$ , there is no need to push domino number $2$ ;
Since there is an edge $(2, 3)$ , there is no need to push domino number $3$ ;

The input graph is stored in the adjacency list $g$ .

The reverse graph (a graph where all edge directions are reversed) is stored in the adjacency list $g r$ .

vector<vector<int> > g, gr;
vector<int> used, top, color;

The function dfs1 performs a depth-first search on the input graph. Vertices are added to the array $t o p$ in the order of their processing completion during the dfs.

void dfs1(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (!used[to]) dfs1(to);
  top.push_back(v);
}

The function dfs2 performs a depth-first search on the reverse graph. All vertices visited during a recursive call of $df s 2$ belong to the same strongly connected component. Each of these vertices is assigned the color $c$ .

void dfs2(int v, int c)
{
  color[v] = c;
  for (int to : gr[v])
    if (color[to] == -1) dfs2(to, c);
}

The main part of the program. Read the input data. Construct the reverse graph.

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

Prform a depth-first search on the input graph, storing the order in which vertices finish processing in the array $t o p$ .

used.resize(n+1);
for(i = 1; i <= n; i++)
  if (!used[i]) dfs1(i);

Next, perform a depth-first search on the reverse graph. The vertices of the reverse graph are processed in the order they appear in the array $t o p$ , starting from the end (right to left). Vertices belonging to the same strongly connected component are assigned the same color. The current color used for coloring is stored in the variable $c$ .

For convenience in further processing, we reverse the array $t o p$ , allowing us to process its vertices from left to right.

color.assign(n+1,-1);
reverse(top.begin(), top.end());
c = 0;
for (int v : top)
  if (color[v] == -1) dfs2(v, c++);

The variable $c$ contains the number of strongly connected components.

used.assign(c,1);
for (i = 1; i < g.size(); i++)
  for (int to : g[i])

Iterate through all edges of the graph $(i, t o)$ . Check whether the vertices $i$ and $t o$ belong to different strongly connected components. This is true if they are colored with different colors. In such a case, if we push any domino from the strongly connected component to which vertex $i$ belongs, domino $t o$ will inevitably fall as well. This means there is no need to push a domino of color $co l or [t o]$ . Therefore, set $u se d [co l or [t o]] = 0$ .

    if (color[i] != color[to]) used[color[to]] = 0;

The variable $c$ keeps track of the number of dominoes that need to be pushed. If for any color $i$ , the condition $u se d [i] = 1$ holds, it means that no domino of color $i$ will fall regardless of which domino of another color is pushed. In this case, it will be necessary to push at least one domino of color $i$ .

c = 0;
for(i = 0; i < used.size(); i++)
  if (used[i]) c++;

Print the answer.

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

Open problem

Let's declare the adjacency list of the graph $g$ .

vector<vector<int> > g;

The function dfs performs a depth-first search starting from vertex $v$ . We topologically sort the vertices of the graph and store them in the array $t o p$ .

void dfs(int v)
{
  used[v] = 1;
  for (int to : g[v])
    if (used[to] == 0) dfs(to);
  top.push_back(v);
}

The main part of the program. Read the input data. Bild the adjacency list of the directed graph.

scanf("%d %d", &n, &m);
g.resize(n + 1);
while (m--)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
}

Run a depth-first search on the disconnected graph.

used.resize(n + 1);
for (i = 1; i <= n; i++)
  if (used[i] == 0) dfs(i);

Iterate over the vertices of the graph in the order opposite to their topological sort, that is, we iterate over the vertices in the $t o p$ array from left to right.

dp.resize(n + 1);
for (int u : top)
{

A path from vertex $u$ to itself has length $0$ (initialization).

  dp[u] = 0;

Iterate over the vertices $v$ adjacent to $u$ . Consider the edge $(u, v)$ .

  for (int v : g[u])

For all such vertices $v$ , find the maximum among the values $d p [v] + 1$ .

    dp[u] = max(dp[u], dp[v] + 1);
}

Find and print the largest element in the $d p$ array. It corresponds to the length of the longest path in the graph.

res = *max_element(dp.begin(), dp.end());
printf("%d\n", res);

Open problem

Let's create $26$ segment trees for sums computation — one for each letter from ' $a$ ' to ' $z$ '. Each tree must support multiple updates.

For example, for the letter ' $a$ ' and the string " $aba c d ab c d a$ ", the corresponding segment tree would look like this:

Using such a tree, we can determine in logarithmic time how many times a given letter occurs in the range $[l; r]$ .

Processing a query on the range $[l; r]$ reduces to counting sort. First, in the array $c n t$ , we count how many times each letter occurs within this range.

Then, depending on the value of $k$ , we "reconstruct" this section of the string:

if $k = 1$ , the characters are arranged in non-decreasing order — that is, from ' $a$ ' to ' $z$ ';
if $k = 0$ , they are arranged in non-increasing order — from ' $z$ ' to ' $a$ '.

To do this, for the entire range $[l; r]$ , for each letter ' $a$ ' + $j$ , whose count is known from the cnt array, we set the corresponding number of ones in the segment tree, starting from position $l$ (if sorting in ascending order) or from position $r$ (if sorting in descending order).

For example, suppose the substring " $a c b d b c ab$ " occupies positions $[10; 17]$ . Let's count the number of occurrences of each letter in this range:

The letter ' $a$ ' occurs $2$ times;
The letter ' $b$ ' occurs $3$ times;
The letter ' $c$ ' occurs $2$ times;
The letter ' $d$ ' occurs $1$ time;

To sort the letters in the range in ascending order, we first need to reset the values to 0 in the segment tree of each letter over the interval $[10; 17]$ , and then perform the following operations:

For the letter ' $a$ ' set each element in the range $[10; 11]$ to $1$ ;
For the letter ' $b$ ' set each element in the range $[12; 14]$ to $1$ ;
For the letter ' $c$ ' set each element in the range $[15; 16]$ to $1$ ;
For the letter ' $d$ ' set each element in the range $[17; 17]$ to $1$ ;

Such "updates" to the segment trees effectively simulate the permutation of characters over the desired range without directly modifying the string itself.

After processing all queries, the final string is reconstructed from the contents of the $26$ segment trees: for each letter, its tree is traversed sequentially, and at positions where the value equals $1$ , the corresponding character is written into the resulting string.

For each letter from ' $a$ ' to ' $z$ ', we create a separate segment tree. Thus, there are $A L P H A BET = 26$ trees in total, each supporting sum queries and multiple updates.

#define MAX 100010
#define ALPHABET 26
struct node
{
  int sum, add;
} SegTree[4*MAX][ALPHABET];

Declare an array to count the number of occurrences of each letter.

int cnt[ALPHABET];

Build $26$ segment trees based on the string $s$ — one for each letter of the Latin alphabet.

void build(int v, int lpos, int rpos)
{
  if (lpos == rpos)
  {
    SegTree[v][s[lpos] - 'a'].sum = 1;
    for (int i = 0; i < ALPHABET; i++)
      SegTree[v][i].add = -1;
  }
  else
  {
    int mid = (lpos + rpos) / 2;
    build(v * 2, lpos, mid);
    build(v * 2 + 1, mid + 1, rpos);
    for (int i = 0; i < ALPHABET; i++)
    {
      SegTree[v][i].sum = 
             SegTree[v * 2][i].sum + SegTree[v * 2 + 1][i].sum;
      SegTree[v][i].add = -1;
    }
  }
}

The vertex $v$ corresponds to the segment $[lp os, r p os]$ , with $mi d = (lp os + r p os) /2$ . Perform a push operation for this vertex in the segment tree with index $v er$ .

void Push(int v, int lpos, int mid, int rpos, int ver)
{
  if (SegTree[v][ver].add != -1)
  {
    SegTree[2 * v][ver].add = SegTree[v][ver].add;
    SegTree[2 * v][ver].sum = (mid - lpos + 1) * SegTree[v][ver].add;
    SegTree[2 * v + 1][ver].add = SegTree[v][ver].add;
    SegTree[2 * v + 1][ver].sum = (rpos - mid) * SegTree[v][ver].add;
    SegTree[v][ver].add = -1;
  }
}

The vertex $v$ corresponds to the segment $[lp os, r p os]$ . In the segment tree with index $v er$ , set the value $v a l$ for all elements with indices from $l e f t$ to $r i g h t$ .

void SetValue(int v, int lpos, int rpos, int left, int right, 
              int val, int ver)
{
  if (left > right) return;
  if ((lpos == left) && (rpos == right))
  {
    SegTree[v][ver].add = val;
    SegTree[v][ver].sum = (right - left + 1) * val;
    return;
  }

  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos, ver);

  SetValue(2 * v, lpos, mid, left, min(mid, right), val, ver);
  SetValue(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right, 
           val, ver);

  SegTree[v][ver].sum = 
         SegTree[2 * v][ver].sum + SegTree[2 * v + 1][ver].sum;
}

The vertex $v$ corresponds to the segment $[lp os, r p os]$ . Find the sum of elements in the range $[l e f t; r i g h t]$ in the segment tree with index $v er$ .

int Summa(int v, int lpos, int rpos, int left, int right, int ver)
{
  if (left > right) return 0;
  if ((lpos == left) && (rpos == right)) return SegTree[v][ver].sum;

  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos, ver);

  return Summa(2 * v, lpos, mid, left, min(mid, right), ver) +
    Summa(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right, ver);
}

Perform a push operation on all vertices of the segment tree with index $v er$ . Then, insert the letter $v er$ + ' $a$ ' into all positions of the string $s$ where its value in the segment tree $v er$ equals $1$ .

void get(int v, int lpos, int rpos, int ver)
{
  if (SegTree[v][ver].sum == 0) return;
  if (lpos == rpos)
  {
    s[lpos] = ver + 'a';
    return;
  }

  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos, ver);

  get(2 * v, lpos, mid, ver);
  get(2 * v + 1, mid + 1, rpos, ver);
}

The main part of the program. Read the input data. Based on the input string $s$ , build $26$ segment trees — one for each letter of the Latin alphabet.

cin >> n >> q;
cin >> s;
s = " " + s;
build(1,1,n);

Process $q$ queries sequentially.

for (i = 0; i < q; i++)
{
  cin >> l >> r >> command;

Perform a counting sort of all letters in the range $[l; r]$ . To do this, first count the number of occurrences of each letter ' $a$ ' + $j$ in this interval and store the result in $c n t [j]$ .

  for (j = 0; j < ALPHABET; j++)
    cnt[j] = Summa(1, 1, n, l, r, j);

Then, starting from position $p os$ , we'll move to the right or to the left depending on the value of the variable $co mman d$ .

  pos = (command == 1) ? l : r;
  for (j = 0; j < ALPHABET; j++)
  {
    if (!cnt[j]) continue;
    SetValue(1, 1, n, l, r, 0, j);
    if (command)
    {
      SetValue(1, 1, n, pos, pos + cnt[j] - 1, 1, j);
      pos += cnt[j];
    }
    else
    {
      SetValue(1, 1, n, pos - cnt[j] + 1, pos, 1, j);
      pos -= cnt[j];
    }
  }
}

The generation of the resulting string is performed based on the contents of the segment trees. The function $g e t (1, 1, n, i)$ , using the data from the $i$ -th segment tree, places all letters ' $a$ ' + $i$ at their corresponding positions in the string $s$ . The get function performs a complete push, traversing all vertices of the segment tree in $O (n)$ time.

for (i = 0; i < ALPHABET; i++)
  get(1, 1, n, i);

Print the resulting string.

cout << s.substr(1);

The metro system consists of $n$ stations located on $l$ lines. Each station belongs to one or several lines (in this case, a passenger can transfer to any of the lines passing through this station). Each line includes at least two stations and intersects with at least one other line. The metro network is connected.

Travel between two adjacent stations on the same line is possible in both directions and takes $2$ minutes. A transfer from one line to another within the same station takes $1$ minute. Other time costs can be neglected.

Determine the minimum time required for the manager of the company “Diez-Product” to travel from station $a$ to the company’s office located near station $b$ .

Input. The first line contains two positive integers $n$ and $l$ ( $1 \leq l \leq 10$ ). Each of the next $l$ lines lists the consecutive station numbers of each metro line. The last line contains the numbers and line indices of the starting and destination stations. All numbers are positive and do not exceed $70$ .

Output. Print the minimum travel time between the specified stations.

Examples. In the given example, it is required to find the shortest route from station $2$ on line $1$ to station $7$ on line $3$ .

Move along line $1$ from station $2$ to station $1$ : $2$ minutes.
Transfer at station $1$ from line $1$ to line $2$ : $1$ minute.
Move along line $2$ from station $1$ to station $5$ : $4$ minutes.
Transfer at station $5$ from line $2$ to line $3$ : $1$ minute.
Move along line $3$ from station $5$ to station $7$ : $2$ minutes.

Thus, the entire trip takes $2 + 1 + 4 + 1 + 2 = 10$ minutes.

Open problem

The shortest distance from the source to a vertex $v$ belonging to line $l$ is stored in $d i s t [v] [l]$ , where $1 \leq v \leq 70$ and $1 \leq l \leq 10$ . The graph is represented as an adjacency list. For each edge, in addition to its direction and cost, the number of the metro line to which the destination vertex belongs is also stored.

The algorithm starts from station $s$ , located on line $l in e 1$ . The goal is to find the minimum travel cost required to reach station $f$ , which lies on line $l in e 2$ .

When moving between vertices, it is necessary to check whether they belong to the same line: if the lines differ, an additional cost of $1$ is added (representing a line transfer).

Using Dijkstra's algorithm, we find the shortest distance from state $(s, l in e 1)$ to state $(f, l in e 2)$ .

Example

In the given example, it is required to find the shortest route from station $2$ on line $1$ to station $7$ on line $3$ .

Move along line $1$ from station $2$ to station $1$ : $2$ minutes.
Transfer at station $1$ from line $1$ to line $2$ : $1$ minute.
Move along line $2$ from station $1$ to station $5$ : $4$ minutes.
Transfer at station $5$ from line $2$ to line $3$ : $1$ minute.
Move along line $3$ from station $5$ to station $7$ : $2$ minutes.

Thus, the entire trip takes $10$ minutes.

The number of vertices in the graph does not exceed $M A X = 71$ . The number of metro lines does not exceed $L I NES = 11$ .

#define MAX 71
#define LINES 11

The shortest distance from the source to a vertex $v$ belonging to line $l$ is stored in $d i s t [v] [l]$ . We declare an array to store the shortest distances.

int dist[MAX][LINES];

The structure node contains information about an edge:

$t o$ is the destination vertex;
$cos t$ is the cost of the edge;
$l in e$ is the metro line to which the edge belongs;

struct node
{
  int to, cost, line;
  node(int to, int cost, int line) : to(to), cost(cost), line(line) {}
};

The node structure is also used in the priority queue, where:

$t o$ is the current vertex;
$cos t$ is the minimum travel cost to reach vertex $t o$ (on line $l in e$ );
$l in e$ is the metro line number on which vertex $t o$ is located.

In the priority queue, vertices are ordered by increasing travel cost.

bool operator< (node a, node b)
{
  return a.cost > b.cost;
}

Declare an adjacency list to represent the graph.

vector<vector<node> > g;

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

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

Read the $i$ -th metro line. The travel time between two consecutive stations $u$ and $v$ is $2$ .

for (i = 1; i <= l; i++)
{

Read station $u$ — the first station of the $i$ -th metro line. The next station after $u$ is $v$ .

  scanf("%d ", &u);
  while (scanf("%d%c", &v, &ch))
  {

Movement between stations is possible in both directions, and the cost of each edge is $2$ .

    g[u].push_back(node(v, 2, i));
    g[v].push_back(node(u, 2, i));
    u = v;

Once the end of the line description is reached, we stop reading data for the current metro line.

    if (ch == '\n') break;
  }
}

Initialize the array for storing the shortest distances.

for (i = 1; i <= n; i++)
for (j = 1; j <= l; j++)
  dist[i][j] = 2000000000;

Read the information about the starting and destination stations. For each station, the metro line it belongs to is specified.

scanf("%d %d %d %d", &s, &line1, &f, &line2);

The algorithm starts from station $s$ , located on line $l in e 1$ .

dist[s][line1] = 0;

Insert into the priority queue a node structure containing the starting vertex $s$ on line $l in e 1$ . The cost of reaching the starting vertex is $0$ .

priority_queue<node, vector<node> > pq;
pq.push(node(s, 0, line1)); // (v, cost, line)
while (!pq.empty())
{

Extract from the priority queue the vertex $v$ with the minimum cost.

  int cost = pq.top().cost;
  int v = pq.top().to;
  int l1 = pq.top().line;
  pq.pop(); // dist[v][l1] = cost

Iterate over all vertices adjacent to $v$ .

  for (i = 0; i < g[v].size(); i++)
  {

Consider the edge $v \to t o$ with cost $w$ , which belongs to line $l 2$ .

    int to = g[v][i].to;
    int w = g[v][i].cost;
    int l2 = g[v][i].line;

If we move along the edge $v \to t o$ , the total cost of the path becomes $cos t + w$ .

    int tot_cost = cost + w;

If vertices $v$ and $t o$ belong to different lines, a transfer from line $l 1$ to line $l 2$ must be made.

    if (l1 != l2) tot_cost += 1;

If moving along the edge $v \to t o$ improves the current value, update $d i s t [t o] [l 2]$ and insert vertex $t o$ into the queue (its total cost is $t o t_cos t$ , and it is located on line $l 2$ ).

    if (tot_cost < dist[to][l2])
    {
      dist[to][l2] = tot_cost;
      pq.push(node(to, tot_cost, l2));
    }
  }
}

Print the result — the minimum travel cost to reach vertex $f$ on line $l in e 2$ .

printf("%d\n", dist[f][line2]);

Comments

Nothing yet

Be the first one to start the conversation!

Loading

Just a moment, getting data from the server