July 11, 2019 SRM 762 Editorial

Div 2 Easy – PartitionArray

In this problem you have to find out if it’s possible to divide the given array of integers A into contiguous subarrays each having positive sum of its elements. And if so construct any such partition.

Obviously, if the sum of elements in A is non-positive then no solution exists. Otherwise the array A itself is a valid partition. The time complexity linearly depends on the size of A.

As a reference check the following contestant solution: https://community.topcoder.com/stat?c=problem_solution&cr=40572448&rd=17608&pm=15594

Div 2 Medium – Restrictions

In this problem you have to find the lexicographically smallest n-length array of positive integers satisfying the given set of m constraints. According to the i-th constraint all elements in the contiguous subarray (l[i], r[i]) must be greater \ less than or equal to the given value val[i].

The problem can be solved for each array element independently. Consider an element at index k. What are the minimal and the maximal possible values that can be assigned to it? Let’s iterate over all constraints effective for index k and find the maximum value among all “greater than or equal to” items and denote it with MIN. Similarly we find the minimal value among all “less than or equal to” entries and denote it with MAX. If MIN value exceeds MAX value then no solution exists for the entire problem. Otherwise we assign MIN value to the k-th element of the resulting array. Note that initially MIN is equal to 1 since we are looking for an array of positive integers and MAX is equal to infinity.

The time complexity is O(n*m).

The reference solution:

https://community.topcoder.com/stat?c=problem_solution&cr=40925078&rd=17608&pm=15598

Div 2 Hard – Strawberry

In this problem an array X of length n+1 is being constructed using the following rules:

• X[0] = 0;
• X[2*j + 1] = X[j] + T, where T is an integer chosen at random between 0 and 2*k, inclusive, using the given probabilities A for each value;
• X[2*j + 2] = X[2*j + 1] – R, where R is an integer chosen at random between 0 and 2*k, inclusive, using the given probabilities B for each value.

You have to find the probability that each element of X does not exceed k by its absolute value.

The problem can be solved by a dynamic programming approach, where the state is an index in array X and the corresponding value. The overall number of states is (n+1)*(2*k + 1). The transitions between the states are made by iterating over all possible values of T and R.

The time complexity is O(n*k^2).

The reference solution:

https://community.topcoder.com/stat?c=problem_solution&cr=40869555&rd=17608&pm=15600

Div 1 Easy – LexicographicPartition

In this problem you have to divide the given array of integers A into contiguous subarrays each having positive sum of its elements. A solution is represented as a sequence of partition lengths. Among all valid ways to divide the array you have to find the lexicographically smallest one.

First, note that a solution exists if and only if the sum of the elements in A is positive. In such case the array A itself is a valid partition. The lexicographically smallest partition can be found by using a greedy approach. Let’s try to split A into two parts – the prefix and the suffix such that both have a positive sum of the elements and the prifix contains as few elements as possible. If this is possible recursively solve the same problem for the suffix, otherwise the array A is the only valid partition.

Since the prefix and the suffix sums can be updated in O(1) the overall complexity is O(n) where n is the length of A.

As a reference check the following solution:

https://community.topcoder.com/stat?c=problem_solution&cr=40557524&rd=17608&pm=15597

Div 1 Medium – StrawberryHard

In this problem an array X of length n+1 is being constructed using the following rules:

• X[0] = 0;
• X[2*j + 1] = X[j] + T, where T is an integer chosen at random between 0 and 2*k, inclusive, using the given probabilities A for each value;
• X[2*j + 2] = X[2*j + 1] – R, where R is an integer chosen at random between 0 and 2*k, inclusive, using the given probabilities B for each value.

You have to find the probability that each element of X does not exceed k by its absolute value.

The problem can be solved by a dynamic programming approach, where the state is an index in array X and the corresponding value. The overall number of states is (n+1)*(2*k + 1).

Let dp[j][v] be a probability of a valid construction of the first j elements of X where the last one is equal to v. 

The transitions between the states could be made by simply iterating over all possible values of T and R which would result in O(n*k^2) solution like in div2 version of the problem. However this is too slow and would result in TL.

Since dp[2*j + 1][v] = dp[2*j][v]*T[0] + dp[2*j][v – 1]*T[1] + … 

and dp[2*j + 2][v] = dp[2*j + 1][v]*R[0] + dp[2*j + 1][v + 1]*R[1] + …

transitions between dp[j] and dp[j + 1] can be made faster by applying FFT.

This leads us to O(n*k*log(k)) solution.

The reference solution:

https://community.topcoder.com/stat?c=problem_solution&cr=40869555&rd=17608&pm=15600

Div 1 Hard – DistancePermutation

In this problem you are given a tree with hidden root which is chosen at random. You check the vertices one by one in random order. For each vertex being checked you get a distance from the vertex to the root. Whenever the tree root can be uniquely identified you stop. What is the expected number of vertex checks?

First, let’s fix the tree root and denote it with R. Consider tree vertex V. Let’s denote the following:

• st(V) – the subtree which corresponds to V;
• d(V) – the distance from V to R;
• h(V) – the height of st(V);
• ch(V) – the children of V;
• chst(V) – subtrees which correspond to ch(V).

Consider ch(R) and chst(R). We will stop as soon as we check R or there are two checks in different chst(R). In other words if the first check is located inside one of chst(R) then any check outside of it will identify the root. Which means that all checks in the sequence except for maybe the last one belong to one of chst(R).

Let’s call a vertex V good if except of R all vertices at distance d(V) from V are located in st(V). Note that all ch(R) are good. For each good vertex V we will count the number of non-empty check sequence prefixes from st(V) that does not identify the root or identity the root with its last check.

Let’s call a child C of vertex V deep if h(C) >= d(V)-1 or shallow otherwise. Let deep(V) be the number of deep children of V. Note that if C is a shallow child of V then any check inside st(C) is equivalent to the check of V. 

There are few cases:

1. deep(V) = 0. Any check within st(V) will be the last one.

2. deep(V) = 1. Let W is the deep child of V. If the first check is not inside st(W) then the following check will definitely be the last one. Otherwise at any point a check outside of st(W) will be the last one. So we recursively move from V to W. Note that W is the only good child of V.

3. deep(V) >= 2. No child of V is good. By using a dynamic programming approach we count the check sequence prefixes. The state consists of:

• a number of deep children of V considered;
• the length of the check prefix;
• Is there any deep child C of vertex V with no checks in st(C)?

As a reference check the following solution:

https://community.topcoder.com/stat?c=problem_solution&cr=22263204&rd=17608&pm=14725