# AtCoder Beginner Contest 189 Editorial

# Problem A - Slot (opens new window)

Just check whether C1=C2=C3C_1=C_2=C_3.

  • Time complexity is O(1)\mathcal{O}(1).
  • Space complexity is O(1)\mathcal{O}(1).
Code (Rust)
use proconio::input;
use proconio::marker::Chars;

fn main() {
    input! {
        s: Chars,
    }
    println!("{}", if s[0] == s[1] && s[1] == s[2] {"Won"} else {"Lost"});
}
1
2
3
4
5
6
7
8
9

# Problem B - Alcoholic (opens new window)

Since Takahashi drinks in the given order, we just simulate how he drinks and check if he is drunken after drinking the current glass.

  • Time complexity is O(N)\mathcal{O}(N).
  • Space complexity is O(1)\mathcal{O}(1).
Code (Rust)
use proconio::input;

fn main() {
    input! {
        n: usize,
        mut x: usize,
        liquor: [(usize, usize); n],
    }

    x *= 100;
    let mut tot = 0;
    for i in 0..n {
        tot += liquor[i].0 * liquor[i].1;
        if tot > x {
            println!("{}", i + 1);
            return;
        }
    }
    println!("-1");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Problem C - Mandarin Orange (opens new window)

This is a classical problem. It is the same as LC84 - Largest Rectangle in Histogram (opens new window). We can solve this problem using a monotonic stack.

In the stack, we store heights and their starting positions. We keep the elements in the stack in an ascending order, that is to say, the largest height is at the top.

Now when we have a new height at position ii, we pop from the stack until the stack is empty, or the largest height is smaller than the current height. During the process, we update our answer (each popped height can extend to as far as i−1i-1), and also record the leftmost position. Then we push the current height along with the leftmost position into the stack.

To avoid handling borders, we can add a 00 at the end of the array.

  • Time complexity is O(N)\mathcal{O}(N).
  • Space complexity is O(N)\mathcal{O}(N).
Code (Rust)
use proconio::input;
use std::collections::VecDeque;

fn main() {
    input! {
        n: usize,
        mut a: [usize; n],
    }

    a.push(0);
    let mut ans = 0;
    let mut dq: VecDeque<(usize, usize)> = VecDeque::new();
    for i in 0..=n {
        let mut nl = i;
        while !dq.is_empty() && dq.back().unwrap().0 > a[i] {
            let (h, l) = *dq.back().unwrap();
            ans = ans.max(h * (i - l));
            dq.pop_back();
            nl = l;
        }
        if dq.is_empty() || dq.back().unwrap().0 < a[i] {
            dq.push_back((a[i], nl));
        }
    }
    println!("{}", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# Problem D - Logical Expression (opens new window)

This is a very simple dynamic programming problem. We just store two values, ff for the number of ways to get false and tt for the number of ways to get true. The transition is

(f,t)={(2f+t,t)si=AND(f,2t+f)si=OR(f,t)=\left\{\begin{aligned} & (2f+t,t) & s_i=\text{AND}\\ & (f, 2t+f) & s_i=\text{OR}\end{aligned}\right.

  • Time complexity is O(N)\mathcal{O}(N).
  • Space complexity is O(1)\mathcal{O}(1).
Code (Rust)
use proconio::input;

fn main() {
    input! {
        n: usize,
        s: [String; n],
    }

    let mut f = 1u64;
    let mut t = 1u64;

    for si in s {
        if si == "AND" {
            let nf = f * 2 + t;
            let nt = t;
            f = nf;
            t = nt;
        } else {
            let nf = f;
            let nt = t * 2 + f;
            f = nf;
            t = nt;
        }
    }

    println!("{}", t);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# Problem E - Rotate and Flip (opens new window)

It is natural to think of sorting the queries first, according to their timestamps.

Now let's look at the operations. Suppose we have (x,y)(x,y):

  • Operation I changes it to (y,−x)(y,-x)
  • Operation II changes it to (−y,x)(-y, x)
  • Operation III changes it to (2p−x,y)(2p-x,y)
  • Operation IV changes it to (x,2p−y)(x,2p-y)

Since the operations are applied to all points at the same time, we will not calculate the position of each point, instead, we want to know the final transform.

Operation I & II swaps xx and yy, while changing the sign of one axis. Operation III & IV flips one axis and then adds 2p2p to it. To handle all the operations, we will use five variables, swapswap denoting if xx and yy are swapped, sxs_x denoting the sign of the current xx axis, sys_y denoting the sign of the current yy axis, cxc_x denoting the extra value for xx and cyc_y denoting the extra value for yy.

Now we have:

  • Operation I: swapswap is flipped, cxc_x and cyc_y is swapped, sxs_x and sys_y is swapped, then sys_y and cyc_y are flipped.
  • Operation II: swapswap is flipped, cxc_x and cyc_y is swapped, sxs_x and sys_y is swapped, then sxs_x and cxc_x are flipped.
  • Operation III: sxs_x is flipped, and cxc_x is flipped then added 2p2p.
  • Operation IV: sys_y is flipped, and cyc_y is flipped then added 2p2p.

For each query, after applying enough operations, we can answer the query according to the five variables:

  • If swapswap is false, the answer will be (sxx0+cx,syy0+cy)(s_xx_0+c_x,s_yy_0+c_y)

  • If swapswap is true, the answer will be (sxy0+cx,syx0+cy)(s_xy_0+c_x,s_yx_0+c_y)

  • Time complexity is O(Qlog⁥Q)\mathcal{O}(Q\log Q).

  • Space complexity is O(Q)\mathcal{O}(Q).

Code (Rust)
use proconio::input;
use proconio::marker::Usize1;
use std::cmp::Ordering;

fn main() {
    input! {
        n: usize,
        points: [(i64, i64); n],
        m: usize,
    }

    let mut ops: Vec<(usize, i64)> = vec![];
    for _i in 0..m {
        input! {
            t: usize,
        }
        if t <= 2 {
            ops.push((t, 0));
        } else {
            input! {
                p: i64,
            }
            ops.push((t, p));
        }
    }

    input! {
        q: usize,
        queries: [(usize, Usize1); q],
    }

    let mut ans = vec![(0i64, 0i64); q];
    let mut order: Vec<usize> = (0..q).collect();
    order.sort_by(|a, b| if queries[*a].0 <= queries[*b].0 {
        Ordering::Less
    } else {
        Ordering::Greater
    });

    let mut swap = false;
    let mut sx = 1i64;
    let mut sy = 1i64;
    let mut cx = 0i64;
    let mut cy = 0i64;
    let mut op = 0usize;
    for i in order {
        let (a, b) = queries[i];
        while op < a {
            let (t, p) = ops[op];
            match t {
                1 => {
                    swap = !swap;
                    std::mem::swap(&mut cx, &mut cy);
                    std::mem::swap(&mut sx, &mut sy);
                    sy = -sy;
                    cy = -cy;
                },
                2 => {
                    swap = !swap;
                    std::mem::swap(&mut cx, &mut cy);
                    std::mem::swap(&mut sx, &mut sy);
                    sx = -sx;
                    cx = -cx;
                },
                3 => {
                    sx = -sx;
                    cx = p * 2 - cx;
                },
                4 => {
                    sy = -sy;
                    cy = p * 2 - cy;
                },
                _ => {

                }
            }
            op += 1;
        }
        if swap {
            ans[i] = (points[b].1 * sx + cx, points[b].0 * sy + cy);
        } else {
            ans[i] = (points[b].0 * sx + cx, points[b].1 * sy + cy);
        }
    }

    for i in 0..q {
        println!("{} {}", ans[i].0, ans[i].1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

# Problem F - Sugoroku2 (opens new window)

Let's first simplify this problem to the following form:

  • There is a mission, our succeeding probability is psp_s, and the cost is EsE_s, while our failing probability is pf=1−psp_f=1-p_s, and the cost is EfE_f.
  • We will stop as long as we succeed, otherwise we keep trying.
  • What is the expected value of our total cost?

The expected value of the total cost can be represented as:

E=Esps+(Ef+Es)pfps+(2Ef+Es)pf2ps+⋯E=E_sp_s+(E_f+E_s)p_fp_s+(2E_f+E_s)p_f^2p_s+\cdots

It equals to:

Esps+pfps((Ef+Es)+(2Ef+Es)pf+⋯)E_sp_s+p_fp_s((E_f+E_s)+(2E_f+E_s)p_f+\cdots)

We need to calculate two sums:

∑s=Es+Espf+Espf2+⋯=Es11−pf=Esps\sum_s=E_s+E_sp_f+E_sp_f^2+\cdots=E_s\frac{1}{1-p_f}=\frac{E_s}{p_s}

and

∑f=Ef+2Efpf+3Efpf2+⋯\sum_f=E_f+2E_fp_f+3E_fp_f^2+\cdots

which is a bit harder.

Actually, we have:

∑fpf=Efpf+2Efpf2+⋯\sum_fp_f=E_fp_f+2E_fp_f^2+\cdots

So we have:

(1−pf)∑f=Ef(1+pf+pf2+⋯)=Ef11−pf=Efps(1-p_f)\sum_f=E_f(1+p_f+p_f^2+\cdots)=E_f\frac{1}{1-p_f}=\frac{E_f}{p_s}

So

∑f=Efps2\sum_f=\frac{E_f}{p_s^2}

Then we return to the original equation and now we have:

E=Esps+pfps(∑f+∑s)=Esps+pfps(Esps+Efps2)=Esps+(1−ps)(Es+Efps)E=E_sp_s+p_fp_s(\sum_f+\sum_s)=E_sp_s+p_fp_s(\frac{E_s}{p_s}+\frac{E_f}{p_s^2})=E_sp_s+(1-p_s)(E_s+\frac{E_f}{p_s})

Now we return to the original problem and try to calculate EsE_s, EfE_f and psp_s.

Here, if we arrive at the NN-th position, we succeed. If we are sent back to the 00-th position, we fail.

The idea is similar to LC837 - New 21 Game (opens new window). We store the sum of the probability of the positions which can come to the current position, then

pi=∑pMp_i=\frac{\sum_p}{M}

Of course, the broken positions will not contribute to ∑p\sum_p. Also, we need to add pip_i (if ii is not broken) and remove pi−Mp_{i-M} (if i−Mi-M is not broken) when iâ‰ĨMi\geq M.

But here we also need the expected value EiE_i, which can be represented as:

Ei=∑pj(Ej+1)∑p=1+∑pjEj∑pE_i=\frac{\sum p_j(E_j+1)}{\sum_p}=1+\frac{\sum p_jE_j}{\sum_p}

The expression indicates that instead of calculating EiE_i, we can calculate piEip_iE_i instead:

piEi=∑pM+∑pjEjMp_iE_i=\frac{\sum_p}{M}+\frac{\sum p_jE_j}{M}

In a similar manner, we can calculate piEip_iE_i accumulatively. Note that the broken positions' pEpE contributes to pfEfp_fE_f instead of ∑pE\sum_{pE}.

Since surpassing the NN-th position is also counted as reaching the NN-th position, our enumeration will stop at the N−1N-1-th position. For each position that can reach the NN-th position, we will calculate its contribution to pNp_N and pNENp_NE_N according to the proportion i+M−N+1M\frac{i+M-N+1}{M}.

Finally, we can get pfEfp_fE_f, ps=pNp_s=p_N and psEs=pNENp_sE_s=p_NE_N, and with these values, we can calculate the final answer EE.

  • Time complexity is O(N)\mathcal{O}(N).
  • Space complexity is O(N)\mathcal{O}(N).
Code (Rust)
use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        k: usize,
        a: [usize; k],
    }

    let mut broken = vec![false; n + 1];
    for i in a {
        broken[i] = true;
    }

    let mut prob_exp = vec![0.0; n + 1];
    let mut prob = vec![0.0; n + 1];
    prob[0] = 1.0;

    let mut prob_sum: f64 = 1.0;
    let mut exp_sum: f64 = 0.0;

    if m >= n {
        let goal_pct = (m - n + 1) as f64 / m as f64;
        prob[n] += prob[0] * goal_pct;
        prob_exp[n] += (prob_exp[0] + prob[0]) * goal_pct;
    }

    let mut prob_exp_fail = 0.0;

    for i in 1..n {
        prob[i] = prob_sum / m as f64;
        prob_exp[i] = prob[i] + exp_sum / m as f64;
        if !broken[i] {
            prob_sum += prob[i];
            exp_sum += prob_exp[i];
            if i + m >= n {
                let goal_pct = (i + m - n + 1) as f64 / m as f64;
                prob[n] += prob[i] * goal_pct;
                prob_exp[n] += (prob_exp[i] + prob[i]) * goal_pct;
            }
        } else {
            prob_exp_fail += prob_exp[i];
        }
        if i >= m && !broken[i - m] {
            prob_sum -= prob[i - m];
            exp_sum -= prob_exp[i - m];
        }
    }

    if prob[n] < 1e-8 {
        println!("-1");
    } else if (prob[n] - 1.0).abs() < 1e-8 {
        println!("{}", prob_exp[n]);
    } else {
        let exp_fail = prob_exp_fail / (1.0 - prob[n]);
        println!("{}", prob_exp[n] + (1.0 - prob[n]) * (prob_exp[n] + exp_fail) / prob[n]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59