Tutorial•1 day ago

Educational Round #3 — Editorial

A huge disaster occurred this morning at the café where you used to have snacks during your university studies. The cleaner, Larisa Ivanovna, accidentally knocked over one of the cabinets while sweeping the floor, causing all the kitchen utensils stored inside to scatter across the floor. Fortunately, it only contained saucepans with lids. However, some of them got bent or broken, so they had to be thrown away.

Now the schoolmaster wants to calculate the losses and determine how many new saucepans and lids should be purchased. But first, it is necessary to find out how many remaining saucepans can be covered by the remaining lids.

The saucepans and lids are round. A lid can cover a saucepans only if its radius is not less than the radius of the pot.

Input. The first line contains integers $n, m (1 \leq n, m \leq 1000)$ — the number of remaining saucepans and lids. The second line contains $n$ integers $a_{i} (1 \leq a_{i} \leq 1000)$ — the radii of the remaining saucepans. The third line contains $m$ integers $b_{i} (1 \leq b_{i} \leq 1000)$ — the radii of the remaining lids.

Output. Print one number — the largest number of saucepans that can be covered by the available lids.

beginrow

Open problem

Upon entering the treasure cave, Aladdin chose not to take the old, blackened lamp. Instead, he began filling his backpack with gold coins and precious gems. Of course, he wanted to take everything, but miracles don't happen — his backpack had a limited carrying capacity and might not withstand excessive weight.

Many times, he removed some items and replaced them with others, striving to maximize the total value of his backpack's contents.

The task is to determine the maximum value of the cargo that Aladdin can carry.

We assume that the cave contains $n$ different types of items, with an unlimited number of each type available. The backpack can hold a maximum weight of $s$ . Each item of type $i$ has a weight of $w_{i}$ and a value of $v_{i} (i = 1, 2, ..., n)$ .

Input. The first line contains two positive integers $s$ and $n (1 \leq s \leq 250, 1 \leq n \leq 35)$ — the maximum weight the backpack can carry and the number of item types.

The next $n$ lines each contain two numbers $w_{i}$ and $v_{i} (1 \leq w_{i} \leq 250, 1 \leq v_{i} \leq 250)$ — the weight and value of an item of type $i$ .

Output. Print the maximum total value of the cargo that can be carried without exceeding the weight limit $s$ .

beginrow

Open problem

Let $d p_{k} [s]$ be the maximum value of cargo with a weight of at most $s$ , considering only the first $k$ types of items.

Now, consider two possible options when forming cargo of weight $i$ :

Do not use an item of type $k$ : In this case, the optimal value remains unchanged, meaning:

d p_{k} [i] = d p_{k - 1} [i]

Use an item of type $k$ : Then its weight $w_{k}$ will occupy part of the knapsack's capacity, and the value will increase by $v_{k}$ , meaning:

d p_{k} [i] = d p_{k} [i - w_{k}] + v_{k} .

Since the goal is to maximize the cargo value, we obtain the following recurrence relation:

d p_{k} [i] = ma x (d p_{k - 1} [i], d p_{k} [i - w_{k}] + v_{k}), w_{k} \leq i \leq s

Base cases:

d p_{0} [i] = 0 и d p_{k} [0] = 0

Let the function $f (k, s)$ compute the maximum value of cargo that can be packed into a knapsack with a weight limit of $s$ , using the first $k$ types of items. Then, the next recurrence relation holds:

f (k, s) = ma x (f (k - 1, s), f (k, s - w [k]) + v [k])

Finally, we need to compute the value of $f (k, s)$ using memoization.

Declare the arrays:

$w [i]$ — the weight of an item of type $i$ ;
$p [i]$ — the value of an item of type $i$ ;
$d p [i]$ — the maximum value of cargo with a weight of at most $i$ ;

#define MAXW 252
#define MAXN 37
int w[MAXN], p[MAXN];
int dp[MAXW];

Read the input data.

scanf("%d %d", &s, &n);
for (i = 0; i < n; i++)
  scanf("%d %d", &w[i], &p[i]);

Process $n$ types of items sequentially.

for (k = 0; k < n; k++)
{

Update the values in the $d p$ array, considering the possibility of using items of type $k$ . Since the number of items of each type is unlimited, each item can be chosen multiple times.

  for (i = w[k]; i <= s; i++)
    dp[i] = max(dp[i], dp[i - w[k]] + p[k]);
}

