We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. NP Complete
  4. Sam's Puzzle (Approximate)
  5. Discussions

Sam's Puzzle (Approximate)

Problem
Submissions
Leaderboard
Discussions

    You are viewing a single comment's thread. Return to all comments →

  • shehanjayalath
    3 years ago+ 0 comments

    C++14 Solution

    #include <iostream>
    #include <vector>
    #include <queue>
    #include <tuple>
    #include <functional>
    #include <chrono>
    #include <cassert>
    #define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
    #define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= int(m); --(i))
    typedef long long ll;
    using namespace std;
    template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
    template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
    template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
    
    const int inf = 1e9+7;
    const int limit = 500;
    int goodness(vector<vector<int> > const & f) {
        int n = f.size();
        int cnt = 0;
        repeat (y,n) repeat (xr,n) repeat (xl,xr) cnt += (f[y][xl] < f[y][xr]);
        repeat (x,n) repeat (yr,n) repeat (yl,yr) cnt += (f[yl][x] < f[yr][x]);
        return cnt;
    }
    vector<vector<int> > rotate(int y, int x, int k, vector<vector<int> > const & f) {
        vector<vector<int> > g = f;
        repeat (dy,k) repeat (dx,k) g[y+dx][x+k-dy-1] = f[y+dy][x+dx];
        return g;
    }
    pair<int, int> find_cell(vector<vector<int> > const & f, int k) {
        int n = f.size();
        repeat (y,n) repeat (x,n) if (f[y][x] == k) return { y, x };
        assert (false);
    }
    bool is_next_fixed(int y, int x, vector<vector<bool> > const & fixed) {
        return (y == 0 or fixed[y-1][x]) and (x == 0 or fixed[y][x-1]);
    }
    
    void solve_fast(int n, vector<vector<int> > & f, vector<tuple<int, int, int> > & result) {
        vector<vector<bool> > fixed = vectors(n, n, bool());
        vector<int> fixed_length(n);
        int next_fixed = 1;
        while (result.size() < limit*0.96 and next_fixed <= n*n) {
            int py, px; tie(py, px) = find_cell(f, next_fixed);
            if (is_next_fixed(py, px, fixed)) {
                fixed[py][px] = true;
                next_fixed += 1;
            } else {
                bool found = false;
                vector<vector<int> > dist = vectors(n, n, inf);
                vector<vector<tuple<int, int, int, int, int> > > path = vectors(n, n, tuple<int, int, int, int, int>());
                reversed_priority_queue<tuple<int, int, int> > que;
                dist[py][px] = 0;
                que.emplace(0, py, px);
                auto commit = [&](int y, int x) {
                    deque<tuple<int, int, int> > acc;
                    while (y != py or x != px) {
                        int ry, rx, rk; tie(y, x, ry, rx, rk) = path[y][x];
                        acc.emplace_front(ry, rx, rk);
                    }
                    if (result.size() + acc.size() > limit) return;
                    for (auto it : acc) {
                        int ry, rx, rk; tie(ry, rx, rk) = it;
                        f = rotate(ry, rx, rk, f);
                        result.push_back(it);
                    }
                    found = true;
                };
                while (not que.empty()) {
                    int z, y, x; tie(z, y, x) = que.top(); que.pop();
                    if (is_next_fixed(y, x, fixed)) {
                        commit(y, x);
                        break;
                    }
                    auto push = [&](int ny, int nx, int ry, int rx, int rk) {
                        if (dist[ny][nx] != inf) return;
                        dist[ny][nx] = z+1;
                        path[ny][nx] = make_tuple(y, x, ry, rx, rk);
                        que.emplace(z+1, ny, nx);
                    };
                    for (int k = 2; y+k-1 <  n and x+k-1 <  n and not fixed[y    ][x    ]; ++ k) push(y,     x+k-1, y,     x,     k); // right
                    for (int k = 2; y+k-1 <  n and x-k+1 >= 0 and not fixed[y    ][x-k+1]; ++ k) push(y+k-1, x,     y,     x-k+1, k); // down
                    for (int k = 2; y-k+1 >= 0 and x+k-1 <  n and not fixed[y-k+1][x    ]; ++ k) push(y-k+1, x,     y-k+1, x,     k); // up
                    for (int k = 2; y-k+1 >= 0 and x-k+1 >= 0 and not fixed[y-k+1][x-k+1]; ++ k) push(y,     x-k+1, y-k+1, x-k+1, k); // left
                }
                if (not found) break;
            }
        }
    }
    
    void solve_slow(int n, vector<vector<int> > & f, vector<tuple<int, int, int> > & result) {
        chrono::high_resolution_clock::time_point clock_begin = chrono::high_resolution_clock::now();
        while (result.size() < limit) {
            chrono::high_resolution_clock::time_point clock_end = chrono::high_resolution_clock::now();
            if (chrono::duration_cast<chrono::milliseconds>(clock_end - clock_begin).count() >= 1900) break;
            int best_y, best_x, best_k;
            int best = goodness(f);
            repeat (y,n) repeat (x,n) repeat_from_reverse (k,2,min(n-y,n-x)+1) {
                int z = goodness(rotate(y, x, k, f));
                if (best < z) {
                    best_y = y;
                    best_x = x;
                    best_k = k;
                    best   = z;
                }
            }
            if (best == goodness(f)) break;
            f = rotate(best_y, best_x, best_k, f);
            result.emplace_back(best_y, best_x, best_k);
        }
    }
    
    vector<tuple<int, int, int> > solve(int n, vector<vector<int> > f) {
        vector<tuple<int, int, int> > result;
        solve_fast(n, f, result);
        solve_slow(n, f, result);
        return result;
    }
    
    int main() {
        int n; cin >> n;
        vector<vector<int> > f = vectors(n, n, int());
        repeat (y,n) repeat (x,n) cin >> f[y][x];
        int gb = goodness(f);
        int gmax = n*n*(n-1);
        vector<tuple<int, int, int> > result = solve(n, f);
        cout << result.size() << endl;
        assert (result.size() <= 500);
        for (auto it : result) {
            int y, x, k; tie(y, x, k) = it;
            cout << y+1 << ' ' << x+1 << ' ' << k << endl;
            assert (0 <= y and y < n and 0 <= x and x < n and 1 <= k and max(y,x) + k <= n);
            f = rotate(y, x, k, f);
        }
        repeat (y,n) {
            repeat (x,n) cerr << (f[y][x] <= 9 ? " " : "") << f[y][x] << " ";
            cerr << endl;
        }
        cerr << "size: " << result.size() << endl;
        int ga = goodness(f);
        cerr << "points: " << ((ga - gb)/(double)(gmax - gb)) << endl;
        return 0;
    }
    
    -2|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy