AtCoder Regular Contest 060 review

Link

• ARC 060 top page
• Editorial

C: Tak and Cards – 高橋君とカード

• Dynamic programming

I could come up only full search using bit operation during the contest.

But it can be solved by DP. Below is full score (Section 3.3 of editorial) implementation.

/*
 * Ref http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
 * 3.3 Full score solution
 *
 * DP
 */
#include <cstdio>
#include <iostream>

typedef long long ll;
using namespace std;

ll x[51];

// dp_j[t] : possible #of sum = t - n*X using card y[i] (0<=i<=j) where y[i] := x[i] - a
ll dp[2][2*51*51];

int main(){
    //freopen("c4.in", "r", stdin);
    ll n, a;
    ll X = 0;  // Maximum absolute value of y[i], up to 50

    cin >> n >> a;

    for (ll i = 0; i < n; ++i) {
        cin >> x[i];
        x[i] -= a;
        X = max(X, abs(x[i]));
    }

    // Init
    dp[0][n*X] = 1LL;
    for (int j = 0; j < n; ++j) {
        for (ll t = 2*n*X; t >= 0; --t) {
            ll prevt = t-x[j];
            if (0 <= prevt && prevt <= 2*n*X) {
                dp[1][t] = dp[0][t] + dp[0][prevt];
            }
        }
        swap(dp[0], dp[1]);
    }

    cout << dp[0][n*X] - 1 << endl;
    return 0;
}

D: Digit Sum – 桁和

I came up different approach from editorial.

Let ai be i-th digit with base b. Then,

$$ n = \sum_i b^i a_i $$ $$ s = f(b, n) = \sum_i a_i $$

applies. If we subtract these equation, we obtain

$$ n – s = \sum_i (b^i – 1) a_i $$

Both side should be integer, and right hand side can be divided by \( (b−1) \). So \(b−1\) is a divisor of \(n−s\). To find out divisor of \(n−s\), it is enough to scan from 1 to \(\sqrt{n−s}\). The computational complexity is thus \(O(\sqrt{n−s})\)

/*
 *
 */
#include <cstdio>
#include <iostream>
#include <cmath>

#define INF ((ll)1e11 + 5)
typedef long long ll;
using namespace std;

// check whether f(b, n) == s exists or not.
bool check(ll b, ll n, ll s) {
    ll fbn = 0;
    while (n != 0) {
        fbn += n % b;
        n /= b;
    }
    return  fbn == s;
}

int main(){
    //freopen("d5.in", "r", stdin);
    ll n, s;
    cin >> n >> s;

    ll d = n - s;
    if (d < 0) {
        cout << -1 << endl;
    } else if (d == 0) {
        cout << n+1 << endl;
    } else { // n > s
        ll minB = INF;
        ll ub = (ll)sqrt((double) d) + 1LL;
        for (ll i = 1; i <= ub; ++i) {
            if (d % i == 0) {
                if (check(i + 1, n, s)) minB = min(minB, i + 1);
                if (check(d / i + 1, n, s)) minB = min(minB, d / i + 1);
            }
        }
        if (minB == INF) {
            cout << -1 << endl;
        } else {
            cout << minB << endl;
        }
    }
    return 0;
}

E: Tak and Hotels – 高橋君とホテル

During the contest, I was writing primitive solution. Its computational complexity is \(O(NQ)\) and thus it can answer only small size problem 〜 \(10^3 ∗ 10^3 = 10^6 \).

/*
 * Improve search to use upper_bound()
 * Computational Complexity O(NQ)  --- not change from e1.cpp
 */
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

int x[100005];
vector<pair<int, int>> vec; //  x_i, city

int main(){
    //freopen("e.in", "r", stdin);
    int n;
    int L;
    int Q;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
        vec.push_back(make_pair(x[i], i+1));
    }
    cin >> L;
    cin >> Q;

    sort(vec.begin(), vec.end());
    sort(x, x+n);

    for (int j = 0; j < Q; ++j) {
        int a, b;
        int ai, bi;
        cin >> a >> b;
        for (int i = 0; i < n; ++i) {
            if (vec[i].second == a) ai = i;
            if (vec[i].second == b) bi = i;
        }

        if (ai > bi) { swap(ai, bi); }

        ll day = 0;
        while (ai < bi) {
            int* xub = upper_bound(x, x+n, x[ai]+L);
            ai = xub - x - 1;
            day++;
        }
        cout << day << endl;
    }

    return 0;
}

 To solve big size solution, you beed a pre-calculation to prepare table r[k][i], explained in editorial.

Sample implementation is below.

/*
 * Ref: http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
 *
 * LCA (Lowest Common Ancestor), Doubling
 * O((N+Q)log N)
 */
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

int x[100005];
map<int, int> city_x_map; //  city, x_i

int r[18][100005]; // r[k][i]: hotel number, which we can reach from i-th hotel within 2^k days. (2^17 > 100005)

// assuming a <= b
ll calcDay(int a, int b) {
    ll day = 0;
    while (true) {
        if (a == b) { return day; }

        int k = 0;
        while(r[k][a] < b) {
            k++;
            //cout << "k " << k << ", a " << a << ", r[k][a] " << r[k][a] << endl;
        }
        // now r[k][a] >= b, update a and day
        if (k == 0) {
            return day+1LL;
        } else {
            a = r[k-1][a];
            day += (1LL << (k - 1));
        }
    }
}

int main(){
    //freopen("e.in", "r", stdin);
    int n;
    int L;
    int Q;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
        city_x_map.insert(make_pair(i+1, x[i]));
    }
    cin >> L;
    cin >> Q;

    sort(x, x+n);

    // Prepare r[k][i] using doubling
    for (int i = 0; i < n; ++i) {
        r[0][i] = (int)(upper_bound(x, x+n, x[i]+L) - x) - 1;
    }
    int maxK = 0;
    while (n >> maxK > 0) maxK++;
    for (int k = 0; k < maxK; ++k) {
        for (int i = 0; i < n; ++i) {
            r[k+1][i] = r[k][r[k][i]];
        }
    }

    // solve
    for (int j = 0; j < Q; ++j) {
        int a, b;     // original hotel number
        int axi, bxi; // hotel x coordinate
        cin >> a >> b;
        axi = city_x_map[a];
        bxi = city_x_map[b];

        if (axi > bxi) { swap(axi, bxi); }

        a = lower_bound(x, x+n, axi) - x;  // sorted hotel number
        b = lower_bound(x, x+n, bxi) - x;  // sorted hotel number

        //cout << a << " " << b << endl; // debug

        ll day = calcDay(a, b);

        cout << day << endl;
    }
    return 0;
}