Print the answer.

printf("%d\n", dp[s]);

Algorithm implementation — recursion

Declare the arrays:

$w [i]$ — the weight of an item of type $i$ ;
$p [i]$ — the value of an item of type $i$ ;
$d p [i]$ — the maximum value of cargo with a weight of at most $i$ ;

#define MAXW 252
#define MAXN 37
#define INF 2000000000
int w[MAXN], v[MAXN];
int dp[MAXN][MAXW];

The function $f (k, s)$ computes the maximum value of cargo that can be packed into a knapsack with a weight limit of $s$ , using the first $k$ types of items.

int f(int k, int s)
{

If $k = 0$ or $s = 0$ , the knapsack is empty, and its value is $0$ .

  if (k == 0 || s == 0) return 0;

If $s < 0$ , we have exceeded the allowed weight, making this option invalid. Therefore, we return $- I NF$ (where $I NF$ is a sufficiently large number).

  if (s < 0) return -INF;

If the value of $f (k, s)$ is already computed, return it.

  if (dp[k][s] != -1) return dp[k][s];

Compute $f (k, s)$ and store it in $d p [k] [s]$ .

  return dp[k][s] = max(f(k - 1, s), f(k, s - w[k]) + v[k]);
}

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

scanf("%d %d", &s, &n);
for (i = 1; i <= n; i++)
  scanf("%d %d", &w[i], &v[i]);

Compute and print the answer.

memset(dp, -1, sizeof(dp));
printf("%d\n", f(n, s));

King Julien, the ruler of all lemurs, has exactly $2 \cdot k$ lemurs under his command — two lemurs of each of the $k$ species. Julien loves parties, so every evening he throws one. However, the VIP area unfortunately has room only for himself and $n$ other lemurs.

Since Julien dislikes repeating himself, he wants to invite a set of lemurs to the VIP area that has never appeared before. Two lemurs of the same species are considered indistinguishable. Two sets of lemurs are considered the same if they coincide as multisets of species.

Help Julien determine how many distinct parties he can host. As the answer may be very large, print it modulo $1 0^{9} + 7$ .

Input. A single line contains two integers $k$ and $n (1 \leq k \leq 500000, 0 \leq n \leq 2 \cdot k)$ — the number of lemur species and the number of available VIP seats (excluding Julien himself).

Output. Print one single integer — the number of distinct parties modulo $1 0^{9} + 7$ .

Open problem

For $n$ seats, some species will be represented by two lemurs, and some by one. Let $i$ pairs of lemurs be chosen (that is, $i$ species are represented by two individuals). The number of ways to make such a choice is $C_{k}^{i}$ . After this, there will be $n - 2 i$ free seats in the VIP area. These seats can be occupied by lemurs from $k - i$ remaining species, choosing one lemur from each. The number of ways to choose such lemurs is calculated by the formula $C_{k - i}^{n - 2 i}$ .

Since the value of $i$ can take any integer from $0$ to $k$ , the final answer is obtained as the sum over all possible values of $i$ :

i = 0 \sum k C_{k}^{i} \cdot C_{k - i}^{n - 2 i}

Example

Let's consider a second example, where there are $k = 4$ pairs of lemurs and $n = 3$ seats in the VIP area. Using the formula, we get:

i = 0 \sum k C_{4}^{i} \cdot C_{4 - i}^{3 - 2 i} = C_{4}^{0} \cdot C_{4}^{3} + C_{4}^{1} \cdot C_{3}^{1} = 4 + 12 = 16

Let's list only the nonzero terms. We'll consider the value $C_{n}^{k}$ to be zero if any of the following three inequalities hold: $k < 0$ , $n < 0$ или $k > n$ .

Let us denote the lemurs by the letters ${a, a, b, b, c, c, d, d}$ , where identical letters correspond to lemurs of the same species.

The term $C_{4}^{0} \cdot C_{4}^{3} = 4$ corresponds to the situation where no pair of lemurs of the same species is chosen, that is, each of the three selected lemurs belongs to a different species. The four possible selections are as follows:

Now consider the term $C_{4}^{1} \cdot C_{3}^{1} = 12$ . In this case, two lemurs are chosen from one species (there are $4$ possible ways to do this). For the remaining one seat, one lemur is chosen from the three remaining species. Thus, there are a total of $12$ possible selections.

