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 actual plot — they're inspired by five theme songs actually — and I'm not spoiling anyone of the series! ^ ^
Sympathy for those failing system tests on B... This problem was intended to experience a lot of hacks but somehow there are not so many.
Here are the detailed solutions to the problems. Feel free to write in the comments if there's anything incorrect or unclear.
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;
}
One more thing — Staying up late is bad for health.
Tutorial is loading...
Solution 1 - O(n^5)
#include <cstdio>
#include <cstring>
typedef long long int64;
static const int MAXN = 52;
static const int MODULUS = 1e9 + 7;
#define _ % MODULUS
#define __ %= MODULUS
int n, d[MAXN];
int64 f[2][MAXN][MAXN][MAXN][MAXN] = {{{{{ 0 }}}}};
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &d[i]);
int cur = 0, next = 1;
f[cur][d[0] == 2][d[0] == 3][d[1] == 2][d[1] == 3] = 1;
for (int i = 1; i < n - 1; ++i) {
memset(f[next], 0, sizeof f[next]);
for (int p1 = 0; p1 <= n; ++p1)
for (int p2 = 0; p1 + p2 <= n; ++p2)
for (int c1 = 0; c1 + p1 + p2 <= n; ++c1)
for (int c2 = 0; c1 + c2 + p1 + p2 <= n; ++c2) if (f[cur][p1][p2][c1][c2] > 0) {
int64 val = f[cur][p1][p2][c1][c2];
// (1) Start a new level
if (p1 == 0 && p2 == 0) {
(f[cur][c1][c2][0][0] += val)__;
continue;
}
// (2) Stay on current level
// Which type of vertex in the last level?
for (int last_level = 0; last_level <= 1; ++last_level) {
int last_ways;
if (last_level == 0) {
last_ways = p1;
if (--p1 < 0) { ++p1; continue; }
} else {
last_ways = p2;
if (--p2 < 0) { ++p2; continue; } else ++p1;
}
// Which type of vertices in the current level?
if (d[i + 1] == 2) {
// a) Leave as it is
(f[next][p1][p2][c1 + 1][c2] += val * last_ways)__;
// b) 1-plug
if (c1 >= 1)
(f[next][p1][p2][c1 - 1][c2] += val * last_ways * c1)__;
// c) 2-plug
if (c2 >= 1)
(f[next][p1][p2][c1 + 1][c2 - 1] += val * last_ways * c2)__;
} else {
// a) Leave as it is
(f[next][p1][p2][c1][c2 + 1] += val * last_ways)__;
// b) 1-plug
if (c1 >= 1)
(f[next][p1][p2][c1][c2] += val * last_ways * c1)__;
// c) 2-plug
if (c2 >= 1)
(f[next][p1][p2][c1 + 2][c2 - 1] += val * last_ways * c2)__;
// d) 1-plug + 1-plug
if (c1 >= 2)
(f[next][p1][p2][c1 - 2][c2] += val * last_ways * c1 * (c1 - 1) / 2)__;
// e) 2-plug + 2-plug
if (c2 >= 2)
(f[next][p1][p2][c1 + 2][c2 - 2] += val * last_ways * c2 * (c2 - 1) / 2)__;
// f) 1-plug + 2-plug
if (c1 >= 1 && c2 >= 1)
(f[next][p1][p2][c1][c2 - 1] += val * last_ways * c1 * c2)__;
}
if (last_level == 0) ++p1; else ++p2, --p1;
}
}
cur ^= 1, next ^= 1;
}
printf("%lld\n", f[cur][0][0][0][0]);
return 0;
}
Solution 2 - O(n^3) by KAN
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
#ifdef WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
const int maxn = 55;
const int MOD = 1000000007;
int ways[maxn][maxn][maxn];
int answer[maxn][maxn];
int n;
int d[maxn];
int sumd[maxn];
inline void add(int &a, ll b)
{
a = (a + b) % MOD;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &d[i]);
ways[0][0][0] = 1;
for (int c0 = 0; c0 <= n; c0++)
{
for (int c2 = 0; c2 <= n; c2++)
{
for (int c1 = 0; c1 <= n; c1++) if (c1 + c2 > 0)
{
if (c2 > 0)
{
if (c0 > 1) add(ways[c0][c1][c2], (ll)ways[c0 - 2][c1][c2 - 1] * (c0 * (c0 - 1) / 2)); // 2-0, 2-0
if (c2 > 1 && c0 > 0) add(ways[c0][c1][c2], (ll)ways[c0 - 1][c1 + 1][c2 - 2] * (c2 - 1) * c0); // 2-2, 2-0
if (c2 > 2) add(ways[c0][c1][c2], (ll)ways[c0][c1 + 2][c2 - 3] * ((c2 - 1) * (c2 - 2) / 2)); // 2-2, 2-2
if (c1 > 0 && c2 > 1) add(ways[c0][c1][c2], (ll)ways[c0][c1][c2 - 2] * c1 * (c2 - 1)); // 2-2, 2-1
if (c1 > 0 && c0 > 0) add(ways[c0][c1][c2], (ll)ways[c0 - 1][c1 - 1][c2 - 1] * c1 * c0); // 2-1, 2-0
if (c1 > 1) add(ways[c0][c1][c2], (ll)ways[c0][c1 - 2][c2 - 1] * (c1 * (c1 - 1) / 2)); // 2-1, 2-1
} else
{
if (c0 > 0) add(ways[c0][c1][c2], ways[c0 - 1][c1 - 1][c2] * c0); // 1-0
if (c1 > 1) add(ways[c0][c1][c2], (ll)ways[c0][c1 - 2][c2] * (c1 - 1)); // 1-1
}
}
}
}
for (int i = 0; i < n; i++) sumd[i + 1] = sumd[i] + d[i];
answer[n][n - 1] = 1;
for (int l = n - 1; l > 0; l--)
{
for (int r = l; r < n; r++)
{
int cnt2 = sumd[r + 1] - sumd[l] - 2 * (r - l + 1);
int cnt1 = r - l + 1 - cnt2;
for (int nextlvl = 0; nextlvl <= 2 * cnt2 + cnt1 && nextlvl <= n; nextlvl++)
{
int curways = ways[nextlvl][cnt1][cnt2];
if (r + nextlvl < n)
{
add(answer[l][r], (ll)answer[r + 1][r + nextlvl] * curways);
}
}
}
}
if (d[0] + 1 > n) cout << 0 << endl;
else cout << answer[1][d[0]] << endl;
return 0;
}
This is the round with the most solutions so far perhaps? There are at least 3 × 2 × 3 × 3 × 3 = 162 different ways to pass all problems in this round =D
Pla-tinum happy though I'm supposed to be
Pla-tinum sad is somehow how I get
Personally I'd like to express my gratitude to the community for creating this amazing first-time experience for me. Thank you, and see you next round. Probably it will be for Ha... Well, let's wait and see :)
Cheers \(^ ^)/
