May 18, 2018 Single Round Match 734 Editorials

The author of this round and editorial is [Vasyl[alphacom]]. The round was held on 16th May 21:00 UTC-4.
Div 2 Easy – TheRoundCityDiv2
In this problem we have to count lattice points on a plane that are at most r units far from the origin.
Obviously we count only points which both coordinates do not exceed r by an absolute value.
Since r is at most 100, we can simply iterate over all lattice points (x, y) where -r <= x, y <= r and count such that x^2 + y^2 <= r^2.
The time complexity is O(r^2).
For example, see the source code:
https://community.topcoder.com/stat?c=problem_solution&cr=23082681&rd=17158&pm=14898

Div 2 Hard – TheRectangularCityDiv2
In this problem you are given a matrix of 0s and 1s.
You have to count the number of paths which
* start at any border cell
* visit all matrix 0s and no matrix 1s
* end at any border cell
Since there are at most 20 matrix cells the problem can be solved using a dynamic programming approach.
We’ll have states with two dimensions:
* mask – the cell binary mask representing a visited cell set
* last – the last visited cell
The state value is the number of ways to visit all the cells represented by the mask and finish in cell last.
The transitions between the states can be done by iterating over all neighbours of the last cell.
For example, see the source code:
https://community.topcoder.com/stat?c=problem_solution&cr=40745004&rd=17158&pm=14902

Div 1 Easy – TheRoundCityDiv1
In this problem we have to count lattice points on a plane that are at most r units far from the origin and are visible from the origin.
A lattice point is visible from the origin if a line segment connecting the point and the origin contains no other lattice points.
Notice that we can first count only visible lattice points (x, y) such that x > 0 and y >= 0 and then multiply the result by 4.
It’s easy to see that for each visible form the origin lattice point (x, y) gcd(x, y) = 1.
Here gcd is the greatest common divisor and we assume (x, y) is not at the origin.
Let’s iterate over all x coordinates from 1 to r, inclusive.
Then we find the maximal possible value of y coordinate maxY = floor(sqrt(r^2 – x^2)).
Now we have to count coprime with x numbers in range [0, maxY].
This can be done by using inclusion–exclusion principle over all distinct prime divisors of x.
The time complexity linearly depends on the total number of prime divisors of integers from 1 to r which is O(r*log(r)).
For example, see the source code:
https://community.topcoder.com/stat?c=problem_solution&cr=22907549&rd=17158&pm=14897

Div 1 Medium – TheSquareCityDiv1
This is a harder version of Div 2 problem TheSquareCityDiv2.
In this problem first you have to construct a matrix of integers.
Then for each cell X we find several values:
1) next(X) – a next cell Y with the maximal value such that a Manhattan distance between X and Y is at most r.
If there are multiple such cells you choose the one with the smallest row and then the one with the smallest column.
If next(X)=X we call cell X a terminal cell.
2) d(X) – a destination cell which can be found using the following rules:
* let d(X) = X;
* while d(X) is not a terminal cell d(X) = next(d(X)).
3) cnt(X) – a number of cells Y such that d(Y) = X.
Finally, we have to find the number of cells X such that cnt(X) > 0 and a maximal value of cnt(X) over all cells.
Let’s construct n(X, R) in the same way as next(X) but instead of r we’ll use variable R.
Then next(X) = n(X, r).
It’s easy to see that for each cell X n(X, 0) = X.
Let X1, X2, X3, X4 are direct neighbours of X, then
n(X, R+1) = max(n(X1, R), n(X2, R), n(X3, R), n(X4, R)).
Thus we can find all values next(X) in O(r*n^2) time.
Now we have a directed acyclic graph defined by next(X).
We can simply find the required values by traversing the graph using dfs or bfs in O(n^2) time.
The overall complexity is O(r*n^2)).

Div 1 Hard – TheRectangularCityDiv1
This is a harder version of Div 2 problem TheRectangularCityDiv2.
In this problem you are given a matrix of 0s and 1s.
You have to count the number of paths which
* start at any border cell
* visit all matrix 0s and no matrix 1s
* end at any border cell
The problem can be solved by dynamic programming with profile.
The profile will consist of n or m (which one is smaller) cells.
Cells on one side of the profile have already been visited and they form several (possibly none) partial paths which may connect to each other and should later form a single final path we are looking for.
The profile configuration describes the way partial paths relate to the profile cells.
Note that we can have up to 5 partial paths in a profile.
The state will have a few dimensions:
* the current cell
* the profile configuration
* the number of opened connections (partial path ends) of the current cell (from 0 to 2)
* the number of the final path ends (from 0 to 2)
The value is the number of ways to get the given configuration.
The transitions between states can be done by iterating over all possible ways how the next cell connects to its neighbours from the current profile (up to 2). Note that the next cell can also be one of the final path ends.