It is clear that it is impossible to place two lemurs from two different species in only $3$ seats. Therefore, all the remaining terms of the sum are equal to zero.

Declare the constants.

#define MAX 1000001
#define MOD 1000000007

Let us define the following arrays:

$f a c t$ contains the factorials of numbers modulo $MO D$ ;
$f a c t in v$ contains the values inverse to the factorials of numbers modulo $MO D$ :

fact[n] = n! mod 1000000007
factinv[n] = n! -1 mod 1000000007

typedef long long ll;
ll fact[MAX], factinv[MAX];

The function pow computes the power of a number modulo $p$ : $x^{n} m o d p$ .

ll pow(ll x, ll n, ll p)
{
  if (n == 0) return 1;
  if (n % 2 == 0) return pow((x * x) % p, n / 2, p);
  return (x * pow(x, n - 1, p)) % p;
}

The function inverse finds the number that is the modular inverse of $x$ with respect to a prime modulo $p$ . Since $p$ is a prime number, by Fermat's little theorem the following equality holds:

x^{p - 1} m o d p = 1 f or e v ery 1 \leq x < p

This equality can be rewritten as:

(x \cdot x^{p - 2}) m o d p = 1,

which means that the modular inverse of $x$ is $x^{p - 2} m o d p$ .

ll inverse(ll x, ll p)
{
  return pow(x, p - 2, p);
}

The function Cnk computes the value of the binomial coefficient using the following formula:

C_{n}^{k} = \frac{n !}{k ! ( n - k )!}

ll Cnk(int n, int k)
{
  return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;
}

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

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

Fill the factorial arrays $f a c t$ and $f a c t in v$ .

fact[0] = 1;
for (i = 1; i < MAX; i++)
  fact[i] = (fact[i - 1] * i) % MOD;

factinv[0] = 1;
for (i = 1; i < MAX; i++)
   factinv[i] = inverse(fact[i], MOD);

Compute the answer using the formula $\sum_{i = 0}^{k} C_{k}^{i} \cdot C_{k - i}^{n - 2 i}$ . The value of the binomial coefficient $C_{n}^{k}$ is considered to be zero if any of the following three conditions hold: $k < 0$ , $n < 0$ or $k > n$ .

res = 0;
for (i = 0; i <= k; i++)
{
  if (n - 2 * i < 0 || k - i < 0 || n - 2 * i > k - i) continue;
  res = (res + Cnk(k, i) * Cnk(k - i, n - 2 * i)) % MOD;
}

Print the answer.

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

Given a tree with $n$ vertices, where the vertex numbered $i (1 \leq i \leq n)$ contains $c_{i}$ coins. Select a subset of vertices such that no two of them are adjacent (i.e., connected by an edge), and the sum of coins in the selected vertices is maximized.

Input. The first line contains the number of vertices $n (1 \leq n \leq 1 0^{5})$ in a tree. Each of the next $n - 1$ lines contains two integers $u$ and $v (1 \leq u, v \leq n)$ , defining an edge in the tree. The last line contains $n$ non-negative integers $c_{1}, ... c_{n}$ — the number of coins in each vertex of the tree.

Output. Print the maximum possible sum of coins that can be obtained by selecting a subset of vertices in the tree with no adjacent vertices.

Open problem

Let $v$ be a vertex of the tree. Let's define:

$d p_{1} (v)$ as the maximum sum of coins that can be collected from the subtree rooted at $v$ if we take the coins in vertex $v$ .
$d p_{2} (v)$ as the maximum sum of coins that can be collected from the subtree rooted at $v$ if we do not take the coins in vertex $v$ .

Then the answer to the problem will be $ma x (d p_{1} (1), d p_{2} (1))$ , assuming the first vertex is taken as the root of the tree.

Let’s define the given functions recursively:

If we take the coins in vertex $v$ , then we cannot take coins from its children:

d p_{1} (v) = c_{v} + i = 1 \sum k d p_{2} (t o_{i}), w h ere t o_{1}, ..., t o_{k} a re t h e so n s o f v er t e x v .

If we do not take the coins in vertex $v$ , then we can choose either to take or not take coins from its children. We select the option with the maximum sum of coins:

