Mmedv7 months ago

Educational Round #8 — Editorial

Read the number of toy types $n$ .

scanf("%d",&n);

Accumulate the number of required toys in the variable $r es$ .

res = 0;

Read and process the information about each toy type.

for (i = 0; i < n; i++)
{
  scanf("%d %lf",&num,&price);
  if (price < 50.0) res += num;
}

Print the answer.

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

Eolymp #1427. Calculator

Vasya is a student who has a younger brother, Petya. Petya has just started first grade and began learning arithmetic. For homework, he was given many addition and subtraction problems. Petya asked Vasya to check his work. Seeing two pages full of problems, Vasya was shocked by the amount of work and decided to teach Petya to use a computer for self-checking. To do this, Vasya decided to write a program that calculates the answers to the arithmetic problems.

Input. One line contains digits and the symbols ' $+$ ' and ' $-$ '. The length of the line does not exceed $1 0^{4}$ 10^4, and the value of each number in the line does not exceed $1 0^{4}$ 10^4.

Output. Print one integer — the result of the calculation.

Open problem

Read the first term into the variable $r es$ .

scanf("%d",&res);

Read the operation sign $c h$ (addition or subtraction), followed by an integer $x$ . Add $x$ to or subtract it from the total result $r es$ .

while (scanf("%c%d", &ch, &x) == 2)
  if (ch == '+') res += x; else res -= x;

Print the result of the computations.

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

Algorithm implementation — iostream

Read the first term into the variable $r es$ .

cin >> res;

Read the input data until the end of the file. Read the operation sign $c h$ (either addition or subtraction) and the number $x$ that follows it.

while (cin >> ch >> x)

Add $x$ to $r es$ or subtract $x$ from $r es$ .

  if (ch == '+') res += x; else res -= x;

Print the result of the computations.

cout << res << endl;

Eolymp #4283. Stepan and pairs

Stepan is interested in the greatest common divisor of a pair of numbers, namely $GC D (x, y)$ GCD(x, y). Given an integer $n$ , Stepan wants to know how many pairs of integers $(i, j)$ exist such that $1 \leq i, j \leq n$ 1 \le i, j \le n and $i = GC D (i, j)$ i = GCD(i, j).

Input. One integer $n (1 \leq n \leq 1 0^{6})$ n~(1 \le n \le 10^6).

Output. Print the number of such pairs.

Open problem

Eolymp #7534. Locked Treasure

A group of $n$ bandits has hidden a stolen treasure in a room. The door to the room should be unlocked only when it is necessary to take the treasure out. Since the bandits do not trust each other, they want to be able to open the room and take the loot only if at least $m$ of them agree to do so.

They decided to install several locks on the door in such a way that it opens only when all the locks are opened. Each lock may have up to $n$ keys, distributed among some subset of the bandits. A group of bandits can open a lock if and only if at least one member of the group possesses a key to that lock.

Given the values $n$ and $m$ , determine the minimum possible number of locks such that, with a proper distribution of keys every group consisting of at least $m$ bandits can open all the locks, while no group of smaller size can open all the locks.

For example, when $n = 3$ and $m = 2$ , it is sufficient to have $3$ locks. The keys to lock $1$ are given to bandits $1$ and $2$ , the keys to lock $2$ are given to bandits $1$ and $3$ , and the keys to lock $3$ are given to bandits $2$ and $3$ . No bandit can open all the locks alone, but any group of two bandits can open all of them. It is easy to see that two locks are not sufficient in this case.

Input. The first line contains the number of test cases. Each of the following lines corresponds to one test case and contains two integers $n (1 \leq n \leq 30)$ n~(1 \le n \le 30) and $m (1 \leq m \leq n)$ m~(1 \le m \le n).

Output. For each test case, print the minimum number of required locks on a separate line.

Open problem

Consider an arbitrary group of $m - 1$ m - 1 bandits. According to the conditions, this group must not be able to open the door. That means there must exist at least one lock for which none of these $m - 1$ m - 1 bandits has a key.

Therefore, for every subset of bandits of size $m - 1$ m - 1, there must exist a corresponding lock whose keys are not given to any member of that subset.

Consider the following constructive key distribution algorithm:

For each subset of bandits of size $m - 1$ m - 1, create one lock.
The keys to this lock are given to all the remaining bandits; that is, the keys are received by $n - (m - 1) = n - m + 1$ n - (m - 1) = n - m + 1 bandits.

The algorithm is correct because:

For a group of $m - 1$ m - 1 people, none of them has a key to their corresponding lock. Therefore, the door cannot be opened.
Now consider a group of $m$ people. Take any lock. It is "forbidden" only for one specific subset of $m - 1$ m - 1 bandits. In a group of $m$ people, there is necessarily at least one person outside this subset. Hence, the group has a key to every lock.

The minimum number of required locks is equal to $C_{n}^{m - 1}$ C_n^{m-1}, which is the number of subsets of size $m - 1$ m - 1 taken from a set of $n$ elements.

Example

Let there be $n = 4$ bandits.

