Tutorial•15 日前

Educational Round #8 — Editorial

Let's fix $j$ (for example $j = 12$ ) and find the number of $i$ such that $i = GC D (i, 12)$ .

The values of $i$ that satisfy this equation are $i = 1, 2, 3, 4, 6, 12$ . So, any $i$ that is a divisor of $12$ satisfies the equation $i = GC D (i, 12)$ .

The number of such $i$ for which $i = GC D (i, j)$ is equal to the number of divisors $d (j)$ of $j$ . Since $1 \leq j \leq n$ , we need to find the count of all divisors of numbers from $1$ to $n$ . In other words, we need to find the sum $d (1) + d (2) + ... + d (n)$ . However, calculating $d (n)$ requires factoring the number $n$ , so direct computation of this sum takes $O (n)$ time.

Let's look at the sum of divisors in a different way. Among the divisors of numbers from $1$ to $n$ , one appears $⌊ \frac{n}{1} ⌋$ times, two appears $⌊ \frac{n}{2} ⌋$ times, and so on (the divisor $i$ appears $⌊ \frac{n}{i} ⌋$ times). The number of required pairs of integers is

i = 1 \sum n ⌊ \frac{n}{i} ⌋

This sum can be computed in $O (n)$ time.

Example

For $n = 6$ we have the next pairs:

The number of pairs is

6/1 + 6/2 + 6/3 + 6/4 + 6/5 + 6/6 = = 6 + 3 + 2 + 1 + 1 + 1 = 14

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)$ and $m (1 \leq m \leq 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$ 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$ bandits has a key.

Therefore, for every subset of bandits of size $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$ , 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$ bandits.

The algorithm is correct because:

For a group of $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$ 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}$ , which is the number of subsets of size $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$ .

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

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

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

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$ . The number of locks is $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:

Store the hotel costs in the $a$ array. We’ll call the interval $[i ... j]$ good if the sum of hotel costs within it does not exceed $m$ .

Let’s implement a sliding window using two indices $i$ and $j$ , and maintain it so that the current interval $[i ... j]$ is good. Let $s$ be the sum of hotel costs within the interval $[i ... j]$ . If $s + a [j + 1] \leq m$ , then expand the current interval to $a [i ... j + 1]$ . Otherwise, shrink it to $a [i + 1... j]$ . Find the maximum among the costs of all considered good intervals.

Example

Consider the movement of pointers for the given example.

When $i = 0, j$ moves forward until the sum of numbers in the interval $[i ... j]$ does not exceed $m = 12$ . Stop at the interval $[0...3]$ because the sum there is equal to $10$ , while the sum in the interval $[0...4]$ is equal to $15$ .
When $i = 1$ , we cannot move $j$ forward because the sum in the interval $[1...4]$ is equal to $13$ .
When $i = 2$ move $j$ forward to the interval $[2...4]$ .

The maximum value among all good intervals is equal to $12$ and is achieved in the interval $[2...4]$ .

Read the input data.

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

Initialize the variables:

in $res$ , 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 $res$ 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);

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)$ — the number of test cases. Each of the following $t$ lines contains three values: the number of players $n (n \leq 1000)$ , a real number $p (0 \leq p \leq 1)$ — the probability of the winning event in a single throw, and the player number $i (1 \leq i \leq 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$ ;
The players take turns in a cycle: $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$ players do not win. The probability of this event is $(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}

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

All $n$ players make one throw each and lose: $(1 - p)^{n}$
The first $i - 1$ players lose again in the second round. The probability of this event is $(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}

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

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)^{kn} + ...)

The expression in parentheses is an infinite geometric progression with first term equal to $1$ and common ratio $(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}}

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

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}$ 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})$ — the number of items.

The second line contains $n$ integers $a_{i} (1 \leq a_{i} \leq 1 0^{9})$ , where $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})$ — 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}$ . 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$ 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$ must be additionally dried using the radiator. The amount of water that won't evaporate naturally is $a_{i} - m$ . Since the radiator removes $k - 1$ extra units of water per minute, this item will require

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

