— Dark mode

Putka Open 2020 – 4/5

Ruudukko

  • Start: 2020-11-06 18:00:00
  • End: 2020-11-08 23:00:00
CSES - Putka Open 2020 – 4/5 - Results
Submission details
Task:Ruudukko
Sender:Laakeri
Submission time:2020-11-08 16:32:26 +0200
Language:C++11
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED5
#2ACCEPTED12
#3ACCEPTED27
#4ACCEPTED28
#5ACCEPTED28
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 5details
#2ACCEPTED0.01 s2, 5details
#3ACCEPTED0.01 s3, 5details
#4ACCEPTED0.01 s4, 5details
#5ACCEPTED0.01 s5details
#6ACCEPTED0.01 s5details
#7ACCEPTED0.01 s2, 5details
#8ACCEPTED0.01 s2, 5details
#9ACCEPTED0.01 s3, 5details
#10ACCEPTED0.01 s3, 5details
#11ACCEPTED0.01 s3, 5details
#12ACCEPTED0.01 s3, 5details
#13ACCEPTED0.01 s4, 5details
#14ACCEPTED0.02 s5details
#15ACCEPTED0.01 s3, 5details
#16ACCEPTED0.05 s5details

Code

/*
Reference:
A. Itai, C. H. Papadimitriou and J. L. Szwarcfiter.
Hamilton Paths in Grid Graphs.
SIAM Journal on Computing, 11(4):676-686, 1982.
*/
#include <bits/stdc++.h>
using namespace std;

int h[55][55];

void check(string res, int n, int m, int y1, int x1, int y2, int x2) {
	for (int i=1;i<=n;i++){
		for (int ii=1;ii<=m;ii++){
			h[i][ii]=0;
		}
	}
	assert((int)res.size() == n*m-1);
	int ty=y1;
	int tx=x1;
	assert(1<=ty&&ty<=n&&1<=tx&&tx<=m);
	h[ty][tx]=1;
	for (char c : res) {
		if (c=='R') tx++;
		if (c=='L') tx--;
		if (c=='D') ty++;
		if (c=='U') ty--;
		assert(1<=ty&&ty<=n&&1<=tx&&tx<=m);
		assert(h[ty][tx]==0);
		h[ty][tx]=1;
	}
	assert(ty==y2&&tx==x2);
}

string tr(string res, string trs) {
	while (!trs.empty()){
		char t=trs.back();
		trs.pop_back();
		if (t=='Y'){
			for (char& c : res) {
				if (c=='D') {
					c='U';
				} else if (c=='U'){
					c='D';
				}
			}
		} else if (t=='X'){
			for (char& c : res) {
				if (c=='L') {
					c='R';
				} else if (c=='R'){
					c='L';
				}
			}
		} else if (t=='C'){
			for (char& c : res) {
				if (c=='R'){
					c='D';
				} else if(c=='L') {
					c='U';
				} else if(c=='U'){
					c='L';
				} else if(c=='D'){
					c='R';
				}
			}
		} else{
			assert(0);
		}
	}
	return res;
}

bool brute(int n, int m, int y1, int x1, int y2, int x2, string& res) {
	if (y1<1||x1<1||y1>n||x1>m||h[y1][x1]) {
		return false;
	}
	if (y1==y2 && x1==x2) {
		if ((int)res.size() == n*m-1){
			return true;
		}
		return false;
	}
	h[y1][x1]=1;
	res+='U';
	if (brute(n, m, y1-1, x1, y2, x2, res)) {
		return true;
	}
	res.pop_back();
	res+='D';
	if (brute(n, m, y1+1, x1, y2, x2, res)){
		return true;
	}
	res.pop_back();
	res+='L';
	if (brute(n, m, y1, x1-1, y2, x2, res)){
		return true;
	}
	res.pop_back();
	res+='R';
	if (brute(n, m, y1, x1+1, y2, x2, res)){
		return true;
	}
	res.pop_back();
	h[y1][x1]=0;
	return false;
}