For $m = 1$ , the number of locks is $C_{4}^{0} = 1$ C_4^0 = 1.

Lock	Subset	Keys
1	{}	1, 2, 3, 4

Each bandit should be given a key to the single lock.

For $m = 2$ , the number of locks is $C_{4}^{1} = 4$ C_4^1 = 4.

Lock	Subset	Keys
1	{1}	2, 3, 4
2	{2}	1, 3, 4
3	{3}	1, 2, 4
4	{4}	1, 2, 3

The optimal distribution of locks among the bandits is as follows:

Any two bandits will be able to open all four locks and take the treasure.

For $m = 3$ , the number of locks is $C_{4}^{2} = 6$ C_4^2 = 6.

Lock	Subset	Keys
1	{1, 2}	3, 4
2	{1, 3}	2, 4
3	{1, 4}	2, 3
4	{2, 3}	1, 4
5	{2, 4}	1, 3
6	{3, 4}	1, 2

The optimal distribution of locks among the bandits is as follows:

Any two bandits will be missing the key to exactly one lock. Any three bandits will be able to open all six locks and take the treasure.

For $m = 4$ , the number of locks is $C_{4}^{3} = 4$ C_4^3 = 4.

Lock	Subset	Keys
1	{1, 2, 3}	4
2	{1, 2, 4}	3
3	{1, 3, 4}	2
4	{2, 3, 4}	1

The optimal distribution of locks among the bandits is as follows:

In order to open all four locks, each bandit must bring his single unique key.

Now consider the case $n = 5, m = 3$ n = 5, m = 3. The number of locks is $C_{5}^{2} = 10$ C_5^2 = 10.

Lock	Subset	Keys	Lock	Subset	Keys
1	{1, 2}	3, 4, 5	6	{2, 4}	1, 3, 5
2	{1, 3}	2, 4, 5	7	{2, 5}	1, 3, 4
3	{1, 4}	2, 3, 5	8	{3, 4}	1, 2, 5
4	{1, 5}	2, 3, 4	9	{3, 5}	1, 2, 4
5	{2, 3}	1, 4, 5	10	{4, 5}	1, 2, 3

The optimal distribution of locks among the bandits is as follows:

In the cells $c nk [n] [k]$ cnk[n][k] we compute the values of the binomial coefficients $C_{n}^{k}$ C_n^k.

#define MAX 31
long long cnk[MAX][MAX];

The function FillCnk fills the array $c nk$ with the values of the binomial coefficients.

void FillCnk(void)
{
  memset(cnk,0,sizeof(cnk));
  for (int n = 0; n < MAX; n++) cnk[n][0] = 1;
  for (int n = 1; n < MAX; n++)
  for (int k = 1; k <= MAX; k++)
    cnk[n][k] = cnk[n-1][k] + cnk[n-1][k-1];
}

C++

The main part of the program. Call the function FillCnk.

FillCnk();

Read the number of test cases $t es t s$ .

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

Read the input data for the current test case and print the answer.

  scanf("%d %d",&n,&m);
  printf("%lld\n",cnk[n][m-1]);
}

Eolymp #10682. Hotels Along the Croatian Coast

Along the beautiful Adriatic coast, there are $n$ hotels. Each hotel has its cost in euros.

Petr won $m$ euros in the lottery. Now he wants to buy a sequence of consecutive hotels one after another so that the sum of the costs of these consecutive hotels is as large as possible, but does not exceed $m$ .

You need to calculate this maximum possible total cost.

Input. The first line contains two integers $n$ and $m (1 \leq n \leq 3 \cdot 1 0^{5}, 1 \leq m < 2^{31})$ m~(1 \le n \le 3 \cdot 10^5, 1 \le m < 2^{31}). The next line contains $n$ positive integers less than $1 0^{6}$ 10^6, representing the costs of the hotels in the order they are located along the coast.

Output. Print the desired maximum cost (it will be greater than $0$ in all tests).

Open problem

Read the input data.

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

Initialize the variables:

in $r es$ , the maximum value among the costs of all processed good intervals is computed;
in $s$ , the sum of numbers in the current interval $[i ... j]$ is maintained. All the numbers in the current interval $[i ... j]$ are stored in the queue $q$ ;

s = res = 0;

Process the hotel costs sequentially.

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

Read and add the cost $v a l$ of the current hotel to the queue.

  scanf("%d", &val);
  q.push(val);

Update the sum $s$ within the interval. All elements of the current interval are stored in the queue $q$ .

  s += val;

If the sum of numbers in the current interval exceeds $s$ , we remove elements from the beginning of the interval.

  while (s > m)
  {
    s -= q.front();
    q.pop();
  }

Compute the maximum value $r es$ among the sums of elements in good intervals (where the cost of hotels does not exceed $m$ ).

  if (s > res) res = s;
}

Print the answer.

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

Eolymp #1571. What is the probability?

Probability is often an integral part of computer algorithms. When deterministic algorithms are unable to solve a problem within a reasonable amount of time, probabilistic algorithms come to the rescue. However, in this problem you are not required to design a probabilistic algorithm — you only need to compute the probability that a particular player wins the game.

