First I would like to apologize for the error in the test cases of problem G. All solutions were rejudged and 3 teams/participants were affected, I am very sorry.

Also, thanks to Ashishgup for discovering the error.

I hope you enjoyed the problems in general, below is a brief description of the solutions (if you need a detailed explanation of some problem write in the comments)

Any feedback is appreciated :)

A. Printing Books

While the number of digits left is enough, increase X to the closest power of 10, and subtract the number of digits needed from N. Let's denote the number of digits in X as d(X) and the smallest power of 10 greater than X as p(X).

while (p(X)-X)*d(X) <= N
    N-=(p(X)-X)*d(X)
    X=p(X)
    ans+=p(X)-X

At the end, there might be some leftovers from N, if it is not divisible by d(X), then the answer is -1. Otherwise, add to ans.

B. Ali and Wi-Fi

Let's say you want to join a subset of the given networks, to do this, you must stand in the area of intersection of all the circles of these networks. This area is enclosed by some arcs of the circles and points of intersection of these arcs, the area always contains points of intersection between 2 or more of these circles, or a center of one or more of the circles. So it is possible to obtain the optimal answer at one of the intersection points or at the center of some circle.

This way, we need to check O(n²) points (n centers, and at most 2 points from each pair of circles). To check each point, we go through all circles and store the speeds of the circles that cover this point, then sort these speeds and take the maximum m speeds.

Complexity: O(n³log(n))

C. Shahhoud Training Hussain

Each day, Hussein receives K problems, and solves min(P, K) of them. So he will miss K - min(P, K) problems everyday.

Since we have N days, the answer is N * (K - min(K, P))

Complexity: O(1)

D. Largest Group

For each girl, calculate the mask of the boys that this girl is friends with. Now for each one of the 2^P possible subsets of girls, calculate the bitwise AND of the masks of these girls, the number of 1's in the binary representation of the resulting number is equal to the number of boys that are friends with each of the chosen girls, we add it to the number of chosen girls and we get the answer for this subset. Find the maximum answer between all subsets.

Complexity: O(2^PP)

E. Minesweeper

This problem can be solved using backtrack or DP Bitmask, I will explain the DP solution:

Let's add rows one by one. We represent a row using a mask (0 if its a mine, 1 if its a free cell).

In order to know which mask can be added as the current row, we need to know the masks of the 2 previous rows, and check that the last row can be placed between the current mask and the one before the last.

So we have dp[i][mask1][mask2] is the number of ways to set the first i rows, with the last 2 rows being mask1 and mask2. To calculate it, we loop through all valid masks for the new row and add dp[i + 1][mask2][newMask].

The only thing left is to write a function that takes 3 masks, and checks if the middle row does not violate any of the rules when placed between the other 2 masks.

Complexity: O(rc2^3c)

F. A Missing Problem in TCPC2017

There are many ways to solve this problem, either mark the available problems and then find the unmarked problem, or calculate the sum of the available problems and print n * (n + 1) / 2 - sum, or find the first i that is not equal to a[i] and print it.

Complexity: O(n)

G. Robots

Solution 1:

Sort the robots by x_i, and go through them in decreasing order. Simulate the first query step by step and store in a set the value of edges that this robot goes through. Now for each query, starting from the node that the previous query ends in, keep going up in the tree and deleting those edges from the set until every element in the set is less than x_i. After that, continue simulating the query going down step by step, adding the edges to the set.

Each edge will be added at most once to the set, and it gets deleted when it is larger than all x values left, so it won't be added to the set again.

Complexity: O(nlog(n))

Solution 2:

Sort the robots by x_i.

If a robot x_i and robot x_j (x_i < x_j) pass through a node during their movement, then every other robot x_k such that x_i ≤ x_k ≤ x_j will also pass through this node.

We can start a dfs traversal at node 1 and keep the range of robots that will pass through this node. Then, in each node, we go through the children, and for each one find the range of robots that will go to that child. And also find the range that will end up in this node and add them to the answer.

Complexity: O(n + qlog(q))

H. Buying Products

For each shop, take the two cheapest products, and add them to a set.

The answer is the sum of the cheapest k products in the set.

Complexity: O(nlog(n) + k)

I. A Movie in Byteland

First give each name (ltr and rtl) a number according to it's order lexicographically among all names. and also store for each name whether is has an 'm' or not.

Now we have n pairs of numbers and we need to find the longest increasing subsequence, where a pair (a, b) is bigger than another pair (c, d) if a > c and b > d. We also need to satisfy the rule that any two consecutive names exactly one of them has an 'm' in it.

To solve this problem, we sort the pairs by the first value, then we only need the subsequence to be increasing by the second value.

Use two segment trees, one for the pairs that have an 'm' in it, and one for the pairs that don't. The rest is just like the ordinary nlogn solution for LIS. The answer for the pair that has an 'm' is calculated using the segment tree that doesn't have an 'm' and so on.

Complexity: O(nlog(n))

J. The Volcano Eruption

Create a graph where each circle is a node, and any pair of intersecting circles have an edge between them.

Let's find the number of components that have at least once circle that intersects with each side of the street, this component will cut the street, so we must use a suit to pass it. Therefore the answer is the number of such components.

Complexity: O(n²)

K. Poor Ramzi

Let dp[l][r] be the number of sumindromes that can be achieved from the range [l, r].

To calculate this dp, iterate through all possible prefixes [l, i] and suffixes [j, r] such that i < j and sum(l..i) = sum(j...r) and add dp[i][j] to the answer.

Also add 1 to dp[l][r] to consider summing all the range into one integer.

Complexity: O(n⁴)

L. Eyb0ss

First, we can calculate the sum of maximums alone, and the sum of minimums alone, then subtract them.

How to find the sum of maximums?

Let's consider the linear version of the problem, given n integers, find the sum of maximum numbers in each range [l, r].

To solve this problem, we go through each number and find the number of ranges where this number is the maximum.

We can find the closest number x greater than it before it and the closest number y greater than it after it using a stack.

The current number is the maximum in all ranges that start after x and end before y. We add to the answer the current number multiplied by the number of these ranges.

Now, let's go back to the 2D version.

For each pair of rows r1 and r2 (r1 < r2), we want to calculate the sum of maximums in all rectangles that start at r1 and end at r2. For each column, only the maximum number in this column between r1 and r2 can be a possible maximum in the rectangle. So we find the maximum number in each column and store them in an array, then apply the linear version of the problem on this array.

Note: to simplify the implementation, you can first calculate the sum of maximums, then multiply all the numbers in the array by -1, then find the sum of maximums again and sum the two answers.

Complexity: O(n³)