1 / 2
Jun 12

Can anyone help me? I’m having trouble with this question. I’ve been trying for an entire afternoon, but always get TLE. I started with brute force BFS, and later switched to bidirectional BFS, but it still times out. Thank you very much!!!

#include<bits/stdc++.h>
using namespace std;
using sta = array<int, 4>;
using ll = long long;

const int n = 70;
int t, a, b, c, d;
struct my_hash {
    size_t operator() (const sta &x) const {
        ll hash_val = (ll)x[0] * (n + 1) * (n + 1) * (n + 1) + 
                        (ll)x[1] * (n + 1) * (n + 1) + 
                        (ll)x[2] * (n + 1) +
                        (ll)x[3];
            return hash<ll>()(hash_val);
    }
};
int bfs(sta &x, unordered_map<sta, int, my_hash> &dis1, unordered_map<sta, int, my_hash> &dis2, queue<sta> &q) {
    for(int i = 0; i < x.size(); i++) {
        int l = x[i] - 1;
        if(l >= 1) {
            bool flag = 0;
            for(int k = 0; k < 4; k++) {
                if(k != i && x[k] == l) {
                    flag = 1;
                    break;
                }
            }
            if(!flag) {
                sta nxt = x;
                nxt[i] = l;
                sort(nxt.begin(), nxt.end());
                if(dis2.count(nxt)) {
                    return dis2[nxt] + dis1[x] + 1;
                }
                if(dis1.find(nxt) == dis1.end()) {
                    dis1[nxt] = dis1[x] + 1;
                    q.push(nxt);
                }
            }
        }
        int r = x[i] + 1;
        if(r <= n) {
            bool flag = 0;
            for(int k = 0; k < 4; k++) {
                if(k != i && x[k] == r) {
                    flag = 1;
                    break;
                }
            }
            if(!flag) {
                sta nxt = x;
                nxt[i] = r;
                sort(nxt.begin(), nxt.end());
                if(dis2.count(nxt)) {
                    return dis2[nxt] + dis1[x] + 1;
                }
                if(dis1.find(nxt) == dis1.end()) {
                    dis1[nxt] = dis1[x] + 1;
                    q.push(nxt);
                }
            }
        }
    }
    for(int i = 0; i < x.size(); i++) {
        for(int j = 0; j < x.size(); j++) {
            if(i == j) continue;
            int op = x[j] * 2 - x[i];
            if(op >= 1 && op <= n) {
                bool flag = 0;
                for(int k = 0; k < 4; k++) {
                    if(k != i && op == x[k]) {
                        flag = 1;
                        break;
                    }
                }
                if(!flag) {
                    sta nxt = x;
                    nxt[i] = op;
                    sort(nxt.begin(), nxt.end());
                    if(dis2.count(nxt)) {
                        return dis2[nxt] + dis1[x] + 1;
                    }
                    if(dis1.find(nxt) == dis1.end()) {
                        dis1[nxt] = dis1[x] + 1;
                        q.push(nxt);
                    }
                }
            }
        }
    }
    return -1;
}
void solve() {
    cin >> a >> b >> c >> d;
    sta st = {1, 2, 3, 4};
    sta ed = {a, b, c, d};
    sort(ed.begin(), ed.end());
    queue<sta> q1;
    queue<sta> q2;
    unordered_map<sta, int, my_hash> dis1, dis2;
    dis1[st] = 0;
    dis2[ed] = 0;
    q1.push(st);
    q2.push(ed);
    if(st == ed) {
        cout << 0 << endl;
        return;
    }
    int res = -1;
    while(!q1.empty() && !q2.empty()) {
        // for(int i = 0; i < 4; i++) {
        //     cout << x[i] << ' ' << y[i] << endl;  
        //     cout << endl;
        // }
        int cur_res;
        if(q1.size() >= q2.size()) {
            sta cur = q2.front();
            q2.pop();
            cur_res = bfs(cur, dis2, dis1, q2);
        } else {
            sta cur = q1.front();
            q1.pop();
            cur_res = bfs(cur, dis1, dis2, q1);
        }
        if(cur_res != -1) {
            res = cur_res;
            break;
        }
    }
    cout << res << endl;
}
int main() {
    cin >> t;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    while(t--) solve();
    return 0;
}
  • created

    Jun 11
  • last reply

    22d
  • 1

    reply

  • 57

    views

  • 2

    users

  • 1

    link

9 days later

I’ve not solved this but some thoughts…

  • Do you need to recreate the memo for each test case? Since the board is a fixed size, and the starting condition is always the same, you can re-use the memo between test cases. Possibly precompute the complete memo to get O(1) queries.
  • Would using a fixed array for the memo be faster than hashing and a map? Perhaps not. Since the chips are indistinguishable, you’d probably want to sort them before checking the memo, while your hashing gets around that problem quite neatly.

ADV04F3