# AtCoder Grand Contest 007 review

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