The game involves $n$ players who take turns throwing an object similar to a die (the number of faces is not necessarily six). The players move in order: first the first player, then the second, and so on up to the $n$ -th player. If in a given round none of the players wins, the game continues again starting from the first player.

A player wins if, during their turn, a certain event occurs (for example, the number $3$ is rolled, a green face appears, and so on), after which the game ends immediately. The probability that this winning event occurs in a single throw is $p$ .

Determine the probability that the player with number $i$ wins.

Input. The first line contains a single integer $t (t \leq 1000)$ t~(t \le 1000) — the number of test cases. Each of the following $t$ lines contains three values: the number of players $n (n \leq 1000)$ n~(n \le 1000), a real number $p (0 \leq p \leq 1)$ p~(0 \le p \le 1) — the probability of the winning event in a single throw, and the player number $i (1 \leq i \leq n)$ i~(1 \le i \le n) for which the winning probability should be computed.

Output. For each test case, print the probability that the $i$ -th player wins. The answer should be printed with exactly $4$ digits after the decimal point.

Open problem

Let us consider the game from the perspective of probability theory:

Each throw is independent of the others;
The probability of winning on a single throw is $p$ ;
The probability of failure on a single throw is $1 - p$ 1 - p;
The players take turns in a cycle: $1, 2, ..., n, 1, 2, ...$ 1, 2, ..., n, 1, 2, ...;
The game ends immediately as soon as someone wins.

We are interested in the probability that the $i$ -th player wins.

The fact that the $i$ -th player wins means that:

no one has won before his winning throw;
the winning event occurs on his turn.

Moreover, the $i$ -th player may win:

on his first throw;
on his second throw;
on his third throw;
and so on.

The final probability is equal to the sum of the probabilities of all these cases.

For the $i$ -th player to win on his first turn, two conditions must be satisfied:

The first $i - 1$ i - 1 players do not win. The probability of this event is $(1 - p)^{i - 1}$ (1 - p)^{i - 1}
The $i$ -th player wins. The probability of this event is $p$ .

Since the events are independent, the probability that the $i$ -th player wins on his first turn is equal to

p \cdot (1 - p)^{i - 1}

p \cdot (1 - p)^{i - 1}

The $i$ -th player wins on his second turn if:

All $n$ players make one throw each and lose: $(1 - p)^{n}$ (1 - p)^n
The first $i - 1$ i - 1 players lose again in the second round. The probability of this event is $(1 - p)^{i - 1}$ (1 - p)^{i - 1}.
The $i$ -th player wins. The probability of this event is $p$ .

The probability that the $i$ -th player wins on his second turn is equal to

p \cdot (1 - p)^{i - 1} \cdot (1 - p)^{n}

p \cdot (1 - p) ^ {i - 1} \cdot (1 - p)^n

By reasoning in the same way, we obtain that the probability for the $i$ -th player to win on his $k$ -th turn is equal to

p \cdot (1 - p)^{i - 1} \cdot (1 - p)^{n (k - 1)}

p \cdot (1 - p)^{i - 1} \cdot (1 - p)^{n(k - 1)}

Now it remains to sum the obtained probabilities. The overall probability that the $i$ -th player wins is equal to

p \cdot (1 - p)^{i - 1} (1 + (1 - p)^{n} + (1 - p)^{2 n} + .. + (1 - p)^{k n} + ...)

p \cdot (1 - p)^{i-1} (1 + (1 - p)^n + (1 - p)^{2n} + .. + (1 - p)^{kn} + ...)

The expression in parentheses is an infinite geometric progression with first term equal to $1$ and common ratio $(1 - p)^{n}$ (1 - p)^n. The winning probability is equal to

p \cdot (1 - p)^{i - 1} \frac{1}{1 - ( 1 - p ) ^{n}} = \frac{p \cdot ( 1 - p ) ^{i - 1}}{1 - ( 1 - p ) ^{n}}

p \cdot (1 - p)^{i - 1} \frac{1}{1-(1-p)^n} = \frac{p \cdot (1 - p)^{i - 1}}{1 - (1 - p)^n}

It should be noted separately that when $p = 0$ p = 0, the answer is $0$ .

Read the input data.

scanf("%d",&t);
while(t--)
{
  scanf("%d %lf %d",&n,&p,&i);

If the probability $p$ is equal to $0$ , print $0$ .

  if (p == 0) printf("0\n");
  else
  {

Otherwise, compute the required probability using the formula given above. Print the result with $4$ digits after the decimal point.

    res = p * pow(1 - p,i - 1) / (1 - pow(1 - p,n));
    printf("%.4lf\n",res);
  }
}

Eolymp #5363. Drying

Washing clothes in winter is no easy task, and drying them is even more challenging. But Jane is a clever girl and isn't afraid of routine chores. To speed up the drying process, she decided to use a radiator. However, the radiator is small and can dry only one item at a time.

Jane wants to dry the laundry as quickly as possible. She's asking you to write a program that determines the minimum amount of time needed to dry the entire set of clothes.

