CSES - Putka Open 2020 – 4/5

CSES - Putka Open 2020 – 4/5 - Results

Submission details
Task:	Ruudukko
Sender:	Hennkka
Submission time:	2020-11-08 00:53:51 +0200
Language:	Rust
Status:	READY
Result:	17

Feedback
group	verdict	score
#1	ACCEPTED	5
#2	ACCEPTED	12
#3	WRONG ANSWER	0
#4	RUNTIME ERROR	0
#5	WRONG ANSWER	0

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

Compiler report

warning: unused import: `rand::prelude::*`
 --> input/code.rs:1:5
  |
1 | use rand::prelude::*;
  |     ^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::collections::BTreeMap`
 --> input/code.rs:2:5
  |
2 | use std::collections::BTreeMap;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: value assigned to `y` is never read
   --> input/code.rs:113:13
    |
113 |             y += 1;
    |             ^
    |
    = note: `#[warn(unused_assignments)]` on by default
    = help: maybe it is overwritten before being read?

warning: value assigned to `y` is never read
   --> input/code.rs:116:13
    |
116 |             y -= 1;
    |             ^
    |
    = help: maybe it is overwritten before being read?

warning: unused variable: `y1`
   --> input/code.rs:237:21
    |
237 |                 let y1 = 1;
    |                     ^^ help: consider prefixing with an underscore: `_y1`
    |
    = note: `#[warn(unused_variables)]` on by default

wa...

Code

use rand::prelude::*;
use std::collections::BTreeMap;
use std::io::BufRead;

fn flip_y(path: String) -> String {
    path.chars()
        .map(|c| match c {
            'U' => 'D',
            'D' => 'U',
            c => c,
        })
        .collect()
}

fn flip_x(path: String) -> String {
    path.chars()
        .map(|c| match c {
            'R' => 'L',
            'L' => 'R',
            c => c,
        })
        .collect()
}

fn reverse(path: String) -> String {
    path.chars()
        .rev()
        .map(|c| match c {
            'R' => 'L',
            'L' => 'R',
            'U' => 'D',
            'D' => 'U',
            c => c,
        })
        .collect()
}

