CSES - Putka Open 2020 – 4/5

CSES - Putka Open 2020 – 4/5 - Results

Submission details
Task:	Ruudukko
Sender:	Mahtimursu
Submission time:	2023-03-11 03:42:21 +0200
Language:	C++ (C++17)
Status:	READY
Result:	17

Feedback
group	verdict	score
#1	ACCEPTED	5
#2	ACCEPTED	12
#3	TIME LIMIT EXCEEDED	0
#4	TIME LIMIT EXCEEDED	0
#5	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.00 s	1, 5	details
#2	ACCEPTED	0.01 s	2, 5	details
#3	TIME LIMIT EXCEEDED	--	3, 5	details
#4	TIME LIMIT EXCEEDED	--	4, 5	details
#5	RUNTIME ERROR	0.03 s	5	details
#6	TIME LIMIT EXCEEDED	--	5	details
#7	ACCEPTED	0.01 s	2, 5	details
#8	ACCEPTED	0.00 s	2, 5	details
#9	ACCEPTED	0.00 s	3, 5	details
#10	ACCEPTED	0.00 s	3, 5	details
#11	ACCEPTED	0.01 s	3, 5	details
#12	WRONG ANSWER	0.00 s	3, 5	details
#13	ACCEPTED	0.01 s	4, 5	details
#14	TIME LIMIT EXCEEDED	--	5	details
#15	WRONG ANSWER	0.02 s	3, 5	details
#16	TIME LIMIT EXCEEDED	--	5	details

Code

#include <bits/stdc++.h>

typedef long long ll;

#define M 1000000007
#define N (1 << 18)

#define y first
#define x second

using namespace std;

map<tuple<int, int, pair<int, int>, pair<int, int>>, int> dp;

// FROM https://cses.fi/342/result/1233306

bool solveSmall(int h, int w, int y0, int x0, int y1, int x1) {
	if (x0 > x1 || (x0 == x1 && y0 > y1)) return solveSmall(h, w, y1, x1, y0, x0);
 
	if (h == 1) {
		if (x0 == 0 && x1 == w-1) return true;
		if (x0 == w-1 && x1 == 0) return true;
		return false;
	} else {
		if (x0 == x1 && 0 < x0 && x0 < w-1) return false;
		return true;
	}
}

bool works(int h, int w, int y0, int x0, int y1, int x1) {
	if (y0 == y1 && x0 == x1) return false;
	if (w < h) return works(w, h, x0, y0, x1, y1);
	if (! ((h*w ^ abs(x0 - x1) ^ abs(y0 - y1)) & 1)) return false;
	if ((h*w & 1) && ((x0 + y0) & 1)) return false;
 
	if (h <= 2) return solveSmall(h, w, y0, x0, y1, x1);
	if (h == 3 && (!(w & 1))) {
		if (y0 == 1) {
			if ((x0 & 1) && x1 < x0) return false;
			if (!(x0 & 1) && x1 > x0) return false;
		} else {
			if (!(x0 & 1) && (x1 < x0 - 1)) return false;
			if ((x0 & 1) && (x1 > x0 + 1)) return false;
		}
	}   
	return true;
}

// END FROM

bool inside(int n, int m, pair<int, int> p) {
    return p.x <= m && p.y <= n && p.x > 0 && p.y > 0;
}

bool ok(int h, int w, pair<int, int> s, pair<int, int> t) {
    return works(h, w, s.y - 1, s.x - 1, t.y - 1, t.x - 1);
}

pair<int, int> offset(pair<int, int> p, pair<int, int> off) {
    return {p.y + off.y, p.x + off.x};
}

map<tuple<int, int, pair<int, int>, pair<int, int>>, pair<tuple<int, int, pair<int, int>, pair<int, int>>, tuple<int, int, pair<int, int>, pair<int, int>>>> mp;
map<tuple<int, int, pair<int, int>, pair<int, int>>, string> connector;

const int cutoff = 20;

