Editorial for Bedao Mini Contest 24 - Robot


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ntnguyen

Đặt ~x = x_e - x_s~, ~y = y_e - y_s~.

Xét mọi dãy con độ dài ~k~ trong dãy, giả sử ta chuyển hết dãy con về I.

Gọi ~x'~ là tổng đường đi theo phương ngang, ~y'~ là tổng đường đi theo phương dọc sau khi đã thay đổi dãy. Ta có thể dễ dàng tính được các giá trị này trong ~O(1)~ bằng tổng dồn.

Để robot đến được đích thì ~x' = x~ và ~y' = y~. Khi đó, ta cần thay đổi tối thiểu ~|x - x'| + |y - y'|~ giá trị trong dãy con. Nếu ~|x - x'| + |y - y'| \le k~ thì đáp án là "YES".

Độ phức tạp: ~O(n)~.

#include <bits/stdc++.h>
#define ll long long
#define pa pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 1e5 + 5;
int n, k;
int x_s, y_s, x_e, y_e;
int x_sum[N], y_sum[N];
string S;
bool pass() {
    int X = x_e - x_s, Y = y_e - y_s;
    for (int L = 1, R = k; R <= n; L++, R++) {
        int x_temp = x_sum[L - 1] + (x_sum[n] - x_sum[R]);
        int y_temp = y_sum[L - 1] + (y_sum[n] - y_sum[R]);
        if (abs(X - x_temp) + abs(Y - y_temp) <= k) return true;
    }
    return false;
}
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    #ifdef LOCAL_MACHINE 
        if (fopen("task.inp", "r")) {
            freopen("task.inp", "r", stdin);
            freopen("task.out", "w", stdout);
        }
    #endif
    int t; cin >> t;
    while(t--) {
        cin >> n >> k;
        cin >> x_s >> y_s >> x_e >> y_e;
        cin >> S; S = ' ' + S;
        // Build prefix sum
        for (int i = 1; i <= n; i++) {
            x_sum[i] = x_sum[i - 1] + (S[i] == 'L' ? -1 : (S[i] == 'R' ? 1 : 0));
            y_sum[i] = y_sum[i - 1] + (S[i] == 'U' ? -1 : (S[i] == 'D' ? 1 : 0));
        }
        cout << (pass() ? "YES" : "NO") << '\n';
    }
    return 0;
}

Comments

Please read the guidelines before commenting.



  • 0
    vudinhlong  commented on Sept. 29, 2024, 9:42 a.m.

    Wrong Answer Solution :))