Jane has just washed $n$ items. During the wash, each item absorbed $a_{i}$ a_i units of water. Every minute, the amount of water in each item decreases by $1$ (as long as the item is not yet dry). Once the amount of water reaches $0$ , the item is considered dry and can be packed.

Additionally, each minute, Jane can choose one item and place it on the radiator. The radiator is hot enough that an item placed on it loses $k$ units of water per minute (but no more than the amount of water it contains: if an item has less than $k$ units of water, it simply dries completely in that minute).

Your task is to determine the minimum amount of time needed to dry all the clothes with optimal use of the radiator. Drying is considered complete when all items are fully dry.

Input. The first line contains one integer $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) — the number of items.

The second line contains $n$ integers $a_{i} (1 \leq a_{i} \leq 1 0^{9})$ a_i~(1 \le a_i \le 10^9), where $a_{i}$ a_i is the amount of water in the $i$ -th item after washing.

The third line contains one integer $k (1 \leq k \leq 1 0^{9})$ k~(1 \le k \le 10^9) — the evaporation rate of water from an item placed on the radiator (in units of water per minute).

Output. Print one integer — the minimum number of minutes required to completely dry all items.

Open problem

Let $ma x$ be the largest value among all $a_{i}$ a_i. Obviously, after $ma x$ minutes, all the laundry will dry naturally, even without using the radiator.

Let the answer be a value $m$ . This means that all items containing at most $m$ units of water will have enough time to dry naturally. Any item that contains more than $m$ units of water will require additional drying on the radiator.

We assume that each item loses $1$ unit of water per minute, regardless of whether it is on the radiator or not. However, if an item is placed on the radiator, it loses an additional $k - 1$ k - 1 units of water per minute, meaning it loses $k$ units per minute in total.

If $m$ minutes are enough to dry all the items, then each item with $a_{i} > m$ a_i > m must be additionally dried using the radiator. The amount of water that won't evaporate naturally is $a_{i} - m$ a_i - m. Since the radiator removes $k - 1$ k - 1 extra units of water per minute, this item will require

⌈ \frac{a _{i} - m}{k - 1} ⌉

\left\lceil {a_i - m \over k - 1} \right\rceil

minutes of radiator time.

The total number of minutes $i = 1 \sum n ⌈(a_{i} - m) / (k - 1)⌉$ \displaystyle \sum_{i=1}^n \lceil (a_i - m) / (k - 1) \rceil the radiator is used must not exceed $m$ , since only one item can be dried per minute. The summation is taken over all indices i for which $a_{i} > m$ a_i > m.

Thus, the check is performed as follows: if, for a given value of $m$ , the total required radiator time does not exceed $m$ , then this value of $m$ is considered valid. The smallest valid value of $m$ can be found using binary search.

Example

Initially, there are three items with water amounts: $(2, 3, 9)$ (2, 3, 9).

In the first minute, place the third item on the radiator. The state becomes: $(1, 2, 4)$ (1, 2, 4).

In the second minute, again place the third item on the radiator. The state becomes: $(0, 1, 0)$ (0, 1, 0).

In the third minute, the second item dries naturally. The final state is: $(0, 0, 0)$ (0, 0, 0).

Let's consider the value $m = 2$ . In this case, all items containing no more than $2$ units of water will dry naturally.

The remaining items will require drying using the radiator.

The second item contains $3$ units of water, so the radiator needs to remove $3 - 2 = 1$ 3 - 2 = 1 unit.

The third item contains $9$ units of water, so the radiator needs to remove $9 - 2 = 7$ 9 - 2 = 7 units.

This will take $⌈ 1/4 ⌉ + ⌈ 7/4 ⌉ = 3$ \lceil 1/4 \rceil + \lceil 7/4 \rceil = 3 minutes. This exceeds $m = 2$ , so two minutes are not enough.

Declare the array.

#define MAX 100001
int a[MAX];

Read the input data.

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

In $r$ minutes, all the laundry will definitely dry, even without using the radiator.

l = 0; r = *max_element(a,a+n);

If $k \leq 1$ k \le 1, then drying with the radiator is equivalent to natural drying, and the radiator provides no advantage.

if (k <= 1) 
{
  printf("%d\n",r); return 0;
}

The minimum required number of minutes $m$ can be found using binary search on the interval $[l; r]$ [l; r].

while (r - l > 1)
{
  m = (r + l) / 2;

The variable $d r y$ accumulates the total number of minutes during which the radiator needs to be used. All the laundry must be dried within $m$ minutes.

  dry = 0;
  for (i = 0; i < n; i++)  
  {
    if (a[i] > m) 
      dry += (a[i] - m + k - 2) / (k - 1);
    if (dry > m) break;
  }
  if (dry > m) l = m; else r = m;
}

C++

Print the answer.

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

Eolymp #11058. Chasing a butterfly

On clear summer days, Nyusha enjoys catching butterflies in the fresh air. But today, she encountered a particularly cunning butterfly — it flew into a labyrinth and tried to hide from her inside.

