Connect on a Grid (Challenge) SOLUTION CONGRID

Connect on a Grid (Challenge) November Challenge 2020

You are given a grid with N rows (numbered 1 through N from top to bottom) and N columns (numbered 1 through N from left to right). Let’s denote a cell in the i-th row and the j-th column by (i,j).
There are K checkpoints (numbered 1 through K) in the grid. For each valid i, the i-th checkpoint is in the cell (Xi,Yi) and it has two parameters Li and Ri.
A path with length l is a sequence of pairwise distinct cells (r1,c1)→(r2,c2)→…→(rl,cl) such that for each valid i, the cell (ri,ci) shares a side with the cell (ri+1,ci+1). Let’s call the cells (r1,c1) and (rl,cl) the endpoints of the path.
We are interested in sets of paths which satisfy the following conditions:
Each path must start in a checkpoint and end in a different checkpoint. It must not contain any other cells with checkpoints.
The paths are disjoint, i.e. no cell may be in two or more paths.
For each path: let’s denote its length by C and the checkpoints it connects by p and q; then, max(Lp,Lq)≤C≤min(Rp,Rq) must hold.
Your goal is to find a valid set of paths whose size is as large as possible.
The first line of the input contains two space-separated integers N and K.
K lines follow. For each valid i, the i-th of each lines contains four space-separated integers Xi, Yi, Li and Ri.
First, print a line containing a single integer M ― the number of paths in your set.
Then, print M lines. For each valid i, the i-th of these lines should contain two space-separated integers Si and Ti, followed by a space and a string Fi, describing the i-th of your paths in the following way:
The path starts in the cell containing the Si-th checkpoint and ends in the cell containing the Ti-th checkpoint.
Fi describes the sequence of moves used to reach the ending cell from the starting cell.
Let’s denote the current cell by (x,y); initially, this is (XSi,YSi). Then, for each character c of Fi from the beginning to the end:
If c is ‘L’, we move to the cell (x,y−1).
If c is ‘R’, we move to the cell (x,y+1).
If c is ‘U’, we move to the cell (x−1,y).
If c is ‘D’, we move to the cell (x+1,y).
At the end of this process, (x,y) should be (XTi,YTi).
K is even
1≤Xi,Yi≤N for each valid i
2≤Li≤Ri≤64 for each valid i
Example Input
6 6
1 2 4 5
2 3 3 8
3 6 2 6
4 1 3 7
4 6 3 3
6 6 1 10
Example Output
1 4 LDDD
2 3 RRRD
6 5 UU
The positions of checkpoints are marked by integers in the following grid:
We choose a set of 3 paths:
From checkpoint 1 to checkpoint 4: (1,2)→(1,1)→(2,1)→(3,1)→(4,1).
From checkpoint 2 to checkpoint 3: (2,3)→(2,4)→(2,5)→(2,6)→(3,6).
From checkpoint 6 to checkpoint 5: (6,6)→(5,6)→(4,6).
Test generation
The source code used to generate test data can be downloaded here.
First, a parameter E to limit the lengths of the paths is chosen. E can be 8, 16, 32 or 64. There are 3 test files for each value of E.
The generator constructs a set H of disjoint undirected paths covering the whole grid as follows:
For each pair (r,c) (1≤r,c≤N), add the path which contains only the cell (r,c) to H. Now, H contains N2 paths.
Let S be the set of all 4N2 tuples (x,y,d), where x and y are integers between 1 and N and d=(d0,d1) is a pair of integers from the set {(−1,0),(1,0),(0,−1),(0,1)}.
While S is not empty, choose an element (x,y,d) from S uniformly randomly and remove it from S. Let’s denote A=(x,y) and B=(x+d0,y+d1).
If B is not a valid cell in the grid, continue the process.
Otherwise, find the path P∈H that has the cell A as an endpoint and the path Q∈H that has the cell B as an endpoint.
If both paths P and Q exist (it follows that they are unique) and the sum of their lengths does not exceed E, then remove P and Q from H and add the path formed by concatenating them (and connecting cells A and B) to H. Note that the paths can be concatenated because the cells A and B are adjacent.
Afterwards, paths with length 1 are removed from H. For each path that remains in H, a checkpoint is placed in each of its endpoints (therefore, K=2|H|). The checkpoints are numbered randomly.
Next, the parameters L1,L2,…,LK and R1,R2,…,RK are generated. For each the path P∈H:
Let’s denote the length of this path by l.
We choose an integer t between 0 and min(8,E/4) uniformly randomly.
Then, for each of its endpoints, choose its parameters Li and Ri uniformly randomly and independently among all pairs of integers (L,R) which satisfy 2≤L≤l≤R≤E and R−L=t.
If you do not output a set of paths satisfying all constraints, you will receive the WA verdict.
The score of each test file is (2M/K)4, where K/2 is the maximum possible value of M. The score of a submission is the sum of scores of all test files. Your goal is to maximise the score of your submission.
There are 12 test files. During the contest, the displayed score will account for exactly 4 test files (one for each value of E), i.e. your score reflects your submission’s performance on 33% of the test files. However, if your program gets a non-AC verdict on any test file, your submission’s verdict will be non-AC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program’s scores over the other 8 test files.
import sys
def main(N, K, C):
    R = []
    return R
N, K = [int(x) for x in input().strip().split()[:2]]
C = []
for _ in range(K):
    Xi, Yi, Li, Ri = [int(x) for x in input().strip().split()[:4]]
    C.append((Xi, Yi, Li, Ri))
R = main(N, K, C)
for S, T, F in R:
    print(S, T, F)

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS


Related :

Related :

Leave a Comment

error: Content is protected !!