d p_{2} (v) = i = 1 \sum k ma x (d p_{1} (t o_{i}), d p_{2} (t o_{i})), w h ere t o_{1}, ..., t o_{k} a re t h e so n s o f v er t e x v .

If $v$ is a leaf with $c_{v}$ coins, then the functions take the following values: $d p_{1} (v) = c_{v}$ and $d p_{2} (v) = 0$ .

Example

Let's assign the labels $d p_{1} (v) / d p_{2} (v)$ to the vertices of the trees from the examples.

For the first example, we have:

$d p_{1} (1) = c_{1} + d p_{2} (2) + d p_{2} (3) = 1 + 3 + 0 = 4$ ;
$d p_{2} (1) = ma x (d p_{1} (2), d p_{2} (2)) + ma x (d p_{1} (3), d p_{2} (3)) = 5 + 7 = 12$ ;
$d p_{1} (2) = c_{2} + d p_{2} (4) + d p_{2} (5) = 5 + 0 + 0 = 5$ ;
$d p_{2} (2) = ma x (d p_{1} (4), d p_{2} (4)) + ma x (d p_{1} (5), d p_{2} (5)) = 1 + 2 = 3$ ;

For the second example, we have:

$d p 1 (1) = c_{1} + d p_{2} (2) + d p_{2} (3) = 3 + 11 + 0 = 14$ ;
$d p_{2} (1) = ma x (d p_{1} (2), d p_{2} (2)) + ma x (d p_{1} (3), d p_{2} (3)) = 11 + 5 = 16$ ;
$d p_{1} (2) = c_{2} + d p_{2} (4) + d p_{2} (5) = 7 + 0 + 0 = 7$ ;
$d p_{2} (2) = ma x (d p_{1} (4), d p_{2} (4)) + ma x (d p_{1} (5), d p_{2} (5)) = 10 + 1 = 11$ ;

Exercise

Assign the labels $d p_{1} (v) / d p_{2} (v)$ to the vertices of the tree:

Declare the arrays.

vector<vector<int> > g;
vector<int> dp1, dp2, cost;

The dfs function implements depth-first search. Compute the values of $d p_{1}$ and $d p_{2}$ at all vertices of the tree.

void dfs(int v, int p = -1)
{
  dp1[v] = cost[v];
  dp2[v] = 0;

  for (int to : g[v])
  {
    if (to == p) continue;

    dfs(to, v);

    dp1[v] += dp2[to];
    dp2[v] += max(dp1[to], dp2[to]);
  }
}

The main part of the program. Read the tree and the array of coins.

scanf("%d",&n);
g.resize(n+1);
for(i = 1; i < n; i++)
{
  scanf("%d %d",&u,&v);
  g[u].push_back(v);
  g[v].push_back(u);
}

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

Let the root of the tree be at vertex $1$ . Start the depth-first search from there.

dfs(1);

Compute and print the answer.

ans = max(dp1[1], dp2[1]);
printf("%d\n",ans);

Let $f (a, b)$ be the minimum number of moves required to cut a rectangle of size $a \times b$ into squares. We'll store this value in the cell $d p [a] [b]$ .

If the rectangle is already a square $(a = b)$ , no cuts are needed, so $f (a, a) = 0$ .

A rectangle $a \times b$ can be cut either vertically or horizontally. Let's first consider a vertical cut.

With a vertical cut, the rectangle $a \times b$ is divided into two rectangles: $a \times k$ and $a \times (b - k)$ . For the resulting rectangles to be non-degenerate, the condition $1 \leq k < b$ must hold. Then recursively solve the problem for each of these two rectangles and add $1$ to the result, as we made one vertical cut. We choose such a $k$ that minimizes the sum $f (a, k) + f (a, b - k) + 1$ :

f (a, b) = 1 \leq k < b min (f (a, k) + f (a, b - k)) + 1

For a horizontal cut, we get a similar formula:

f (a, b) = 1 \leq k < a min (f (k, b) + f (a - k, b) + 1

It remains to choose the minimum value among these two options.

Example

In the first test, $3$ cuts are required:

The first cut divides the $3 \times 5$ rectangle into $3 \times 3$ and $2 \times 3$ ;
The second cut divides the $2 \times 3$ rectangle into $2 \times 2$ and $2 \times 1$ ;
The third cut divides the $2 \times 1$ rectangle into $1 \times 1$ and $1 \times 1$ ;

Let's declare constants and the array.

#define MAX 501
#define INF 0x3F3F3F3F

int dp[MAX][MAX];

The function $f (a, b)$ returns the minimum number of moves required to cut a rectangle of size $a \times b$ into squares.

int f(int a, int b)
{

If the rectangle is already a square $(a = b)$ , no cuts are needed.

  if (a == b) return 0;

If the value of $f (a, b)$ is not computed $(d p [a] [b] = \infty)$ , compute it.

  if (dp[a][b] == INF)
  {

Perform all possible vertical cuts.

    for (int k = 1; k < b; k++)
      dp[a][b] = min(dp[a][b], f(a, k) + f(a, b - k) + 1);

Perform all possible horizontal cuts.

    for (int k = 1; k < a; k++)
      dp[a][b] = min(dp[a][b], f(k, b) + f(a - k, b) + 1);
  }

Return the result $f (a, b) = d p [a] [b]$ .

  return dp[a][b];
}

The main part of the program. Read the dimensions of the rectangle $a$ and $b$ .

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

Compute and print the answer.

memset(dp, 0x3F, sizeof(dp));
printf("%d\n", f(a, b));

The Law of the Jungle is very clear: every wolf, once he has started a family, may leave his Pack. But as soon as his cubs grow up and become strong enough, he must bring them to the Council of the Pack, which is usually held once a month during the full moon, and present them to all the other wolves.

Father Wolf waited until his cubs had grown a little and started to run about. Then, on one of the nights when the Pack gathered, he led them — together with Mowgli and Mother Wolf — to the Council Rock. It was the top of a hill strewn with large boulders, behind which a hundred wolves could easily hide. Akela, the great gray lone wolf, chosen as leader of the whole Pack for his strength and agility, called out from his rock:

— The Law is known to you, the Law is known to you! Look well, wolves!

Father Wolf pushed the Frog, Mowgli, into the center of the circle. Mowgli sat down on the ground, laughed, and began to play with some sticks.

He came up with a simple task: to make a rectangle of the maximum possible area from these sticks — not necessarily using all of them.

Input. The first line contains the number of sticks $n (1 \leq n \leq 16)$ . The second line contains their lengths — positive integers in the range from $1$ to $1 0^{8}$ .

Output. Print the maximum possible area of a rectangle that can be made from the given set of sticks, or $0$ if forming a rectangle is impossible.

Open problem

Let $S$ be the given set of sticks. It is required to find two disjoint subsets $A$ and $B$ of $S$ such that the sticks in each of them can be divided into two subsets with equal total lengths.

For every subset $ma s k \subseteq S$ , compute the total length of its sticks and store it in $s u m [ma s k]$ .

Iterate over all subsets $I \subset S$ . For each subset $I$ , go through all of its subsets $J \subset I$ . If there exists such a subset $J$ that $2 \cdot s u m [J] = s u m [I]$ (that is, the total length of sticks in $J$ is exactly half of the total length of sticks in $I$ ), then the subset $I$ can be used as a pair of opposite sides of a rectangle. In this case, set $c an [I] = t r u e$ .

The entire procedure runs in $O (3^{n})$ .

Iterate over all subsets of the set of sticks. If for some subset I there exists a subset $J \subset I$ such that $c an [J] = t r u e$ and $c an [I x or J] = t r u e$ (that is, the subsets $J$ and $I x or J$ are disjoint), then we obtain one of the possible distributions of sticks between the horizontal and vertical sides of the rectangle.

The side lengths of such a rectangle are $s u m [J] /2$ and $s u m [I x or J] /2$ . Among all such possible rectangles, choose the one with the maximum area.

The lengths of the sticks are stored in the array $a$ . For each subset of sticks $ma s k$ , store their total length in the array $s u m [ma s k]$ . The value $c an [ma s k]$ is set to $t r u e$ if the subset $ma s k$ can be divided into two parts with equal total lengths — these will correspond to the opposite sides of a rectangle.

#define MAX 16
int a[MAX];
int sum[1 << MAX];
bool can[1 << MAX];

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

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

Iterate over all subsets of sticks and compute the total length of each subset.

for (i = 0; i < 1 << n; i++)
  for (j = 0; j < n; j++)
    if (i & (1 << j)) sum[i] += a[j];

Then, iterate through all possible subsets of the set of sticks. If for some subset $I$ there exists a subset $J \subset I$ such that the total length of sticks in $J$ is exactly half of the total length of sticks in $I$ , set $c an [I] = t r u e$ . In this case, the sticks from subset $I$ can be used as opposite sides of a rectangle.

for (i = 1; i < 1 << n; i++) 
{
  int s = sum[i];
  for (j = i; j > 0; j = (j - 1) & i)
    if (sum[j] * 2 == s) 
    {
      can[i] = true;
      break;
    }
}

Iterate over all subsets of the set of sticks. If for some subset $I$ there exists a subset $J \subset I$ such that $c an [J] = t r u e$ and $c an [I x or J] = t r u e$ , then we obtain one of the possible distributions of sticks between the horizontal and vertical sides of the rectangle. The side lengths of such a rectangle are $s u m [J] /2$ and $s u m [I x or J] /2$ .

res = 0;
for (i = 1; i < 1 << n; i++)
  for (j = i; j > 0; j = (j - 1) & i)
    if (can[j] && can[i ^ j])
      res = max(res, sum[j] / 2 * 1LL * sum[i ^ j] / 2);

Print the area of the rectangle with the maximum size found.

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

Once, Detective Saikat was investigating a murder case. At the crime scene, he discovered a staircase with a number written on each step. Finding this suspicious, he decided to remember all the numbers he encountered along the way. Soon, he noticed a pattern: for each number on the staircase, he recorded the sum of all previously encountered numbers that were smaller than the current one.

Your task is to find the total sum of all numbers recorded by the detective in his notebook.

Input. The first line contains an integer $t (t \leq 10)$ — the number of test cases. The next $2 t$ lines follow. The first of these lines contains an integer $n (1 \leq n \leq 1 0^{5})$ — the number of steps. The next line contains $n$ integers — the numbers written on the steps. All numbers are in the range from $0$ to $1 0^{6}$ .

Output. For each test case, print the final sum in a separate line.

Open problem

Let the maximum array size be $M A X$ . Create a Fenwick tree $F e n w i c k$ .

#define MAX 1000001
vector<long long> Fenwick;

The function Summa0_i computes the sum $a_{0} + a_{1} + ... + a_{i}$ .

long long Summma0_i(int i)
{
  long long result = 0;
  for (; i >= 0; i = (i & (i + 1)) - 1)
    result += Fenwick[i];
  return result;
}

The function IncElement increases the value of an element: $a_{i} = a_{i} + d e lt a$ .

void IncElement(int i, int delta)
{
  for (; i < MAX; i = (i | (i+1)))
    Fenwick[i] += delta;
}

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

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

Initialize the $F e n w i c k$ array with zeros.

  Fenwick.assign(MAX,0);

The desired sum recorded in the detective's notebook will be computed in the variable $s u m$ .

  sum = 0;

Process the numbers written on the steps one by one.

  for (i = 0; i < n; i++)
  {

For each $v a l u e$ , written on a step, increase $a_{v a l u e}$ by $v a l u e$ and compute the sum of all previously encountered numbers smaller than $v a l u e$ . This sum is $a_{0} + a_{1} + a_{2} + ... + a_{v a l u e - 1}$ .

    scanf("%d",&value);
    IncElement(value, value);
    sum += Summma0_i(value - 1);
  }

Print the total sum of all numbers written in the detective's notebook.

  printf("%lld\n",sum);
}