int solve(int n, int m, pair<int, int> s, pair<int, int> t) {
    //if (n < m) return solve(m, n, {s.x, s.y}, {t.x, t.y});
    if (s > t) return solve(n, m, t, s);
    int best = n * m;
    if (best <= cutoff) return best;
    if (dp[make_tuple(n, m, s, t)]) return dp[make_tuple(n, m, s, t)];
    //cout << n << " " << m << endl;

    int min_i = min(s.y, t.y);
    int max_i = max(s.y, t.y);

    int min_j = min(s.x, t.x);
    int max_j = max(s.x, t.x);

    // Try stripping

    if (min_i > 2) {
        if (ok(n - 2, m, offset(s, {-2, 0}), offset(t, {-2, 0}))) {
            auto x1 = make_tuple(2, m, make_pair(1, 0), make_pair(0,0));
            auto x2 = make_tuple(n - 2, m, offset(s, {-2, 0}), offset(t, {-2, 0}));
            mp[make_tuple(n, m, s, t)] = make_pair(x1, x2);

            return dp[make_tuple(n, m, s, t)] = solve(n - 2, m, offset(s, {-2, 0}), offset(t, {-2, 0}));
        }
    }

    if (max_i < n - 1) {
        if (ok(n - 2, m, s, t)) {
            auto x1 = make_tuple(2, m, make_pair(n - 2, 0), make_pair(0,0));
            auto x2 = make_tuple(n - 2, m, s, t);
            mp[make_tuple(n, m, s, t)] = make_pair(x1, x2);

            return dp[make_tuple(n, m, s, t)] = solve(n - 2, m, s, t);
        }
    }

    if (min_j > 2) {
        if (ok(n, m - 2, offset(s, {0, -2}), offset(t, {0, -2}))) {
            auto x1 = make_tuple(n, 2, make_pair(0, 1), make_pair(0,0));
            auto x2 = make_tuple(n, m - 2, offset(s, {0, -2}), offset(t, {0, -2}));
            mp[make_tuple(n, m, s, t)] = make_pair(x1, x2);

            return dp[make_tuple(n, m, s, t)] = solve(n, m - 2, offset(s, {0, -2}), offset(t, {0, -2}));
        }
    }

    if (max_j < m - 1) {
        if (ok(n, m - 2, s, t)) {
            auto x1 = make_tuple(n, 2, make_pair(0, m - 2), make_pair(0,0));
            auto x2 = make_tuple(n, m - 2, s, t);
            mp[make_tuple(n, m, s, t)] = make_pair(x1, x2);

            return dp[make_tuple(n, m, s, t)] = solve(n, m - 2, s, t);
        }
    }

    max_i = min(max_i, min_i + 2);
    max_j = min(max_j, min_j + 2);


    // Split vertical

    pair<tuple<int, int, pair<int, int>, pair<int, int>>, tuple<int, int, pair<int, int>, pair<int, int>>> ans;
    string conn;
    

    for (int i = min_i; i < max_i; ++i) {
        for (int j = 1; j <= m; ++j) {
            int first_n = i;
            int second_n = n - i;

            pair<int, int> first_e = {first_n, j};
            pair<int, int> second_e = {first_n + 1, j};

            // s -> first_e && second_e -> t

            if (inside(first_n, m, s) 
                && inside(second_n, m, offset(t, {-first_n, 0}))
                && ok(first_n, m, s, first_e) 
                && ok(second_n, m, offset(t, {-first_n, 0}), offset(second_e, {-first_n, 0}))
            ) {
                int cur = solve(first_n, m, s, first_e);
                if (cur < best) cur = max(cur, solve(second_n, m, offset(t, {-first_n, 0}), offset(second_e, {-first_n, 0}))); 
                
                if (cur < best) {
                    best = cur;

                    auto x1 = make_tuple(first_n, m, s, first_e);
                    auto x2 = make_tuple(second_n, m, offset(second_e, {-first_n, 0}), offset(t, {-first_n, 0}));

                    conn = "D";
                    ans = make_pair(x1, x2);
                }
            }

            // s -> second_e && first_e -> t

            if (inside(first_n, m, t) 
                && inside(second_n, m, offset(s, {-first_n, 0}))
                && ok(first_n, m, t, first_e) 
                && ok(second_n, m, offset(s, {-first_n, 0}), offset(second_e, {-first_n, 0}))
            ) {
                int cur = solve(first_n, m, t, first_e);
                if (cur < best) cur = max(cur, solve(second_n, m, offset(s, {-first_n, 0}), offset(second_e, {-first_n, 0})));
                
                if (cur < best) {
                    best = cur;

                    auto x1 = make_tuple(second_n, m, offset(s, {-first_n, 0}), offset(second_e, {-first_n, 0}));
                    auto x2 = make_tuple(first_n, m, first_e, t);

                    conn = "U";
                    ans = make_pair(x1, x2);
                }
            }
        }
    }

    for (int j = min_j; j < max_j; ++j) {
        for (int i = 1; i <= n; ++i) {
            int first_m = j;
            int second_m = m - j;

            pair<int, int> first_e = {i, first_m};
            pair<int, int> second_e = {i, first_m + 1};

            // s -> first_e && second_e -> t

            if (inside(n, first_m, s) 
                && inside(n, second_m, offset(t, {0, -first_m}))
                && ok(n, first_m, s, first_e) 
                && ok(n, second_m, offset(t, {0, -first_m}), offset(second_e, {0, -first_m}))
            ) { 
                int cur = solve(n, first_m, s, first_e);
                if (cur < best) cur = max(cur, solve(n, second_m, offset(t, {0, -first_m}), offset(second_e, {0, -first_m})));
                
                if (cur < best) {
                    best = cur;

                    auto x1 = make_tuple(n, first_m, s, first_e);
                    auto x2 = make_tuple(n, second_m, offset(second_e, {0, -first_m}), offset(t, {0, -first_m}));

                    conn = "R";
                    ans = make_pair(x1, x2);
                }
            }

            // t -> first_e && s -> second_e

            if (inside(n, first_m, t) 
                && inside(n, second_m, offset(s, {0, -first_m}))
                && ok(n, first_m, t, first_e) 
                && ok(n, second_m, offset(s, {0, -first_m}), offset(second_e, {0, -first_m}))
            ) {
                int cur = solve(n, first_m, t, first_e);
                if (cur < best) cur = max(cur, solve(n, second_m, offset(s, {0, -first_m}), offset(second_e, {0, -first_m})));

                if (cur < best) {
                    best = cur;
                    
                    auto x1 = make_tuple(n, second_m, offset(s, {0, -first_m}), offset(second_e, {0, -first_m}));
                    auto x2 = make_tuple(n, first_m, first_e, t);

                    conn = "L";
                    ans = make_pair(x1, x2);
                }
            }
        }
    }

    //if (best == n * m) exit(-1);

    mp[make_tuple(n, m, s, t)] = ans;
    connector[make_tuple(n, m, s, t)] = conn;
    return dp[make_tuple(n, m, s, t)] = best;
}