string go(int n, int m, int y1, int x1, int y2, int x2, bool ac=false) {
	assert(n>=1&&m>=1);
	string trs;
	if (n>m){
		swap(n,m);
		swap(y1,x1);
		swap(y2,x2);
		trs+='C';
	}
	if (x1>x2){
		x1=m+1-x1;
		x2=m+1-x2;
		trs+='X';
	}
	if (y1>y2){
		y1=n+1-y1;
		y2=n+1-y2;
		trs+='Y';
	}
	if ((n*m)%2==0){
		if ((y1+x1)%2 == (y2+x2)%2){
			return "-";
		}
	} else {
		if ((y1+x1)%2 == 1 || (y2+x2)%2 == 1) {
			return "-";
		}
	}
	if (n==1) {
		if (x1==1&&x2==m){
			string res;
			for (int j=0;j<m-1;j++){
				res+='R';
			}
			return tr(res, trs);
		}
		return "-";
	}
	if (n==2) {
		if (x1==x2&&x1>1&&x1<m){
			return "-";
		}
		if (x1==x2){
			if (x1==m){
				trs+='X';
				x1=1;
				x2=1;
			}
			assert(y1==1&&y2==2);
			string res;
			for (int j=0;j<m-1;j++){
				res+='R';
			}
			res+='D';
			for (int j=0;j<m-1;j++){
				res+='L';
			}
			return tr(res, trs);
		}
		if (y1==y2){
			if (y1==2){
				trs+='Y';
				y1=1;
				y2=1;
			}
			string res;
			for (int j=0;j<x1-1;j++){
				res+='L';
			}
			res+='D';
			for (int j=0;j<x1-1;j++){
				res+='R';
			}
			for (int j=0;j<(x2-x1)/2;j++){
				res+="RURD";
			}
			for (int j=0;j<m-x2+1;j++){
				res+='R';
			}
			res+='U';
			for (int j=0;j<m-x2;j++){
				res+='L';
			}
			return tr(res, trs);
		}
		string res;
		for (int j=0;j<x1-1;j++){
			res+='L';
		}
		res+='D';
		for (int j=0;j<x1-1;j++){
			res+='R';
		}
		for (int j=0;j<(x2-x1)/2-1;j++){
			res+="RURD";
		}
		res+="RUR";
		for (int j=0;j<m-x2;j++){
			res+='R';
		}
		res+='D';
		for (int j=0;j<m-x2;j++){
			res+='L';
		}
		return tr(res, trs);
	}
	if (n==3&&m%2==0&&(x1+y1)%2==1){
		if (x1<x2-1) {
			return "-";
		}
		if (y1==2&&x1<x2){
			return "-";
		}
	}
	// Now should be feasible
	if (ac) {
		return "";
	}
	if (n<=5&&m<=5){
		for (int i=1;i<=n;i++){
			for (int ii=1;ii<=m;ii++){
				h[i][ii]=0;
			}
		}
		string res;
		bool succ=brute(n, m, y1, x1, y2, x2, res);
		assert(succ);
		return tr(res, trs);
	}
	assert(x1<=x2&&y1<=y2);
	for (int it=0;it<2;it++){
		swap(n,m);
		swap(y1,x1);
		swap(y2,x2);
		trs+='C';
		if (x1<=2){
			x1=m+1-x1;
			x2=m+1-x2;
			trs+='X';
		}
		if (x1>2 && x2>2 && go(n, m-2, y1, x1-2, y2, x2-2, true)!="-"){
			string r=go(n, m-2, y1, x1-2, y2, x2-2);
			assert(r != "-");
			string res;
			bool u=false;
			int ty=y1;
			int tx=x1-2;
			for (char c : r) {
				if (c=='U') {
					if (tx==1 && !u) {
						string r2=go(n, 2, ty, 2, ty-1, 2);
						assert(r2 != "-");
						res+='L';
						for (char c2 : r2) {
							res+=c2;
						}
						res+='R';
						u=true;
					} else {
						res+=c;
					}
					ty--;
				} else if (c=='D') {
					if (tx==1 && !u) {
						string r2=go(n, 2, ty, 2, ty+1, 2);
						assert(r2 != "-");
						res+='L';
						for (char c2 : r2) {
							res+=c2;
						}
						res+='R';
						u=true;
					} else {
						res+=c;
					}
					ty++;
				} else if (c=='L'){
					tx--;
					res+=c;
				} else if(c=='R'){
					tx++;
					res+=c;
				}
			}
			return tr(res, trs);
		}
	}
	assert(n<=m);
	if (x1>x2){
		x1=m+1-x1;
		x2=m+1-x2;
		trs+='X';
	}
	if (y1>y2){
		y1=n+1-y1;
		y2=n+1-y2;
		trs+='Y';
	}
	if (!(x1<=2&&x2>=m-1)) {
		swap(n,m);
		swap(y1,x1);
		swap(y2,x2);
		trs+='C';
		if (x1>x2){
			x1=m+1-x1;
			x2=m+1-x2;
			trs+='X';
		}
	}
	assert(x1<=2&&x2>=m-1);
	if (n==3){
		string r1=go(3, 2, y1, x1, 1, 2);
		assert(r1 != "-");
		string r2=go(3, m-2, 1, 1, y2, x2-2);
		assert(r2 != "-");
		return tr(r1+"R"+r2, trs);
	}
	for (int i=1;i<=n;i++){
		int py=i;
		int px=2;
		if ((py+px)%2 == (y1+x1)%2) continue;
		if (i==y1 && i>1 && i < n) continue;
		string r1=go(n, 2, y1, x1, py, px);
		assert(r1 != "-");
		string r2=go(n, m-2, py, 1, y2, x2-2);
		assert(r2 != "-");
		return tr(r1+"R"+r2, trs);
	}
	assert(0);
}