The labyrinth consists of $n$ rooms, numbered from $1$ to $n$ , some of which are connected by corridors. It is known that there is exactly one simple path between any two rooms, passing only through the corridors. In other words, the labyrinth forms a tree with $n$ vertices and $n - 1$ n - 1 edges.

The entrance to the labyrinth is located in room number $1$ . A leaf is defined as any room connected to exactly one other room and not being the root (i.e., not room $1$ ). Each leaf contains an exit from the labyrinth. The butterfly starts its flight from room $1$ , heading toward one of the exits. It moves at a constant speed, never turns around, and travels through one corridor per minute, moving to a neighboring room. All corridors are of equal length.

To catch the butterfly, Nyusha decided to enlist the help of some friends. Initially, each of them can take position in any room that contains an exit. As soon as the butterfly begins its journey from the entrance toward some exit, the friends may immediately start moving from their rooms toward the entrance. They move at the same speed as the butterfly. If any of them encounters the butterfly — whether in a room or in the middle of a corridor — it is considered caught. However, if the butterfly reaches an exit without encountering any of the friends, it successfully escapes to freedom.

Help Nyusha determine the minimum number of friends needed to guarantee catching the butterfly, regardless of which exit it chooses.

Input. The first line contains a single integer $n (2 \leq n \leq 200000)$ n~(2 \le n \le 200000) — the number of rooms in the labyrinth.

The following $n - 1$ n - 1 lines describe the corridors connecting the rooms. Each line contains two integers $u$ and $v (1 \leq u, v \leq n, u \neq = v)$ v~(1 \le u, v \le n, u \neq v) — the indices of the rooms connected by a corridor.

It is guaranteed that the given corridor system forms a tree.

Output. Print a single integer — the minimum number of friends required to guarantee that the butterfly will be caught.

Open problem

Perform a depth-first search starting from vertex $1$ . For each vertex, compute two values:

$d [v]$ — the distance from vertex $1$ to vertex $v$ . If $p$ is the parent of $v$ , then
$d [v] = d [p] + 1$
d[v] = d[p] + 1
$h [v]$ — the distance from vertex v to the nearest leaf in the subtree rooted at $v$ . If $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k are the children of vertex $v$ , then
$h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])$
h[v] = 1 + min(h[to_1], h[to_2], ..., h[to_k])
If $v$ is a leaf of the tree, set $h [v] = 0$ h[v] = 0.

Next, perform a second depth-first search. During this traversal, compute the value $r es [v]$ — the minimum number of friends that need to be placed in some of the leaves of the subtree rooted at vertex $v$ in order to guarantee catching the butterfly, assuming it chooses to fly into this subtree.

If $h [v] \leq d [v]$ h[v] \le d[v], then $r es [v] = 1$ res[v] = 1. In this case, it is enough to place one friend in the leaf with the minimal depth in the subtree rooted at vertex $v$ : they will reach vertex $v$ no later than the butterfly flying from the root.

Otherwise, if $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k are the children of vertex $v$ , then

r es [v] = r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}]

res[v] = res[to_1] + res[to_2] + ... + res[to_k]

If the butterfly is not caught at vertex $v$ itself, we must be prepared to intercept it in any of the subtrees of $v$ 's children.

The final answer to the problem is the value $r es [1]$ .

Example

In the first example (shown in the left diagram), two friends are required, and they should be placed at the two exits. The butterfly can fly from vertex $1$ either to vertex $2$ or to vertex $3$ . In either case, it will be intercepted by one of Nyusha's friends.

In the second example (shown in the right diagram), one friend is enough, who can be placed at either of the two exits — vertex $3$ or $4$ . The butterfly will fly from vertex $1$ to vertex $2$ in one minute. During that same time, the friend will reach vertex $2$ and catch the butterfly there.

Let us consider the next example.

Nyusha will need three friends to catch the butterfly.

Declare a constant for infinity and arrays.

#define INF 2000000000
vector<vector<int> > g;
vector<int> d, h, res;

The function dfs $(v, p, c n t)$ (v, p, cnt) performs a depth-first search starting from vertex $v$ and returns the value $h [v]$ . Here, $p$ is the parent of vertex $v$ , and cnt is the distance from vertex $1$ to $v$ . During the traversal, the values $d [v]$ and $h [v]$ are computed for each vertex $v$ .

int dfs(int v, int p = -1, int cnt = 0)
{

The value $c n t$ , which equals the distance from vertex $1$ to $v$ , is stored in $d [v]$ .

  d[v] = cnt;
  int height = INF;

Iterate over all the children of the vertex $v$ . Consider the edge $v \to t o$ v \to to. If $t o$ equals the parent of $v (t o = p)$ v~(to = p), skip it and move to the next child.

  for (int to : g[v])
    if (to != p)

In the variable $h e i g h t$ compute the value

min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}]),

min(h[to_1], h[to_2], ..., h[to_k]),

where $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k are the children of vertex $v$ .

h e i g h t = min (h e i g h t, df s (t o, v, c n t + 1));

