Greetings!
Codeforces Round 418 (Div. 2) has just come to an end. This is my first round here, and hope you all enjoyed the contest! > <
Seems the statements still created a few issues :( Anyway hope you liked it, and the characters feature the Monogatari anime series. Let me state again that the statements has little to do with the plot and you are not spoiled for the series! ^ ^
So for the impatient, here are the detailed tutorials for problems A, B and C. More are being boiled in the teapot... Goo-doo goo-doo.
Tutorial is loading...
Solution 1
#include <cstdio>
static const int MAXN = 102;
int n, k;
int a[MAXN], b[MAXN];
int main()
{
scanf("%d%d", &n, &k);
int last_zero = -1;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
if (a[i] == 0) last_zero = i;
}
for (int i = 0; i < k; ++i) scanf("%d", &b[i]);
if (k > 1) {
puts("Yes");
} else {
a[last_zero] = b[0];
bool valid = false;
for (int i = 1; i < n; ++i)
if (a[i] <= a[i - 1]) { valid = true; break; }
puts(valid ? "Yes" : "No");
}
return 0;
}
Solution 2
#include <cstdio>
#include <algorithm>
static const int MAXN = 102;
int n, k;
int a[MAXN], b[MAXN];
int p[MAXN], r[MAXN];
inline bool check()
{
for (int i = 1; i < n; ++i) if (r[i] <= r[i - 1]) return true;
return false;
}
int main()
{
scanf("%d%d", &n, &k);
int last_zero = -1;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
if (a[i] == 0) last_zero = i;
}
for (int i = 0; i < k; ++i) scanf("%d", &b[i]);
bool valid = false;
for (int i = 0; i < k; ++i) p[i] = i;
do {
for (int i = 0, ptr = 0; i < n; ++i) {
r[i] = (a[i] == 0) ? b[p[ptr++]] : a[i];
}
if (check()) { valid = true; break; }
} while (std::next_permutation(p, p + k));
puts(valid ? "Yes" : "No");
return 0;
}
Tutorial is loading...
Solution 1
#include <cstdio>
#include <cstring>
static const int MAXN = 1e3 + 4;
int n;
int a[MAXN], b[MAXN];
int pa[2][MAXN], pb[2][MAXN];
inline void try_recover(int *a, int *p1, int *p2)
{
int dup_ct = 0;
int dup1 = -1, dup2 = -1, absent = -1;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (a[i] == a[j]) dup1 = i, dup2 = j;
for (absent = 1; absent <= n; ++absent) {
bool occurred = false;
for (int i = 0; i < n; ++i) if (a[i] == absent) { occurred = true; break; }
if (!occurred) break;
}
memcpy(p1, a, n * sizeof(int));
memcpy(p2, a, n * sizeof(int));
p1[dup1] = absent;
p2[dup2] = absent;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
try_recover(a, pa[0], pa[1]);
try_recover(b, pb[0], pb[1]);
int *ans = NULL;
if (memcmp(pa[0], pb[0], n * sizeof(int)) == 0 || memcmp(pa[0], pb[1], n * sizeof(int)) == 0)
ans = pa[0];
else ans = pa[1];
for (int i = 0; i < n; ++i) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
return 0;
}
Solution 2 - Casework
#include <cstdio>
#include <utility>
static const int MAXN = 1e3 + 4;
int n;
int a[MAXN], b[MAXN];
std::pair<int, int> get_duplication(int *a)
{
static int occ[MAXN];
for (int i = 1; i <= n; ++i) occ[i] = -1;
for (int i = 0; i < n; ++i) {
if (occ[a[i]] != -1) return std::make_pair(occ[a[i]], i);
else occ[a[i]] = i;
}
return std::make_pair(-1, -1);
}
inline void fix_permutation(int pos)
{
static bool occ[MAXN];
for (int i = 1; i <= n; ++i) occ[i] = false;
for (int i = 0; i < n; ++i) if (i != pos) occ[a[i]] = true;
for (int i = 1; i <= n; ++i) if (!occ[i]) { a[pos] = i; return; }
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
std::pair<int, int> dup_a, dup_b;
dup_a = get_duplication(a);
dup_b = get_duplication(b);
if (dup_a == dup_b) {
a[dup_a.first] = b[dup_b.first];
} else if (dup_a.first == dup_b.first || dup_a.first == dup_b.second) {
a[dup_a.second] = b[dup_a.second];
fix_permutation(dup_a.first);
} else if (dup_a.second == dup_b.first || dup_a.second == dup_b.second) {
a[dup_a.first] = b[dup_a.first];
fix_permutation(dup_a.second);
} else {
a[dup_a.first] = b[dup_a.first];
a[dup_a.second] = b[dup_a.second];
}
for (int i = 0; i < n; ++i) printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
return 0;
}
Tutorial is loading...
Solution
#include <cstdio>
#include <algorithm>
static const int MAXN = 1502;
static const int ALPHABET = 26;
int n;
char s[MAXN];
int ans[ALPHABET][MAXN] = {{ 0 }};
int q, m_i;
char c_i;
int main()
{
scanf("%d", &n); getchar();
for (int i = 0; i < n; ++i) s[i] = getchar() — 'a';
for (char c = 0; c < ALPHABET; ++c) {
for (int i = 0; i < n; ++i) {
int replace_ct = 0;
for (int j = i; j < n; ++j) {
if (s[j] != c) ++replace_ct;
ans[c][replace_ct] = std::max(ans[c][replace_ct], j - i + 1);
}
}
for (int i = 1; i < MAXN; ++i)
ans[c][i] = std::max(ans[c][i], ans[c][i - 1]);
}
scanf("%d", &q);
for (int i = 0; i < q; ++i) {
scanf("%d %c", &m_i, &c_i);
printf("%d\n", ans[c_i - 'a'][m_i]);
}
return 0;
}
Tutorial is loading...
Solution 1 - DP on trees
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
typedef long long int64;
static const int MAXN = 1004;
#ifndef M_PI
static const double M_PI = acos(-1.0);
#endif
int n;
int x[MAXN], y[MAXN], r[MAXN];
int par[MAXN];
std::vector<int> e[MAXN];
// Whether one of C[u] and C[v] is contained in another
inline bool circle_contains(int u, int v)
{
return ((int64)(x[u] - x[v]) * (x[u] - x[v]) + (int64)(y[u] - y[v]) * (y[u] - y[v]) <= (int64)(r[u] - r[v]) * (r[u] - r[v]));
}
int64 f[MAXN][2][2];
void dfs_dp(int u)
{
int64 g[2][2] = {{ 0 }};
for (int v : e[u]) {
dfs_dp(v);
for (int i = 0; i <= 1; ++i)
for (int j = 0; j <= 1; ++j)
g[i][j] += f[v][i][j];
}
for (int i = 0; i <= 1; ++i)
for (int j = 0; j <= 1; ++j) {
f[u][i][j] = std::max(
// (1) <u> is assigned to the first group
g[i ^ 1][j] + (int64)r[u] * r[u] * (i == 0 ? +1 : -1),
// (2) <u> is assigned to the second group
g[i][j ^ 1] + (int64)r[u] * r[u] * (j == 0 ? +1 : -1)
);
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);
for (int i = 0; i < n; ++i) {
par[i] = -1;
for (int j = 0; j < n; ++j)
if (r[j] > r[i] && circle_contains(i, j)) {
if (par[i] == -1 || r[par[i]] > r[j]) par[i] = j;
}
e[par[i]].push_back(i);
}
int64 ans = 0;
for (int i = 0; i < n; ++i) if (par[i] == -1) {
dfs_dp(i);
ans += f[i][0][0];
}
printf("%.8lf\n", (double)ans * M_PI);
return 0;
}
Solution 2 - Greedy
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
typedef long long int64;
static const int MAXN = 1004;
#ifndef M_PI
static const double M_PI = acos(-1.0);
#endif
int n;
int x[MAXN], y[MAXN], r[MAXN];
int par[MAXN];
std::vector<int> e[MAXN];
bool level[MAXN];
// Whether one of C[u] and C[v] is contained in another
inline bool circle_contains(int u, int v)
{
return ((int64)(x[u] - x[v]) * (x[u] - x[v]) + (int64)(y[u] - y[v]) * (y[u] - y[v]) <= (int64)(r[u] - r[v]) * (r[u] - r[v]));
}
void dfs_colour(int u, bool c)
{
level[u] = c;
for (int v : e[u]) dfs_colour(v, c ^ 1);
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);
for (int i = 0; i < n; ++i) {
par[i] = -1;
for (int j = 0; j < n; ++j)
if (r[j] > r[i] && circle_contains(i, j)) {
if (par[i] == -1 || r[par[i]] > r[j]) par[i] = j;
}
e[par[i]].push_back(i);
}
for (int i = 0; i < n; ++i) if (par[i] == -1) dfs_colour(i, false);
int64 ans = 0;
for (int i = 0; i < n; ++i)
ans += (int64)r[i] * r[i] * (par[i] == -1 || (level[i] == true) ? +1 : -1);
printf("%.8lf\n", (double)ans * M_PI);
return 0;
}
Goo-doo goo-doo...