string rev(string s) {
    map<char, char> sw;
    sw['U'] = 'D';
    sw['D'] = 'U';
    sw['L'] = 'R';
    sw['R'] = 'L';

    string ans;
    for (char c : s) ans += sw[c];
    reverse(ans.begin(), ans.end());
    return ans;
}

bool vis[51][51];

string run_brute(int n, int m, pair<int, int> c, pair<int, int> t, int left) {
    //cout << n << " " << m << " " << c.x << " " << c.y << " " << left << endl;
    if (c.x < 1 || c.x > m || c.y < 1 || c.y > n) return "X";
    if (vis[c.y][c.x]) return "X";
    if (left == 0) {
        return c == t ? "" : "X";
    }

    vis[c.y][c.x] = 1;

    string p = run_brute(n, m, {c.y - 1, c.x}, t, left - 1);
    if (p != "X") return "U" + p;

    p = run_brute(n, m, {c.y + 1, c.x}, t, left - 1);
    if (p != "X") return "D" + p;

    p = run_brute(n, m, {c.y, c.x - 1}, t, left - 1);
    if (p != "X") return "L" + p;

    p = run_brute(n, m, {c.y, c.x + 1}, t, left - 1);
    if (p != "X") return "R" + p;

    vis[c.y][c.x] = 0;
    return "X";
}

string brute(int n, int m, pair<int, int> s, pair<int, int> t) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) vis[i][j] = 0;
    }

    string got = run_brute(n, m, s, t, n * m - 1);

    //cout << "brute: " << n << " " << m << " " << s.y << " " << s.x << " " << t.y << " " << t.x << " g: " << got << endl;

    return got;

    return run_brute(n, m, s, t, n * m - 1);
}