height = min(height, dfs(to, v, cnt + 1));

If $h e i g h t = I N F$ height = INF, then vertex $v$ is a leaf, and set $h [v] = 0$ h[v] = 0. Otherwise rerturn

h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])

h[v] = 1 + min(h[to_1], h[to_2], ..., h[to_k])

  return h[v] = (height == INF) ? 0 : 1 + height;
}

The function dfs2 $(v, p)$ performs a depth-first search starting from vertex $v$ and returns the value $r es [v]$ . Here, $p$ is the parent of vertex $v$ .

int dfs2(int v, int p = -1)
{
  int s = 0;

Let $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k be the children of vertex $v$ . In the variable $s$ , compute the sum:

r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}]

res[to_1] + res[to_2] + ... + res[to_k]

  for (int to : g[v])
    if (to != p)
    {
      dfs2(to, v);
      s += res[to];
    }

If $h [v] \leq d [v]$ h[v] \le d[v], then one friend is sufficient, and $r es [v] = 1$ res[v] = 1. Otherwise

r es [v] = r es [t o_{1}] + r es [t o_{2}] + ... + r es [t o_{k}] = s

res[v] = res[to_1] + res[to_2] + ... + res[to_k] = s

  return res[v] = (h[v] <= d[v]) ? 1 : s;
}

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

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

C++

Initialize the arrays.

d.resize(n + 1);
h.resize(n + 1);
res.resize(n + 1);

Run two depth-first searches. The first traversal computes the values of $d [v]$ and $h [v]$ for each vertex $v$ .

dfs(1);
dfs2(1);

Print the answer — the minimum number of friends needed to catch the butterfly.

printf("%lld\n", res[1]);

Eolymp #4104. Distance in Tree

A connected graph that contains no cycles is called a tree.

The distance between two vertices of a tree is defined as the length (in edges) of the shortest path connecting them.

Given a tree with $n$ vertices and a positive integer $k$ , calculate the number of distinct pairs of vertices in the tree whose distance is exactly $k$ . Note that the pairs $(v, u)$ and $(u, v)$ are considered the same.

Input. The first line contains two integers $n$ and $k (1 \leq n \leq 50000, 1 \leq k \leq 500)$ k~(1 \le n \le 50000, 1 \le k \le 500) — the number of vertices in the tree and the required distance between vertices.

Each of the following $n - 1$ n - 1 lines describes an edge of the tree in the format $a_{i} b_{i} (1 \leq a_{i}, b_{i} \leq n, a_{i} \neq = b_{i})$ a_i~b_i~(1 \le a_i, b_i \le n, a_i \ne b_i), where $a_{i}$ a_i and $b_{i}$ b_i are the vertices connected by the $i$ -th edge. All edges are distinct.

Output. Print one integer — the number of distinct pairs of vertices in the tree whose distance is exactly $k$ .

Open problem

Let $d p [v] [x]$ dp[v][x] denote the number of vertices at distance $x$ from vertex $v$ in the subtree rooted at $v$ . Set $d p [v] [0] = 1$ dp[v][0] = 1, since the only vertex at distance $0$ from $v$ is $v$ itself.

Suppose that vertex $v$ has children $u_{1}, u_{2}, ..., u_{p}$ u_1, u_2, ..., u_p. Then the number of vertices at distance $x$ from vertex $v$ in the subtree rooted at $v$ is equal to the sum of the numbers of vertices at distance $x - 1$ x - 1 from each of the vertices $u_{1}, u_{2}, ..., u_{p}$ u_1, u_2, ..., u_p.

d p [v] [x] = i = 1 \sum p d p [u_{i}] [x - 1]

dp[v][x] = \sum_{i = 1}^p dp[u_i][x-1]

Consider the subtree rooted at vertex $v$ . Let's count the number of paths of length $k$ that lie entirely within this subtree and pass through vertex $v$ . We divide such paths into two groups:

paths that start at vertex $v$ . Their number is equal to $d p [v] [k]$ dp[v][k].
paths that pass through vertex $v$ and whose endpoints are located in the subtrees of the children of vertex $v$ .

Consider a path of length $k$ that passes through the root of the subtree $v$ . Let the distance from vertex $v$ to one end of the path be $x (1 \leq x \leq k - 1)$ x~(1 \le x \le k - 1). Suppose this end lies in the subtree of some child $u_{1}$ u_1. Then the distance from $v$ to the other end of the path is $k - x$ k - x, and this other end can be located in any other subtree except the subtree rooted at $u_{1}$ u_1.

If the distance from the first end of the path to vertex $v$ is $x$ , then the distance from this end to vertex $u_{1}$ u_1 is $x - 1$ x - 1. The number of ways to choose such a first end is $d p [u_{1}] [x - 1]$ dp[u_1][x - 1].

The number of ways to choose the second end of the path is equal to the number of vertices at distance $k - x$ k - x from vertex $v$ that do not belong to the subtree rooted at $u_{1}$ u_1. This number is

d p [v] [k - x] - d p [u_{1}] [k - x - 1]

