Mmedv10 months ago

Educational Round #4 — Editorial

Read the input data.

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

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

if (!n) res = 0; else

If the number of toasts does not exceed the capacity of the pan, it will take $4$ minutes to toast them.

if (n <= k) res = 4; else
{

Each toast must be toasted on both sides, which means that the total number of sides to toast is $⌈ 2 n / k ⌉$ . Each toasting session (regardless of the number of toasts on the pan, as long as it does not exceed its capacity) takes $2$ minutes.

  res = 2 * n / k;
  if (2 * n % k) res++;
  res *= 2;
}

Print the answer.

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

Eolymp #10271. ADA School

In the ADA School classroom, there are $n \times m$ n \times m desks arranged in a rectangular grid with $n$ rows and $m$ columns. Each desk is occupied by exactly one student.

Before the lesson begins, the teacher decides to shuffle the students a bit. After the rearrangement, two conditions must be met:

Each desk must still be occupied by exactly one student.
Each student must move to a desk adjacent to their original one, meaning a desk located directly to the left, right, above, or below.

Is it possible to rearrange the students while satisfying both conditions?

Input. The first line contains the number of test cases $t$ . Each of the next $t$ lines contains two integers $n$ and $m (2 \leq n, m \leq 1000)$ m~(2 \le n, m \le 1000).

Output. For each test case, print "YES" if the rearrangement is possible and "NO" otherwise.

Open problem

Read the number of test cases $t$ .

scanf("%d", &t);
while (t--)
{

Read the input data for each test case.

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

If $n$ and $m$ are both odd, print "NO".

  if (n % 2 == 1 && m % 2 == 1)
    puts("NO");

Otherwise, print "YES". '

  else
    puts("YES");
}

Eolymp #9061. Secular reception

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}$ 10^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}$ 10^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})$ p~(1 \le q \le p \le 10^5) — the speeds of Bof and Agent English, respectively.

Output. In the first line, print the number $n (2 \leq n \leq 100)$ n~(2 \le n \le 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})$ y~(0 \le x, y \le 10^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

Read the input data.

scanf("%d %d", &q, &p);

If the speeds of Johnny English and Bof are the same, then they move from point $(0, 0)$ to point $(1, 1)$ .

if (q == p)
{
  printf("2\n");
  printf("%d %d\n", 0, 0);
  printf("%d %d\n", 1, 0);
  return 0;
}

C++

If $p \neq = q$ p \ne q, then the route consists of four points.

printf("4\n");
printf("%d %d\n", 0, 0);
printf("%d %d\n", 2 * q, 0);
printf("%d %d\n", 2 * q, p - q);
printf("%d %d\n", 2 * q, 0);

Eolymp #10345. Painting the Barn (Silver)

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$ 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})$ k~(1 \le k \le n \le 10^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}$ x_1, y_1, x_2, y_2, defining a rectangle with its bottom-left corner at $(x_{1}, y_{1})$ (x_1, y_1) and top-right corner at $(x_{2}, y_{2})$ (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

Declare a two-dimensional array $d p$ .

#define MAX 1001
int dp[MAX][MAX];

Read the input data.

scanf("%d %d", &n, &k);
while (n--)
{

For each rectangle $(a, b) - (c, d)$ (a, b) - (c, d), perform the following four operations.

  scanf("%d %d %d %d", &a, &b, &c, &d);
  dp[a][b]++;
  dp[a][d]--;
  dp[c][b]--;
  dp[c][d]++;
}

Count the number of wall cells covered with exactly $k$ layers of paint in the variable $r es$ .

res = 0;

Compute the prefix sums in the $d p$ array.

for (i = 0; i < MAX; i++)
  for (j = 0; j < MAX; j++)
  {
    if (i) dp[i][j] += dp[i - 1][j];
    if (j) dp[i][j] += dp[i][j - 1];
    if (i && j) dp[i][j] -= dp[i - 1][j - 1];

If the cell $(i, j)$ is covered with $k$ layers of paint, increment $r es$ by $1$ .

    if (dp[i][j] == k) res++;
  }

Print the answer.

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

Eolymp #11245. Palindrome Partitioning

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$ 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

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)$ IsPal(i, j) checks whether the substring $s_{i} ... s_{j}$ s_i~...~s_j is a palindrome. The substring $s_{i} ... s_{j}$ s_i~...~s_j is a palindrome if $s_{i} = s_{j}$ s_i = s_j and $s_{i + 1} ... s_{j - 1}$ s_{i+1}~...~s_{j-1} is a palindrome. The values of $I s P a l (i, j)$ IsPal(i, j) are stored in the cells of the array $p a l [i] [j]$ pal[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)$ f(i, j) returns the minimum number of cuts required to partition the substring $s_{i} ... s_{j}$ s_i~...~s_j into palindromes.