fn solve(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) -> Option<String> {
    assert!(1 <= x1 && x1 <= w);
    assert!(1 <= x2 && x2 <= w);
    assert!(1 <= y1 && y1 <= h);
    assert!(1 <= y2 && y2 <= h);
    if y2 < y1 {
        return solve(h, w, h + 1 - y1, x1, h + 1 - y2, x2).map(flip_y);
    }
    if x2 < x1 {
        return solve(h, w, y1, w + 1 - x1, y2, w + 1 - x2).map(flip_x);
    }

    if h == 1 {
        if x1 == 1 && x2 == w {
            Some("R".repeat(w - 1))
        } else {
            None
        }
    } else if h == 2 {
        if y1 == 2 {
            return solve(h, w, h + 1 - y1, x1, h + 1 - y2, x2).map(flip_y);
        }
        assert!(y1 == 1);

        if x1 == x2 {
            if x1 == 1 {
                // Go right, down, and then back left
                return Some(format!("{}D{}", "R".repeat(w - 1), "L".repeat(w - 1)));
            } else if x1 == w {
                // Go left, down, and then back right
                return Some(format!("{}D{}", "L".repeat(w - 1), "R".repeat(w - 1)));
            } else {
                return None;
            }
        }
        assert!(x1 < x2);
        // Go first left until the left wall, then back, then fill the space in between, right and back left
        let mut res = "".to_string();
        let mut x = x1;
        while x > 1 {
            res.push('L');
            x -= 1;
        }
        res.push('D');
        while x < x1 {
            res.push('R');
            x += 1;
        }
        // Now we need to go up and down until we reach x2, hopefully on the other side
        let mut y = 2;
        while x + 1 < x2 {
            res.push('R');
            x += 1;
            if y == 1 {
                res.push('D');
                y += 1;
            } else {
                res.push('U');
                y -= 1;
            }
        }
        // In next step we share x coordinate with x2
        res.push('R');
        x += 1;
        if y == y2 {
            // We hit end, this a failure because the other cell in this column is unvisited
            return None;
        }
        // Now we just walk right until wall, go up or down, and then walk back to x2
        while x < w {
            res.push('R');
            x += 1;
        }
        if y == 1 {
            res.push('D');
            y += 1;
        } else {
            res.push('U');
            y -= 1;
        }
        while x > x2 {
            res.push('L');
            x -= 1;
        }

        assert!(res.len() == h * w - 1);
        Some(res)
    } else if h == 3 {
        fn fill_left(h: usize, w: usize, y: usize) -> Option<(usize, String)> {
            assert!(h == 3);
            if y == 2 {
                // If we have path from (2, w) to (1, w), then we also have the reverse path
                fill_left(h, w, 1)
                    .and_then(|(y, p)| if y == 2 { Some((1, reverse(p))) } else { None })
            } else if y == 1 {
                let y = if w % 2 == 0 { 2 } else { 3 };
                let res = format!(
                    "{}D{}",
                    "L".repeat(w - 1),
                    solve(2, w, 1, 1, y - 1, w).unwrap()
                );
                Some((y, res))
            } else {
                assert_eq!(y, 3);
                let y = if w % 2 == 0 { 2 } else { 1 };
                let res = format!("{}U{}", "L".repeat(w - 1), solve(2, w, 2, 1, y, w).unwrap());
                Some((y, res))
            }
        }
        // if y1 == 3 {
        //     return solve(h, w, h + 1 - y1, x1, h + 1 - y2, x2).map(flip_y);
        // }
        // assert!(y1 == 1 || y1 == 2);

        if x1 != x2 {
            // Solve both ends separately, then try to combine them in the middle
            let left = fill_left(h, x1, y1);
            let right = fill_left(h, w + 1 - x2, y2).map(|(y, p)| (y, flip_x(reverse(p))));
            // println!("Left: {:?}", left);
            // println!("Right: {:?}", right);

            match (left, right) {
                (Some((ly, lp)), Some((ry, rp))) => {
                    if x1 + 1 == x2 {
                        // They are next to each others, the y coordinates need to match
                        if ly == ry {
                            Some(format!("{}R{}", lp, rp))
                        } else {
                            None
                        }
                    } else {
                        // Not next to each others
                        if ly == 2 || ry == 2 {
                            None
                        } else {
                            let suffix = if ly == ry { "UUR" } else { "" };
                            let midwidth = if ly == ry { x2 - x1 - 2 } else { x2 - x1 - 1 };
                            if midwidth == 0 {
                                None
                            } else {
                                let midres = format!(
                                    "{}D{}D{}{}",
                                    "R".repeat(midwidth),
                                    "L".repeat(midwidth - 1),
                                    "R".repeat(midwidth),
                                    suffix
                                );
                                let midres = if ly < ry { midres } else { flip_y(midres) };
                                Some(format!("{}{}{}", lp, midres, rp))
                            }
                        }
                    }
                }
                _ => None,
            }
        } else {
            // The endpoints are in the same column
            if y1 == 2 || y2 == 2 {
                // One of the endpoints is on the center row
                if w % 2 == 1 {
                    // No solutions with odd number of columns
                    return None;
                }

                let rev = y2 != 2;
                let (y1, y2) = if rev { (y2, y1) } else { (y1, y2) };
                let fy = y1 != 1;
                let y1 = 1;
                assert!(y1 == 1);
                assert!(y2 == 2);

                let res = if x1 % 2 == 1 {
                    if x1 == 1 {
                        // We are at the left wall, fill the right side
                        Some(format!("R{}LU", flip_x(fill_left(h, w - 1, 1).unwrap().1)))
                    } else {
                        // Flip the board and retry
                        solve(h, w, y1, w + 1 - x1, y2, w + 1 - x2).map(flip_x)
                    }
                } else {
                    // Odd number of columns to the left, go there, then zigzag
                    if x1 == w {
                        Some(format!("L{}RU", fill_left(h, x1 - 1, 1).unwrap().1))
                    } else {
                        Some(format!(
                            "L{}RR{}L",
                            fill_left(h, x1 - 1, 1).unwrap().1,
                            flip_x(fill_left(h, w - x1, 3).unwrap().1)
                        ))
                    }
                };
                let res = if fy { res.map(flip_y) } else { res };
                if rev {
                    res.map(reverse)
                } else {
                    res
                }
            } else {
                let fy = y1 != 1;
                let y1 = 1;
                let y2 = 3;
                let res = if w % 2 == 0 || x1 % 2 != 1 {
                    // Solutions exist only for cases where x divides the width into two even-width parts
                    None
                } else {
                    let left = if x1 == 1 {
                        "D".to_string()
                    } else {
                        format!("L{}R", fill_left(h, x1 - 1, 1).unwrap().1)
                    };
                    let right = if x1 == w {
                        "D".to_string()
                    } else {
                        reverse(format!("R{}L", flip_x(fill_left(h, w - x1, 3).unwrap().1)))
                    };
                    Some(format!("{}{}", left, right))
                };
                if fy {
                    res.map(flip_y)
                } else {
                    res
                }
            }
        }
    } else {
        unimplemented!()
    }
}

