We hope you enjoyed these problems!
Author: Lyz09
Hint 1
Consider the case where $$$k=1$$$.
Tutorial
Tutorial is loading...
Implementation
#include<iostream>
using namespace std;
int t,n;
int main()
{
cin>>t;
while(t--)
{
cin>>n;
bool ans=false;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x==100)
ans=true;
}
if(ans)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
Author: lizhous
Hint 1
Consider for a given $$$p$$$, which elements can be placed at $$$p$$$ with one reversal operation.
Tutorial
Tutorial is loading...
Implementation
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
int n,a,x,m,sum;
priority_queue <int> nm[2];
bool hv[2];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--)
{
sum=0;
hv[0]=hv[1]=0;
while(!nm[0].empty()) nm[0].pop();
while(!nm[1].empty()) nm[1].pop();
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a;
nm[i&1].push(a);
sum+=a;
}
for(int i=1;i<=m;i++)
{
cin>>x;
if((!nm[x&1].empty()&&nm[x&1].top()>=0)||!hv[x&1])
{
sum-=nm[x&1].top();
nm[x&1].pop();
hv[x&1]=1;
}
}
cout<<sum<<"\n";
}
}
Author: ma2021tyoi0037
Hint 1
Consider how to determine whether the median of an interval equals $$$x$$$.
Hint 2
What could be the median of each subsequence?
Tutorial
Tutorial is loading...
Implementation
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=5e3+10;
int n,a[N],b[N],mid,dp[N];
void run(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
memcpy(b+1,a+1,n<<2);
sort(b+1,b+n+1);
mid=b[(n+1)>>1];
for(int i=1;i<=n;i++){
if(a[i]==mid){
a[i]=0;
continue;
}
a[i]=(a[i]>mid?1:-1);
}
for(int i=1,flg=0;i<=n;i++){
dp[i]=0;
flg=!a[i];
if(flg and (i==1 or dp[i-1]))dp[i]=dp[i-1]+1;
for(int j=i-3,sm=a[i];j>=0;j-=2){
flg+=!a[j+1];
flg+=!a[j+2];
sm+=a[j+1]+a[j+2];
if(abs(sm)>=flg or (j and !dp[j]))continue;
dp[i]=max(dp[i],dp[j]+1);
}
// cout<<dp[i]<<" \n"[i==n];
}
cout<<dp[n]<<'\n';
}
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin>>T;
while(T--)run();
}
2222D - Permutation Construction
Author: Lyz09
Hint 1
Try to perform a prefix sum on $$$a$$$.
Hint 2
Consider what the upper bound of the answer is.
Tutorial
Tutorial is loading...
Implementation
#include<iostream>
#include<algorithm>
using namespace std;
#define N 200010
int t,n,a[N],p[N];
pair<long long,int> b[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
b[0].first=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i].first=b[i-1].first+a[i];
b[i].second=i;
}
for(int i=n;i>=1;i--)
b[i].first=b[i-1].first;
sort(b+1,b+n+1);
for(int i=n;i>=1;i--)
p[b[i].second]=n-i+1;
for(int i=1;i<=n;i++)
cout<<p[i]<<" \n"[i==n];
}
}
Author: Lyz09
Hint 1
Try to use $$$0$$$ and $$$2^n-1$$$ in the solution.
Tutorial
Tutorial is loading...
Implementation
#include<iostream>
#include<set>
using namespace std;
int t,n;
set<long long> s;
int makeI(long long x)
{
cout<<"I "<<x<<endl;
int ans=0;
cin>>ans;
return ans;
}
int makeQ(long long y)
{
cout<<"Q "<<y<<endl;
int ans=0;
cin>>ans;
return ans;
}
int query(long long x)
{
int res=makeQ(x);
for(long long w:s)
if(w>=x)
res--;
return res;
}
long long guess(int n)
{
long long pre=0;
for(int i=n-1;i>=0;i--)
if(query(pre|(1ll<<i))>0)
{
pre|=(1ll<<i);
}
return pre;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
s.clear();
cout<<0<<endl;
s.insert(0);
int res1=makeI(0);
if(res1==1)
{
makeI((1ll<<n)-1);
long long w=guess(n);
cout<<"A "<<1<<" "<<w<<endl;
continue;
}
long long c=guess(n);
s.insert(c);
if(c==(1ll<<n)-1)
{
int res2=makeI(1);
if(res2!=res1)
{
cout<<"A "<<3<<" "<<c<<endl;
}
else
{
cout<<"A "<<2<<" "<<c<<endl;
}
continue;
}
int res2=makeI((1ll<<n)-1);
if(query((1ll<<n)-1)>0)
{
cout<<"A "<<2<<" "<<c<<endl;
}
else
{
cout<<"A "<<3<<" "<<c<<endl;
}
}
}
Author: hzy_____ Preparation: Rebex
Hint 1
Under what circumstances can an edge with cost $$$w$$$ be added between vertex $$$u$$$ and vertex $$$v$$$ in a new graph?
Hint 2
Consider divide and conquer.
Tutorial
Tutorial is loading...
Implementation
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int S=300005;
int n,m,k;
vector<pair<int,int> > vec[S];
int fa[S],hei[S],pt[S],fa2[S];
int top,*pot[S*3],val[S*3];
long long ans;
int fnd(int x){return fa[x]==x?x:fnd(fa[x]);}
int fnd2(int x){return fa2[x]==x?x:fa2[x]=fnd2(fa2[x]);}
inline void push(int &x){pot[++top]=&x,val[top]=x;}
inline void pop(){*pot[top]=val[top],top--;}
inline void merge(int x,int y,int w)
{
int rx=fnd(x),ry=fnd(y);
if(rx==ry) return;
int px=pt[rx],py=pt[ry];
if(px!=0&&py!=0)
{
int rx=fnd2(px),ry=fnd2(py);
if(rx!=ry) ans+=w,fa2[rx]=fa2[ry];
}
if(hei[rx]>hei[ry]) swap(rx,ry);
push(hei[ry]),hei[ry]=max(hei[ry],hei[rx]+1);
push(pt[ry]),pt[ry]=max(pt[ry],pt[rx]);
push(fa[rx]),fa[rx]=ry;
}
void doit(int l,int r,int w)
{
if(l==r) return;
int tp=top;
int mid=l+r>>1;
for(int i=r;i>=mid+1;i--)
for(auto t:vec[i]) merge(t.first,t.second,w);
doit(l,mid,w);
while(top>tp) pop();
for(int i=l;i<=mid;i++)
{
if(!vec[i].empty()&&w==i) w++;
for(auto t:vec[i]) merge(t.first,t.second,w);
}
doit(mid+1,r,w);
while(top>tp) pop();
}
inline void slove()
{
cin>>n>>m>>k;
for(int i=0;i<=m;i++) vec[i].clear();
for(int i=1,x,y,w;i<=m;i++) cin>>x>>y>>w,vec[w].emplace_back(x,y);
vector<int> tmp;
for(int i=1,x;i<=k;i++) cin>>x,tmp.push_back(x);
sort(tmp.begin(),tmp.end());
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
k=tmp.size();
for(int i=1;i<=n;i++) pt[i]=0;
for(int i=0;i<k;i++) pt[tmp[i]]=i+1;
for(int i=1;i<=n;i++) fa[i]=i,hei[i]=1;
for(int i=1;i<=k;i++) fa2[i]=i;
ans=0;
doit(0,m,0);
for(int i=1;i<=k;i++) if(fnd2(i)!=fnd2(1)) return cout<<"-1\n",void();
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T-->0) slove();
return 0;
}
Author: Lyz09 Developer: Z-301
Hint 1
What is the value of a path that passes through the centroid of a tree?
Hint 2
What is the value of a path that does not pass through the centroid of a tree?
Hint 3
This is a convolution problem. Enumerate only the terms in the polynomial with non-zero coefficients and prove that the time complexity is correct.
Tutorial
Tutorial is loading...
Implementation
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
class edge{
public:
edge(int x, int y, int z, int zz){v = x, w = y, c = z, nxt = zz;}
int v, w, c, nxt;
};
class graph{
private:
vector<int> head;vector<edge> e;
public:
void init(int n){head.clear(), e.clear();for (int i = 0;i <= n;i ++) head.emplace_back(-1);}
graph(){}graph(int n){init(n);}
inline int addedge(int u, int v, int w = 0, int c = 0){e.emplace_back(v, w, c, head[u]), head[u] = e.size() - 1;return e.size() - 1;}
inline int add2edge(int u, int v, int w = 0){int tmp = addedge(u, v, w);addedge(v, u, w);return tmp;}
inline int addfedge(int u, int v, int w, int c = 0){int tmp = addedge(u, v, w, c);addedge(v, u, 0, -c);return tmp;}
inline int& h(int u){return head[u];}
inline edge& operator[](int i){return e[i];}
}G;
const int N = 100005;ll ans[N];vi a[N];vector<ll> b[N];
int t, n, al, mns, rt, sz[N], cnt[N];
void dfs(int u, int fa){int mx = 0;sz[u] = 1;
for (int i = G.h(u);i != -1;i = G[i].nxt){
int v = G[i].v;if (v == fa) continue;
dfs(v, u), sz[u] += sz[v], mx = max(mx, sz[v]);
}mx = max(mx, al - sz[u]);
if (mx < mns) rt = u, mns = mx;
}
void dfs1(int u, int fa, int mx, int rt){
a[rt].push_back(max(mx, sz[u]));
for (int i = G.h(u);i != -1;i = G[i].nxt){
int v = G[i].v;if (v == fa) continue;
dfs1(v, u, max(mx, sz[u] - sz[v]), rt);
}
}
void calc(vi& a, vector<ll>& s, vi& b, int o){
int p = upper_bound(a.begin(), a.end(), o) - a.begin();
for (int i = 0, j;i < b.size();i ++){
j = upper_bound(a.begin(), a.end(), b[i]) - a.begin();
if (b[i] > o) ans[o] -= j, ans[b[i]] += j;j = max(j, p);
if (j < a.size()) ans[o] -= a.size() - j, s[j] ++;
}
}
void dfs2(int u, int fa){vi vc;
for (int i = G.h(u);i != -1;i = G[i].nxt){
int v = G[i].v, w = sz[v];if (v == fa) continue;
ans[n - w - w] += 1ll * cnt[w] * w, cnt[w] += w, vc.push_back(w);
}sort(vc.begin(), vc.end()), vc.erase(unique(vc.begin(), vc.end()), vc.end());
for (int x : vc) for (int y : vc) if (x < y)
ans[n - x - y] += 1ll * cnt[x] * cnt[y];
for (int v : vc) ans[n - v] += (u != rt) * cnt[v], cnt[v] = 0;
for (int i = G.h(u);i != -1;i = G[i].nxt){
int v = G[i].v;if (v != fa) dfs2(v, u);}
}
void solve(int u){vi to;
for (int i = G.h(u);i != -1;i = G[i].nxt){
int v = G[i].v;to.push_back(v), dfs1(v, u, 0, v);
sort(a[v].begin(), a[v].end()), b[v].resize(a[v].size(), 0);
}
for (int x : to) if (sz[x] * 3 >= n) for (int y : to) if (x < y || sz[y] * 3 < n) calc(a[x], b[x], a[y], n - sz[x] - sz[y]);
for (int v : to){ll ls = 0;
for (ll& x : b[v]) ls = x += ls;
for (int i = 0;i < a[v].size();i ++)
ans[max(a[v][i], n - sz[v])] ++,
ans[a[v][i]] += b[v][i];a[v].clear(), b[v].clear();
}dfs2(rt, 0);
}
int main(){scanf("%d", &t);
while (t --){scanf("%d", &n), G.init(n);
for (int i = n - 1, u, v;i --;)
scanf("%d%d", &u, &v), G.add2edge(u, v);memset(ans, 0, n + 1 << 3);
al = n, mns = N, dfs(1, 0), dfs(rt, 0), solve(rt), ans[n] += n;
for (int i = 1;i <= n;i ++) printf("%lld ", ans[i]);putchar('\n');
}
}
Author: CutieSmileHaruka
Hint 1
You are given an array $$$a$$$. How to count the number of arrays $$$b$$$ that satisfy $$$f(b) = a$$$ and $$$ \forall 1 \le i \le n, b_i \le r_i $$$.?
Hint 2
You are given an array $$$a$$$. How to count the number of arrays $$$b$$$ that satisfy $$$f(f(b)) = a$$$ and $$$ \forall 1 \le i \le n, b_i \le r_i $$$.?
Hint 3
How many arrays $$$a$$$ satisfy there exists an array $$$b$$$ such that $$$f(f(b)) = a$$$?
Hint 4
Tutorial
Tutorial is loading...
Implementation
// 全身全霊！MORE MORE JUMP!!
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define mod 998244353
using namespace std;
typedef __int128_t lll;
template<typename T, const int M>
struct BHasher{inline int operator()(T x){return x % M;}};
template<typename T1, typename T2, int M, typename Hsr = BHasher<T1, M>>
struct HashMap{
struct node{int nx;T1 ky;T2 vl;};
int h[M];vector<node> nd;Hsr hsh;
HashMap(){memset(h, -1, sizeof(h));}
void clear(){memset(h, -1, sizeof(h)), nd.clear();}
inline bool find(T1 k){int p = hsh(k);
for (int i = h[p];i != -1;i = nd[i].nx)
if (nd[i].ky == k) return 1;return 0;
}
inline T2& operator[](T1 k){int p = hsh(k);
for (int i = h[p];i != -1;i = nd[i].nx)
if (nd[i].ky == k) return nd[i].vl;
nd.push_back((node){h[p], k, T2()});
return nd[h[p] = nd.size() - 1].vl;
}
};
const int N = 55, K = 1005, M = 1296000;HashMap<lll, int, 1919839> id;
int t, n, m, k, c, a[N], fa[M], to[M][N], C[N][N], f[M], ans[K], rt, cnt;
unsigned char b[M][N], bb[N], ps[M][N], sk[N], tmp[N], sm[M], ct[M], dep[M];
void dfs(int p, int sm){
if (p > n){m ++;
memcpy(ps[m], sk, sizeof(sk));
memcpy(b[m], bb, sizeof(bb));
return;
}
for (int x = 0;x <= n && sm <= n;x ++, sm += p){
if (x) sk[++ c] = p;
bb[p] = x, dfs(p + 1, sm);
if (x) sk[c --] = 0;
}
}
inline lll hsh(unsigned char* A){lll st = 0;
for (int i = 1;i <= n;i ++)
st <<= 1, st |= 1, st <<= A[i];return st;
}
inline unsigned char gdep(int x){return dep[x] ? dep[x] : dep[x] = gdep(fa[x]) + 1;}
inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;}
int main(){scanf("%d", &t), n = N - 5;
for (int i = 0;i <= n;i ++){C[i][0] = 1;
for (int j = 1;j <= i;j ++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;}
while (t --){scanf("%d%d", &n, &k), m = cnt = 0, dfs(1, 0);
memset(dep, 0, m + 1 << 1), memset(f, 0, m + 1 << 2), memset(ans, 0, k + 1 << 2);
for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);
for (int i = 1;i <= m;i ++){
lll st = hsh(b[i]);id[st] = i;
for (int j = n, p = -1;j >= 1;j --){
p += b[i][j] + 1;if (b[i][j])
to[i][j] = id[((st >> p) << p - 1) | (st & ((lll)1 << p) - 1)];
}
}
for (int i = 1;i <= m;i ++){
memset(tmp, 0, sizeof(tmp)), sm[i] = ct[i] = 0;
for (int j = 1;j <= n;j ++)
tmp[b[i][j]] ++, sm[i] += j * b[i][j], ct[i] += b[i][j];
if (sm[i] == 1) rt = i;
fa[i] = id[hsh(tmp)];
}f[1] = dep[1] = dep[rt] = 1;
for (int i = n, ss = 0;i >= 1;i --){
for (int o = 1;o <= n;o ++) ss += a[o] == i;
for (int j = m;j >= 1;j --)
if (ct[j] <= n - i + 1 && sm[j] <= ss)
for (int k = 1, x, now;ps[j][k];k ++)
if (now = f[to[j][x = ps[j][k]]])
f[j] = (f[j] + 1ll * now * C[ss - sm[j] + x][x]) % mod;
}
for (int i = 2;i <= m;i ++) add(ans[gdep(i) + 2], f[i]);
for (int i = 1;i <= n;i ++) cnt += a[i] > 0;
add(ans[3], mod - cnt), add(ans[2], cnt - (a[1] > 0)), add(ans[1], 1 + (a[1] > 0));
for (int i = 1;i <= k;i ++) printf("%d ", ans[i]);putchar('\n');
}
}
Auto comment: topic has been updated by CutieSmileHaruka (previous revision, new revision, compare).
yet another implementation round
In C i got to the point where median of segments = median of fulll array if it exists
the trick lies in where we can compute if median of a segment = M using the comparisons which are precomputed once we fix the median
Learned something new.
my apparach for C
First, I precomputed the median for all prefix subarrays of odd size. Then for each recursive call, I enforced that prefix median onto the rest
Cool problem E.
Subject: Weak Test Data Report: Inefficient DP Solution Passes Time Limit in [Insert Problem Letter] — Nanatsukaze — Save Our Sound https://mirror.codeforces.com/contest/2222/problem/A
To the Problem Setter / Contest Coordinators,
I am writing to report a case of weak test data for the problem Nanatsukaze — Save Our Sound.An incredibly inefficient, Unbounded Knapsack Dynamic Programming solution is currently passing all system tests and being Accepted. The code has a worst-case time complexity that should clearly result in a Time Limit Exceeded (TLE), but it passes because the system tests are missing a specific "worst-case" scenario where the answer is "Yes" and $$$N$$$ is maximized.The Flaw in the Accepted CodeThe code attempts to check every possible score from $$$0$$$ to $$$100 \cdot n$$$ by running an unbounded knapsack DP for each target score independently.Furthermore, the code dynamically allocates a vector inside the DP function during every single iteration of the loop.
Here is the exact submission that gets accepted: https://mirror.codeforces.com/contest/2222/submission/372573074
Why it should TLE (Complexity Analysis)If the array does not contain 100 (meaning the answer is "No"), the DP quickly fails on target = 1 and breaks the loop. The execution time is negligible.However, if the array does contain 100 (meaning the answer is "Yes"), the DP loop never breaks early. It must check every number up to $$$100 \cdot N$$$.For a maxed-out test case where $$$T = 100$$$, $$$N = 10$$$, and all $$$a_i = 100$$$:The outer loop runs $$$100 \times 10 = 1,000$$$ times per testcase.can() is called $$$1,000$$$ times, allocating a vector on the heap every single time.The nested loops inside can() result in roughly $$$10,000,000$$$ operations per test case.For $$$T=100$$$, this results in $$$\approx 10^9$$$ operations and 100,000 dynamic memory allocations, which takes roughly 5 to 10 seconds locally and heavily exceeds standard time limits.
The Missing Worst-Case Test DataTo break this code, the system tests need a file filled with maximum values where the answer is "Yes".
100 10 100 100 100 100 100 100 100 100 100 100 10 100 100 100 100 100 100 100 100 100 100 ... (repeated 100 times total)
I find the explanation for problem C not very understandable. Can you explain in more detail how to compute dp[i] exactly.
My approach for C was: 1. Start walking through the array, if the median so far is as desired AND it is possible to split the rest of the array in some way to fulfill the condition, then I should cut off the array so far, sum+=1, start over with the shorter array. 2. My approach to finding out whether or not the rest of the array was splittable at all was: if the rest of the array is odd length, just check if the array as whole is valid (has correct median), if the rest of the array is even length, check for every index where we would split it into two odd-length arrays if both of these odd-length arrays are valid. If that is the case at no index, I figured, it wouldn't be possible at all.
This survived the first 3 test cases, but failed on pretest 4. I am not even quite sure which assumption is incorrect (1. or 2.). Does someone know what is wrong with my approach?
C can be solved without the fact that the median of each subarray is also the median of the whole sequence. Let $$$f(l, r)$$$ be the median of $$$a_l, a_{l+1}, \dots, a_r$$$. We fix the median as $$$x$$$, and let $$$dp_i$$$ be the number of subarrays when each one has median $$$x$$$. The idea is we only iterate through all $$$j$$$ such that $$$f(j, i)=x$$$, meaning across all $$$x$$$ there will be $$$O(n^2)$$$ transitions. I'm just unsure if $$$f$$$ can be computed faster than $$$O(n^2 \log n)$$$.