Amin and Murad decided to create a Minecraft game server.

They invited $k$ guests to the grand opening of the server. The guests live in different cities, and when connecting to the server, they will experience a certain latency (ping) depending on their location. Realizing the potential issues, Amin and Murad decided to choose the most optimal location for hosting the server.

There are $n$ cities, numbered from $1$ to $n$ , and $m$ bidirectional communication channels between them. A connection to the server is only possible through these channels. Using them, it is possible to establish a connection between any two cities. Each pair of cities may have at most one direct communication channel, and no city is connected to itself. Each channel has a transmission delay of $w_{i}$ .

The connection delay between a city and the server is defined as the minimum possible sum of delays along the path from that city to the server.

Amin and Murad want to choose a city to host the server so that the total connection delay for all guests is minimized. If the server is hosted in the same city where a guest lives, the delay for that guest is considered to be zero.

If there are multiple cities with the same minimum total delay, Amin and Murad will choose the city with the smallest number.

Determine the city where the server will be hosted and the total connection delay for all guests to the server.

Input. The first line contains three integers $n (1 \leq n \leq 1 0^{4}), m (1 \leq m \leq 4 * 1 0^{4})$ , and $k (1 \leq k \leq 100)$ — the number of cities, the number of communication channels, and the number of guests, respectively. The second line contains $k$ distinct integers $c_{i} (1 \leq c_{i} \leq n)$ — the numbers of the cities where the guests live.