fn main() {
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();

    let t: usize = lines.next().unwrap().unwrap().parse().unwrap();
    for _ in 0..t {
        let input: Vec<usize> = lines
            .next()
            .unwrap()
            .unwrap()
            .split_whitespace()
            .map(|v| v.parse().unwrap())
            .collect();
        if let Some(res) = solve(input[0], input[1], input[2], input[3], input[4], input[5]) {
            println!("YES");
            println!("{}", res);
        } else {
            println!("NO");
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert_solution(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize, path: &str) {
        let mut visited = vec![false; h * w];
        let mut x = x1;
        let mut y = y1;
        visited[(x - 1) + (y - 1) * w] = true;
        for c in path.chars() {
            match c {
                'U' => y -= 1,
                'D' => y += 1,
                'L' => x -= 1,
                'R' => x += 1,
                c => panic!("Invalid action '{}'", c),
            }
            assert!(
                x >= 1 && x <= w && y >= 1 && y <= h,
                "Solution {} walked out of bounds",
                path
            );
            assert!(
                !visited[(x - 1) + (y - 1) * w],
                "Solution {} has already visited cell {}, {}",
                path,
                y,
                x
            );
            visited[(x - 1) + (y - 1) * w] = true;
        }
        assert!(
            visited.into_iter().all(std::convert::identity),
            "Solution {} didn't visit all cells",
            path
        );
        assert!((x, y) == (x2, y2));
    }

    fn assert_solvable(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) {
        assert_solution(h, w, y1, x1, y2, x2, &solve(h, w, y1, x1, y2, x2).unwrap());
    }

    fn assert_unsolvable(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) {
        assert!(solve(h, w, y1, x1, y2, x2).is_none());
    }

    #[test]
    fn test_solve1() {
        assert_solvable(1, 3, 1, 1, 1, 3);
        assert_solvable(1, 3, 1, 3, 1, 1);
        assert_unsolvable(1, 3, 1, 2, 1, 3);
    }

    #[test]
    fn test_solve2() {
        assert_unsolvable(2, 2, 1, 1, 2, 2);
        assert_solvable(2, 2, 1, 1, 2, 1);

        assert_solvable(2, 3, 1, 1, 2, 3);
        assert_unsolvable(2, 3, 1, 1, 1, 3);
    }

    #[test]
    fn test_solve3() {
        assert_solvable(3, 3, 1, 1, 3, 3);
        assert_solvable(3, 4, 1, 2, 1, 3);
        assert_unsolvable(3, 3, 1, 2, 1, 3);

        // Width 1
        assert_solvable(3, 1, 1, 1, 3, 1);
        assert_solvable(3, 1, 3, 1, 1, 1);
        assert_unsolvable(3, 1, 1, 1, 2, 1);
        assert_unsolvable(3, 1, 3, 1, 2, 1);
        assert_unsolvable(3, 1, 2, 1, 1, 1);
        assert_unsolvable(3, 1, 2, 1, 3, 1);

        // Wider
        for x in 1..=6 {
            assert_solvable(3, 6, 1, x, 2, x);
            assert_solvable(3, 6, 2, x, 1, x);
            assert_solvable(3, 6, 2, x, 3, x);
            assert_solvable(3, 6, 3, x, 2, x);
        }

        for x in 1..=7 {
            if x % 2 == 1 {
                assert_solvable(3, 7, 1, x, 3, x);
                assert_solvable(3, 7, 3, x, 1, x);
            } else {
                assert_unsolvable(3, 7, 1, x, 3, x);
                assert_unsolvable(3, 7, 3, x, 1, x);
            }
        }

        // Other manual samples
        assert_solvable(3, 6, 3, 2, 3, 3);
        assert_solvable(3, 6, 1, 2, 1, 3);
        assert_unsolvable(3, 6, 1, 2, 1, 4);
        assert_unsolvable(3, 6, 1, 2, 1, 5);
        assert_unsolvable(3, 6, 1, 2, 1, 6);

        assert_solvable(3, 6, 1, 3, 1, 4);
        assert_unsolvable(3, 6, 1, 3, 1, 5);
        assert_solvable(3, 6, 1, 3, 1, 6);
    }
}

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: WRONG ANSWER

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

Test 4

Group: 4, 5

Verdict: RUNTIME ERROR

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)

Error:

thread 'main' panicked at 'not implemented', input/code.rs:263:9
note: run with `RUST_BACK...

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

Error:

thread 'main' panicked at 'not implemented', input/code.rs:263:9
note: run with `RUST_BACK...

Test 6

Group: 5

Verdict: RUNTIME ERROR

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)

Error:

thread 'main' panicked at 'not implemented', input/code.rs:263:9
note: run with `RUST_BACK...

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: WRONG ANSWER

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: WRONG ANSWER

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

Test 11

Group: 3, 5

Verdict: WRONG ANSWER

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 DRURDRUULLLLLURULLDDLDD ...` 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: RUNTIME ERROR

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

Error:

thread 'main' panicked at 'not implemented', input/code.rs:263:9
note: run with `RUST_BACK...

Test 14

Group: 5

Verdict: RUNTIME ERROR

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)

Error:

thread 'main' panicked at 'not implemented', input/code.rs:263:9
note: run with `RUST_BACK...

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

Test 16

Group: 5

Verdict: RUNTIME ERROR

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)

Error:

thread 'main' panicked at 'not implemented', input/code.rs:263:9
note: run with `RUST_BACK...

Putka Open 2020 – 4/5

Ruudukko

Compiler report

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