Mmedv11 months ago

Educational Round #3 — Editorial

Eolymp #7832. Number of maximums

An array of $n$ integers is given. Find the number of maximum elements in the array.

Input. The first line contains the number $n (n \leq 100)$ n~(n \le 100) — the number of elements in the array. The second line contains $n$ integers, each with an absolute value not exceeding $100$ .

Output. Print the number of maximum elements in the array.

beginrow

Open problem

Declare an array.

int m[101];

Read the input array. Find its maximum element $ma x$ .

scanf("%d", &n);
max = -2000000000;
for (i = 0; i < n; i++)
{
  scanf("%d", &m[i]);
  if (m[i] > max) max = m[i];
}

C++

In the variable $c n t$ , count the number of maximum elements.

cnt = 0;
for (i = 0; i < n; i++)
  if (m[i] == max) cnt++;

Print the answer.

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

Eolymp #8352. Taxi

At rush hour, three taxi buses arrived at the stop simultaneously, all following the same route, and passengers immediately boarded them. The drivers noticed that the number of people in the different buses varied and decided to transfer some passengers so that each bus would have the same number of passengers. Determine the minimum number of passengers that need to be transferred for this.

Input. Three integers, not exceeding $100$ — the number of passengers in the first, second, and third busses, respectively.

Output. Print a single number — the minimum number of passengers that need to be transferred. If this is impossible, print IMPOSSIBLE.

beginrow

Open problem

Read the input data.

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

If the total number of people is not divisible by $3$ , then print IMPOSSIBLE.

if((a + b + c) % 3 != 0)
  puts("IMPOSSIBLE");
else
{
  res = 0;

Compute the number $d$ of people in minibuses after the transfer.

  d = (a + b + c) / 3;

In the variable $r es$ count the number of transfered people.

  if (a > d) res += a - d;
  if (b > d) res += b - d;
  if (c > d) res += c - d;

Print the answer.

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

Eolymp #7335. Saucepans and lids

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)$ n, m~(1 \le n, m \le 1000) — the number of remaining saucepans and lids. The second line contains $n$ integers $a_{i} (1 \leq a_{i} \leq 1000)$ a_i~(1 \le a_i \le 1000) — the radii of the remaining saucepans. The third line contains $m$ integers $b_{i} (1 \leq b_{i} \leq 1000)$ b_i~(1 \le b_i \le 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

Declare arrays to store the radii of saucepans and lids.

#define MAX 1010
int pan[MAX], lid[MAX];

Read the input data.

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

Sort the radii of pans and lids.

sort(pan,pan+n);
sort(lid,lid+m);

Using the greedy method, search for the smallest lid each time that can cover the smallest pan.

for (i = j = 0; (i < n) && (j < m); j++)
  if (pan[i] <= lid[j]) i++;

Print the number of covered pans.

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

Eolymp #1661. Aladdin's knapsack

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}$ w_i and a value of $v_{i} (i = 1, 2, ..., n)$ 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)$ n~(1 \le s \le 250, 1 \le n \le 35) — the maximum weight the backpack can carry and the number of item types.

The next $n$ lines each contain two numbers $w_{i}$ w_i and $v_{i} (1 \leq w_{i} \leq 250, 1 \leq v_{i} \leq 250)$ v_i~(1 \le w_i \le 250, 1 \le v_i \le 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

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)$ 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$ k = 0 or $s = 0$ , the knapsack is empty, and its value is $0$ .

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

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

  if (s < 0) return -INF;

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

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

Compute $f (k, s)$ f(k, s) and store it in $d p [k] [s]$ dp[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));

Eolymp #11269. Lemurian parties - easy

King Julien, the ruler of all lemurs, has exactly $2 \cdot k$ 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$ 10^9 + 7.

Input. A single line contains two integers $k$ and $n (1 \leq k \leq 500000, 0 \leq n \leq 2 \cdot k)$ n~(1 \le k \le 500000,~0 \le n \le 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$ 10^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}$ C_k^i. After this, there will be $n - 2 i$ n - 2i free seats in the VIP area. These seats can be occupied by lemurs from $k - i$ 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}$ C_{k - i}^{n - 2i}.

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}

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

Example

Let's consider a second example, where there are $k = 4$ 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

\sum_{i = 0}^k C_4^i \cdot C_{4 - i}^{3 - 2i} = 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}$ C_n^k to be zero if any of the following three inequalities hold: $k < 0$ k < 0, $n < 0$ n < 0 или $k > n$ k > n.

Let us denote the lemurs by the letters ${a, a, b, b, c, c, d, d}$ \{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$ 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$ 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 $M O D$ ;
$f a c t in v$ factinv contains the values inverse to the factorials of numbers modulo $M O 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$ x^n~mod~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 er y 1 \leq x < p

x^{p-1}~mod~p~=~1~for~every~1 \le x < p

This equality can be rewritten as:

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

(x \cdot x^{p-2})~mod~p~=~1,

which means that the modular inverse of $x$ is $x^{p - 2} m o d p$ x^{p-2}~mod~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 )!}

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

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

C++

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

Eolymp #973. Maximum sum on a tree