minutes of radiator time.

The total number of minutes $i = 1 \sum n ⌈(a_{i} - m) / (k - 1)⌉$ 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$ .

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

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

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

In the third minute, the second item dries naturally. The final state is: $(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$ unit.

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

This will take $⌈ 1/4 ⌉ + ⌈ 7/4 ⌉ = 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$ , 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]$ .

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

The variable $d ry$ 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;
}

Print the answer.

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

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$ 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)$ — the number of rooms in the labyrinth.

The following $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)$ — 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$
$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}$ are the children of vertex $v$ , then
$h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])$
If $v$ is a leaf of the tree, set $h [v] = 0$ .

Next, perform a second depth-first search. During this traversal, compute the value $res [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]$ , then $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}$ are the children of vertex $v$ , then

res [v] = res [t o_{1}] + res [t o_{2}] + ... + res [t o_{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 $res [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)$ 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$ . If $t o$ equals the parent of $v (t o = 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}]),

where $t o_{1}, t o_{2}, ..., t o_{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));

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

h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{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 $res [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}$ be the children of vertex $v$ . In the variable $s$ , compute the sum:

res [t o_{1}] + res [t o_{2}] + ... + res [t o_{k}]

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

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

res [v] = res [t o_{1}] + res [t o_{2}] + ... + res [t o_{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);
}

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

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)$ — the number of vertices in the tree and the required distance between vertices.

Each of the following $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})$ , where $a_{i}$ and $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]$ denote the number of vertices at distance $x$ from vertex $v$ in the subtree rooted at $v$ . Set $d p [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}$ . 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$ from each of the vertices $u_{1}, u_{2}, ..., u_{p}$ .

d p [v] [x] = i = 1 \sum p d p [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]$ .
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)$ . Suppose this end lies in the subtree of some child $u_{1}$ . Then the distance from $v$ to the other end of the path is $k - x$ , and this other end can be located in any other subtree except the subtree rooted at $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}$ is $x - 1$ . The number of ways to choose such a first end is $d p [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$ from vertex $v$ that do not belong to the subtree rooted at $u_{1}$ . This number is

d p [v] [k - x] - d p [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])

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

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

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

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

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

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

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

Let's define the function IsPal $(i, j)$ , that returns $1$ if the substring $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)$ are stored in the cells of a two-dimensional array $p a l [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 .

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

Let us note the base cases:

If $i \geq 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

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

If the substring $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$ , if the substring $s_{i} ... s_{j}$ is a palindrome, we can immediately set $d p [i] [j] = 1$ .

Now consider the general case. Let the substring $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$ .

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

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$ ,
$d p [k + 1] [j] = 1$ ,

then the substring $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$ .

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

Finally, count the number of pairs $(i, j)$ for which $i < j$ and $d p [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}$ is a palindrome. The substring $s_{i} \dots s_{j}$ is a palindrome if $s_{i} = s_{j}$ and the substring $s_{i + 1} \dots 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]$ .

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}$ of the string $s$ in increasing order of their length $l e n$ . This is important because the value of $d p [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}$ is $j = i + l e n$ .

  j = i + len;

If the substring $s_{i} \dots 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}$ is not a palindrome, we try to represent it as a concatenation of two superpalindromes.

If $s_{i} \dots s_{k}$ and $s_{k + 1} \dots s_{j}$ are superpalindromes, then $s_{i} \dots 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;
    }
}

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}$ 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)$ 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)$ is a palindrome and the substring $s_{k + 1} \dots s_{j} (k + 1 < j)$ is a superpalindrome, then the substring $s_{i} \dots 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}$ 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 $res$ 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;

Comments

Nothing yet

Be the first one to start the conversation!

Loading

Just a moment, getting data from the server