Idea: Neon
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
string p, h;
bool read(){
if (!(cin >> p >> h))
return false;
return true;
}
void solve(){
int n = h.size();
vector<int> cntp(26);
forn(i, p.size())
++cntp[p[i] - 'a'];
forn(i, n){
vector<int> cnth(26);
for (int j = i; j < n; ++j){
++cnth[h[j] - 'a'];
if (cntp == cnth){
puts("YES");
return;
}
}
}
puts("NO");
}
int main() {
int tc;
scanf("%d", &tc);
forn(_, tc){
read();
solve();
}
return 0;
}
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int AL = 26;
string p, h;
bool read(){
if (!(cin >> p >> h))
return false;
return true;
}
void solve(){
vector<int> cntp(AL), cnt(AL);
vector<bool> eq(AL);
int sum = 0;
auto chg = [&cntp, &cnt, &eq, &sum](int c, int val){
sum -= eq[c];
cnt[c] += val;
eq[c] = (cntp[c] == cnt[c]);
sum += eq[c];
};
forn(i, p.size())
++cntp[p[i] - 'a'];
forn(i, AL){
eq[i] = (cnt[i] == cntp[i]);
sum += eq[i];
}
int m = p.size();
int n = h.size();
forn(i, n){
chg(h[i] - 'a', 1);
if (i >= m) chg(h[i - m] - 'a', -1);
if (sum == AL){
puts("YES");
return;
}
}
puts("NO");
}
int main() {
int tc;
scanf("%d", &tc);
forn(_, tc){
read();
solve();
}
return 0;
}
Idea: Roms
#include <bits/stdc++.h>
using namespace std;
int t, a, b;
bool ok(int res, int d){
long long sum = res * 1LL * (res + 1) / 2;
if(sum < d) return false;
return sum % 2 == d % 2;
}
int main() {
cin >> t;
for(int tc = 0; tc < t; ++tc){
cin >> a >> b;
int d = abs(a - b);
if(d == 0){
cout << "0\n";
continue;
}
int res = 1;
while(!ok(res, d)) ++res;
cout << res << endl;
}
return 0;
}
Idea: MikeMirzayanov
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n;
vector<int> a;
bool read(){
if (scanf("%d", &n) != 1)
return false;
a.resize(2 * n);
forn(i, 2 * n)
scanf("%d", &a[i]);
return true;
}
void solve(){
int cur = 0;
map<int, int> difr;
difr[0] = 0;
cur = 0;
for (int i = n; i < 2 * n; ++i){
if (a[i] == 1)
++cur;
else
--cur;
if (!difr.count(cur))
difr[cur] = i - (n - 1);
}
int ans = 2 * n;
int dif = count(a.begin(), a.end(), 1) - count(a.begin(), a.end(), 2);
cur = 0;
for (int i = n - 1; i >= 0; --i){
if (a[i] == 1)
++cur;
else
--cur;
if (difr.count(dif - cur))
ans = min(ans, n - i + difr[dif - cur]);
}
if (difr.count(dif)){
ans = min(ans, difr[dif]);
}
printf("%d\n", ans);
}
int main() {
int tc;
scanf("%d", &tc);
forn(_, tc){
read();
solve();
}
return 0;
}
Idea: Neon
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); i++)
typedef long long li;
typedef pair<li, li> pt;
const int N = 500010;
int n;
pt a[N];
vector<int> g[N];
bool used[N];
void dfs(int v, int p = -1) {
used[v] = true;
for (auto to : g[v]) if (to != p) {
if (!used[to])
dfs(to, v);
}
}
int main() {
scanf("%d", &n);
forn(i, n) scanf("%d%d", &a[i].x, &a[i].y);
vector<pt> evs;
forn(i, n) {
evs.pb(mp(a[i].x, i));
evs.pb(mp(a[i].y, i));
}
sort(all(evs));
int cnt = 0;
set<pt> cur;
for (auto it : evs) {
if (cnt >= n) break;
if (cur.count(it)) {
cur.erase(it);
} else {
int i = it.y;
int r = a[i].y;
for (auto jt : cur) {
if (jt.x > r) break;
int j = jt.y;
g[i].pb(j);
g[j].pb(i);
cnt++;
if (cnt >= n) break;
}
cur.insert(mp(a[i].y, i));
}
}
dfs(0);
puts(cnt == n - 1 && count(used, used + n, 1) == n ? "YES" : "NO");
}
Idea: Neon
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); i++)
typedef pair<int, int> pt;
const int N = 500 * 1000 + 13;
int n;
vector<int> g[N], vs[N];
pt segs[N];
void dfs(int v, int p = -1) {
int sum = 0;
int bst = -1;
for (auto to : g[v]) if (to != p) {
dfs(to, v);
sum += 2 * sz(vs[to]);
if (bst == -1 || sz(vs[to]) > sz(vs[bst]))
bst = to;
}
if (bst == -1) {
vs[v].pb(v);
segs[v] = mp(1, 2);
return;
}
swap(vs[v], vs[bst]);
int lst = segs[bst].y;
sum -= 2 * sz(vs[v]);
sum += 1;
segs[bst].y += sum;
for (auto to : g[v]) if (to != p && to != bst) {
int add = lst - 1;
for (auto u : vs[to]) {
segs[u].x += add;
segs[u].y += add;
vs[v].pb(u);
}
lst = segs[to].y;
sum -= 2 * sz(vs[to]);
segs[to].y += sum;
vs[to].clear();
}
vs[v].pb(v);
segs[v] = mp(lst, segs[bst].y + 1);
}
int main() {
scanf("%d", &n);
forn(i, n - 1) {
int x, y;
scanf("%d%d", &x, &y);
--x; --y;
g[x].pb(y);
g[y].pb(x);
}
dfs(0);
for (int i = 0; i < n; i++)
printf("%d %d\n", segs[i].x, segs[i].y);
return 0;
}
Idea: BledDest
1278F - Cards
First of all, I would like to thank Errichto for his awesome lecture on expected value: part 1, part 2. This problem was invented after I learned the concept of estimating the square of expected value from that lecture — and the editorial uses some ideas that were introduced there.
Okay, now for the editorial itself. We call a number $$$a$$$ as good if $$$1 \le a \le n$$$, and the $$$a$$$-th shuffle of the deck resulted in a joker on top. $$$x$$$ from our problem is the number of such good numbers $$$a$$$. We can represent $$$x^2$$$ as the number of pairs $$$(a_1, a_2)$$$ such that every element of the pair is a good number, $$$x^3$$$ as the number of triples, and so on — $$$x^k$$$ is the number of $$$k$$$-tuples $$$(a_1, a_2, \dots, a_k)$$$ such that each element of a tuple is a good number.
So we can rewrite the expected value of $$$x^k$$$ as the expected number of such tuples, or the sum of $$$P(t)$$$ over all tuples $$$t$$$, where $$$P(t)$$$ is the probability that $$$t$$$ consists of good numbers. How to calculate the probability that $$$t$$$ is a good tuple? Since all shuffles of the deck result in a joker with probability $$$\frac{1}{m}$$$, $$$P(t)$$$ should be equal to $$$\frac{1}{m^k}$$$ — but that is true only if all elements in $$$t$$$ are unique. How to deal with tuples with repeating elements? Since all occurences of the same element are either good or bad (with probability $$$\frac{1}{m}$$$ of being good), the correct formula for $$$P(t)$$$ is $$$P(t) = \frac{1}{m^d}$$$, where $$$d$$$ is the number of distinct elements in the tuple.
Okay, then for each $$$d \in [1, k]$$$ we have to calculate the number of $$$k$$$-tuples with exactly $$$d$$$ distinct elements. To do that, we use dynamic programming: let $$$dp_{i, j}$$$ be the number of $$$i$$$-tuples with exactly $$$j$$$ distinct elements. Each transition in this dynamic programming solution models adding an element to the tuple; if we want to compute the transitions leading from $$$dp_{i, j}$$$, we either add a new element to the tuple (there are $$$n - j$$$ ways to choose it, and we enter the state $$$dp_{i + 1, j + 1}$$$), or we add an already existing element (there are $$$j$$$ ways to choose it, and we enter the state $$$dp_{i + 1, j}$$$).
Overall complexity is $$$O(k^2 \log MOD)$$$ or $$$O(k^2 + \log MOD)$$$, depending on your implementation.
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 5043;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1)
z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
int n, m, k;
int dp[N][N];
int main()
{
cin >> n >> m >> k;
dp[0][0] = 1;
for(int i = 0; i < k; i++)
for(int j = 0; j < k; j++)
{
dp[i + 1][j] = add(dp[i + 1][j], mul(dp[i][j], j));
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(dp[i][j], n - j));
}
int ans = 0;
for(int i = 1; i <= k; i++)
ans = add(ans, mul(dp[k][i], binpow(inv(m), i)));
cout << ans << endl;
}