Hi, Codeforces!
1529A - Eshag любит большие массивы
problem idea and solution: AmShZ
editorial
Tutorial is loading...
official solution
// khodaya khodet komak kon
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;
typedef pair <ll, ll> pll;
# define A first
# define B second
# define endl '\n'
# define sep ' '
# define all(x) x.begin(), x.end()
# define kill(x) return cout << x << endl, 0
# define SZ(x) int(x.size())
# define lc id << 1
# define rc id << 1 | 1
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
const int xn = 1e2 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 1e9 + 7;//998244353;
const int base = 257;
int qq, n, a[xn], mn, ans;
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
cin >> qq;
while (qq --){
cin >> n, mn = inf, ans = 0;
for (int i = 1; i <= n; ++ i)
cin >> a[i], mn = min(mn, a[i]);
for (int i = 1; i <= n; ++ i)
ans += a[i] != mn;
cout << ans << endl;
}
return 0;
}
1529B - Sifid и странные подпоследовательности
problem idea and solution: Davoth
editorial
Tutorial is loading...
official solution
// khodaya khodet komak kon
// Nightcall - London Grammer
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;
typedef pair <ll, ll> pll;
# define A first
# define B second
# define endl '\n'
# define sep ' '
# define all(x) x.begin(), x.end()
# define kill(x) return cout << x << endl, 0
# define SZ(x) int(x.size())
# define lc id << 1
# define rc id << 1 | 1
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
const int xn = 1e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 1e9 + 7;//998244353;
const int base = 257;
int qq, n, a[xn], ans, mn;
bool flag;
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
cin >> qq;
while (qq --){
cin >> n, ans = 0;
for (int i = 1; i <= n; ++ i)
cin >> a[i], ans += (a[i] <= 0);
sort(a + 1, a + n + 1), mn = inf;
for (int i = 1; i <= n; ++ i)
if (a[i] > 0)
mn = min(mn, a[i]);
flag = (mn < inf);
for (int i = 2; i <= n; ++ i)
if (a[i] <= 0)
flag &= (a[i] - a[i - 1] >= mn);
if (flag)
cout << ans + 1 << endl;
else
cout << ans << endl;
}
return 0;
}
problem idea and solution: shokouf, AmShZ
editorial
Tutorial is loading...
official solution
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 2e5 + 10;
ll dp[2][N]; int A[2][N], n; vector<int> adj[N];
void DFS(int v, int p = -1) {
dp[0][v] = dp[1][v] = 0;
for (int u : adj[v]) {
if (u == p) continue;
DFS(u, v);
dp[0][v] += max(abs(A[0][v] - A[1][u]) + dp[1][u], dp[0][u] + abs(A[0][v] - A[0][u]));
dp[1][v] += max(abs(A[1][v] - A[1][u]) + dp[1][u], dp[0][u] + abs(A[1][v] - A[0][u]));
}
}
void Solve() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &A[0][i], &A[1][i]);
fill(adj + 1, adj + n + 1, vector<int>());
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
DFS(1);
printf("%lld\n", max(dp[0][1], dp[1][1]));
}
int main() {
int t; scanf("%d", &t);
while (t--) Solve();
return 0;
}
1528B - Kavi разбивает на пары
problem idea and solution: alireza_kaviani
editorial
Tutorial is loading...
official solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define X first
#define Y second
#define endl '\n'
const int N = 1e6 + 10;
const int MOD = 998244353;
int n, dp[N], S;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = i + i; j <= n; j += i) {
dp[j]++;
}
}
dp[0] = S = 1;
for (int i = 1; i <= n; i++) {
dp[i] = (dp[i] + S) % MOD;
S = (S + dp[i]) % MOD;
}
cout << dp[n] << endl;
return 0;
}
problem idea and solution: AliShahali1382
editorial
Tutorial is loading...
official solution
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=300010, LOG=20;
int n, m, k, u, v, x, y, t, a, b, ans;
int par1[MAXN], par2[MAXN];
int stt[MAXN], fnt[MAXN], timer;
vector<int> G1[MAXN], G2[MAXN];
set<pii> st;
int Add(int v){
auto it=st.lower_bound({stt[v], v});
if (it!=st.end() && fnt[it->second]<=fnt[v]) return -2;
if (it==st.begin()) return -1;
--it;
int res=it->second;
if (fnt[v]>fnt[res]) return -1;
st.erase(it);
return res;
}
void dfs1(int node){
stt[node]=timer++;
for (int v:G2[node]) dfs1(v);
fnt[node]=timer;
}
void dfs2(int node){
int res=Add(node);
if (res!=-2) st.insert({stt[node], node});
ans=max(ans, (int)st.size());
for (int v:G1[node]) dfs2(v);
if (res!=-2){
st.erase({stt[node], node});
if (res!=-1) st.insert({stt[res], res});
}
}
void Solve(){
cin>>n;
for (int i=1; i<=n; i++) G1[i].clear(), G2[i].clear();
for (int i=2; i<=n; i++) cin>>par1[i], G1[par1[i]].pb(i);
for (int i=2; i<=n; i++) cin>>par2[i], G2[par2[i]].pb(i);
timer=1;
ans=0;
dfs1(1);
dfs2(1);
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int T;
cin>>T;
while (T--) Solve();
return 0;
}
better implementation of official solution: AaParsa
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define X first
#define Y second
#define endl '\n'
const int N = 3e5 + 10;
int t, n, L[N], R[N], timer, now, ans;
vector<int> Srsh[N], Msht[N];
set<pii> st;
void MshtDFS(int u) {
L[u] = timer++;
for (int v : Msht[u]) {
MshtDFS(v);
}
R[u] = timer;
}
int ispar(int u, int v) {
return L[u] <= L[v] && R[v] <= R[u];
}
void SrshDFS(int u) {
int last = now;
// add u
auto it = st.lower_bound({L[u], 0});
if (it != st.end())
now += 1 - ispar(u, it->Y);
if (it != st.begin()) {
auto nxt = it--;
now += 1 - ispar(it->Y, u);
if (nxt != st.end())
now -= 1 - ispar(it->Y, nxt->Y);
}
st.insert({L[u], u});
ans = max(ans, now);
// DFS
for (int v : Srsh[u]) {
SrshDFS(v);
}
// remove u
st.erase({L[u], u});
now = last;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> t;
while (t --> 0) {
cin >> n;
for (int i = 1; i <= n; i++) {
Srsh[i].clear();
Msht[i].clear();
}
for (int u = 2; u <= n; u++) {
int par; cin >> par;
Srsh[par].push_back(u);
}
for (int u = 2; u <= n; u++) {
int par; cin >> par;
Msht[par].push_back(u);
}
timer = 0;
MshtDFS(1);
ans = now = 0;
SrshDFS(1);
cout << ans + 1 << endl;
}
return 0;
}
python solution: Tet
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
# region fastio
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
class FenwickTree:
def __init__(self, x):
"""transform list into BIT"""
self.bit = x
for i in range(len(x)):
j = i | (i + 1)
if j < len(x):
x[j] += x[i]
def update(self, idx, x):
"""updates bit[idx] += x"""
while idx < len(self.bit):
self.bit[idx] += x
idx |= idx + 1
def query(self, end):
"""calc sum(bit[:end])"""
end += 1
x = 0
while end:
x += self.bit[end - 1]
end &= end - 1
return x
def findkth(self, k):
"""Find largest idx such that sum(bit[:idx]) <= k"""
idx = -1
for d in reversed(range(len(self.bit).bit_length())):
right_idx = idx + (1 << d)
if right_idx < len(self.bit) and k >= self.bit[right_idx]:
idx = right_idx
k -= self.bit[idx]
return idx + 1
g1 = []
g2 = []
st = []
ft = []
def dfs1(graph, start=0):
n = len(graph)
tim = 1
visited = [False] * n
stack = [start]
while stack:
start = stack[-1]
if not visited[start]:
st[start] = tim
tim = tim + 1
visited[start] = True
for child in graph[start]:
if not visited[child]:
stack.append(child)
else:
stack.pop()
ft[start] = tim
def Do(v):
global ans , cnt , mem
fen.update(st[v] , 1);
if(fen.query(ft[v] - 1) - fen.query(st[v])):
mem += [[v , 0 , 0]]
return;
u = fen2.query(st[v]);
ok[v] = 1
cnt += 1
fen2.update(st[v] , v - u)
fen2.update(ft[v] , u - v)
mem += [[v , u , ok[u]]]
cnt -= ok[u]
ok[u] = 0
return;
def undo():
global cnt , ans , mem
[v , u , a] = mem[-1]
if(a != 0):
ok[u] = 1
cnt += 1
cnt -= 1
ok[v] = 0
fen.update(st[v] , -1)
fen2.update(st[v] , u - v)
fen2.update(ft[v] , v - u)
mem.pop()
return;
def dfs(graph, start=0):
global ans , cnt
n = len(graph)
visited = [False] * n
stack = [start]
while stack:
start = stack[-1]
if not visited[start]:
Do(start)
ans = max(ans , cnt)
visited[start] = True
for child in graph[start]:
if not visited[child]:
stack.append(child)
else:
stack.pop()
undo()
def solve():
global n, g1 , g2 , V , st , ft , fen , fen2 , mem , ok , cnt , ans
n = int(input())
if(n == 1):
print(1)
exit(0)
g1 = [] ; g2 = []
for i in range(n):
g1.append([])
g2.append([])
# 0 base
V = list(map(int , input().split()))
for i in range ( 1 , n ):
v = V[i - 1]-1
g1[v].append(i)
V = list(map(int , input().split()))
for i in range ( 1 , n ):
v = V[i-1]-1
g2[v].append(i)
st = [0] * (n + 100)
ft = [0] * (n + 100)
fen = FenwickTree([0] * (n + 3))
fen2 = FenwickTree([0] * (n + 3))
mem = []
ok = [0]*(n + 100)
cnt = 0
ans = 0
dfs1(g2)
dfs(g1)
print(ans)
q = int(input())
for i in range (q):
solve()
another O(n.log) solution with seg-tree: N.N_2004
#include<bits/stdc++.h>
#define lc (id * 2)
#define rc (id * 2 + 1)
#define md ((s + e) / 2)
#define dm ((s + e) / 2 + 1)
#define ln (e - s + 1)
using namespace std;
typedef long long ll;
const ll MXN = 3e5 + 10;
const ll MXS = MXN * 4;
ll n, timer, ans, Ans;
ll lazy[MXS], seg[MXS];
ll Stm[MXN], Ftm[MXN];
vector<ll> adj[MXN][2];
void Build(ll id = 1, ll s = 1, ll e = n){
lazy[id] = -1, seg[id] = 0;
if(ln > 1) Build(lc, s, md), Build(rc, dm, e);
}
void Shift(ll id, ll s, ll e){
if(lazy[id] == -1) return;
seg[id] = lazy[id];
if(ln > 1) lazy[lc] = lazy[rc] = lazy[id];
lazy[id] = -1;
}
void Upd(ll l, ll r, ll x, ll id = 1, ll s = 1, ll e = n){
Shift(id, s, e);
if(e < l || s > r) return;
if(l <= s && e <= r){
lazy[id] = x; Shift(id, s, e);
return;
}
Upd(l, r, x, lc, s, md), Upd(l, r, x, rc, dm, e);
seg[id] = max(seg[lc], seg[rc]);
}
ll Get(ll l, ll r, ll id = 1, ll s = 1, ll e = n){
Shift(id, s, e);
if(e < l || s > r) return 0;
if(l <= s && e <= r) return seg[id];
return max(Get(l, r, lc, s, md), Get(l, r, rc, dm, e));
}
void prep(ll u, ll par, ll f){
Stm[u] = ++ timer;
for(auto v : adj[u][f]){
if(v != par) prep(v, u, f);
}
Ftm[u] = timer;
}
bool Is_Jad(ll j, ll u){
return (Stm[j] <= Stm[u] && Ftm[u] <= Ftm[j]);
}
void DFS(ll u, ll par, ll f){
ll j = Get(Stm[u], Ftm[u]);
if(!j) Upd(Stm[u], Ftm[u], u), ans ++;
else{
if(Is_Jad(j, u)){
Upd(Stm[j], Ftm[j], 0);
Upd(Stm[u], Ftm[u], u);
}
}
Ans = max(Ans, ans);
for(auto v : adj[u][f]){
if(v != par) DFS(v, u, f);
}
if(!j) Upd(Stm[u], Ftm[u], 0), ans --;
else{
if(Is_Jad(j, u)){
Upd(Stm[u], Ftm[u], 0);
Upd(Stm[j], Ftm[j], j);
}
}
}
void solve(){
cin >> n, timer = ans = Ans = 0;
for(int i = 1; i <= n; i ++) adj[i][0].clear(), adj[i][1].clear();
for(int t = 0; t < 2; t ++) for(int u = 2, v; u <= n; u ++){
cin >> v, adj[v][t].push_back(u), adj[u][t].push_back(v);
}
Build(), prep(1, 0, 1);
DFS(1, 0, 0);
cout << Ans << '\n';
}
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
ll q; cin >> q;
while(q --) solve();
return 0;
}
/*!
HE'S AN INSTIGATOR,
ENEMY ELIMINATOR,
AND WHEN HE KNOCKS YOU BETTER
YOU BETTER LET HIM IN.
*/
//! N.N
1528D - Это птица! Нет, это самолет! Нет, это AaParsa!
problem idea and solution: AmShZ, AliShahali1382
editorial
Tutorial is loading...
official solution
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int N=605;
int n, m, k, u, v, x, y, t, a, b;
bool mark[N];
int G[N][N], D[N];
inline void upd(int &x, int y){ if (x>y) x=y;}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
memset(G, 63, sizeof(G));
cin>>n>>m;
while (m--){
cin>>u>>v>>x;
G[u][v]=min(G[u][v], x);
}
for (int i=0; i<n; i++){
memset(D, 63, sizeof(D));
memset(mark, 0, sizeof(mark));
for (int v=0; v<n; v++) upd(D[v], G[i][v]);
while (1){
int v=-1;
for (int x=0; x<n; x++) if (!mark[x]){
if (v==-1 || D[v]>D[x]) v=x;
}
if (v==-1) break ;
mark[v]=1;
upd(D[(v+1)%n], D[v]+1);
for (int u=0; u<n; u++)
upd(D[(u+D[v])%n], D[v]+G[v][u]);
}
for (int j=0; j<n; j++){
if (i==j) cout<<"0 ";
else cout<<D[j]<<" ";
}
cout<<"\n";
}
return 0;
}
a different O(n^3) solution: Atreus
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 600 + 5;
int n;
int dp[maxn];
bool mark[maxn];
vector<pair<int,int>> g[maxn];
int go[maxn];
int dis(int s, int t) {
if (s <= t)
return t - s;
return n - (s - t);
}
void dijkstra(int src) {
memset(dp, 63, sizeof dp);
memset(mark, 0, sizeof mark);
dp[src] = 0;
set<int> S;
for (int i = 0; i < n; i++)
S.insert(i);
for (int i = 0; i < n - 1; i++) {
int v = -1;
for (int j = 0; j < n; j++) {
if (mark[j])
continue;
if (v == -1 or dp[v] > dp[j])
v = j;
}
S.erase(v);
mark[v] = 1;
if (v != src) {
auto it = S.lower_bound(v);
if (it == S.end())
it = S.lower_bound(0);
int nex = *it;
dp[nex] = min(dp[nex], dp[v] + dis(v, nex));
}
for (int i = 2 * n - 1; i >= 0; i--) {
int v = i % n;
if (!mark[v])
go[v] = v;
else
go[v] = go[(v + 1) % n];
}
for (auto [u, w] : g[v]) {
int nex = go[(u + dp[v]) % n];
dp[nex] = min(dp[nex], dp[v] + w + dis((u + dp[v]) % n, nex));
}
}
}
int main() {
ios_base::sync_with_stdio(false);
int m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int v, u, w;
cin >> v >> u >> w;
g[v].push_back({u, w});
}
for (int i = 0; i < n; i++) {
dijkstra(i);
for (int j = 0; j < n; j++)
cout << dp[j] << " \n"[j == n-1];
}
}
1528E - Mashtali и деревья Hagh
problem idea and solution: AliShahali1382
Thanks to Kininarimasu for the editorial.
editorial
Tutorial is loading...
official solution
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=998244353, inv6=166374059;
const int MAXN=1000010, LOG=20;
ll n, m, k, u, v, x, y, t, a, b, ans;
ll dp[MAXN], ps[MAXN];
ll pd[MAXN], sp[MAXN];
ll C3(ll x){
return x*(x-1)%mod*(x-2)%mod*inv6%mod;
}
ll C2(ll x){
return x*(x-1)/2%mod;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>n;
dp[0]=ps[0]=1;
pd[0]=sp[0]=1;
for (int i=1; i<=n; i++){
ps[i]=(1 + ps[i-1] + ps[i-1]*(ps[i-1]+1)/2)%mod;
dp[i]=ps[i]-ps[i-1];
pd[i]=dp[i]-dp[i-1];
sp[i]=(sp[i-1]+pd[i])%mod;
}
for (int i=0; i<n; i++) ans=(ans + pd[i]*sp[n-1-i])%mod;
ans=(ans + 2*C3(ps[n-1]+2))%mod;
if (n>=2) ans=(ans - 2*C3(ps[n-2]+2))%mod;
ans=(ans + 2*C2(ps[n-1]+1))%mod;
if (n>=2) ans=(ans - 2*C2(ps[n-2]+1))%mod;
if (ans<0) ans+=mod;
cout<<ans<<"\n";
return 0;
}
problem idea and solution: AmShZ, AliShahali1382
editorial
Tutorial is loading...
official solution
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;
typedef pair <ll, ll> pll;
# define A first
# define B second
# define endl '\n'
# define sep ' '
# define all(x) x.begin(), x.end()
# define kill(x) return cout << x << endl, 0
# define SZ(x) int(x.size())
# define lc id << 1
# define rc id << 1 | 1
# define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
const int xn = 3e5 + 10;
const int xm = 18;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 998244353;
const int base = 257;
int n, k, C[xn], ans, A[xn], B[xn], rev[xn];
int fact[xn], ifact[xn];
void NTT(int *A, bool inv){
int n = (1 << xm);
for (int i = 0; i < (1 << xm); ++ i)
if (rev[i] < i)
swap(A[i], A[rev[i]]);
for (int ln = 1; ln < n; ln <<= 1){
int w = power(3, mod / 2 / ln, mod);
if (inv)
w = power(w, mod - 2, mod);
for (int i = 0; i < n; i += ln + ln){
int wn = 1;
for (int j = i; j < i + ln; ++ j){
int x = A[j], y = 1ll * A[j + ln] * wn % mod;
A[j] = (x + y) % mod;
A[j + ln] = (x - y + mod) % mod;
wn = 1ll * wn * w % mod;
}
}
}
if (inv){
int invn = power(1 << xm, mod - 2, mod);
for (int i = 0; i < n; ++ i)
A[i] = 1ll * A[i] * invn % mod;
}
}
int main(){
InTheNameOfGod;
cin >> n >> k;
C[0] = fact[0] = 1;
for (int i = 1; i < xn; ++ i){
C[i] = 1ll * C[i - 1] * (n - i + 1) % mod * power(i, mod - 2, mod) % mod;
fact[i] = 1ll * fact[i - 1] * i % mod;
}
ifact[xn - 1] = power(fact[xn - 1], mod - 2, mod);
for (int i = xn - 2; i >= 0; -- i)
ifact[i] = 1ll * ifact[i + 1] * (i + 1) % mod;
for (int i = 1; i < (1 << xm); ++ i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (xm - 1));
for (int i = 0; i <= k; ++ i){
A[i] = 1ll * power(i, k, mod) * ifact[i] % mod;
B[i] = ifact[i];
if (i % 2)
B[i] = (mod - B[i]) % mod;
}
NTT(A, 0), NTT(B, 0);
for (int i = 0; i < xn; ++ i)
A[i] = 1ll * A[i] * B[i] % mod;
NTT(A, 1);
for (int i = 1; i <= k; ++ i)
ans = (ans + 1LL * A[i] * C[i] % mod * power(n + 1, n - i, mod) % mod * fact[i] % mod) % mod;
cout << ans << endl;
return 0;
}
Auto comment: topic has been updated by AliShahali1382 (previous revision, new revision, compare).
Woow !! Fast editorial Thanks :)
There might be an error in the n log n solution with segtree (div1. problem C).
fixed, thanks!
I hope all the future rounds will be as good as this one
I hope all future rounds
To be continued... :(
Nice contest with nice problems! Thanks
Genius problems. Nice job.
Bad tests in D? The $$$\log n$$$ part in my $$$\mathcal{O}(nm \log n)$$$ code triggers only $$$0.025 N^3$$$ times in large tests: 117257732
EDIT: dorijanlendvaj found a large input where it triggers $$$0.5 N^3$$$ times, that's $$$20$$$ times better than the original test data!
we wanted to fail high-constant O(n^3.log)(like seg-trees) and let easily optimized O(n^3) or O(n^3.log) with heaps to pass.
Via 1529B — Sifid and Strange Subsequences
This is what happens when you don't help in making statements. :(
Dfs Based Solution of C Parsa's Humongous Tree without DP based on the fact that during path traversal on a tree from root , A particular node is reached only once.
We return a pair {a,b} from every node.
A has the best solution from that node to all nodes below it when left_mini is assigned to that node.
B has the best solution from that node to all nodes below it when right_maxi is assigned to that node.
We store best possible values of the current node from all children node i.e. one with maxi on all possible calls and other with mini and then return it.
In the end when recursive calls end print the maximum of the pair of values returned from the root.
Solution
What you are describing is the same DP on a tree. The official solution also uses DFS.
U don't need to save results in a array for Dp in this DFS
Both best case possibilities are calculated and return from there.
Where is the editorial on F?..
I've added it but it doesn't seem to appear ...
will probably get fixed soon
For Div2 D- "x≤n: In this case, due to the lemma mentioned above all the segments must have the same length, thus their length must be a divisor of n, in this case they can be paired in D(n) ways; where D(n) is the number of divisors of n.".
The equality should not be present I think. It should be only x<n. Correct me if I am wrong!
If 1 is paired with n, each number from n+1 to 2n must belong in a segmemt with length n, where the length of a segment is defined as the number of elements inside it.
The pairing is unique as well ...
The sequence x[i]-2*x[i-1] starts 1,0,1,-1,2,... and is http://oeis.org/A051950
I have done Question b in two way 1st submission : 117264950 2nd submission : 117264953 I can't find why my second submission failed I did the same thing but just in another manner, can anyone help me out please
It took me a lot of time but I found out what's wrong with your code. Actually, you are failing edge case when seq is [-1] or [0] because in your second program you'll be having cnt = 1 and since there is only 1 item in the array it will not enter the while loop, and bool will evaluate to true and it will increase it by 1 resulting in ans = 2. Luckily your former code worked for these edge cases.
First thank you very much for your efforts Could you please help me this submission , it is failing on 10000th test case 117240464
I have submitted your code with a minor change, it got ac. You just had to account for the special case when n equals 1.
i am sorry for every one get wrong answer in problem B test 15 i put it in hacks :( can you give contriubution for it
Can anyone explain the DP applied in Kavi on the Pairing Duty problem in simple words?
In Div 1 Problem D:
"To handle the "waiting" concept, we can add n fake edges, i-th of which is from the i-th vertex to the (i+1 mod n) -th vertex with weight equal to one."
What is a vertex here? Does this sentence mean the cities? But waiting for 1 second doesn't move you to the next city, so that can't be. Or can it? Is the assumption, that "if we can reach city X from some other city Y, then we could've waited for 1s in Y and then we would've reached X+1"? That seems also to be the explanation for "It can be proved that doing dijkstra in the new graph is sufficient if we guarantee that the first used edge is not fake."
Well, It seems I answered my own question here while writing it down. Debugging-Rubber-Ducky for the win. But since I really was confused by this and I don't feel that this step is trivial, I'm gonna leave this comment here.
"It can be proved that doing dijkstra in the new graph is sufficient if we guarantee that the first used edge is not fake.
We can map waiting for x seconds and then using an edge to go to u from v to using a cannon and then using x fake edges to go to u from v."
Oh, yes you are right. I'm just thick as a brick and didn't get that sentence before. Thanks for the heads up! :)
Can someone explain how to find Stirling numbers of the 2nd kind in O(k log k) (for F)?
From wikipedia page \begin{gather*} S(n, k) = \frac{1}{k!}\sum_{i=0}^k (-1)^i \binom{k}{i} (k-i)^n \end{gather*}
You can rewrite it as \begin{gather*} S(n, k) = \sum_{i=0}^k \underbrace{\left((-1)^i\cdot \frac{1}{i!}\right)}_{a_i} \cdot \underbrace{\left(\frac{1}{(k-i)!}\cdot(k-i)^n\right)}_{b_{k-i}} \end{gather*}
So you can calculate arrays $$$a$$$ and $$$b$$$, and stirling numbers are just convolution of these arrays:
\begin{gather*} S(n, k) = \sum_{i=0}^k a_i \cdot b_{k-i} \end{gather*}
I am getting TLE for Div 2 C Mysolution. I have done almost the same as Editorial (using memorization of recursion). Please anyone help me with debugging. Thank you
unordered_mapandunordered_setare dangerous in CPThank you for replying. I want to know What is the exact reason not to use unordered_map and unordered_set.
Here
*in CF not CP
I am getting a TLE too on my Div2C. Can someone help me with debugging too ? Thank You. [My Solution]http://codeforces.net/contest/1529/submission/117308814)
just add fastIO to your submission bc input quite large. Same code but has fastIO
Since E editorial is not out yet, here is how I solved. Let $$$dp_i$$$ be the answer for all trees such that there exists a root and all edges are directed in the same direction from root and the root has at most $$$2$$$ children. We transition
$$$dp_i$$$ = $$$dp_{i-1} + dp_{i-1}*pdp_{i-2} + dp_{i-1}*(dp_{i-1}+1)/2$$$ where $$$pdp_i = \sum_{j=0}^i dp_j$$$
Then let $$$dp2_i$$$ be the same as $$$dp_i$$$ except the tree must have $$$2$$$ children. So $$$dp2_i = dp_i - dp_{i-1}$$$.
The answer for these cases is
$$$2*(dp_n + dp_{n-1}*pdp_{n-2}*(pdp_{n-2}+1)/2 + pdp_{n-2}*dp_{n-1}*(dp_{n-1}+1)/2 + dp_{n-1}*(dp_{n-1}+1)*(dp_{n-1}+2)/6) - 1$$$
This is because $$$dp_n$$$ holds the answer for at most $$$2$$$ children and the other section accounts for the rest. We multiply by $$$2$$$ to account for both edges directions, and subtract $$$1$$$ because a single path is isomorphic.
This obviously doesn't handle all cases, but all other cases can be found in the following form. Let $$$t_{up,k}$$$ be a tree where the root has $$$2$$$ children and the edges are directed up and the longest path is $$$k$$$, and let $$$t_{down,k}$$$ be a tree where the root has $$$2$$$ children and the edges are directed down and the longest path is $$$k$$$. Then all other cases are $$$t_{up,k}$$$ which exists on some path of length $$$l$$$ to and connects to $$$t_{down, n-k-l}$$$
We can count every other case as $$$\sum_{i=0}^{n-1} (dp_i-1)*dp2_{n-1-i}$$$
This works because we pretend the path is always length $$$1$$$, then if we do $$$dp_i*dp2_{n-1-i}$$$ we handle all cases except for when the $$$t_{up, k}$$$ is empty, and that only happens one time.
Here is my submission: 117272002
Sorry I understand everything now D: took me too long
Good!
We can count every other case as ∑n−1i=0(dpi−1)∗dp2n−1−i????
In problem B: my solution passed the pretests but giving time limit exceeded in test 4. It runs in O(nlogn) time l. Here is my submission Can someone help me finding what's wrong in my code?
In your code's solve, second range must be time limit exceeded.
the range is $$$O(n)$$$.And the min_element also is $$$O(n)$$$.so it's $$$O(n^2)$$$.
can anybody please tell in B why its optimal to always choose negative elements
the time complexity of min_element() is O(n), you are doing it (n-1) times in the worst case. you should think of propagating from the start only.
because their maximum element is negative and absolute of all differences is greater than or equals to zero that is greater than negative maximum element.
Suppose we choose more than 1 positive numbers a, b..., |a — b| < max(a, b), that means we can't choose more 1 positive numbers. Suppose all the numbers we choose is non-positive numbers, |ai — aj| >= max(ai, aj) is always true. So we just firstly choose all the non-positive numbers from the array, then calculate the minimum distance between these chosen numbers, we call it mn. And then check the original array if there is a positive number that is no greater than mn.
Problem B Div-2 — It's easy to prove that a strange subsequence can't contain more than one positive element.
Can someone please prove this ?
Assume that it contains two positive elements — say 2 and 5 . Max is 5. Difference is 3 . Similarly, it is easy to see that difference of two positive numbers will always be less than the greater element of those two numbers. Hence taking more than one positive number is not possible
For two positive elements, we have the property that their absolute difference will be strictly smaller than the larger element. So, you can clearly see that this violates the strange condition
can anyone find error on my code for Div2 C failing on test case 2. I can't find any error ,i checked it more than 10 times ,any help will be really appreciated
In div1 C / div2 E , Can someone explain the part 3 , i.e. "Among the vertices inside it, find the maximum number of vertices such that none of them is the ancestor of the other in Keshi's tree." . How are we doing it .
When you give a dfs order of a tree, there will be no pair satisfies
$$$in[u] < in[v], out[u] < out[v]$$$
and u is a ancestor of v if and only if $$$in[u] < in[v] \leq out[v] \leq out[u]$$$. so,
if neither of u or v is the ancestor of the other, then $$$[in[u], out[u]), [in[v], out[v])$$$ will be disjoint interval. and
std::setis enough to maintain it.which also means euler tour generates a set of laminar ranges
-PurpleCrayon
Sounds like something important. What does it mean tho'?
all ranges of tin and tout are either completely disjoint or contained within each other
So, when you are at a leaf you have a set of intervals with you corresponding to the path from $$$1$$$ to the that leaf. And you want to know maximum number of non-overlapping segments? Could you explain how you implemented it using
std::set?UPD: Never mind. I got the idea. We can maintain only the disjoint intervals
Do you mean to say that in that set we only keep those intervals which will guarantee the max ans? If you do then won't it cause a problem while erasing a certain node? If not then what do you mean?
Yes, we are maintaining the intervals that would cause maximum answer... The idea is that whenever you add a new segment in the set, then there are only three cases —
(1) The new segment doesn't intersect with any (in this case we simply add it)
(2) It comes inside some existing segment (so we remove the existing segment and add this one)
(3) If this segment covers some additional segments within it (we don't add it)..
So, whenever we add a segment it removes $$$\textbf{atmost 1}$$$ segment from the set. We can keep track of which segment removes which one, and any change can be rolled back easily.
Oh that's brilliant. Thanks
Bye Bye Specialist!!
Hello Pupil!!
In Div 2 C, I think the condition should be $$$a_u \geq a_v$$$ for the first case and similarly $$$a_u \leq a_v$$$ for the second case. AliShahali1382
No, the case $$$a_u = a_v$$$ is handled in the third (otherwise) part.
No it's not handled in the third part. Because beauty of tree will still depend on $$$a_v$$$.
Ah, I see what you mean. I should rephrase that part.
It's better to compare the number of vertices $$$p$$$ such that $$$a_p > a_v$$$ and the number of vertices $$$q$$$ such that $$$a_q < a_v$$$. Thanks for noticing!
Very good round. ! Thanks for this round ! Graph and DP is always fun to solve in a contest. !
In Div-1 C [Editorial]: What are efficient ways to compute below?
Among the vertices inside it, find the maximum number of vertices such that none of them is the ancestor of the other in Keshi's tree.
This one of the best contest I have ever given on codeforces.
Can anyone explan in 2D,when $$$x\le n$$$,why each length must be a divisor of n?
Here, $$$1$$$ pairs up with $$$x$$$ and $$$x <= n$$$. Let say pattern repeats $$$p + 1$$$ times, the bottom right equation in the image is for total length which is $$$2n-1$$$. (I have numbered from $$$1$$$ to $$$2n$$$).
$$$l(p+1) = n$$$ tells us that $$$l$$$ must be divisor of $$$n$$$.
thans a lot!
Did anyone try solving Div2-D by solving the complementary problem??
The complementary problem was to find the total number of bad pairings, where a pairing is considered to be bad if, for at least two segments $$$A$$$ and $$$B$$$ among those, the following condition holds:
$$$1)$$$ $$$A$$$ and $$$B$$$ don't lie completely inside each other.
$$$2)$$$ $$$A$$$ and $$$B$$$ don't have the same length.
I was able to find exactly two segments $$$A$$$ and $$$B$$$, which will follow the above condition(if I am not wrong in computing that xD), but could not reduce it further. Is it even possible this way or is there any other approach to solve it??
I referred the editorial for Div2(C)/Div1(A)... But my solution failed after multiple attempts. Can someone please help me out? My solution 117289608
You forgot to call dfs.
Adding
dfs(1 , 0)should fix your code...Clear the global arrays before every test case as well, apart from calling the dfs function.
Yeah ... also his maxn had an extra 0.
Fixed code
"To be continued ..." in Div. 1 C's editorial?
At the time of posting, the editorial was incomplete and said "To be continued ...", now it has been fixed.
I really don't deserve the downvotes.
dpforces
Can someone describe the data strcuture used for Div1 C? It just displays "to be continued".
I used a segment tree.
tin[u]is the entry time of the vertex u andtout[u]is the exit time of the vertex u during dfs.1) To insert a node: First check if any of its ancestor is already inserted. If yes, remove the ancestor. Now, to insert the node, update the value in segment tree at the index
tin[u]astout[u].2) To delete a node: Update the value in segment tree at the index
tin[u]as0.3) To check if any ancestor is present: If current node is u, any ancestor v will satisfy the property
tin[v] < tin[u] && tout[v] > tout[u], so to check if any ancestor is already inserted, the range max query on this segment tree will bemax_query(1, tin[u] - 1) > tout[u]if an ancestor in inserted.For reference you can look at 117219173.
Thanks
Won't there be a situation when it is better to remove the current node instead of the ancestor?
Nope, all the subsets which are satisfied by any ancestor will also be satisfied by this vertex, but not vice-versa.
Wait, so if the current node is itself an ancestor of some of the previous nodes in the path, then does that mean it is the current node that will be removed?
"It's easy to see that the vertices in the data structure always form a path from root to some vertex v in Soroush's tree." so v (the current node) will never be an ancestor of any node currently in the data structure.
No, I meant what happens if the current node (v) is an ancestor of some node in the data structure according to Keshi's tree?
Then we just ignore it and won't insert it.
Thanks, I will try to implement it with this thing in mind.
A bit of a late reply, I am currently trying to wrap my head around this segtree solution implementation, but I have a question: how does the code actually take into consideration the case when
uis an ancestor of a previously visited nodev(by "ancestor" I mean an ancestor in Keshi's tree)? What I mean is that, in the DFS function in Soroush's tree, how does the code take into consideration the case when the current nodeuis an ancestor (in Keshi's tree) of a previously visited nodevby the DFS?In div2 D, lets say n=4(8points) And lets say we pair 1 with 4 What are the rest of the pairs? Can anyone list them?
You can't pair 1 with 4 that's invalid. If u draw on paper u can see why. You can pair 1 with 3 and 2 with 4 followed by 5 with 7 and 6 with 8.
But when we calculate the divisors of n, we get 1,2 and 4, right?
You don't include n amongst divisors. (I think maybe this wasn't mentioned in editorial)
for n = 4 these are the valid equal length pairings.
which is 3 — 1 = 2.
resolved
One minute it is correct my bad.. actually the way I have implemented is a bit different
there is one more pair (1,5) (2,6) (3,7) (4,8)
You may want to edit your comment. I am sorry for the mistake.
these are actually those equal length pairings which do not have anything lying inside them
But this is when x>n In the other case, when x<=n, we still cannot take x=n right?
According to the tutorial's method, author discuss the problem for 2 cases x <= n and x > n, and as we can see, in the former, we can only take length at most n — 1,also in the solution, d(n) is proper divisor of n. But from my point of view, talk in x <= n + 1 and x > n + 1 is more natural, from then on, length is <= n now, d(n) is all divisors of n, including itself, the formula has finally become $$$dp_n = \sum_{i = 1} ^ {n - 1} dp_i + d(n)$$$. also it is no need to initialize $$$dp_0 = 1$$$ (which has no useful purpose) anymore.
yes we can't take when x = n.
the one case which is contributing to total number of divisors is from the x > n case and nothing lying within it.
If you see my code I have added + 1 separately in dp[i] = dp[i-1] + 1 + count[even divisors of 2*n]
and from the number of even divisors I have subtracted -1;
strangely the net sum ends up being dp[i] = dp[i-1] + divisors.
even divisors of 2 * n is same as odd divisors of n
I really loved the problems!
Sorry to correct one possible little mistakes about the editorial of problem 1528A. In case 3(p=q),to maximize the beauty of the tree, au must be rv or uv.For example, if au=3,lv=0,rv=7, p=q=4, av=4,5,9,5,1,2,0,-1, the original beauty is 21.If change au into rv, the beauty will be 35.(In a word,I mean " The beauty of the tree doesn't depend on av" is not very rigorous.) However,thanks for your editorials again! They have helped me a lot!
Fixed, thanks for noticing.
Can someone tell, how to solve Div2C/Div1A if we need to minimise the sum instead of maximising?
Just a thought: We can define $$$dp_{v , j}$$$ as the minimum beauty of $$$v$$$'s subtree if $$$a_v$$$ is equal to $$$j$$$. This is too slow though, because I don't see any fact like the one in the maximizing version in here :(
I think that would work, if we have small ranges, but how to do if we have large ranges as in the problem?
That's why I said it's too slow. Maybe we can prove that $$$dp_{v , j}$$$ is convex or maybe not ...
But it should be a fun problem if it turns out to be convex :D
how would we solve the div2 problem A if we were asked to find the max no of operations instead of max no of elements to be deleted?
The algorithm I provided deletes $$$1$$$ element at a time, thus does the maximum number of operations. It's worth noting that the answer to both of the problems is the same.
Getting TLE on test case 4 of Div2 C. It follows the editorial explanation. Any help would be appreciated. Here's my submission.
Add
cin.tie(0) , ios::sync_with_stdio(0);to your main function and it should be fine.Thanks a lot. It works now. But why does it not work within the time constraints? Most of the n <= 1e5 cases work fine without fast I/O in O(nlogn) sorting time. Why does this solution, which is supposed to be O(n), fail to run in the required time?
It's not as simple as that, the sum of $$$n$$$ over all test cases can be as large as $$$2 \cdot 10^5$$$, there can be approximately $$$2 \cdot 10^5 \cdot (5 + 9 + 9)$$$ characters in the input which is quite a lot.
I'm sorry I did not understand, could you elaborate?
I said that you might need to read more than 4600000 characters from the input (4.5e6). cin itself is slow so you can't read that many characters in time. So you have to add that magical line to your code to make it work faster.
This is because by default, before you call the function
cin, the callcout << flushis done. Addingcin.tie(0)untiescinfromcoutand stops this.Can anybody please help me what is wrong with this code it is showing TLE test set 4 of question 3 Please help Thank you in advance
Here is my code: https://codeforces.net/contest/1528/submission/117327246
You forgot to add
cin.tie(0) , ios::sync_with_stdio(0);to your main function.First time to solve C without fst though I used O(n(logn)^2) algorithm.
Can someone explain to me for 1528A — Parsa's Humongous Tree why every vertex needs to be either lu or ru. I'm finding it difficult to understand. Thanks
It doesn't, but we proved that an optimal assignment exists that each $$$a_v$$$ is either $$$l_v$$$ or $$$r_v$$$.
what does it mean by ans += a[i] != mn; in the 2nd for loop?
If $$$a_i \neq mn$$$: $$$ans += 1$$$
Can someone tell me why this code times out? (https://codeforces.net/contest/1529/submission/117339337)
The problem is 1528A — Parsa's Humongous Tree. Thanks!
Please read the comments above ... at least two people have already asked this.
You forgot to use
ios::sync_with_stdio(0), cin.tie(0);.In problem Div1C:
You don't need this check at all to AC. This is because of the condition that $$$p[i] < i$$$ for all $$$i$$$ in both trees. Assume that $$$x$$$ is a parent of $$$y$$$ in any tree, then that ensures that $$$x<y$$$. You can see that it can't be true that $$$x$$$ is a parent of $$$y$$$ in Soroush's tree (and is therefore in the stack of nodes beforehand when we start DFS at $$$y$$$), and $$$y$$$ is a parent of $$$x$$$ in the other tree, since that would require $$$y<x$$$ and $$$x<y$$$.
In 1528A — Parsa's Humongous Tree, i used a bit different approach in dp which seems quite similar to me with the one provided in editorial . But it is not passing the pretests and i can't figure out what is wrong with my approach. I am new to dp. Can someone help me out?
Code using my own approach: my approach Code using editorial's approach: editorial approach
In problem C official solution, because of the way the trees are given in the input (each vertex in both trees has higher label than its ancestors), there's actually no need to check the case where $$$res = -2$$$. For any pair of vertices $$$u, v$$$, if $$$u$$$ is ancestor of $$$v$$$ in the first tree $$$(u < v)$$$, $$$v$$$ can't be ancestor of $$$u$$$ in the second tree as it would imply $$$u > v$$$. So, you always insert the current vertex, you just need to check if there's any ancestor of it and if there is, just remove it :)
Here's the submission 117369367 with the corresponding assert.
In the editorial solution of 1528A, the proof claims we can get a better result by changing av to lv or rv because the contribution from its children increase in this process. But at the same time it can reduce the contribution from its parent right? How do we say that the net result of changing av is an increase in beauty?
No, not $$$v$$$'s children but the vertices adjacent to $$$v$$$, this includes $$$v$$$'s parent as well.
Got it!! Thanks
https://codeforces.net/contest/1529/submission/117382997 This is my solution for problem C. It is showing TLE. Can anyone debug my solution,Pease.
There's nothing wrong with your code. The input is quite large so you have to add
cin.tie(0) , ios::sync_with_stdio(0);before reading input to do it faster.Well, the editorial of the 1528C - Trees of Tranquillity has some mistakes.
In the sixth to last line, $$$p\geq st_v0$$$ should be changed to $$$p\geq st_v$$$.
"is less than $$$st_v$$$" should be changed to "is less than $$$ft_v$$$".
Q2 could've been solved using binary search as well which would reduce the time complexity. https://del.dog/binarysearchsolution.txt here is my solution using binary seach.
Here is a stupid solution for Div.1 C:
The problem is as such: choose a maximum subset of a path in Soroush's tree such that if $$$u$$$ and $$$v$$$ are in that subset neither $$$u$$$ nor $$$v$$$ is an ancestor of the other in Keshi's tree.
The problem can be solved as such: dfs on Soroush's tree, take node $$$u$$$ if none of its subtree in Keshi's tree is taken. If $$$u$$$ has ancestor $$$p$$$ in Keshi's tree that was already taken, greedily take $$$u$$$ in place of $$$v$$$, this works because a lower node is an ancestor of fewer nodes, in another word: picking $$$u$$$ instead of $$$p$$$ offers the chance to pick $$$v$$$ where $$$v$$$ is a child of $$$p$$$ and a sibling of $$$u$$$.
To solve this we'll need two kinds of queries: 1. on a path from root to $$$u$$$ find if a node is already taken, 2. in the subtree of $$$u$$$ find if a node is already taken. Both queries can be done by using a an approach similar to here.
Similar to the editorial we store $$$st$$$ and $$$ft$$$ for each node, notice that for the range $$$[0, st_u]$$$ a node exists exactly once if it is on the path from root to $$$u$$$ and may exist twice otherwise, thus we just need to focus on nodes that occurred a single time. To add a node we update the segment tree at $$$st_u$$$ and $$$ft_u$$$ to be $$$u$$$, to remove a node we set them to $$$0$$$.
Since at most one ancestor is taken at a time, we can implement an xor segment tree on the dfs order and query the range $$$[0, st_u]$$$; undesirable nodes cancel themselves out, all other nodes will be $$$0$$$ except for (potentially) one node: $$$p$$$ which we will then remove and take $$$u$$$ instead. To solve 2, I just implemented an or segment tree (max would work as well) to find if a node exists in subtree.
my solution, not pretty
For problem F, how do you go from the sum with binomial coefficients to the sum with Stirling numbers? Also, should the sum be from CNT=1 to n?
I got it.
We can interpret $$$\sum_{r=1}^n \binom{n}{r} \cdot n^{n-r} \cdot r^k$$$ as the number of functional graphs whose vertex set is $$$V = A\cup B\cup Z$$$ such that
$$$|A|=n$$$, $$$|B|=k$$$, and $$$Z=\{z\}$$$ with $$$f(z)=z$$$,
$$$f(V)\subset A\cup Z$$$ (no element of $$$B$$$ has any incoming edges),
Let $$$C=\{a\in A:f(a)=z\}$$$ be the elements in $$$A$$$ that map to $$$z$$$. Then, $$$|C|=r$$$ and $$$f(A\setminus C)\subset A$$$ (the elements in $$$A$$$ that don't map to $$$z$$$ all map to some element in $$$A$$$),
$$$f(B)\subset C$$$.
This interpretation is correct because there are $$$\binom{n}{r}$$$ ways to choose the subset $$$C$$$, then $$$n^{n-r}$$$ ways to choose how $$$A\setminus C$$$ maps to $$$A$$$, and $$$r^k$$$ ways to choose how $$$B$$$ maps to $$$C$$$.
We can count these functional graphs in another way. First, let $$$i=|f(B)|$$$.
Choose how to map $$$B$$$ to $$$f(B)$$$ by first partitioning $$$B$$$ into $$$i$$$ sets. There are $$$\begin{Bmatrix}k\\i\end{Bmatrix}$$$ ways to partition $$$B$$$ into $$$i$$$ sets and $$$i!$$$ ways to order these sets.
There are $$$\binom{n}{i}$$$ ways to choose a subset of $$$A$$$ to be $$$f(B)$$$.
There are $$$(n+1)^{n-i}$$$ ways to choose how $$$A\setminus f(B)$$$ maps to $$$A\cup Z$$$.
Can anyone explain why pairing is unique for x <= n in Div2 D/ Div1 B.
There's an error in tutorial of Div1B.
$$$dp[i]$$$ is not equal to $$$\sum_{0}^{n-1} dp_i+D(n)$$$, but equals to $$$\sum_{0}^{n-1} dp_i+D(n)-1$$$ instead.
That's because length must be a divisor of $$$N$$$ and less than $$$N$$$, otherwise $$$x>N$$$.
Oops! Sorry, it's fixed now; Although it might take some time for the changes to appear. Thanks for noticing!
Can somebody explain magical number 63 in div.1-D solution? From the first glance it implies that answers can't exceed 63...
What are you talking about?
1528D -> official solution (not editorial but code)
I'm assuming that you are talking about
memset(a, 63, sizeof a).Memset works by writing values byte by byte based on the given value. So if you want to set an array to large values, use memset with 63, this will set all values to 1,061,109,567.
Got it! Thnx for explanation.
B. Sifid and Strange Subsequences
Considering The Test Case
14 9276 -5771 -783 -6209 2041 -9286 -8065 3975 -2961 2689 -1680 9924 1483 3067
The -ve numbers are -9286,-8065,-6209,-5771,-2961,-1680,-783
And the minimum +ve number is 1483
I am confused about how can just adjacent checking ensure that the difference of pairs in the subarray satisfy the condition of strange sequence. For example abs(-9286-(-8065)) is not > 1483 similarly it holds true for -1680 and -783. Can someone please explain me why is this intuition incorrect .
Consider this task: Given a non-decreasing array $$$a$$$, you must find a pair of elements $$$a_i$$$ and $$$a_j$$$ such that $$$i < j$$$ and $$$|a_i - a_j|$$$ is minimum. Obviously, there exists an answer such that $$$j-i = 1$$$, because otherwise we could have chosen $$$a_{i+1}$$$ without getting a worse result.
Deleted
It TLEs because you are an illiterate moron who refuses to read the other comments.
It's been asked here, here, here and here.
Also your fixed code: 146310603
My fault, I read the other comments, but forgot to delete mine,
can anyone help me in debugging first question? I am getting time limit exceeded on test case 4?261641603 thanks in advance:)