Each of the following $m$ lines contains three integers $u_{i}, v_{i}$ , and $w_{i} (1 \leq u_{i}, v_{i} \leq n)$ — describing a bidirectional communication channel between cities $u_{i}$ and $v_{i}$ with a delay of $w_{i} (1 \leq w_{i} \leq 1 0^{4})$ .

Output. Print two integers — the number of the city where the server will be hosted, and the total connection delay for all guests to this server.

Open problem

Since $n \leq 1 0^{4}$ , we will represent the graph using an adjacency list.

Run Dijkstra's algorithm from each city where a guest resides. For every vertex, compute the sum of distances to all guest cities.

The vertex with the smallest sum will be the optimal location for hosting the server. If there are multiple such vertices, choose the one with the smallest number.

Note that the server does not necessarily have to be placed in a city where one of the guests lives.

Example

The graph given in the example is as follows:

Run Dijkstra's algorithm from the vertices where the guests reside: $1, 2$ , and $5$ . For each of these vertices, determine the shortest distances to all other cities.

Next, for each vertex of the graph, compute the sum of distances to all the cities with guests. The minimum sum of distances is $13$ , and it is achieved at the vertex with the smallest number $2$ .

Therefore, the server should be placed in city $2$ . The total distance from it to the cities where the guests reside is $5 + 0 + 8 = 13$ .

Declare a constant for infinity.

#define INF 0x3F3F3F3F

The $e d g e$ structure will store information about an edge: the vertex $n o d e$ that the edge leads to, and the weight $d i s t$ of the edge.

struct edge
{
  int node, dist;
  edge(int node, int dist) : node(node), dist(dist) {}
};

Declare a comparator for sorting pairs $(n o d e, d i s t)$ in descending order of the $d i s t$ value.

bool operator< (edge a, edge b)
{
  return a.dist > b.dist;
}

Declare an adjacency list to represent the graph.

vector<vector<edge> > g;

The Dijkstra function implements Dijkstra's algorithm. It takes the graph $g$ and the starting vertex $s t a r t$ as input. The return value is an array $d$ , where $d [i]$ contains the shortest distance from the vertex $s t a r t$ to vertex $i$ .

void Dijkstra(vector<vector<edge> >& g, vector<int>& d, int start)
{
  priority_queue<edge> pq;
  pq.push(edge(start, 0));

  d = vector<int>(n + 1, INF);
  d[start] = 0;

  while (!pq.empty())
  {
    edge e = pq.top(); pq.pop();
    int v = e.node;

    if (e.dist > d[v]) continue;

    for (auto e : g[v])
    {
      int to = e.node;
      int cost = e.dist;
      if (d[v] + cost < d[to])
      {
        d[to] = d[v] + cost;
        pq.push(edge(to, d[to]));
      }
    }
  }
}

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

scanf("%d %d %d", &n, &m, &k);
c.resize(k);
for (i = 0; i < k; i++)
  scanf("%d", &c[i]);

Read the input weighted graph.

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

Run Dijkstra's algorithm from the cities where the guests live.

dp.resize(n + 1);
for (i = 0; i < k; i++)
{
  Dijkstra(g, dist, c[i]);

  for (j = 1; j <= n; j++)
   dp[j] += dist[j];
}

Currently, $d p [i]$ contains the sum of the shortest distances from vertex $i$ to all the cities where the guests are located. The next step is to find the minimum value among the elements of the $d p$ array and print the corresponding result. The variable $pt r$ stores the smallest vertex number where the server should be placed.

res = INF;
for (i = 1; i <= n; i++)
{
  if (dp[i] < res)
  {
    res = dp[i];
    ptr = i;
  }
}

Print the answer.

printf("%d %d\n", ptr, dp[ptr]);

Comments

Nothing yet

Be the first one to start the conversation!

Loading

Just a moment, getting data from the server