# AtCoder Regular Contest 060 review

## 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;
}