Submission #675987

#	Time	Username	Problem	Language	Result	Execution time	Memory
675987		Tigerpants	Boarding Passes (BOI22_passes)	C++17	100 / 100	424 ms	38340 KiB

passes

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <bitset>
#include <queue>
#include <iomanip>
#include <cmath>
#include <string>

using namespace std;

typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<bool> vb;
typedef vector<vll> vvll;
typedef vector<vld> vvld;
typedef vector<vvll> vvvll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef set<ll> sll;
typedef set<pll> spll;
typedef map<pll, ll> mpll_ll;
typedef map<ll, pll> mll_pll;
typedef bitset<15> bits;
typedef vector<bits> vbits;
typedef string str;
typedef vector<str> vstr;

#define rep(x, a, b) for (int x = a; x < b; x++)
#define rev_rep(x, a, b) for (int x = a; x >= b; x--)
#define itr_rep(type_, x, b) for (type_::iterator x = b.begin(); x != b.end(); x++)
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()
#define sz(a) a.size()
#define resz(a, b) a.resize(b)
#define sort_all(a) sort(all(a))
#define pb(a) push_back(a)
#define fill_sz(a, b) fill_n(a.begin(), sz(a), b)

const ll MAXN = 100000;
const ll MAXG = 15;
const ld INF = MAXN * MAXN;

ll N, G;
string s;
vvll groups;

vvll prefix_sums;
vvvll passes;

struct Comparer {
    bool operator() (const bitset<15> &b1, const bitset<15> &b2) const {
        return (b1.to_ulong() < b2.to_ulong());
    }
};

bits active(0x0);
map<bits, vld, Comparer> dp_diff;
map<bits, ld, Comparer> dp;

ld calc_passes(ll i, ll k) {
    ld answ = 0;
    rep(j, 0, G) {
        if (!active[j]) {continue;}
        answ += passes[i][j][k];
    }
    answ += ((ld) k * (k - 1)) / 4;
    answ += ((ld) (sz(groups[i]) - k) * (sz(groups[i]) - k - 1)) / 4;
    return answ;
}

void dp_diff_DFS(ll depth=0) {
    if (depth != G) {
        dp_diff_DFS(depth + 1);
        active[depth] = true;
        dp_diff_DFS(depth + 1);
        active[depth] = false;
        return;
    }


    resz(dp_diff[active], G);
    rep(i, 0, G) {
        if (active[i]) {continue;}
        // consider the best way to have ppl from group i board given that groups in active have boarded, store this in dp
        // use ternary search...
        ll l = 0;
        ll r = sz(groups[i]);
        while (r - l > 2) {
            ll m1 = l + (r - l) / 3;
            ll m2 = r - (r - l) / 3;
            ld f1 = calc_passes(i, m1);
            ld f2 = calc_passes(i, m2);
            if (f1 > f2) {
                l = m1;
            } else {
                r = m2;
            }
        }
        

        dp_diff[active][i] = calc_passes(i, l);
        rep(c, l + 1, r + 1) {
            dp_diff[active][i] = min<ld>(dp_diff[active][i], calc_passes(i, c));
        }

        //dp_diff[active][i] = min<ld>(calc_passes(i, l), calc_passes(i, r));
    }
}

ld dp_recursion(bits call) {
    if (dp.count(call)) {return dp[call];}
    ld answ = INF;
    rep (i, 0, G) {
        if (!call[i]) {continue;}
        call[i] = false;
        answ = min<ld>(answ, dp_recursion(call) + dp_diff[call][i]);
        call[i] = true;
    }
    dp[call] = answ;
    return dp[call];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(15);

    cin >> s;
    N = sz(s);
    G = 0;
    rep(i, 0, N) {
        while (s[i] - 'A' >= G) {
            G++;
            groups.pb(vll());
        }
        groups[s[i] - 'A'].pb(i);
    }

    // calculate prefix sums
    resz(prefix_sums, G);
    rep(i, 0, G) {
        resz(prefix_sums[i], N + 1);
        prefix_sums[i][0] = 0;
        rep(j, 0, N) {
            prefix_sums[i][j + 1] = prefix_sums[i][j] + (s[j] - 'A' == i);
        }
    }
    
    // calculate passes between groups
    resz(passes, G);
    rep(i, 0, G) {
        resz(passes[i], G);
        rep(j, 0, G) {
            resz(passes[i][j], sz(groups[i]) + 1);
            fill_sz(passes[i][j], 0);
            // calculate the number of cumulative passes if first k of group i enter from front, and remaining |g|i]| - k enter from back
            // from front
            ll running_cumulative = 0;
            rep(k, 1, sz(groups[i]) + 1) {
                running_cumulative += prefix_sums[j][groups[i][k - 1]];
                passes[i][j][k] += running_cumulative;
            }
            // from back
            running_cumulative = 0;
            rev_rep(k, sz(groups[i]) - 1, 0) {
                running_cumulative += prefix_sums[j][N] - prefix_sums[j][groups[i][k]];
                passes[i][j][k] += running_cumulative;
            }
            // we have made sure that groups[i][k] is _excluded_ from counting as passed, as this makes the passes[e][e] case correct
        }
    }

    // calc subset dp
    dp_diff_DFS();


    // find optimal route...
    bits call(0x0);
    dp[call] = 0;
    rep(i, 0, G) {if (sz(groups[i])) {call[i] = true;}}
    cout << dp_recursion(call) << endl;

    return 0;
}

// for each pair of groups, need to know the number of passes if first k enter from front, and last |g[i]| - k enter from back

Compilation message (stderr)

passes.cpp: In function 'int main()':
passes.cpp:36:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 | #define rep(x, a, b) for (int x = a; x < b; x++)
......
  167 |             rep(k, 1, sz(groups[i]) + 1) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~ 
passes.cpp:167:13: note: in expansion of macro 'rep'
  167 |             rep(k, 1, sz(groups[i]) + 1) {
      |             ^~~

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40