Given a tree with $n$ vertices, where the vertex numbered $i (1 \leq i \leq n)$ i~(1 \le i \le n) contains $c_{i}$ 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})$ n~(1 \le n \le 10^5) in a tree. Each of the next $n - 1$ n - 1 lines contains two integers $u$ and $v (1 \leq u, v \leq n)$ v~(1 \le u, v \le n), defining an edge in the tree. The last line contains $n$ non-negative integers $c_{1}, ... c_{n}$ 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)$ dp_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)$ dp_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))$ max(dp_1(1), dp_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 er e t o_{1}, ..., t o_{k} a r e t h e so n s o f v er t e x v .

dp_1(v) = c_v + \sum_{i=1}^k dp_2(to_i), where~to_1, ..., to_k~are~the~sons~of~vertex~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 er e t o_{1}, ..., t o_{k} a r e t h e so n s o f v er t e x v .

dp_2(v) = \sum_{i=1}^k max(dp_1(to_i), dp_2(to_i)), where~to_1, ..., to_k~are~the~sons~of~vertex~v.

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

Example

Let's assign the labels $d p_{1} (v) / d p_{2} (v)$ dp_1(v) / dp_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$ dp_1(1) = c_1 + dp_2(2) + dp_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$ dp_2(1) = max(dp_1(2), dp_2(2)) + max(dp_1(3), dp_2(3)) = 5 + 7 = 12;
$d p_{1} (2) = c_{2} + d p_{2} (4) + d p_{2} (5) = 5 + 0 + 0 = 5$ dp_1(2) = c_2 + dp_2(4) + dp_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$ dp_2(2) = max(dp_1(4), dp_2(4)) + max(dp_1(5), dp_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$ dp1(1) = c_1 + dp_2(2) + dp_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$ dp_2(1) = max(dp_1(2), dp_2(2)) + max(dp_1(3), dp_2(3)) = 11 + 5 = 16;
$d p_{1} (2) = c_{2} + d p_{2} (4) + d p_{2} (5) = 7 + 0 + 0 = 7$ dp_1(2) = c_2 + dp_2(4) + dp_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$ dp_2(2) = max(dp_1(4), dp_2(4)) + max(dp_1(5), dp_2(5)) = 10 + 1 = 11;

Exercise

Assign the labels $d p_{1} (v) / d p_{2} (v)$ dp_1(v) / dp_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}$ dp_1 and $d p_{2}$ dp_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]);
  }
}

C++

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

C++

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

Eolymp #11722. Rectangle Cutting

A rectangle of size $a \times b$ a \times b is given. Your task is to cut it into squares. In one move, you can select one of the rectangles and split it into two new rectangles so that all side lengths remain integers. Determine the minimum number of moves required to complete this task.

Input. Two integers $a$ and $b (1 \leq a, b \leq 500)$ b~(1 \le a, b \le 500).

Output. Print the minimum number of moves required to cut the rectangle into squares.

Open problem

Let's declare constants and the array.

#define MAX 501
#define INF 0x3F3F3F3F

int dp[MAX][MAX];

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

int f(int a, int b)
{

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

  if (a == b) return 0;

If the value of $f (a, b)$ f(a, b) is not computed $(d p [a] [b] = \infty)$ (dp[a][b] = ∞), 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]$ f(a, b) = dp[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));

Eolymp #1405. Sticks

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)$ n~(1 \le n \le 16). The second line contains their lengths — positive integers in the range from $1$ to $1 0^{8}$ 10^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

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]$ sum[mask]. The value $c an [ma s k]$ can[mask] 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$ 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$ can[I] = true. 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;
    }
}

C++

Iterate over all subsets of the set of sticks. If for some subset $I$ there exists a subset $J \subset I$ J \subset I such that $c an [J] = t r u e$ can[J] = true and $c an [I x or J] = t r u e$ can[I~xor~J] = true, 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$ sum[I xor 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);

Eolymp #4073. Its a Murder!

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)$ t~(t \le 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})$ n~(1 \le n \le 10^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}$ 10^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$ Fenwick.

#define MAX 1000001
vector<long long> Fenwick;

The function Summa0_i computes the sum $a_{0} + a_{1} + ... + a_{i}$ 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;
}

C++

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

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$ Fenwick 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}$ a_{value} 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}$ a_0 + a_1 + a_2 + ... + a_{value - 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);
}

Eolymp #10456. Server

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}$ 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})$ n~(1 \le n \le 10^4), m~(1 \le m \le 4 * 10^4), and $k (1 \leq k \leq 100)$ k~(1 \le k \le 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)$ c_i~(1 \le c_i \le n) — the numbers of the cities where the guests live.

Each of the following $m$ lines contains three integers $u_{i}, v_{i}$ u_i, v_i, and $w_{i} (1 \leq u_{i}, v_{i} \leq n)$ w_i~(1 \le u_i, v_i \le n) — describing a bidirectional communication channel between cities $u_{i}$ u_i and $v_{i}$ v_i with a delay of $w_{i} (1 \leq w_{i} \leq 1 0^{4})$ w_i~(1 \le w_i \le 10^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

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)$ (node, dist) 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]));
      }
    }
  }
}

C++

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

C++

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

C++

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

C++

Print the answer.

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

Educational Round #3 — Editorial

Comments