dp[v][k - x] - dp[u_1][k - x - 1]

According to the multiplication principle, the total number of such paths is

d p [u_{1}] [x - 1] \cdot (d p [v] [k - x] - d p [u_{1}] [k - x - 1])

dp[u_1][x - 1] \cdot (dp[v][k - x] - dp[u_1][k - x - 1])

Thus, the total number of such paths is

d p [v] [k] + 1/2 i = 1 \sum p x = 1 \sum k - 1 d p [u_{i}] [x - 1] \cdot (d p [v] [k - x] - d p [u_{i}] [k - x - 1])

dp[v][k] + 1/2 \sum_{i = 1}^p \sum_{x = 1}^{k - 1} dp[u_i][x-1] \cdot (dp[v][k-x]-dp[u_i][k-x-1])

It remains to sum the above expression over all vertices of the tree.

Example

Consider the tree presented in the example.

The array $g$ stores the tree representation in the form of adjacency lists. The array $d p$ is used to implement dynamic programming.

vector<vector<int> > g;
vector<vector<int> > dp;

The function dfs performs a depth-first search starting from vertex $v$ . The value $p$ denotes the parent of vertex $v$ . During the traversal, the $d p$ array is constructed.

void dfs(int v, int p = -1)
{

Initialize the array $d p [v]$ .

  dp[v].resize(k+1);
  dp[v][0] = 1;

Iterate over all vertices $t o$ that can be reached from vertex $v$ .

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

    dfs(to,v);

    for(int x = 1; x <= k; x++)
      dp[v][x] += dp[to][x-1];
  }
}

C++

The function dfsRes performs a depth-first search starting from vertex $v$ and is intended to compute the desired answer.

void dfsRes(int v, int p = -1)
{

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

    dfsRes(to,v);

    for(int x = 1; x < k; x++)
      resA += 1LL * dp[to][x-1] * (dp[v][k-x] - dp[to][k-x-1]);
  }

  resB += dp[v][k];
}

C++

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

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

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

C++

Using the first depth-first search, construct the $d p$ array.

dp.resize(n+1);
dfs(1);

Compute and print the required answer.

resA = resB = 0;
dfsRes(1);
res = resA / 2 + resB;
printf("%lld\n",res);

Eolymp #470. Super palindromes

Let us call a string of length greater than one a palindrome if it reads the same from left to right and from right to left.

A superpalindrome is a string that can be represented as a concatenation of one or more palindromes.

Given a string $s$ , find the number of substrings of $s$ that are superpalindromes.

Input. One string $s (1 \leq ∣ s ∣ \leq 1000)$ s~(1 \le |s| \le 1000) consisting of lowercase Latin letters.

Output. Print one integer — the number of substrings of the string $s$ that are superpalindromes.

Open problem

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

$i \geq j$ i \ge j, that is, the substring is empty or consists of a single character;
$s_{i} = s_{j}$ s_i = s_j and the substring $s_{i + 1} ... s_{j - 1}$ s_{i + 1} ... s_{j - 1} is a palindrome;

Let's define the function IsPal $(i, j)$ , that returns $1$ if the substring $s_{i} ... s_{j}$ s_i ... s_j is a palindrome, and $0$ otherwise.

To speed up the algorithm, the values of $I s P a l (i, j)$ IsPal(i, j) are stored in the cells of a two-dimensional array $p a l [i] [j]$ pal[i][j].

A string is called a superpalindrome if it can be represented as a concatenation of one or more palindromes. For example, the following strings are superpalindromes:

Let