void solve() {
	int n,m,y1,x1,y2,x2;
	cin>>n>>m>>y1>>x1>>y2>>x2;
	string res = go(n, m, y1, x1, y2, x2);
	if (res == "-"){
		cout<<"NO"<<endl;
		return;
	}
	check(res, n, m, y1, x1, y2, x2);
	cout<<"YES"<<endl;
	cout<<res<<endl;
}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tcs;
	cin>>tcs;
	for (int tc=0;tc<tcs;tc++){
		solve();
	}
}

Test details

Test 1

Group: 1, 5

Verdict: ACCEPTED

input
100
1 45 1 45 1 1
1 18 1 1 1 10
1 47 1 17 1 30
1 33 1 28 1 20
...
view save

correct output
YES
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...
view save

user output
YES
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...
view save

Test 2

Group: 2, 5

Verdict: ACCEPTED

input
100
2 43 1 33 1 21
2 2 1 1 2 2
2 32 1 1 2 8
2 14 1 12 1 14
...
view save

correct output
NO
NO
NO
NO
YES
...
view save

user output
NO
NO
NO
NO
YES
...
view save

Test 3

Group: 3, 5

Verdict: ACCEPTED

input
100
3 4 2 1 2 4
3 38 2 24 1 22
3 29 2 23 2 3
3 8 3 1 1 2
...
view save

correct output
NO
NO
NO
YES
RRRRRRRUULDLULDLULDLLUR
...
view save

user output
NO
NO
NO
YES
RRRRRRRUULDLULDLULDLLUR
...
view save

Test 4

Group: 4, 5

Verdict: ACCEPTED

input
100
4 25 2 19 1 5
4 13 3 10 4 12
4 7 3 1 4 2
4 23 1 19 2 5
...
view save

correct output
YES
DDRRRRRRULLLLLURRRRRULLLLLLLDD...
view save

user output
YES
DLLLLLLLLLLLLLLLLLLDRRRRRRRRRR...
view save

Test 5

Group: 5

Verdict: ACCEPTED

input
100
16 8 13 1 14 8
41 21 19 11 32 12
46 17 13 7 6 11
8 41 4 32 4 12
...
view save

correct output
NO
YES
LURULURULURULURULURRDDDDDDDDDR...
view save

user output
NO
YES
LDDDDDDDDDDDDDDDDDDDDDDLLLLLLL...
view save

Test 6

Group: 5

Verdict: ACCEPTED

input
100
31 38 18 35 31 37
35 48 7 13 21 21
46 21 25 2 4 19
35 2 13 2 35 1
...
view save

correct output
YES
LLLLLLLLLLLLDRRRRRRRRRRRRDLLLL...
view save

user output
YES
LDDDDDDDDDDDDDLLLLLLLLLLLLLLLL...
view save

Test 7

Group: 2, 5

