## Link

I felt you need more invetiveness/creativeness in this contest, and it was difficult.

## A – Shik and Stone

Compared to ARC (regular contest), it is slightly difficult even from problem A.

The most elegant solution is to just check the number of ‘#’ is equal to \(W+H−1\) or not as explained in Editorial.

However, I could not notice it so I checked that we can actually go using only right or down or not.

/* * AC 3 ms 256 KB */ #include <cstdio> #include <iostream> using namespace std; char a[8][9]; int main(){ //freopen("a3.in", "r", stdin); int h, w; scanf("%d %d", &h, &w); for (int i = 0; i < h; ++i) { scanf("%s", &a[i]); } int curH = 0, curW = 0; while (curH != h-1 || curW != w-1) { a[curH][curW] = '.'; if (curH+1 < h && a[curH+1][curW] == '#') {curH++;} else if (curW+1 < w && a[curH][curW+1] == '#') {curW++;} else break; } a[curH][curW] = '.'; bool ans = true; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (a[i][j] == '#') ans = false; } } printf(ans ? "Possible\n" : "Impossible\n"); return 0; }

## B – Construct Sequences

You need to come up with one construction method which satisfies the 3 conditions.

Editorial way is much more easier than below construction.

/* * AC 10 ms 896 KB */ #include <cstdio> #include <iostream> using namespace std; int p[20005]; int q[20005]; int a[20005], b[20005]; int main(){ //freopen("b3.in", "r", stdin); int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &p[i]); q[p[i]] = i; } int lsum = 1, rsum = 1; for (int i = 1; i <= n; ++i) { lsum += q[i]; a[i] = lsum + i; } for (int i = n; i > 0; --i) { rsum += q[i]; b[i] = rsum + (n+1-i); } for (int i = 1; i <= n; ++i) { printf("%d%c", a[i], i == n ? '\n' : ' '); } for (int i = 1; i <= n; ++i) { printf("%d%c", b[i], i == n ? '\n' : ' '); } return 0; }

## C – Pushing Balls

Since most of the participants could not solve it, I’ll skip this.

## D – Shik and Game

This algorithm takes \(O(N^2)\), which pass only 600 points.

/* * */ #include <cstdio> #include <iostream> #define INF 1000000000000000LL using namespace std; typedef long long ll; ll x[100005]; ll dp[100005]; // dp[i]: minimum time until the exit // after you get coin at i-th place and you haven't feed to the rest yet. int main(){ //freopen("d2.in", "r", stdin); int N, E, T; scanf("%d %d %d", &N, &E, &T); x[0] = 0; for (int i = 1; i <= N; ++i) { scanf("%lli", &x[i]); } dp[N] = E - x[N]; //cout << "N = " << N << ", dp[N]= " << dp[N] << endl; for (int i = N - 1; i >= 0; --i) { dp[i] = INF; for (int j = i + 1; j <= N; ++j) { if ((2 * (x[j] - x[i+1])) > T) { dp[i] = min(dp[i], dp[j] + 3 * (x[j] - x[i+1]) + (x[i+1] - x[i])); } else { dp[i] = min(dp[i], dp[j] + (x[j] - x[i+1]) + T + (x[i+1] - x[i])); } } //cout << "i = " << i << ", dp[i]= " << dp[i] << endl; } printf("%lli\n", dp[0]); return 0; }