string parse_result(int n, int m, pair<int, int> s, pair<int, int> t) {
    if (s > t) return rev(parse_result(n, m, t, s));
    int best = n * m;
    if (best <= cutoff) return brute(n, m, s, t);

    auto p1 = mp[make_tuple(n, m, s, t)].first;
    auto p2 = mp[make_tuple(n, m, s, t)].second;

    // Handle stripes

    map<char, pair<int, int>> dir_to_dif;
    dir_to_dif['U'] = {-1, 0};
    dir_to_dif['D'] = {1, 0};
    dir_to_dif['R'] = {0, 1};
    dir_to_dif['L'] = {0, -1};

    if (get<3>(p1) == make_pair(0, 0)) {
        /*cout << "HERE" << endl;
        cout << n << " " << m << endl;*/
        string path = parse_result(get<0>(p2), get<1>(p2), get<2>(p2), get<3>(p2));

        string res;

        pair<int, int> tgt = get<2>(p1);
        pair<int, int> pos = get<2>(p2);

        //cout << n << " " << m << " HERE2 " << path << " " << tgt.y << " " << tgt.x << " " << pos.y << " " << pos.x << " " << get<3>(p2).y << " " << get<3>(p2).x << endl;

        while (pos.x != tgt.x && pos.y != tgt.y) {
            pair<int, int> dif = dir_to_dif[path[res.size()]];
            pos = make_pair(pos.y + dif.y, pos.x + dif.x);
            res += (path[res.size()]);
        }

        //cout << "res: " << res << endl;

        string end_path = path.size() > res.size() + 1 ? path.substr(res.size() + 1, 1e5) : "";

        if (tgt.y == 1) {
            res = res + "U" + brute(2, get<1>(p1), {2, pos.x}, {2, pos.x + dir_to_dif[path[res.size()]].x}) + "D";
        } else if (tgt.y > 1) {
            res = res + "D" + brute(2, get<1>(p1), {1, pos.x}, {1, pos.x + dir_to_dif[path[res.size()]].x}) + "U";
        } else if (tgt.x == 1) {
            res = res + "L" + brute(get<0>(p1), 2, {pos.y, 2}, {pos.y + dir_to_dif[path[res.size()]].y, 2}) + "R";
        } else if (tgt.x > 1) {
            res = res + "R" + brute(get<0>(p1), 2, {pos.y, 1}, {pos.y + dir_to_dif[path[res.size()]].y, 1}) + "L";
        } else {
            cout << tgt.x << " " << tgt.y << " " << get<0>(p1) << " " << get<1>(p1) << endl;
            cout << "ERR";
            exit(0);
        }

        res += end_path;

        return res;
    }

    string s1 = parse_result(get<0>(p1), get<1>(p1), get<2>(p1), get<3>(p1));
    string s2 = parse_result(get<0>(p2), get<1>(p2), get<2>(p2), get<3>(p2));

    //cout << n << " " << m << " s1: " << s1 << " s2: " << s2 << endl;

    //cout << end_first.y << ", " << end_first.x << " | " << start_second.y << ", " << start_second.x << endl; 

    return s1 + connector[make_tuple(n, m, s, t)] + s2;
}

void test_case() {
    int n, m;
    int sy, sx;
    int ty, tx;

    cin >> n >> m >> sy >> sx >> ty >> tx;

    if (!ok(n, m, {sy, sx}, {ty, tx})) {
        cout << "NO" << endl;
        return;
    }

    cout << "YES\n";
    solve(n, m, {sy, sx}, {ty, tx});
    string ans = parse_result(n, m, {sy, sx}, {ty, tx});

    cout << ans << "\n";
    /*cout << "SCORE: " << s << endl;
    if (s > 100) {
        cout << n << " " << m << " " << sy << " " << sx << " " << ty << " " << tx << endl;
    }
    cout << "CASES: " << dp.size() << endl;*/
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        test_case();
        //cout << "\n";
    }

    return 0;
}

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...` Truncated

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 ...` Truncated

Test 3

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

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
(empty)

Test 4

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

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
(empty)

Test 5

Group: 5

Verdict: RUNTIME ERROR

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` view save

Test 6

Group: 5

Verdict: TIME LIMIT EXCEEDED

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
(empty)

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 ...` Truncated

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 ...` Truncated

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 ...` Truncated

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 UURRRRDDLULDLU NO ...` Truncated

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 URRRDDLULDLLUULDDLUULDD ...` Truncated

Test 12

Group: 3, 5

Verdict: WRONG ANSWER

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 ...` Truncated

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 RRRUUULDDLLUURD NO ...` Truncated

Test 14

Group: 5

Verdict: TIME LIMIT EXCEEDED

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
(empty)

Test 15

Group: 3, 5

Verdict: WRONG ANSWER

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 RRRURDRURDRUULLLLLDLULDLDLULDL...` Truncated

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

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
(empty)

Putka Open 2020 – 4/5

Ruudukko

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Tasks

Submissions (Mahtimursu)