February 6, 2019 Single Round Match 749 Editorials

SRM 749 was held on 2nd Feb. Thanks to Blue.Mary for the setting the problems and Vasyl[alphacom] for testing the round and penning the editorials.
Div 2 Easy – FightMonsterDiv2
In this problem you have to find a sum of an arithmetic progression with duration terms. The k-th term (0-based) is equal to attack * (1 + level*k/100). Since the size of the given sequence is at most 100,000 the sum can be computed by simple iteration over all the terms.
The time complexity of such approach is O(duration).
As a reference check the following contestant solution:
https://community.topcoder.com/stat?c=problem_solution&cr=40840409&rd=17398&pm=15297


Div 2 Medium – TransformBoardDiv2

In this problem you are given an N by M binary matrix. You can perform the following operation multiple times: choose two different cells in the same row or the same column. Let A is the value in right \ top cell and B is the value in the other chosen cell. If A=B then assign A=0, B=0, otherwise assign A=0, B=1. You are also given a target matrix and your task is to find any sequence of operations which leads to the target matrix.
There are 2^(N*M) distinct binary matrices and N*M*(N – 1 + M – 1) distinct operations. Since the matrix sizes are small there are at most 2^16 different matrices and 96 different operations.
Let’s build a graph which vertices are binary matrices of the given sizes and edges are operations connecting them. Now our task is to find if two given vertices belong to the same connected component and if so build any path between them. This can be done by DFS or BFS. If we run BFS from one of the vertices, we’ll find a path of the minimal length, which is not required though.
The time complexity is O((N + M) * N * M * 2^(N*M)).
For example, see the following solution
https://community.topcoder.com/stat?c=problem_solution&cr=40340114&rd=17398&pm=15299
 

Div 2 Hard – CountSubarrays

In this problem you are given an array of integers and you have to count the number of its contiguous subarrays with a product equal to the given number X modulo 744,444,499 which is a prime number.
First, let’s split the given array by 0 values it contains and get a set of subarrays with no 0 values. Each such subarrays has no 0 products. If X is 0 then the answer can be easily calculated by subtracting the number of subarrays for each of the set subarray from an overall number of subarrays. Otherwise the answer is the sum of answers for each of the set subarrays.
For each set subarray we calculate partial products modulo 744,444,499. Let a partial product at position k (1-based) is P[k] and P[0] = 1. For position k we are looking for values P[k]/X modulo 744,444,499 among P[0], P[1], …, P[k-1]. This can be done by storing value counters in a map. Note that 1/X = X^(744,444,499-2) modulo 744,444,499 as 744,444,499 is prime.
The time complexity is O(N * log(N)).
As a reference check this solution:
https://community.topcoder.com/stat?c=problem_solution&cr=40761556&rd=17398&pm=15301
 

Div 1 Easy – FightMonsterDiv1

In this problem you are given an infinite arithmetic progression. The k-th term (0-based) is equal to attack * (1 + level*k/100). Let T be the minimal integer such that the sum of the first T terms of the given sequence is at least hp. You have to minimize a time and there are two options:
* find T, time = T;
* multiply any duration consecutive terms of the sequence by 5, find T, time = T+1;
We can find the minimal time independently for both options and then choose a smaller one. In order to find T we could iterate over the sequence terms and stop as soon as we have at least hp as a sum. However this approach could be too slow as hp might be as large as 10^12.
Since all sequence terms are positive, a binary search can be used to find T instead. Basically at each binary search iteration we fix T and compute a partial sum using arithmetic series formulas.
For the second option note that the given progression is non decreasing. Thus it is always optimal to multiply terms with larger indices. A partial sequence sum in this case can be computed as a sum of two arithmetic series.
The time complexity is O(log(hp)).
For example, check this solution
https://community.topcoder.com/stat?c=problem_solution&cr=10574855&rd=17398&pm=15296
Note that you have to be careful in order to avoid integer overflows. One of the possible solutions is to use 128 bit integers, like in
https://community.topcoder.com/stat?c=problem_solution&cr=22692969&rd=17398&pm=15296
 

Div 1 Medium – TransformBoardDiv1

In this problem you are given an N by M binary matrix. You can perform the following operation multiple times: choose two different cells in the same row or the same column. Let A is the value in right \ top cell and B is the value in the other chosen cell. If A=B then assign A=0, B=0, otherwise assign A=0, B=1. You are also given a target matrix and your task is to find any sequence of operations which leads to the target matrix.
The following two observations help to come up with a solution:
* any two 1s can be replaced with two 0s in one or two operations;
* 1 located at (r1, c1) and 0 located at (r2, c2) such that r1 <= r2 and c1 <= c2 can be swapped in one or two operations.
Let’s try to construct a solution in two stages:
* every 1 in the target matrix corresponds to 1 in the current matrix
* target and current matrices are the same
Stage 1. It’s easy to see that each 1 can be only moved down and right. Let’s iterate the target matrix from the top to the bottom and from the left to the right. If at position (r1, c1) target matrix contains 1 and current matrix contains 0 we have to find a free 1 in the current matrix and move it to (r1, c1). For that purpose we can consider all cells (r2, c2) such that target matrix contains 0 at (r2, c2), current matrix contains 1 at (r2, c2) and r2 <= r1, c2 <= c1. Note that greedy approach works here and it’s always optimal to choose any such cell with the maximal c2.
Stage 2. If stage 1 is completed successfully consider all cells where target and current matrices differ. Obviously if the number of such cells is odd we can not complete stage 2. Otherwise use the first observation to get rid of all free 1s in the current matrix.
Note that the total number of operations is at most the number of cells. The time complexity is O(n^2 * m^2) for the simplest implementation which can be easily optimized to O(n^2 * m).
For example, check this implementation
https://community.topcoder.com/stat?c=problem_solution&cr=15881985&rd=17398&pm=15298
 

Div 1 Hard – TurnOffLightsDiv1

In this problem you have to find a minimal length cycle which should include a given set of vertices in a specific graph.
Assume we are at a stair cell of some floor. Sometimes it makes sense to move around the floor and then get back to the initial stair cell. However we must not do it more than once for each stair cell. Moreover if we do such returns from both floor ends some its cells might be never visited. Obviously it is optimal to have the longest floor gap (continuous subinterval with no lights) unvisited.
Now let’s build a dynamic programming solution where a floor can be in one of four states:
* no lights are visited
* all lights are visited
* only lights to the left of the longest gap are visited
* only lights to the right of the longest gap are visited
A DP state can be described as a set of floor states plus a current stair position.
Transitions between states are the following:
* move up or down if possible
* move to the other end of the floor and mark it as visited
* move to the corresponding floor gap and return, update the floor state.
We can use Dijkstra algorithm to find the minimal distance to the final state. Note that the answer does not exceed two times number of the given cells. Thus instead of a priority queue it is enough to have a regular deque for each possible value.
The time complexity is O(N * 4^N).
Check the following solution for a reference
https://community.topcoder.com/stat?c=problem_solution&cr=22692969&rd=17398&pm=15300