Verdict: ACCEPTED

input
100
2 4 1 3 1 4
2 4 2 2 1 1
2 4 2 3 1 2
2 4 2 3 1 4
...
view save

correct output
YES
LLDRRRU
NO
NO
NO
...
view save

user output
YES
LLDRRRU
NO
NO
NO
...
view save

Test 8

Group: 2, 5

Verdict: ACCEPTED

input
100
2 5 1 2 2 4
2 5 1 2 1 1
2 5 2 1 1 2
2 5 1 1 1 5
...
view save

correct output
YES
LDRRURRDL
YES
RRRDLLLLU
NO
...
view save

user output
YES
LDRRURRDL
YES
RRRDLLLLU
NO
...
view save

Test 9

Group: 3, 5

Verdict: ACCEPTED

input
100
3 4 1 1 2 3
3 4 2 4 3 2
3 4 2 1 3 1
3 4 1 4 3 4
...
view save

correct output
YES
DDRRRUULLDR
NO
YES
URRRDDLULDL
...
view save

user output
YES
DDRUURRDDLU
NO
YES
URDRURDDLLL
...
view save

Test 10

Group: 3, 5

Verdict: ACCEPTED

input
100
3 5 3 4 3 2
3 5 3 5 2 3
3 5 3 1 2 2
3 5 3 1 3 2
...
view save

correct output
NO
NO
YES
UURRRRDDLULDLU
NO
...
view save

user output
NO
NO
YES
UURRDRURDDLLLU
NO
...
view save

Test 11

Group: 3, 5

Verdict: ACCEPTED

input
100
3 8 2 8 1 2
3 8 2 4 1 7
3 8 3 4 2 7
3 8 2 5 3 1
...
view save

correct output
NO
NO
NO
YES
LLLDRRRRURDRUULLLLLLLDD
...
view save

user output
NO
NO
NO
YES
DRRRUULDLULLDDLUULLDRDL
...
view save

Test 12

Group: 3, 5

Verdict: ACCEPTED

input
100
3 9 1 3 2 9
3 9 1 6 1 5
3 9 3 6 2 8
3 9 3 2 3 4
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 13

Group: 4, 5

Verdict: ACCEPTED

input
100
4 4 2 2 1 4
4 4 4 1 2 2
4 4 2 1 4 3
4 4 3 1 3 3
...
view save

correct output
YES
DDLUUURRDDDRUUU
YES
UUURRRDLDRDLLUU
NO
...
view save

user output
YES
DDLUUURRDDDRUUU
YES
UUURRRDDDLLURUL
NO
...
view save

Test 14

Group: 5

Verdict: ACCEPTED

input
100
12 27 6 22 1 8
6 25 3 2 4 4
6 16 4 6 5 2
36 33 8 6 1 6
...
view save

correct output
YES
DLDDDDDRUUUURDDDDRUURDDRRULURU...
view save

user output
YES
DLLLLLLLLLLLLLLLLLLLLLDDDDDRRR...
view save

Test 15

Group: 3, 5

Verdict: ACCEPTED

input
100
3 12 3 5 1 4
3 20 3 19 2 19
3 34 3 9 2 9
3 38 2 15 3 15
...
view save

correct output
YES
RRRRRRRUULDLULDLULDLULDLDLULDL...
view save

user output
YES
RRRRRRRUULDLULDLULDLULDLDLLLUU...
view save

Test 16

Group: 5

Verdict: ACCEPTED

input
100
50 50 29 1 16 21
50 50 37 5 23 48
50 50 32 22 45 24
50 50 6 28 12 37
...
view save

correct output
YES
DDDDDDDDDDDDDDDDDDDDDRUUUUUUUU...
view save

user output
YES
DDDDDDDDDDDDDDDDDDDDDRRRRRRRRR...
view save

Tasks

A Neliöt-B Peli-C Tekijät-D Ruudukko-

Submissions (Laakeri)

2020-11-08 16:32:26 1002020-11-08 16:26:25 1002020-11-08 16:25:38 172020-11-08 15:55:03 442020-11-08 15:47:08 172020-11-08 13:49:34 172020-11-07 00:15:44 172020-11-07 00:03:47 52020-11-06 23:20:29 52020-11-06 23:15:43 0