d p [i] [j] = {1, 0, if the substring s_{i} \dots s_{j} (i < j) is a superpalindrome, otherwise .

dp[i][j] = \begin{cases} 1, & \text{if the substring } s_i \ldots s_j\ (i < j) \text{ is a superpalindrome}, \\ 0, & \text{ otherwise}. \end{cases}

Here it is assumed that $i < j$ i < j, that is, the length of the substring is at least two.

Let us note the base cases:

If $i \geq j$ i \ge j, then the substring is either empty or consists of a single character. Such strings are not considered palindromes by definition. Therefore,

d p [i] [j] = 0 при i \geq j

dp[i][j] = 0~при~i ≥ j

In particular, for any position $i$ , we have $d p [i] [i] = 0$ dp[i][i] = 0.

If the substring $s_{i} ... s_{j}$ s_i ... s_j is a palindrome and its length is at least two, then it is automatically a superpalindrome (since it consists of a single palindrome). Therefore, for all pairs of indices $(i, j)$ where $0 \leq i < j < n$ 0 \le i < j < n, if the substring $s_{i} ... s_{j}$ s_i ... s_j is a palindrome, we can immediately set $d p [i] [j] = 1$ dp[i][j] = 1.

Now consider the general case. Let the substring $s_{i} ... s_{j}$ s_i ... s_j not be a palindrome as a whole. It can still be a superpalindrome if it can be split into two parts, each of which is a superpalindrome.

To do this, iterate over all possible split positions $k$ such that $i < k < j - 1$ i < k < j - 1.

The restriction $k < j - 1$ k < j - 1 ensures that both substrings

s_{i} ... s_{k} и s_{k + 1} ... s_{j}

s_i ... s_k~и~s_{k+1} ... s_j

have length at least two, and therefore can potentially be superpalindromes.

If, for some $k$ , the following conditions are satisfied:

$d p [i] [k] = 1$ dp[i][k] = 1,
$d p [k + 1] [j] = 1$ dp[k + 1][j] = 1,

then the substring $s_{i} ... s_{j}$ s_i ... s_j can be represented as a concatenation of two superpalindromes. Therefore, it is itself a superpalindrome, and we set $d p [i] [j] = 1$ dp[i][j] = 1.

If this condition is not satisfied for any valid $k$ , then $d p [i] [j]$ dp[i][j] remains $0$ .

Finally, count the number of pairs $(i, j)$ for which $i < j$ i < j and $d p [i] [j] = 1$ dp[i][j] = 1. This count is exactly the number of substrings of the string $s$ that are superpalindromes.

Example

For the given example — the string " $aba c d c$ " — there are $3$ substrings that are superpalindromes:

For the string " $aaaba$ ", there are $5$ substrings that are superpalindromes:

Declare the arrays.

#define MAX 1010
char s[MAX];
int dp[MAX][MAX];
int pal[MAX][MAX];

The function IsPal $(i, j)$ checks whether the substring $s_{i} \dots s_{j}$ s_i \ldots s_j is a palindrome. The substring $s_{i} \dots s_{j}$ s_i \ldots s_j is a palindrome if $s_{i} = s_{j}$ s_i = s_j and the substring $s_{i + 1} \dots s_{j - 1}$ s_{i + 1} \ldots s_{j - 1} is also a palindrome. The values of the function IsPal $(i, j)$ are stored in the cells of the two-dimensional 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 main part of the program. Read the input string $s$ and compute its length $n$ .

cin >> s; n = s.size();

Initialize the arrays $d p$ and $p a l$ .

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

Iterate over all substrings $s_{i} \dots s_{i + l e n}$ s_i \ldots s_{i + len} of the string $s$ in increasing order of their length $l e n$ . This is important because the value of $d p [i] [j]$ dp[i][j] depends on the values for shorter substrings.

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

The right boundary of the substring $s_{i} \dots s_{i + l e n}$ s_i \ldots s_{i + len} is $j = i + l e n$ j = i + len.

  j = i + len;

If the substring $s_{i} \dots s_{j}$ s_i \ldots s_j is a palindrome, then it is automatically also a superpalindrome.

  if (IsPal(i,j))
  {
    dp[i][j] = 1;
    continue;
  }

If the substring $s_{i} \dots s_{j}$ s_i \ldots s_j is not a palindrome, we try to represent it as a concatenation of two superpalindromes.

If $s_{i} \dots s_{k}$ s_i \ldots s_k and $s_{k + 1} \dots s_{j}$ s_{k+1} \ldots s_j are superpalindromes, then $s_{i} \dots s_{j}$ s_i \ldots s_j is a superpalindrome as well.

  for (k = i + 1; k < j - 1; k++)
    if (dp[i][k] && dp[k + 1][j])
    {
      dp[i][j] = 1;
      break;
    }
}

C++

Count the number of superpalindromes. It is equal to the number of index pairs (i, j) for which dp[i][j] = 1.

res = 0;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
  res += dp[i][j];

Print the answer.

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

Algorithm implementation – recursion

Declare the input string $s$ and arrays.

#define MAX 1010
string s;
int dp[MAX][MAX], pal[MAX][MAX];

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 $1$ if the substring $s_{i} \dots s_{j}$ s_i \ldots s_j is a superpalindrome.

int f(int i, int j)
{

A superpalindrome must contain more than one character.

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

If the value of f $(i, j)$ is already computed, return this value.

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

If the substring $s_{i} \dots s_{j} (i < j)$ s_i \ldots s_j~(i < j) is a palindrome, then it is also a superpalindrome.

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

If the substring $s_{i} \dots s_{k} (i < k)$ s_i \ldots s_k~(i < k) is a palindrome and the substring $s_{k + 1} \dots s_{j} (k + 1 < j)$ s_{k+1} \ldots s_j~(k + 1 < j) is a superpalindrome, then the substring $s_{i} \dots s_{j}$ s_i \ldots s_j is a superpalindrome.

  for (int k = i + 1; k < j - 1; k++)
    if (IsPal(i,k) && f(k + 1,j)) return dp[i][j] = 1;

If none of the conditions described above is satisfied, then the substring $s_{i} \dots s_{j}$ s_i \ldots s_j is not a superpalindrome.

  return dp[i][j] = 0;
}

The main part of the program. Read the input string $s$ and compute its length $n$ .

cin >> s; n = s.size();

Initialize the arrays $d p$ and $p a l$ .

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

In the variable $r es$ count the number of superpalindromes.

res = 0;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
  res += f(i,j);

Print the answer.

cout << res << endl;

Educational Round #8 — Editorial

Comments