int f(int i, int j)
{

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

  if (i >= j) return 0;

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

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

If the substring $s_{i} ... s_{j} (i < j)$ 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}$ s_i~...~s_j into two parts: $s_{i} ... s_{k} (i \leq k)$ s_i~...~s_k~(i \le k) and $s_{k + 1} ... s_{j} (k + 1 \leq j)$ s_{k+1}~...~s_j~(k + 1 \le j). Then, recursively solve the problems for both parts: $s_{i} ... s_{k}$ s_i~...~s_k and $s_{k + 1} ... s_{j}$ s_{k+1}~...~s_j. Find the value of $k (i \leq k < j)$ k~(i \le k < j) for which the sum $f (i, k) + f (k + 1, j) + 1$ 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)$ dp[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;

Eolymp #10869. Building Construction

You are given $n$ buildings with heights $h_{1}, h_{2}, \dots, h_{n}$ h_1, h_2, \ldots, 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$ h_1 = h_2 = \ldots = 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})$ n~(n \le 10^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})$ h_1, h_2, \ldots, h_n~(0 \le h_i \le 10^4).

The third line contains $n$ integers $c_{1}, c_{2}, \dots, c_{n} (0 \leq c_{i} \leq 1 0^{4})$ c_1, c_2, \ldots, c_n~(0 \le c_i \le 10^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

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;
}

C++

The function ternary_search uses the ternary search to find the value of $x \in [l e f t; r i g h t]$ x \in [left; right] for which $f (x)$ is minimal. Initially, the search range is $[l e f t; r i g h t] = [1; n]$ [left; right] = [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;
  }

C++

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]$ [left; right] 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));

Eolymp #1104. Dominos

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})$ m~(1 \le n, m \le 10^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

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);
}

C++

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);
}

C++

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]$ color[to]. Therefore, set $u se d [co l or [t o]] = 0$ used[color[to]] = 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$ used[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);

Eolymp #11452. The longest Path

Given a directed graph $G$ with $n$ vertices and $m$ edges. The vertices are numbered from $1$ to $n$ . For each $i (1 \leq i \leq m)$ i~(1 \le i \le m), a directed edge from vertex $x_{i}$ x_i to vertex $у_{i}$ у_i is given.

The graph $G$ contains no directed cycles.

Find the length of the longest directed path in $G$ . The length of a path is defined as the number of edges in that path.

Input. The first line contains two integers: the number of vertices $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) and the number of edges $m (1 \leq m \leq 1 0^{5})$ m~(1 \le m \le 10^5) of the graph. Each of the next $m$ lines contains two integers $x_{i}, y_{i} (1 \leq x_{i}, y_{i} \leq n)$ x_i, y_i~(1 \le x_i, y_i \le n), describing a directed edge from vertex $x_{i}$ x_i to vertex $у_{i}$ у_i.

Output. Print the length of the longest directed path in the graph $G$ .

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);
}

C++

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);
}

C++

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[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);

Eolymp #7414. A Simple Task

You are given a string $S$ of length $n$ and $q$ queries. Each query has the format $i, j, k$ i, j, k, meaning that you need to sort the substring consisting of the characters from position $i$ to $j$ inclusive in non-decreasing order if $k = 1$ k = 1, or in non-increasing order if $k = 0$ k = 0.

After processing all the queries, print the resulting string.

Input. The first line contains two integers $n$ and $q (1 \leq n \leq 1 0^{5}, 0 \leq q \leq 50000)$ q~(1 \le n \le 10^5, 0 \le q \le 50000) — the length of the string and the number of queries, respectively.

The second line contains the string $S$ , which consists only of lowercase English letters.

Each of the next $q$ lines contains three integers $i, j,$ and $k (1 \leq i \leq j \leq n, k = 0$ k~(1 \le i \le j \le n,~k = 0 or $k = 1)$ k = 1) describing a query.

Output. Print the string $S$ after performing all the queries.

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]$ [l; r].

Processing a query on the range $[l; r]$ [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$ k = 1, the characters are arranged in non-decreasing order — that is, from ' $a$ ' to ' $z$ ';
if $k = 0$ k = 0, they are arranged in non-increasing order — from ' $z$ ' to ' $a$ '.

To do this, for the entire range $[l; r]$ [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 B E T = 26$ ALPHABET = 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;
    }
  }
}

C++

The vertex $v$ corresponds to the segment $[l p os, r p os]$ [lpos, rpos], with $mi d = (l p os + r p os) /2$ mid = (lpos + rpos) / 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;
  }
}

C++

The vertex $v$ corresponds to the segment $[l p os, r p os]$ [lpos, rpos]. 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;
}

C++

The vertex $v$ corresponds to the segment $[l p os, r p os]$ [lpos, rpos]. Find the sum of elements in the range $[l e f t; r i g h t]$ [left; right] 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);
}

C++

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);
}

C++

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]$ [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];
    }
  }
}

C++

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)$ get(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);

Eolymp #68. Metro

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$ 1 \le l \le 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$ 2 + 1 + 4 + 1 + 2 = 10 minutes.

Open problem

The number of vertices in the graph does not exceed $M A X = 71$ MAX = 71. The number of metro lines does not exceed $L I N E S = 11$ LINES = 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]$ dist[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 (auto edge: g[v])
  {

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

    int to = edge.to;
    int w = edge.cost;
    int l2 = edge.line;

If we move along the edge $v \to t o$ v \to to, the total cost of the path becomes $cos t + w$ cost + 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$ v \to to improves the current value, update $d i s t [t o] [l 2]$ dist[to][l2] 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));
    }
  }
}

C++

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

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

Educational Round #4 — Editorial

Comments