Solution for Topcoder Open 2018 / 1A / 1000

sol.cc

#include <vector>
#include <unordered_set>
#include <algorithm>
#include <cmath>
#include <tuple>
#include <iostream>

using namespace std;
typedef long long ll;


struct TupleComp {
    bool operator()(const tuple<ll, ll> &one, const tuple<ll, ll> &other) {
        return get<0>(one) < get<0>(other);
    }
};


struct Greater
{
        template<class T>
        bool operator()(T const &a, T const &b) const { return a > b; }
};


void show_uset(unordered_set<ll> &stuff) {
    for(auto &el : stuff) {
        cout << el << " ";
    }
    cout << endl;
}

void show_vector(vector<ll> &stuff) {
    for(auto &el : stuff) {
        cout << el << " ";
    }
    cout << endl;
}


void show_tup_vec(vector< tuple<ll, ll> > &stuff) {
    for(auto &el : stuff) {
        cout << "(" << get<0>(el) << ", " << get<1>(el) << ")" << " ";
    }
    cout << endl;
}


ll sort_num(ll num) {
    if(num == 0) {
        return 0;
    }
    vector<ll> acc;
    while(num > 0) {
        acc.push_back(num % 10);
        num /= 10;
    }
    sort(acc.begin(), acc.end(), Greater());
    ll multi = 1, ret = 0;
    for(vector<ll>::reverse_iterator rit = acc.rbegin(); rit !=  acc.rend(); rit++) {
        ret += multi * (*rit);
        multi *= 10;
    }
    return ret;
}


ll call_func(ll index, ll value) {
    switch (index) {
        case 0:
            return value + 1;
        case 1:
            return value - 1;
        case 2:
            return value * value;
        default:
            return sort_num(value);
    }
}


class Deadfish {
public:
    ll shortestCode(ll n) {
        ll limit = 10 * n + 1;
        vector<ll> distances(limit, limit);
        // cout << "limit: " << limit << endl;

        unordered_set<ll> was;
        was.insert(0);
        vector< tuple<ll, ll> > heap;
        ll nxt, distance;

        for (ll i = 0; i < 4; i++) {
            nxt = call_func(i, 0);
            if(nxt > 0 && nxt < limit) {
                heap.push_back(make_tuple(-1, nxt));
                push_heap(heap.begin(), heap.end(), TupleComp());
            }
        }

        while(was.find(n) == was.end() && ! heap.empty()) {
            // cout << "n: " << n;
            // cout << "\nwas\n";
            // show_uset(was);
            // cout << "\ndistances\n";
            // show_vector(distances);
            // cout << "\nheap\n";
            // show_tup_vec(heap);
            pop_heap(heap.begin(), heap.end(), TupleComp());
            tie(distance, nxt) = heap.back();
            distance = -distance;
            heap.pop_back();
            // cout << "nxt: " << nxt << endl;
            // cout << "distance: " << distance << endl;

            if(was.find(nxt) != was.end()) {
                continue;
            }

            was.insert(nxt);
            distances[nxt] = distance;

            for (ll i = 0; i < 4; i++) {
                ll nnxt = call_func(i, nxt);
                // cout << "nnxt: " << nnxt << endl;
                if(was.find(nnxt) == was.end() && nnxt > 0 && nnxt < limit) {
                    heap.push_back(make_tuple(-(distance + 1), nnxt));
                    push_heap(heap.begin(), heap.end(), TupleComp());
                }
            }
        }

        return distances[n];
    }
};


int main() {
    Deadfish c;
    ll n;
    cin >> n;
    cout << c.shortestCode(n) << endl;
    return 0;
}