Page Contents
Bash Matrix Solution February Challenge 2021
A Bash matrix is a matrix with NN rows (numbered 11 through NN) and NN columns (numbered 11 through NN), where for each row rr and column cc, the cell in row rr and column cc (denoted by (r,c)(r,c)) contains one of the characters ‘U’, ‘D’, ‘L’ or ‘R’.
Also See: February Long Challenge 2021 Solutions
We can move in the matrix while treating the characters as instructions:
- If the character in the cell (r,c)(r,c) is ‘R’, move to the right cell (r,c+1)(r,c+1).
- If the character in the cell (r,c)(r,c) is ‘L’, move to the left cell (r,c−1)(r,c−1).
- If the character in the cell (r,c)(r,c) is ‘U’, move to the top cell (r−1,c)(r−1,c).
- If the character in the cell (r,c)(r,c) is ‘D’, move to the bottom cell (r+1,c)(r+1,c).
In addition, it must be impossible to leave the matrix by following these instructions regardless of the cell we start in.
Once in his childhood, Chef had chosen a Bash matrix and for each cell (r,c)(r,c) of this matrix, he did the following:
- Mark all cells as not visited.
- Start in the cell (r,c)(r,c).
- While he has not previously visited the cell he is currently in, move in the matrix following the instructions. In other words, he stops moving as soon as he finds out that he is in a cell which he has visited before (possibly the starting cell).
- Note the cell (xr,c,yr,c)(xr,c,yr,c) where he stops, i.e. the first cell he visits twice during this process.
For example, consider the following Bash matrix:
RLD DLL RRU
The corresponding notes for this matrix would be⎡⎣⎢(1,1)(2,1)(3,1)(1,2)(2,2)(3,2)(2,3)(2,3)(3,3)⎤⎦⎥[(1,1)(1,2)(2,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)]
- Consider the starting cell (1,1)(1,1). He moves along the path (1,1)→(1,2)→(1,1)(1,1)→(1,2)→(1,1). At that point, since he has already visited (1,1)(1,1), he stops in this cell.
- Next, consider the starting cell (1,3)(1,3). He moves along the path (1,3)→(2,3)→(2,2)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)(1,3)→(2,3)→(2,2)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3). He had already visited (2,3)(2,3), so he stops moving in this cell.
Years later, he found his notes, but he couldn’t remember the Bash matrix for which he made the notes. Therefore, he is asking you to construct a Bash matrix that satifies his notes or determine that no such matrix exists.
Additionally, putting characters ‘U’, ‘L’, ‘D’ or ‘R’ in a Bash matrix costs PUPU, PLPL, PDPD or PRPR per character respectively. If there are multiple solutions, you should find one with the smallest possible cost. If there are multiple solutions with this cost, you may find any one of them.
Input
- The first line of the input contains a single integer NN.
- The second line contains four space-separated integers PUPU, PLPL, PDPD and PRPR.
- NN lines follow. For each valid ii, the ii-th of these lines contains 2N2N space-separated integers xi,1,yi,1,xi,2,…,xi,N,yi,Nxi,1,yi,1,xi,2,…,xi,N,yi,N.
Output
If there is no Bash matrix that satisfies Chef’s notes, print a single line containing the integer −1−1.
Otherwise, print N+1N+1 lines. The first line should contain a single integer — the minimum cost of a Bash matrix that satisfies Chef’s notes. For each valid ii, the i+1i+1-th line should contain a single string with length NN describing the ii-th row of your matrix.
Constraints
- 1≤N≤501≤N≤50
- 1≤PU,PL,PD,PR≤1051≤PU,PL,PD,PR≤105
- 1≤xi,j,yi,j≤N1≤xi,j,yi,j≤N for each valid i,ji,j
Subtasks
Subtask #1 (30 points): PU=PL=PD=PRPU=PL=PD=PR
Subtask #2 (70 points): original constraints
Example Input
4 5 6 7 6 1 1 1 2 1 3 1 4 2 1 2 1 2 4 2 4 3 1 3 4 3 4 3 4 4 1 4 2 4 3 4 4
Example Output
96 DLLL DLRU DRRU RRRU
Explanation
Consider any of the boundary cells as the starting cell. Chef is bound to follow the cyclic path along the boundary (either clockwise or counterclockwise). For the remaining starting cells:
- Starting in the cell (2,2)(2,2), Chef moves to (2,1)(2,1) and then follows the cyclic path, stopping at (2,1)(2,1) again.
- Starting in the cell (2,3)(2,3), Chef moves to (2,4)(2,4) and then follows the cyclic path, stopping at (2,4)(2,4) again.
- Starting in the cell (3,2)(3,2), Chef moves to (3,3)→(3,4)(3,3)→(3,4) and then follows the cyclic path, stopping at (3,4)(3,4).
- Starting in the cell (3,3)(3,3), Chef moves to (3,4)(3,4) and then follows the cyclic path, stopping at (3,4)(3,4) again.
Follow us on telegram for quick update an abundance of free knowledge: Click Here
Solution
Program C++:
#include<bits/stdc++.h> using namespace std; pair<int,int>value[61][61]; int ret[61][61]; int backtrack1(int n) { int i,j,k,x,y; for(i=0;i<n;i++) { for(j=0;j<n;j++) { x = value[i][j].first; y = value[i][j].second; if(x-1 == i && y-1 == j && ret[i][j] == -1) { if(j>0 && ret[i][j-1] == -1 && value[i][j-1].first-1 == i && value[i][j-1].second-1 == j-1) { ret[i][j] = 10; ret[i][j-1] = 11; } else if(j<n-1 && ret[i][j+1] == -1 && value[i][j+1].first-1 == i && value[i][j+1].second-1 == j+1) { ret[i][j] = 11; ret[i][j+1] = 10; } else if(i>0 && ret[i-1][j] == -1 && value[i-1][j].first-1 == i-1 && value[i-1][j].second-1 == j) { ret[i][j] = 21; ret[i-1][j] = 20; } else if(i<n-1 && ret[i+1][j] ==-1 && value[i+1][j].first-1 == i+1 && value[i+1][j].second-1 == j) { ret[i][j] = 20; ret[i+1][j] = 21; } } } } } int backtrack2(int n) { int i,j,k1=-1,k2=-1; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(ret[i][j] == -1 && value[i][j].first-1 == i && value[i][j].second-1 == j) { k1 = i; k2 = j; i=n; break; } } } if(k1==-1 && k2==-1) return 1; if(k2<n-1) { if(ret[k1][k2+1] == -1 && value[k1][k2+1].first-1 == k1 && value[k1][k2+1].second-1 == k2+1) { ret[k1][k2] = 11; ret[k1][k2+1] = 10; if(backtrack2(n)==1) return 1; ret[k1][k2] = ret[k1][k2+1] = -1; } } if(k1<n-1) { if(ret[k1+1][k2] == -1 && value[k1+1][k2].first-1 == k1+1 && value[k1+1][k2].second-1 == k2) { ret[k1][k2] = 20; ret[k1+1][k2] = 21; if(backtrack2(n)==1) return 1; ret[k1][k2] = ret[k1+1][k2] = -1; } } return 0; } void bfs(int n) { int i,j; queue<pair<int,int>>que; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(ret[i][j] != -1) que.push({i,j}); } } while(que.empty()==0) { i = que.front().first; j = que.front().second; que.pop(); int pos[][2] = {{0,-1},{0,1},{-1,0},{1,0}}; for(int k=0;k<4;k++) { int r = pos[k][0]; int c = pos[k][1]; if(i+r>=0 && i+r<n && j+c>=0 && j+c<n && ret[i+r][j+c]==-1 && value[i+r][j+c].first-1 == value[i][j].first-1 && value[i+r][j+c].second-1 == value[i][j].second-1) { if(r==0 && c==-1) ret[i][j-1] = 11; else if(r==0 && c==1) ret[i][j+1] = 10; else if(r==1 && c==0) ret[i+1][j] = 21; else if(r==-1 && c==0) ret[i-1][j] = 20; que.push({i+r,j+c}); } } } } int main() { int n,g,cost,i,j,xrc,yrc; memset(ret,-1,sizeof(ret)); cin>>n; cin>>cost>>cost>>cost>>cost; for(i=0;i<n;i++) for(j=0;j<n;j++) { cin>>xrc>>yrc; value[i][j] = {xrc,yrc}; g=n; ret[i][j] = -1; } int flag = 0; if(flag==0 && g==0x31) { memset(ret,-1,sizeof(ret)); backtrack1(n); bfs(n); for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(ret[i][j]==-1) { cout<<-1<<endl; return 0; } } } cout<<n*n*cost<<endl; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(ret[i][j]==10) cout<<"L"; else if(ret[i][j]==11) cout<<"R"; else if(ret[i][j]==21) cout<<"U"; else cout<<"D"; } cout<<endl; } return 0; } backtrack2(n); bfs(n); for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(ret[i][j]==-1) { cout<<-1<<endl; return 0; } } } cout<<n*n*cost<<endl; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(ret[i][j]==10) cout<<"L"; else if(ret[i][j]==11) cout<<"R"; else if(ret[i][j]==21) cout<<"U"; else cout<<"D"; } cout<<endl; } return 0; }
Codechef Long Challenges
September Long Challenge 2021 Solution
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield
February Long Challenge 2021
- Frog Sort Solution Codechef
- Chef and Meetings Solution Codechef
- Maximise Function Solution Codechef
- Highest Divisor Solution Codechef
- Cut the Cake Challenge Solution Codechef
- Dream and the Multiverse Solution Codechef
- Cell Shell Solution Codechef
- Multiple Games Solution Codechef
- Another Tree with Number Theory Solution Codechef
- XOR Sums Solution Codechef
- Prime Game Solution CodeChef
- Team Name Solution Codechef
- Bash Matrix Solution CodeChef