Hi, dear contestants!
With the end of Codeforces Round #431 (Div. 1 and Div. 2), some might be complaining behind the screen that problems are too tricky or hard, or have been struggling with some supposedly solvable problem... Yes, this time problems seem hard, but anyways, I hope they provided you with something, say rating, fun, ideas, or experience. I don't want to see anyone losing confidence because of failure (bad luck) in a single contest — please, don't do so.
Here are the hints, tutorials and codes for the problems. Feel free to discuss about problems in the comments, and point out if something is incorrect or unclear. Thank you!
849A - Odds and Ends
by cyand1317
What will the whole array satisfy? Is that a sufficient condition?
#include <cstdio>
static const int MAXN = 102;
int n;
int a[MAXN];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
puts((n % 2 == 1) && (a[0] % 2 == 1) && (a[n - 1] % 2 == 1) ? "Yes" : "No");
return 0;
}
849B - Tell Your World
by cyand1317
First way: consider the first three points. What cases are there?
Second way: consider the first point. Either it's on a single line alone, or the line that passes through it passes through another point. Iterate over this point.
#include <bits/stdc++.h>
#define eps 1e-7
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,a[1007];
bool vis[1007];
bool check(double k,int b)
{
memset(vis,false,sizeof(vis));
int cnt=0;
for (int i=1;i<=n;i++)
{
if (a[i]-b==1LL*k*(i-1))
{
vis[i]=true;
++cnt;
}
}
if (cnt==n) return false;
if (cnt==n-1) return true;
int pos1=0;
for (int i=1;i<=n;i++)
if (!vis[i]&&pos1==0) pos1=i;
for (int i=pos1+1;i<=n;i++)
if (!vis[i])
{
if (fabs((double)(a[i]-a[pos1])/(i-pos1)-k)>eps) return false;
}
return true;
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
a[i]=read();
bool ans=false;
ans|=check(1.0*(a[2]-a[1]),a[1]);
ans|=check(0.5*(a[3]-a[1]),a[1]);
ans|=check(1.0*(a[3]-a[2]),a[2]*2-a[3]);
if (ans) printf("Yes\n"); else printf("No\n");
return 0;
}
#include <cstdio>
#include <algorithm>
static const int MAXN = 1004;
int n;
int y[MAXN];
bool on_first[MAXN];
bool check()
{
for (int i = 1; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if ((long long)i * (y[j] - y[0]) == (long long)j * (y[i] - y[0]))
on_first[j] = true;
else on_first[j] = false;
}
int start_idx = -1;
bool valid = true;
for (int j = 0; j < n; ++j) if (!on_first[j]) {
if (start_idx == -1) {
start_idx = j;
} else if ((long long)i * (y[j] - y[start_idx]) != (long long)(j - start_idx) * (y[i] - y[0])) {
valid = false; break;
}
}
if (valid && start_idx != -1) return true;
}
return false;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d", &y[i]);
bool ans = false;
ans |= check();
std::reverse(y, y + n);
ans |= check();
puts(ans ? "Yes" : "No");
return 0;
}
848A - From Y to Y
by cyand1317
For a given string, how to calculate the cost?
For each letter, count how many times it appears in the original string.
#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
int main()
{
int k;
scanf("%d", &k);
for (int i = 0; i < 26; i++)
{
int cnt = 1;
while ((cnt + 1) * cnt / 2 <= k) cnt++;
k -= cnt * (cnt - 1) / 2;
for (int j = 0; j < cnt; j++) printf("%c", 'a' + i);
}
return 0;
}
#include <cstdio>
#include <vector>
static const int MAXK = 100002;
static const int INF = 0x3fffffff;
int f[MAXK];
int pred[MAXK];
int main()
{
f[0] = 0;
for (int i = 1; i < MAXK; ++i) f[i] = INF;
for (int i = 0; i < MAXK; ++i) pred[i] = -1;
for (int i = 0; i < MAXK; ++i) if (f[i] != INF) {
for (int j = 2; i + j * (j - 1) / 2 < MAXK; ++j)
if (f[i + j * (j - 1) / 2] > f[i] + 1) {
f[i + j * (j - 1) / 2] = f[i] + 1;
pred[i + j * (j - 1) / 2] = j;
}
} else printf("Assertion failed at %d\n", i);
int k;
scanf("%d", &k);
if (k == 0) { puts("a"); return 0; }
std::vector<int> v;
for (; k > 0; k -= pred[k] * (pred[k] - 1) / 2) {
v.push_back(pred[k]);
}
for (int i = 0; i < v.size(); ++i) {
for (int j = 0; j < v[i]; ++j) putchar('a' + i);
}
putchar('\n');
return 0;
}
848B - Rooter's Song
by cyand1317
When do dancers collide? What changes and what keeps the same?
Group dancers by p - t. What happens next?
#include <cstdio>
#include <algorithm>
#include <vector>
static const int MAXN = 100004;
static const int MAXW = 100003;
static const int MAXT = 100002;
int n, w, h;
int g[MAXN], p[MAXN], t[MAXN];
std::vector<int> s[MAXW + MAXT];
int ans_x[MAXN], ans_y[MAXN];
int main()
{
scanf("%d%d%d", &n, &w, &h);
for (int i = 0; i < n; ++i) {
scanf("%d%d%d", &g[i], &p[i], &t[i]);
s[p[i] - t[i] + MAXT].push_back(i);
}
std::vector<int> xs, ys;
for (int i = 0; i < MAXW + MAXT; ++i) if (!s[i].empty()) {
for (int u : s[i]) {
if (g[u] == 1) xs.push_back(p[u]);
else ys.push_back(p[u]);
}
std::sort(xs.begin(), xs.end());
std::sort(ys.begin(), ys.end());
std::sort(s[i].begin(), s[i].end(), [] (int u, int v) {
if (g[u] != g[v]) return (g[u] == 2);
else return (g[u] == 2 ? p[u] > p[v] : p[u] < p[v]);
});
for (int j = 0; j < xs.size(); ++j) {
ans_x[s[i][j]] = xs[j];
ans_y[s[i][j]] = h;
}
for (int j = 0; j < ys.size(); ++j) {
ans_x[s[i][j + xs.size()]] = w;
ans_y[s[i][j + xs.size()]] = ys[ys.size() - j - 1];
}
xs.clear();
ys.clear();
}
for (int i = 0; i < n; ++i) printf("%d %d\n", ans_x[i], ans_y[i]);
return 0;
}
848C - Goodbye Souvenir
by adedalic
Difference between last occurrence and first occurrence equals the sum of differences between pairs of adjacent occurrences. Handle this with some segment tree, or even non-standard size block decomposition, say sizes of O(n2 / 3).
#include <bits/stdc++.h>
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) fore(i, 0, n)
#define all(a) (a).begin(), (a).end()
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back
#define x first
#define y second
using namespace std;
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {
return out << "(" << p.first << ", " << p.second << ")";
}
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {
out << "[";
forn(i, sz(v)) {
if(i > 0)
out << " ";
out << v[i];
}
return out << "]";
}
mt19937 myRand(time(NULL));
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
inline int gett() {
return clock() * 1000 / CLOCKS_PER_SEC;
}
const ld EPS = 1e-9;
const int INF = int(1e9);
const li INF64 = li(INF) * INF;
const ld PI = 3.1415926535897932384626433832795;
const int N = 100 * 1000 + 555;
int n, m, aa[N], a[N];
int qt[N], qx[N], qy[N];
inline bool read() {
if(!(cin >> n >> m))
return false;
forn(i, n)
assert(scanf("%d", &aa[i]) == 1);
forn(i, m) {
assert(scanf("%d%d%d", &qt[i], &qx[i], &qy[i]) == 3);
qx[i]--;
}
return true;
}
vector<int> vars[4 * N];
vector<li> f[4 * N];
li sumAll[4 * N];
inline void addValF(int k, int pos, int val) {
sumAll[k] += val;
for(; pos < sz(f[k]); pos |= pos + 1)
f[k][pos] += val;
}
inline li sum(int k, int pos) {
li ans = 0;
for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
ans += f[k][pos];
return ans;
}
inline li getSumF(int k, int pos) {
return sumAll[k] - sum(k, pos - 1);
}
li getSumST(int v, int l, int r, int lf, int rg, int val) {
if(l >= r || lf >= rg)
return 0;
if(l == lf && r == rg) {
int pos = int(lower_bound(all(vars[v]), val) - vars[v].begin());
return getSumF(v, pos);
}
int mid = (l + r) >> 1;
li ans = 0;
if(lf < mid)
ans += getSumST(2 * v + 1, l, mid, lf, min(mid, rg), val);
if(rg > mid)
ans += getSumST(2 * v + 2, mid, r, max(lf, mid), rg, val);
return ans;
}
void addValST(int k, int v, int l, int r, int pos, int pos2, int val) {
if(l >= r)
return;
if(!k)
vars[v].pb(pos2);
else {
int cpos = int(lower_bound(all(vars[v]), pos2) - vars[v].begin());
addValF(v, cpos, val);
}
if(l + 1 == r) {
assert(l == pos);
return;
}
int mid = (l + r) >> 1;
if(pos < mid)
addValST(k, 2 * v + 1, l, mid, pos, pos2, val);
else
addValST(k, 2 * v + 2, mid, r, pos, pos2, val);
}
int pr[N];
set<int> ids[N];
void build(int k, int v, int l, int r) {
fore(i, l, r)
if(!k)
vars[v].pb(pr[i]);
else {
int pos = int(lower_bound(all(vars[v]), pr[i]) - vars[v].begin());
addValF(v, pos, i - pr[i]);
}
if(l + 1 == r)
return;
int mid = (l + r) >> 1;
build(k, 2 * v + 1, l, mid);
build(k, 2 * v + 2, mid, r);
}
inline void eraseSets(int k, int pos) {
addValST(k, 0, 0, n, pos, pr[pos], -(pos - pr[pos]));
ids[ a[pos] ].erase(pos);
auto it2 = ids[ a[pos] ].lower_bound(pos);
if(it2 != ids[ a[pos] ].end()) {
int np = *it2;
assert(a[np] == a[pos]);
assert(pr[np] == pos);
addValST(k, 0, 0, n, np, pr[np], -(np - pr[np]));
pr[np] = pr[pos];
addValST(k, 0, 0, n, np, pr[np], +(np - pr[np]));
}
a[pos] = -1;
pr[pos] = -1;
}
inline void insertSets(int k, int pos, int nval) {
auto it2 = ids[nval].lower_bound(pos);
assert(it2 == ids[nval].end() || *it2 > pos);
if(it2 != ids[nval].end()) {
int np = *it2;
assert(a[np] == nval);
addValST(k, 0, 0, n, np, pr[np], -(np - pr[np]));
pr[np] = pos;
addValST(k, 0, 0, n, np, pr[np], +(np - pr[np]));
}
pr[pos] = -1;
if(it2 != ids[nval].begin()) {
auto it1 = it2; it1--;
assert(*it1 < pos);
pr[pos] = *it1;
}
addValST(k, 0, 0, n, pos, pr[pos], +(pos - pr[pos]));
ids[nval].insert(pos);
a[pos] = nval;
}
inline void precalc() {
forn(v, 4 * N) {
sort(all(vars[v]));
vars[v].erase(unique(all(vars[v])), vars[v].end());
f[v].assign(sz(vars[v]), 0);
sumAll[v] = 0;
}
}
inline void solve() {
forn(k, 2) {
if(k) precalc();
forn(i, N)
ids[i].clear();
forn(i, n)
a[i] = aa[i];
vector<int> ls(n + 1, -1);
forn(i, n) {
pr[i] = ls[ a[i] ];
ls[ a[i] ] = i;
ids[ a[i] ].insert(i);
}
build(k, 0, 0, n);
// cerr << k << " " << clock() << endl;
forn(q, m) {
if(qt[q] == 1) {
eraseSets(k, qx[q]);
insertSets(k, qx[q], qy[q]);
} else
if(k) printf("%I64d\n", getSumST(0, 0, n, qx[q], qy[q], qx[q]));
}
// cerr << k << " " << clock() << endl;
}
}
int main(){
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int t = gett();
#endif
srand(time(NULL));
cout << fixed << setprecision(10);
while(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << gett() - t << endl;
t = gett();
#endif
}
return 0;
}
848D - Shake It!
by cyand1317
Use DP. f[i][j] keeps the number of subgraphs with i operations and a minimum cut of j. The transition may be in a knapsack-like manner. Add more functions (say another g[i][j]) if needed to make it faster.
There are more than one way to do DP, you can also read about other nice solutions here and here.
#include <cstdio>
#include <cstring>
typedef long long int64;
static const int MAXN = 53;
static const int MODULUS = 1e9 + 7;
#define _ % MODULUS
#define __ %= MODULUS
int n, m;
// f[# of operations][mincut] -- total number of graphs
// g[# of operations][mincut] -- number of ordered pairs of two graphs
int64 f[MAXN][MAXN] = {{ 0 }}, g[MAXN][MAXN] = {{ 0 }};
int64 h[MAXN][MAXN];
inline int64 qpow(int64 base, int exp) {
int64 ans = 1;
for (; exp; exp >>= 1, (base *= base)__) if (exp & 1) (ans *= base)__;
return ans;
}
int64 inv[MAXN];
int main()
{
for (int i = 0; i < MAXN; ++i) inv[i] = qpow(i, MODULUS - 2);
scanf("%d%d", &n, &m);
f[0][1] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i + 1; ++j) {
// Calculate g[i][*]
// pair(i)(j) = graph(p)(r) in series with graph(q)(s)
// where p+q == i-1, min(r, s) == j
for (int p = 0; p <= i - 1; ++p) {
int q = i - 1 - p;
for (int r = j; r <= p + 1; ++r)
(g[i][j] += (int64)f[p][r] * f[q][j])__;
for (int s = j + 1; s <= q + 1; ++s)
(g[i][j] += (int64)f[p][j] * f[q][s])__;
}
// Update all f with g[i][*]
// Iterate over the number of times pair(i)(j) is appended in parallel, let it be t
// h is used as a temporary array
memset(h, 0, sizeof h);
for (int p = 0; p <= n; ++p)
for (int q = 1; q <= p + 1; ++q) {
int64 comb = 1;
for (int t = 1; p + t * i <= n; ++t) {
comb = comb * (g[i][j] + t - 1)_ * inv[t]_;
(h[p + t * i][q + t * j] += f[p][q] * comb)__;
}
}
for (int p = 0; p <= n; ++p)
for (int q = 1; q <= p + 1; ++q)
(f[p][q] += h[p][q])__;
}
}
printf("%lld\n", f[n][m]);
return 0;
}
848E - Days of Floral Colours
by cyand1317
Break the circle down into semicircles. Then there will be 1D/1D recurrences over several functions.
Use FFT in a divide-and-conquer manner to optimize it.
#include <cstdio>
typedef long long int64;
static const int MAXN = 50004;
static const int MODULUS = 998244353;
#define _ % MODULUS
#define __ %= MODULUS
int n;
int64 g[MAXN];
int64 f0[MAXN], f1[MAXN], f2[MAXN];
int main()
{
scanf("%d", &n);
g[0] = 1;
g[2] = 1;
for (int i = 4; i <= n; i += 2) g[i] = (g[i - 4] + g[i - 2])_;
f0[0] = 0;
f1[0] = 1;
f2[0] = 4;
for (int i = 1; i <= n; ++i) {
f0[i] = g[i] * i _ * i _;
for (int j = 1; j <= i - 2; ++j) {
f0[i] += g[j] * j _ * j _ * f0[i - j - 1]_;
f0[i] += g[j - 1] * j _ * j _ * f1[i - j - 2]_;
}
f1[i] = g[i] * (i + 1)_ * (i + 1)_ + f0[i - 1];
for (int j = 1; j <= i - 2; ++j) {
f1[i] += g[j] * (j + 1)_ * (j + 1)_ * f0[i - j - 1]_;
f1[i] += g[j - 1] * (j + 1)_ * (j + 1)_ * f1[i - j - 2]_;
}
f0[i]__; f1[i]__;
}
for (int i = 1; i <= n; ++i) {
f2[i] = g[i] * (i + 2)_ * (i + 2)_ + f1[i - 1];
for (int j = 1; j <= i - 1; ++j) {
f2[i] += g[j] * (j + 1)_ * (j + 1)_ * f1[i - j - 1]_;
f2[i] += g[j - 1] * (j + 1)_ * (j + 1)_ * f2[i - j - 2]_;
}
f2[i]__;
}
int64 ans = 0;
ans += (g[n - 1] + g[n - 3]) * (n - 1)_ * (n - 1)_ * n _;
for (int i = 2; i <= n - 2; ++i) {
ans += g[i - 1] * (i - 1)_ * (i - 1)_ * f0[n - i - 1]_ * i _;
ans += g[i - 2] * (i - 1)_ * (i - 1)_ * f1[n - i - 2]_ * 2 * i _;
if (i >= 3 && i <= n - 3)
ans += g[i - 3] * (i - 1)_ * (i - 1)_ * f2[n - i - 3]_ * i _;
}
printf("%lld\n", ans _);
return 0;
}
#include <cstdio>
#include <cstring>
typedef long long int64;
static const int LOGN = 18;
static const int MAXN = 1 << LOGN;
static const int MODULUS = 998244353;
static const int PRIMITIVE = 2192;
#define _ % MODULUS
#define __ %= MODULUS
template <typename T> inline void swap(T &a, T &b) { static T t; t = a; a = b; b = t; }
int n;
int64 g[MAXN];
int64 g0[MAXN], g1[MAXN], g2[MAXN];
int64 f0[MAXN], f1[MAXN], f2[MAXN];
int64 q0[MAXN], q1[MAXN];
int64 t1[MAXN], t2[MAXN], t3[MAXN], t4[MAXN];
inline int qpow(int64 base, int exp)
{
int64 ans = 1;
for (; exp; exp >>= 1) { if (exp & 1) (ans *= base)__; (base *= base)__; }
return ans;
}
int bitrev[LOGN][MAXN];
int root[2][LOGN];
inline void fft(int n, int64 *a, int direction)
{
int s = __builtin_ctz(n);
int64 u, v, r, w;
for (int i = 0; i < n; ++i) if (i < bitrev[s][i]) swap(a[i], a[bitrev[s][i]]);
for (int i = 1; i <= n; i <<= 1)
for (int j = 0; j < n; j += i) {
r = root[direction == -1][__builtin_ctz(i)];
w = 1;
for (int k = j; k < j + (i >> 1); ++k) {
u = a[k];
v = (a[k + (i >> 1)] * w)_;
a[k] = (u + v)_;
a[k + (i >> 1)] = (u - v + MODULUS)_;
w = (w * r)_;
}
}
}
inline void convolve(int n, int64 *a, int64 *b, int64 *c)
{
static int64 a1[MAXN], b1[MAXN];
memcpy(a1, a, n * 2 * sizeof(int64));
memcpy(b1, b, n * 2 * sizeof(int64));
memset(a + n, 0, n * sizeof(int64));
memset(b + n, 0, n * sizeof(int64));
fft(n * 2, a, +1);
fft(n * 2, b, +1);
int64 q = qpow(n * 2, MODULUS - 2);
for (int i = 0; i < n * 2; ++i) c[i] = a[i] * b[i]_;
fft(n * 2, c, -1);
for (int i = 0; i < n; ++i) c[i] = c[i] * q _;
memcpy(a, a1, n * 2 * sizeof(int64));
memcpy(b, b1, n * 2 * sizeof(int64));
}
// Calcukates f0 and f1.
void solve_1(int l, int r)
{
if (l == r) {
(f0[l] += g0[l])__;
(f1[l] += g1[l])__;
return;
}
int m = (l + r) >> 1;
solve_1(l, m);
int len = 1;
while (len < r - l + 1) len <<= 1;
for (int i = 0; i < len; ++i) q0[i] = (i + l <= m ? f0[i + l] : 0);
for (int i = 0; i < len; ++i) q1[i] = (i + l <= m ? f1[i + l] : 0);
for (int i = len; i < len * 2; ++i) q0[i] = q1[i] = 0;
convolve(len, g0, q0, t1);
convolve(len, g1, q0, t2);
convolve(len, g1, q1, t3);
convolve(len, g2, q1, t4);
for (int i = 0; i < len; ++i) {
if (i + l >= m + 1 - 1 && i + l <= r - 1) {
(f0[i + l + 1] += t1[i])__;
(f1[i + l + 1] += t2[i])__;
}
if (i + l >= m + 1 - 3 && i + l <= r - 3) {
(f0[i + l + 3] += t3[i])__;
(f1[i + l + 3] += t4[i])__;
}
}
solve_1(m + 1, r);
}
// Calculates f2.
void solve_2(int l, int r)
{
if (l == r) {
(f2[l] += (g2[l] + (l >= 1 ? t1[l - 1] : 0)))__;
return;
}
int m = (l + r) >> 1;
solve_2(l, m);
int len = 1;
while (len < r - l + 1) len <<= 1;
for (int i = 0; i < len; ++i) q0[i] = (i + l <= m ? f2[i + l] : 0);
for (int i = len; i < len * 2; ++i) q0[i] = 0;
convolve(len, g2, q0, t2);
for (int i = 0; i < len; ++i) {
if (i + l >= m + 1 - 3 && i + l <= r - 3) {
(f2[i + l + 3] += t2[i])__;
}
}
solve_2(m + 1, r);
}
int main()
{
for (int s = 0; s < LOGN; ++s)
for (int i = 0; i < (1 << s); ++i)
bitrev[s][i] = (bitrev[s][i >> 1] >> 1) | ((i & 1) << (s - 1));
for (int i = 0; i < LOGN; ++i) {
root[0][i] = qpow(PRIMITIVE, MAXN >> i);
root[1][i] = qpow(PRIMITIVE, MAXN - (MAXN >> i));
}
scanf("%d", &n);
g[0] = 1;
g[2] = 1;
for (int i = 4; i <= n; i += 2) g[i] = (g[i - 4] + g[i - 2])_;
for (int i = 0; i <= n; ++i) {
g0[i] = g[i] * i _ * i _;
g1[i] = g[i] * (i + 1)_ * (i + 1)_;
g2[i] = g[i] * (i + 2)_ * (i + 2)_;
}
solve_1(0, n);
int len = 1;
while (len < n) len <<= 1;
convolve(len, g1, f1, t1);
solve_2(0, n);
int64 ans = 0;
ans += (g[n - 1] + g[n - 3]) * (n - 1)_ * (n - 1)_ * n _;
for (int i = 2; i <= n - 2; ++i) {
ans += g0[i - 1] * f0[n - i - 1]_ * i _;
ans += g1[i - 2] * f1[n - i - 2]_ * 2 * i _;
if (i >= 3 && i <= n - 3)
ans += g2[i - 3] * f2[n - i - 3]_ * i _;
}
printf("%lld\n", ans _);
return 0;
}
Behind the scene and random things (read if tired of problemsolving)
Perhaps some may have noticed that at the end of editorial of #418 it's written that
Probably it will be for Ha...
Yes, I had had ideas for the last four problems for Div. 2 by that time. Then I came up with Div. 2 A when lying on bed one night, seems I underestimated its trickiness :/
(1 September 2017 is also when the story of Harry Potter ends, so to me seems like a great coincidence?)
After my unsuccessful performance at the National Olympiad (that's another thing to talk about), on that evening when everything seemed dull, I changed Div. 1 E to what it looks like now — it used to be Div. 1 C or so. "I'm poor at problemsolving. This is the hardest I can come up with," I thought, "and if it doesn't qualify then I'd better give up on holding a round with Div. 1."
Then in early August I created the proposal with all problems. After it was reviewed, some of them were changed, moved or replaced, and I ended up having no Div. 1 D. I had an idea and put it to Div. 1 D, but we had difficulty distinguishing different complexities, so it was set aside and replaced with the problem from adedalic. Schoolwork kept disrupting me from working on preparation, but I managed to allocate time to do it all for my own problems (except tutorials, :P). adedalic's problem is prepared by him and KAN, thank you!
Then two hours before the contest, it was suggested that swapping Div. 1 C and Div. 1 D would be good. I had't had enough time to test the new problem myself, but I thought the second division may prefer data structures to multidimensional DP and agreed. Then Div. 1 contestants jump from A to C and had unfavourable luck... My sympathy, hope you have enjoyed the problems themselves.
These are random fragments of the story behind this round. It wouldn't have been possible without you, dear contestants and members of the community. My deep gratitude!
Also, the problems feature songs created by songwriters and the voice of Hatsune Miku. Let it be happy or sad, separation or reunion, the problems are all inspired by the songs at the very beginning (not necessarily contents though, for example 2A and 1E are just related to the songs in title). Here's the list if you're interested.
- ODDS&ENDS by ryo
- Tell Your World by kz
- from Y to Y by OneRoom
- Rooter's Song by DECO*27
- Sayonara Souvenir (Goodbye Souvenir) by Toa
- shake it! by emon(Tes.)
- Hanairo Biyori (Flower Colored Weather) by Natsume Chiaki
Thank you for reading. Next round? Perhaps something more traditional, who knows? Believe me, I'll try harder if this happens.
Cheers! \(^ ^)/
UPD Packages for problems are uploaded. They are in Polygon format and contain everything including statements, tests & generators, validators & checkers, and solutions. You can download them from Google Drive or Baidu Drive.
