Hi, dear contestants!
With the end of Codeforces Round #431 (Div. 1 and Div. 2), I, as the author of most problems, have a feeling that lots are complaining behind the screen that problems are too tricky or hard, or are 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 hints and codes for the problems. Detailed tutorials of later problems will be available by tomorrow. Meanwhile, feel free to discuss about problems in the comments, and point out if something is incorrect. Thank you for your patience!
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
#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;
}