USACO 4.4 Shuttle Puzzle

BFS with pruning with key observation that W can only moves to right, and B can only moves to left to satisfy the constraints of smallest lexicographic order. Also the judge has tight memory bounds, so decide state duplication needs to use hashing (i.e. if using a set then memory will grow out of bounds for “large” test data set.).

#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <queue>
#include <functional>

using namespace std;

typedef struct State {
    int op; // index of the hole where next operation is going to happen.
    struct State *prev;
    string state;
    int empty; // index of empty hole.
    State(int op, string state, int empty, State *prev) :
    op(op), state(state), empty(empty), prev(prev) {}
} State;

queue<State*> q;
vector<State*> sp;
string target;
string start;
State *ss;
int N;
set<int> visited;
vector<int> solution;

void setup() {
    start = string(2 * N + 1, ' ');
    target = string(2 * N + 1, ' ');
    
    for (int i = 0; i < N; ++i) {
        start[i] = 'W';
        target[i] = 'B';
    }
    
    for (int i = N + 1; i < 2 * N + 1; ++i) {
        start[i] = 'B';
        target[i] = 'W';
    }
    
    ss = new State(0, start, N, nullptr);
    q.push(ss);
    sp.push_back(ss);
}

void bfs() {
    while (!q.empty()) {
        auto s = q.front(); q.pop();
        if (s->state == target) {
            cout << "target state reached." << endl;
            while (s) {
                solution.push_back(s->op);
                s = s->prev;
            }
            return;
        }
        
        int empty = s->empty;
        
        // W_ : W move right
        if (empty > 0 && s->state[empty - 1] == 'W') {
            auto next = new State(*s);
            sp.push_back(next);
            next->state[empty] = 'W';
            next->state[empty - 1] = ' ';
            next->op = empty - 1;
            next->prev = s;
            next->empty--;
            auto h = std::hash<string>{}(next->state);
            if (!visited.count(h)) {
                visited.insert(h);
                q.push(next);
            }
        }
        
        // _B : B move left
         if (empty < 2 * N && s->state[empty + 1] == 'B') {
            auto next = new State(*s);
            sp.push_back(next);
            next->state[empty] = 'B';
            next->state[empty + 1] = ' ';
            next->op = empty + 1;
            next->prev = s;
            next->empty++;
            auto h = std::hash<string>{}(next->state);
            if (!visited.count(h)) {
                visited.insert(h);
                q.push(next);
            }
        }
        
        // WB_ : W jump right
        if (empty > 1 && s->state[empty - 2] == 'W' &&
            s->state[empty - 1] != 'W') {
            auto next = new State(*s);
            sp.push_back(next);
            next->state[empty] = 'W';
            next->state[empty - 2] = ' ';
            next->op = empty - 2;
            next->prev = s;
            next->empty -= 2;
            auto h = std::hash<string>{}(next->state);
            if (!visited.count(h)) {
                visited.insert(h);
                q.push(next);
            }
        }
        
        // _WB : B jump left
        if (empty < 2 * N - 1 && s->state[empty + 2] == 'B' &&
            s->state[empty + 1] == 'W') {
            auto next = new State(*s);
            sp.push_back(next);
            next->state[empty] = 'B';
            next->state[empty + 2] = ' ';
            next->op = empty + 2;
            next->prev = s;
            next->empty += 2;
            auto h = std::hash<string>{}(next->state);
            if (!visited.count(h)) {
                visited.insert(h);
                q.push(next);
            }
        }
    }
}

int main() {
    ifstream fin("shuttle.in");
    ofstream fout("shuttle.out");
    fin >> N;
    setup();
    bfs();
    
    int cnt = 0, size = (int)solution.size() - 1;
    for (int i = size - 1; i >= 0; --i) {
        ++cnt;
        cout << solution[i] + 1;
        fout << solution[i] + 1;
        if (cnt == 20 && i) {
            cout << endl;
            fout << endl;
            cnt = 0;
        } else if (i) {
            cout << " ";
            fout << " ";
        }
    }
    
    for (auto ptr : sp) {
        if (ptr != nullptr) {
            delete ptr; ptr = nullptr;
        }
    }
    
    cout << endl;
    fout << endl;
}

2017-02-01

Distributed System

Why we need n >= 3f + 1 in Byzantine Fault Tolerance

In distributed systems where messages are asynchronous and failures can be Byzantine, we have to use at least n = 3f + 1 replicas in total to tolerate f faulty replicas. But why?

Consider this scenario: a client sends the same command to each of n servers and then waits for servers to execute the command and send back the result. If we have f byzantine servers, then up to f messages could not be trusted, or up to f servers could not responding. So the client must be able to function with n - f responses. In addition, as the messages are asynchronous, these messages could be delayed for an indefinite amount of time. So if there are f messages not received by client, then it could be also be that these f messages are not from faulty servers, but instead caused by networking partition or slow responding non-faulty servers. In this case, where the f messages are from slow but non-faulty servers, we will have n - f messages remaining and out of these n - f messages, there could be at most f faulty messages again from byzantine servers, so the worst case we will have n - 2f correct message. For the system to function properly, the correct messages must out number faulty messages for client to identify which is which, which implies we should have n - 2f > f, so n > 3f where f is the number of byzantine servers.

2017-01-31

TopCoder

SRM 707 DIV 2 500 Steps Construct

Problem with interesting constraints… hopefully figured this out during SRM this time.


using namespace std;

class StepsConstruct {
    int rows;
    int cols;
    char getD(char c) {
        if (c == 'R') return 'L';
        if (c == 'L') return 'R';
        if (c == 'U') return 'D';
        if (c == 'D') return 'U';
        return 'R';
    }
public:
    string construct(vector <string> board, int k) {
        if (board[0][0] == '#') return "";
        rows = (int)board.size(); cols = (int)board[0].size();
        set<pair<int,int>> visited;
        vector<string> paths;
        queue<pair<int, int>> q;
        queue<string> qp;
        q.push(make_pair(0, 0));
        qp.push("");
        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            int x = cur.first, y = cur.second;
            string curp = qp.front();
            qp.pop();
            
            int dx[] = {1, -1, 0, 0};
            int dy[] = {0, 0, 1, -1};
            char steps[] = {'D', 'U', 'R', 'L'};
            for (int i = 0; i < 4; ++i) {
                pair<int,int> cur = {x + dx[i], y + dy[i]};
                if(cur.first < 0 || cur.second < 0 || cur.first >= rows || cur.second >= cols)
                    continue;
                if(visited.count(cur))
                    continue;
                if (board[cur.first][cur.second] == '#') {
                    visited.insert(cur);
                    continue;
                }
                
                string p = curp + steps[i];
                if (cur.first == rows - 1 && cur.second == cols - 1) {
                    paths.push_back(p);
                    continue;
                }

                visited.insert(cur);
                qp.push(p);
                q.push(cur);
            }
        }
        
        int minsteps = INT_MAX;
        for (auto path : paths) {
            minsteps = std::min((int)path.size(), minsteps);
        }
        if (minsteps > k) return "";
        
        string c;
        for (auto path : paths) {
            int steps = (int)path.size();
            if (steps <= k && ((k - steps) % 2 == 0)) {
                int d = k - steps;
                string prefix = "";
                char c = path[0];
                for (int i = 0; i < d; ++i) {
                    prefix += c;
                    c = getD(c);
                }
                return prefix + path;
            }
        }
        return "";
    }
}