1610A - Anti Light's Cell Guessing
Idea: Anti-Light, Preparation: DeadlyCritic
$$$ans \le 2$$$
If $$$n = 1$$$ and $$$m = 1$$$ then $$$ans = 0$$$. 
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
if(n == 1 && m == 1){
cout << "0\n";
}
else if(min(n, m) == 1){
cout << "1\n";
}
else cout << "2\n";
}
}
1610B - Kalindrome Array
Idea: Davoth, Keshi, Preparation: AmShZ, Keshi
For an integer $$$x$$$ we can determine whether or not it's possible to make the array palindrome by removing some of the elements equal to $$$x$$$.
We claim that it is possible iff removing all appearances of $$$x$$$ makes the array palindrome.
Imagine we made the array palindrome by removing some of the elements equal to $$$x$$$. It's obvious that after removing the rest of the elements equal to $$$x$$$ the array remains palindrome.
$$$\textbf{Read the Hints and Assumptions before reading this.}$$$
//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
# define fast_io 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 = 2e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;
int qq, n, m, a[xn], b[xn];
bool ans;
void check(int x){
m = 0;
for (int i = 1; i <= n; ++ i)
if (a[i] != x)
b[++ m] = a[i];
for (int i = 1; i <= m; ++ i)
if (b[i] != b[m + 1 - i])
return;
ans = true;
}
int main(){
fast_io;
cin >> qq;
while (qq --){
cin >> n, ans = true;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
for (int i = 1; i <= n; ++ i){
if (a[i] != a[n + 1 - i]){
ans = false;
check(a[i]);
check(a[n + 1 - i]);
break;
}
}
if (ans)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
1610C - Keshi Is Throwing a Party
Idea: Keshi, Preparation: Keshi
Let $$$ans$$$ be the answer. For any $$$i \le ans$$$ it's possible to invite $$$\textbf{exactly}$$$ $$$i$$$ people, and for any $$$i > ans$$$ it's not possible to invite exactly $$$i$$$ people.
Because removing $$$1$$$ person from the party doesn't make anyone unhappy. So if we can invite $$$p_1, p_2, \ldots, p_k$$$, we also can invite $$$p_1, p_2, \ldots, p_{k - 1}$$$.
We use binary search to find the maximum $$$i$$$ that it's possible to invite exactly $$$i$$$ people.
Assume we want to invite $$$x$$$ people. If there are $$$i$$$ people poorer than person $$$v$$$, there are $$$x - 1 - i$$$ people richer than him. $$$i \le b_v$$$ and $$$x - 1 - i \le a_v$$$ so $$$x - 1 - a_v \le i \le b_v$$$.
$$$\textbf{Read the Hints and Assumptions before reading this.}$$$
//In the name of God
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
ll q, n, a[maxn], b[maxn];
bool ok(ll x){
ll c = 0;
for(ll i = 0; i < n; i++){
if(x - 1 - a[i] <= c && c <= b[i]) c++;
}
return c >= x;
}
int main(){
fast_io;
cin >> q;
while(q--){
cin >> n;
for(ll i = 0; i < n; i++){
cin >> a[i] >> b[i];
}
ll l = -1, r = n + 1, mid;
while(r - l > 1){
mid = (l + r) >> 1;
if(ok(mid)) l = mid;
else r = mid;
}
cout << l << "\n";
}
return 0;
}
1610D - Not Quite Lee
Idea: DeadlyCritic, Preparation: DeadlyCritic
First you should be able to check if an array $$$c$$$ of size $$$k$$$ is good or not.
If you choose some initial sequences $$$t_i$$$ for all $$$c_i$$$ that satisfy the first property, then you can reach any other set of sequences that satisfy the first property. Now you should check if a set of sequences exist that are reachable from your initial sequences and satisfy the second property or not.
If you do it correctly, and choose initial sequences such that $$$i$$$-th sequence starts from $$$0$$$ and ends with $$$c_i-1$$$ then you should end up with the following equaion : $$$\displaystyle x_1c_1 + x_2c_2+ \ldots + x_kc_k = -\sum{ \frac{c_i(c_i-1)}2}$$$. If this equation has an answer $$$(x_1, x_2, \ldots, x_k)$$$ then $$$c$$$ is good, otherwise it's not.
That equation has an answer if and only if $$$\displaystyle g = \gcd(c_1, c_2, \ldots, c_k)$$$ divides $$$\displaystyle \frac{c_i(c_i-1)}2$$$, this is not useful for the main problem in this state, try to go more in-depth.
I will frequently use the fact that if $$$y$$$ is odd and divides $$$x$$$, then $$$y$$$ divides $$$\frac x 2$$$, and if $$$y$$$ is even then $$$\frac y2$$$ divides $$$\frac x 2$$$.
//In The Name of God
//I usually forget about the previous line...
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0), cin.tie(), cout.tie();
using namespace std;
typedef long long ll;
const int maxBt = 30;
const int mod = 1e9+7;
int cnt[maxBt];
int slv(){
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; i++){
cin >> a[i];
}
int to[n+1]; //powers of 2
to[0] = 1;
for(int i = 1; i <= n; i++){
to[i] = to[i-1]*2 % mod;
}
for(int i = 0; i < n; i++){
int x = 0;
for(int k = 0; k < maxBt; k++){
if(a[i] & 1)break;
a[i] >>= 1;
x++;
}
cnt[x]++;
}
int ans = to[n] - to[n-cnt[0]] + mod;
if(ans >= mod)ans -= mod;
int y = n-cnt[0];
for(int l = 1; l < maxBt; l++){
int x = y;
y -= cnt[l];
if(x-y < 2)continue;
int delta = to[x-1]-to[y]+mod;
if(delta >= mod)delta -= mod;
ans += delta;
if(ans >= mod)ans -= mod;
}
return ans;
}
signed main(){
IOS
cout << slv() << '\n';
}
1610E - AmShZ and G.O.A.T.
Idea: AmShZ, Preparation: AmShZ
Firstly we prove that if array $$$c$$$ ($$$c_i \le c_{i + 1}$$$) of length $$$k$$$ is terrible, $$$c$$$ has a terrible subsequence of length $$$3$$$.
If there exists an index $$$i \ge 2$$$ that $$$c_{i + 1} - c_i < c_i - c_1$$$, sequence {$$$c_1, c_i, c_{i + 1}$$$} is terrible. Otherwise we can prove that $$$c_{\lceil \frac{k}{2} \rceil} \le AVG$$$ which is in contraction to the fact that $$$c$$$ is terrible.
We want to find the longest good subsequence of $$$a$$$.
Let $$$b_1, b_2, \ldots, b_k$$$ be values of a good subsequence. For every $$$i \ge 2$$$ we have $$$b_{i + 1} \ge 2 \cdot b_i - b_1$$$.
Let's fix the first element of the subsequence to be $$$a_s$$$.
$$$\textbf{Read the Hints and Assumptions before reading this.}$$$
//khodaya khodet komak kon
# include <bits/stdc++.h>
using namespace std;
const int xn = 2e5 + 10;
int qq, n, a[xn], ans, res, ptr;
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];
for (int i = 1; i <= n; ++ i){
if (a[i] == a[i - 1])
continue;
res = 0, ptr = i;
while (ptr <= n)
ptr = lower_bound(a + ptr + 1, a + n + 1, 2 * a[ptr] - a[i]) - a, ++ res;
ans = max(ans, res);
}
cout << n - ans << "\n";
}
return 0;
}
1610F - Mashtali: a Space Oddysey
Idea: AliShahali1382, Preparation: AliShahali1382
Let's call $$$c_v$$$ as the sum of weights of all edges connected to vertex $$$v$$$.
It's obvious that when $$$c_v$$$ is even, $$$v$$$ would never be Oddysey.
Here we propose an algorithm to make all vertices with odd $$$c_v$$$ Oddysey.
$$$\textbf{Read the Hints and Assumptions before reading this.}$$$
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) x.begin(), x.end()
#define pb push_back
#define SZ(x) ((int)x.size())
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=100000000000000100LL;
const int mod=1000000007;
const int MAXN=300010, LOG=19;
int n, m, mm, k, u, v, x, y, t, a, b;
int U[MAXN], V[MAXN], W[MAXN], ans[MAXN];
int deg[MAXN], parr[MAXN][3], mark[MAXN];
vector<int> G[MAXN][3], E[MAXN];
vector<pii> G2[MAXN];
inline void orient(int i, int u){
if (u==U[i]){
ans[i]=1;
deg[U[i]]-=W[i];
deg[V[i]]+=W[i];
}
else{
ans[i]=2;
deg[U[i]]+=W[i];
deg[V[i]]-=W[i];
}
}
void MergePath(int i, int w){
mm++;
int v=i;
while (1){
while (SZ(G[v][w]) && mark[G[v][w].back()]) G[v][w].pop_back();
if (G[v][w].empty()) break ;
int i=G[v][w].back();
assert(!mark[i]);
mark[i]=1;
E[mm].pb(i);
int u=(U[i]^V[i]^v);
parr[u][w]^=1;
parr[v][w]^=1;
v=u;
}
if (E[mm].empty()){
mm--;
return ;
}
G2[i].pb({v, mm});
G2[v].pb({i, -mm});
}
void dfs(int v){
while (SZ(G2[v]) && mark[abs(G2[v].back().second)]) G2[v].pop_back();
if (G2[v].empty()) return ;
int u=G2[v].back().first, id=G2[v].back().second;
if (id<0){
id*=-1;
reverse(all(E[id]));
}
mark[id]=1;
for (int i:E[id]){
orient(i, v);
v^=V[i]^U[i];
}
assert(v==u);
dfs(u);
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for (int i=0; i<m; i++){
cin>>U[i]>>V[i]>>W[i];
parr[U[i]][W[i]]^=1;
parr[V[i]][W[i]]^=1;
G[U[i]][W[i]].pb(i);
G[V[i]][W[i]].pb(i);
}
int sum=0;
for (int i=1; i<=n; i++) sum+=parr[i][1];
for (int i=1; i<=n; i++) for (int w:{1, 2}) if (parr[i][w]) MergePath(i, w);
for (int i=1; i<=n; i++) for (int w:{1, 2}) MergePath(i, w);
for (int i=0; i<m; i++){
assert(mark[i]);
mark[i]=0;
}
for (int i=1; i<=n; i++) if (SZ(G2[i])&1) dfs(i);
for (int i=1; i<=n; i++) dfs(i);
cout<<sum<<"\n";
for (int i=0; i<m; i++) cout<<ans[i]; cout<<"\n";
return 0;
}
1610G - AmShZ Wins a Bet
Idea: AmShZ, Keshi, Preparation: AmShZ, Keshi, alireza_kaviani, AliShahali1382
We can prove that there exists a way to achieve the lexicographically minimum by removing some balanced substrings. (A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters "+" and "1".)
We will remove some pairs of indices. If there is a pair that we don't remove all the characters between them, by using that character instead of one the initial ones the answer either stays the same or becomes lexicographically smaller.
Because if the character in between is "(", changing the pair is like moving a "(" closer to the front of the outcome which will make it smaller. And if it's ")", changing the pair is like moving a ")" farther from the front of the outcome which will make it smaller.
For each $$$i$$$ find the shortest non-empty balanced substring that starts in index $$$i$$$. Let the length of this substring be $$$l$$$. Set $$$nxt_i$$$ as $$$i + l$$$, or $$$i$$$ if no such substring exists.
For each $$$i$$$ we either keep the $$$i$$$-th character or remove every character in $$$[i, nxt_i)$$$ interval.
Imagine we somehow store the answer for each suffix. Then $$$ans_i = \min(s_i + ans_{i + 1}, ans_{nxt_i})$$$.
$$$\textbf{Read the Hints and Assumptions before reading this.}$$$
//In the name of God
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll maxn = 3e5 + 100;
const ll lg = 20;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
ll n, par[maxn][lg], h[maxn][lg], ls[maxn + maxn], ps[maxn], nxt[maxn], a[maxn], d[maxn], p[maxn];
string s;
ll check(ll v, ll u){
for(ll i = lg; i--;){
if(d[v] < (1 << i) || d[u] < (1 << i)) continue;
if(h[v][i] == h[u][i]){
v = par[v][i];
u = par[u][i];
}
}
if(d[v] == 0) return 1;
return (h[v][0] < h[u][0]);
}
int main(){
fast_io;
p[0] = 1;
for(ll i = 1; i < maxn; i++){
p[i] = p[i - 1] * 2 % mod;
}
cin >> s;
n = Sz(s);
s = ' ' + s;
for(ll i = 1; i <= n; i++){
ps[i] = ps[i - 1] + (s[i] == '(' ? 1 : -1);
}
for(ll i = n + 1; i > 0; i--){
nxt[i] = i;
if(s[i] == '(' && ls[ps[i - 1] + maxn]){
nxt[i] = ls[ps[i - 1] + maxn];
}
ls[ps[i - 1] + maxn] = i;
}
a[n + 1] = n + 1;
for(ll i = n; i > 0; i--){
par[i][0] = a[i + 1];
h[i][0] = (s[i] == '(' ? 0 : 1);
d[i] = d[par[i][0]] + 1;
for(ll j = 1; j < lg; j++){
if(d[i] < (1 << j)) break;
par[i][j] = par[par[i][j - 1]][j - 1];
h[i][j] = (h[i][j - 1] * p[(1 << (j - 1))] + h[par[i][j - 1]][j - 1]) % mod;
}
a[i] = i;
if(check(a[nxt[i]], i)){
a[i] = a[nxt[i]];
}
}
ll v = a[1];
while(v != n + 1){
cout << (h[v][0] ? ')' : '(');
v = par[v][0];
}
cout << "\n";
return 0;
}
1610H - Squid Game
Idea: Tet, AliShahali1382, Preparation: AliShahali1382
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
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 SZ(x) ((int)x.size())
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=100000000000000100LL;
const int mod=1000000007;
const int MAXN=300010, LOG=19;
int n, m, k, u, v, x, y, t, a, b, ans;
int par[LOG][MAXN], h[MAXN], P[MAXN];
int stt[MAXN], fnt[MAXN], timer=1;
int fen[MAXN];
vector<int> G[MAXN], vec[MAXN], out;
int GetPar(int v, int k){
for (int i=0; k; i++) if (k&(1<<i)){
k^=(1<<i);
v=par[i][v];
}
return v;
}
inline void add(int pos, int val){
for (; pos<MAXN; pos+=pos&-pos) fen[pos]+=val;
}
inline int get(int pos){
int res=0;
for (; pos; pos-=pos&-pos) res+=fen[pos];
return res;
}
inline int get2(int v){ return get(fnt[v]-1)-get(stt[v]-1);}
void dfs(int node){
stt[node]=timer++;
for (int v:G[node]) dfs(v);
fnt[node]=timer;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for (int i=2; i<=n; i++){
cin>>par[0][i];
G[par[0][i]].pb(i);
h[i]=h[par[0][i]]+1;
for (int j=1; j<LOG; j++)
par[j][i]=par[j-1][par[j-1][i]];
}
dfs(1);
while (m--){
cin>>x>>y;
if (h[x]>h[y]) swap(x, y);
if (par[0][y]==x) kill(-1)
vec[x].pb(y);
}
iota(P+1, P+n+1, 1);
sort(P+1, P+n+1, [](int i, int j){ return h[i]>h[j];});
vector<pii> crossE;
for (int i=1; i<=n; i++){
int x=P[i];
for (int y:vec[x]){
if (h[x]==h[y]){
crossE.pb({x, y});
continue ;
}
int yy=GetPar(y, h[y]-h[x]-1);
if (par[0][yy]!=x){
crossE.pb({x, y});
continue ;
}
if (get2(yy)-get2(y)) continue ;
ans++;
out.pb(yy);
add(stt[yy], +1);
}
}
for (pii p:crossE){
int x=p.first, y=p.second;
if (get2(x)+get2(y)<ans) continue ;
out.pb(1);
ans++;
break ;
}
cout<<ans<<"\n";
return 0;
}
1610I - Mashtali vs AtCoder
Idea: AliShahali1382, Preparation: AliShahali1382
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
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 SZ(x) ((int)x.size())
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=100000000000000100LL;
const int mod=1000000007;
const int MAXN=300010, LOG=20;
int n, m, k, u, v, x, y, t, a, b, ans;
int par[MAXN], dp[MAXN], dead[MAXN];
vector<int> G[MAXN];
void dfs(int node){
for (int v:G[node]) if (v!=par[node]){
par[v]=node;
dfs(v);
dp[node]^=dp[v]+1;
}
}
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;
for (int i=1; i<n; i++){
cin>>u>>v;
G[u].pb(v);
G[v].pb(u);
}
dfs(1);
ans=dp[1];
cout<<1+(ans==0);
dead[1]=1;
for (int i=2; i<=n; i++){
vector<int> vec;
int v=i;
while (!dead[v]){
vec.pb(v);
dead[v]=1;
v=par[v];
}
reverse(all(vec));
for (int v:vec){
// Kill v
ans^=dp[v]+1;
ans^=dp[v];
ans^=1;
}
cout<<1+(ans==0);
}
cout<<"\n";
return 0;
}
errorgorn cluck cluck cluck!
lol in all seriousness, no hard feeling about it. as a fellow problemsetter i also understand how hard it is to create strong pretets for problems because theres no way you can kill every possible weird thing people do
i still remember in RAIF round there was the A had some condition like
if (a==0 || b==0)and someone wroteif (a*b==0). Theres no way anyone will be able to predict that lolhonestly, i enjoyed this contest. having FGHI to jump around and finally solving G was really fun, thanks for setting this contest :)
update:
now we are both stupid chicken
shit! what a stupid hack test
You should see this too...
In fact this thing TLEs on n=40 locally most of the times but cf reruns TLE submissions so I had to make n larger.
K*re khar
Btw just saying, the story in D was about the fact that we didn't have D $$$7$$$ days before the contest, because of the testers' feedback and also because the fact that I didn't solve C and D until about then, I decided to add D to fix the gap, it wasn't perfect however. Hopefully made the round better.
It kinda fixed the gap according to the numbers, and imo it is a decent problem. Won't ask for more from problem D in a div 1+2.
P/S: It indeed made the round better.
Thanks for your feedback. Makes me happy.
Just a little suggestion: we should use $$$\geq$$$ and $$$\leq$$$ instead of $$$>=$$$ and $$$<=$$$ to make the editorial more pleasant to read.
Thanks!
In problem I, am I the only person who actually solved the AtCoder problem in contest without looking at it?
I think hint 3 from problem D is missing the sum symbol on the RHS.
Thanks!
136659229 Can anyone tell me what is wrong in this code of B (Kalindrome Array). All similar codes got AC.
Integer's cache so that your '==' could be wrong.use int is ok.
Thanks, It solved my problem. But I never faced such type of problem with Integer before. What was the reason now?
The reason is simple you can't compare two objects with ==, cause it checks their references equality, instead you have to use the equals method.
Integer will cache value between -127 to 128, and you can use '==' within this scope.if beyond this scope you should use 'equals' instead of '=='.For more details, you can see the source code of Integer.
The reason is not coding in IDEA or ignoring IDEA's warning about objects comparison
For problem C if the constraints supported O(N*N),then would DP work?
Yes, we can do something like this. dp(len) denotes if the length of the sequence is len, then what is the maximum count of right_most elements that we can add to this sequence. And for each i, with dp(len) we can update dp(len+1) if dp(len) > 0.
I don't think 1-d DP will work, solely because the value of b[i]'s can differ and can produce different output, so I was asking about a solution based on dp[n][b[i]]!
vscode txdy
I cant understand D's explaining gcd(c1,c2,…,ck)=g s=∑ ci(ci−1) / 2 i= (1...k) when g is odd s % g == 0 && ci / 2 % g == 0 why how to explain c1 = 3,c2 = 9
Me neither. Neither I understand what is "x" in
x1c1+x2c2+…+xkck. I would understand it if the equation would be(x1c1 + c1/2) + (x2c2 + c2/2) + ... + (xkck + ck/2). For example if c1 would be 4, we can get sums like 2, 6, 10, ..., no 4, 8, 12, ...; or is "x" supposed not to be integer?Another point:
∑i=1kxici=−sumis it supposed to be∑i=1kxici=−sor what is "sum"?Btw sorry for formatting, but I don't know how it works on CF
How is the below solution wrong for problem B? I am not able to figure out the test case.
136636817
136659229 Same happened with me. Whereas all similar codes got AC.
Same, Got WA on 3414th token.
Works with primitive type. OR, using Integer.equal(Integer) when comparing elements from list of Integer wrapper class also works. Not sure why!
Yeah exactly.
You might get WA on this test:
5
1 3 2 4 1
Edit: the result is correct, my bad
Can someone pls explain the even case in problem D ?
Can anyone E in detail? I am not able to understand hint 1 properly.
We know that an array is bad if it has a terrible subsequence. If the length of our terrible subsequence is bigger than 3, then we can remove some elements and it will remain terrible.
So the array of three elements is terrible of a[1] < AVG < a[2]. If a[1] != a[2], then a[1] always smaller then AVG. So now we need to check AVG < a[2] -> (a[1] + a[2] + a[3]) / 3 < a[2] -> a[1] + a[2] + a[3] < 3 * a[2] -> a[1] + a[3] < 2 * a[2] -> a[3] — a[2] < a[2] — a[1]. If in our array exists three elements (i < j < k) such that a[k] — a[j] < a[j] — a[i] then our array is bad. If we take the first element as i, our a[j] — a[i] will be maximized, and if we take two consecutive j and k then our a[k] — a[j] will be minimized. We can only check all consecutive j and j + 1 if a[j+1] — a[j] < a[j] — a[1], and if it's true in at least one j then our array is bad if it's always false then our array is good.
Hope I understand the hint and explained it correctly.
Yes after reading above, It became clear that only checking the tuple of the form A_1,A_i and A_(i+1) is sufficient and it will account for all the possible tuples. Also, we can show that if make sure no such tuple exists, then for any subsequence, its difference array will be non-decreasing. Hence all subsequence will be good too.
I did read and tried to understand several explenations to C. But still do not get how or why the check "is it possible to invite x persons" works.
What is needed to understand that kind of logic?
To break it down: We are going to invite X persons, and they are already sorted from poorer to richer from 1 through n We keep a counter of how many we invited until now : cnt
When we are going to the i-th person we check for two things 1. we know we already invited cnt poorer persons (Since all people before i-th are poorer than him) if (b[i] >= cnt) then this condition is fulfilled 2. we know if we invited this person we are going to invite another (X-cnt-1) people (X: total invited, cnt: currently invited, 1: the i-th person himself) if(a[i] >= X-cnt-1) then this condition is fulfilled If both conditions are fulfilled, we invite this person and increase cnt by 1 after going through all n people, if (cnt >= X) then we can invite X people
Hope this helps you
Thanks, I couldn't understand this part from editorial, I really appreciate you helping in the comments.
how does selecting a prefix is better than a subsegment of size x from the group. like when do you know when to skip a person as taking him would not be beneficial for the future selections?
When we are checking for valid persons to select we check for both a and b not just one of them, so when we're at the i-th person if he's valid we take him, if we didn't take him we will end up taking another person who's equal to him since the other person will fulfill the same conditions for both a and b.
Look at it like this, If you want to invite $$$k$$$ person, then if you wanted to invite a person $$$x$$$ as $$$y$$$-th poorest in the party, then for a specific $$$k$$$ and $$$x$$$, the possible $$$y$$$-s form a segment, let's say from $$$l_x$$$ to $$$r_x$$$. After this you can use Monotonic Stack + Lazy (i.e. keep a vector $$$v$$$ such that $$$v_i$$$ is equal to if we invite $$$i$$$ friends, how many more rich person we can add, then add friends one by one and keep $$$v$$$ updated in $$$O(logn)$$$), hopefully understandable.
Pretty late but thought I made good proof.
Proof: Assume we don't invite the kth person that means at some point we would obviously have to invite the jth person such that j > k. Wlog, assume the jth person is the first person we invite after choosing not to invite k. Well then I argue that inviting k is equally as good as inviting j. The idea is simple we know we won't invite any one between k + 1 and j — 1 (inclusive), so the only people that get affected are j + 1, j + 2, ..., j + n. In both instances, of j and k these are the only people who get affected, and by affected I mean now we have one person poorer so the condition of b will be harder to satisfy. But we know that both j and k affet the same exact people. So the trick was just to note an observation that we don't invite anything between k and j. So now we have an extremly basic check function to satisfy.
Ahhhh...ok.
Basically we maintain a sorted set of choosen persons, then check in order of richness each single person.
We accept that persons if that persons constraints are so that it fits the next free position in the set of choosen persons.
Thanks for explaining.
thank you brdr
I hope this doesn't get down-voted For problem D, I didn't get the solution proposed above. However, I was thinking of a solution from another angle. Firstly, Odd numbers can can have a sum of 0 by itself so we can have any number of odd numbers in our sequence, Even numbers can have a sum of 0 for sure if there is at least 1 odd number in the sequence since O+E = O. The problem I couldn't figure out, When can E numbers alone (Without any odd number in the sequence) have a sum of 0 I don't know if anyone solved it in this approach, and is it possible this way or the only solution is the one in the editorial?
I did solve it in the way you described, and interestingly the answer to your question is the same condition as the editorial arrives at- if you bucket the even numbers by the maximum power of two that divides them, then to create a bad sequence, you need to have an odd number of elements from any one bucket, zero elements from the buckets below it, and any combination from the bucket above.
For example, if we have 2, 2, 4, 4, 8, 8, 16, 16, 48
We bucket it as follows {2, 2}, {4, 2}, {8, 2}, {16, 3}
And the number of bad sequences u can create is -
select odd number of 2's and no restriction on other buckets: 2C1 * 2^7
select no 2's, odd number of 4's, and no restriction on other buckets: 2C1 * 2*5
and so on.
Solution: 136657523
Never mind, I get it now. Thanks a lot
You can suppose that number 2 means 2x+1, number 4 means 4y+2 and number 6 means 6z+3, your purpose is that you should make their sum equal to zero, you can solve it with Bezout theorem.
Thanks a lot
I have an alternate solution for G without hashing.
136722671
We will only delete a pair of
(and)if they are adjacent.So actually we can think of this as deleting any contiguous valid bracket sequence from the string.
We maintain a stack. This stack only stores
(and valid bracket sequences.An example of a stack is [
(,(()()),(,()]We process the stack from left to right. When we encounter a
(, we just add it to the stack.When we process a
)we will join some suffix of the stack into a valid bracket sequence.For instance, [
(,(()()),(,()] becomes [(,(()()),(())]Now, we want to make it in the lexicographical order, so we have to make sure the stack has some monotonic property for the decreasing bracket sequence. For instance, [
(),(())] might as well be replaced with [(())]. So when we add a valid bracket sequence, we will pop out some suffix of the stack while the bracket sequence is lexicographically bigger.Well, we can compare 2 strings easily using hashes, but actually we can do it without them :o
Define the potential of the stack as $$$P$$$. The potential of the stack is the sum of length of strings in the stack. [
(,(()()),(,()] has potential $$$P=10$$$.Edit: i have no idea why this is fast but yet i cant find a test which makes the comparisons more than $$$O(n \log n)$$$. i dont deserve the AC in contest .-.
Now, to join bracket seqeuences, unfortunately I don't have a better method than merging deques in $$$O(n \log n)$$$. Perhaps there is a better way? Ive looked at some faster submissions and they seem to use this stack method but only storing the first index of the bracket.
My solution 136674351 is a bit different.
The bracket sequence can uniquely be written in the form
where each $$$s_i$$$ and each $$$t_i$$$ are balanced. We never want to remove any parenthesis that is not part of a balanced pair. In the final answer, it is optimal to fully remove each $$$t_i$$$.
Thus it suffices to solve the original problem for instances for the form $$$s($$$ where $$$s$$$ is balanced. We can write $$$s=(u_1)(u_2)...(u_n)$$$ and recursively assume that we have a minimal solution $$$u'_i$$$ for every $$$u_i$$$. We then want to select a non-empty subset $$$m_1,...,m_l$$$ of $$$[1..n]$$$ that leads to a minimal solution $$$s' = (u'_{m_1})...(u'_{m_l})$$$.
Clearly, $$$u'_{m_1}$$$ must be minimal among the $$$u'_i$$$. Then $$$u'_{m_2}$$$ must be minimal among the $$$u'_i$$$ with $$$i > m_{1}$$$, and so on.
Thus we simply have to sort the strings $$$u'_i$$$. Comparing two strings of length $$$a$$$ and $$$b$$$ in time $$$O(min(a,b))$$$ is fast enough, by the same complexity analysis as for the small-to-large trick.
My solution uses a similar kind of idea (see 136678450):
Lemma 1: We only delete contiguous valid bracket sequences
The subsequence of all deleted brackets is a valid bracket sequence: this is because each prefix contains more
(than)brackets. Moreover, assume we delete a pair of brackets(). Then, there is a solution where we also delete every bracket in between: if we do not delete such a bracket — say of type(— in between, then deleting this bracket instead of the originally deleted(bracket can only make the string lexicographically smaller. Together, these two properties prove the lemma.Then, let's move from right to left and compute the optimal solution for a suffix starting at position $$$i$$$. We represent this solution by computing for every $$$i$$$ the position $$$p_i$$$ of the first bracket contained in the optimal solution for the suffix starting at $$$i$$$. Reconstructing the solution for the suffix from the $$$p_i$$$ is easy: the first bracket in the solution is at position $$$p_i$$$, and the remainder is the optimal solution for the suffix starting at $$$p_i+1$$$ (which we can reconstruct recursively).
How do we compute $$$p_i$$$? If the bracket at position $$$i$$$ is
), then $$$p_i = i$$$ since we cannot remove this bracket. So, assume that the bracket is(. If there is no matching)bracket in the string, we will again have $$$p_i = i$$$ since we cannot remove this bracket by Lemma 1. So, the only case remaining is that the suffix starting at position $$$i$$$ looks like(s)twheresis a valid bracket sequence. Let $$$j$$$ be the position where the suffixtstarts (which we can compute using a stack).To obtain a solution for the suffix
(s)t, there are just two cases:(bracket, in which case we have to append the optimal solution for the suffixs)t, which is the suffix starting at position $$$i+1$$$.(bracket, in which case we have to delete the entire substring(s)and we will only keep the optimal solution for the suffixt, which is the suffix starting at position $$$j$$$.Since we know the optimal solutions starting at position $$$i+1$$$ and $$$j$$$, we can simply compare them character by character (using the values $$$p_i$$$) to decide which is lexicographically smaller, but this has a runtime of up to $$$O(n^2)$$$.
Instead, notice that the solution where we keep the first
(bracket looks like(s')t'wheres'is some subsequence ofs, andt'is the optimal solution for the suffixt. So, we actually ask whether(s')t'is lexicographically smaller thant', and we can already decide this after looking at all characters of(s'):(s')is not a prefix oft', we know due to our comparisons which string is smaller.(s')is a prefix oft', I claim that(s')t'is smaller. This is because removing the prefix(s')fromt'would also be a valid solution for the suffixt, but must be larger thant'by the optimality oft'. Therefore, it is easy to see that appending another copy of(s')to the beginning oft'will make the string even smaller.I claim that if we use this optimization, the code runs in time $$$O(n \log n)$$$.
The rough idea is as follows: let
p[x]be the largest prefix of a bracket stringxwhich has at least as many(as)brackets. Then, the comparison from above will consider at most $$$min(|(s')|, |p[t']|)+1$$$ characters: this is because every prefix of(s')has at least as many(as)brackets. Note that $$$|(s')| = 2 + |p[s')t']|$$$ sincep[s')t'] = s', so the number of comparisons is at most $$$min(|p[s')t']|, |p[t']|)+3$$$.If the optimal suffix is
t'and does not contain the brackets from(s'), we can associate the costs the the comparisons with the brackets in(s')since this can happen at most once for any bracket in the string. Otherwise, the optimal suffix is(s')t'and satisfies $$$|p[(s')t']| \ge |p[s')t']| + |p[t']|$$$ becausep[(s')t'] = (s')p[t'] = (p[s')t'])p[t']. Letxbe the smaller of the two stringsp[s')t']andp[t']. Then, the brackets fromxare now in an optimal suffix satisfying $$$|p[(s')t']| \ge 2 |x|$$$. Since every bracket can be contained in at most $$$O(\log n)$$$ many such doubling steps, the total number of comparisons is $$$O(n \log n)$$$.Can someone please explain hint 3 in problem D, I can't understand what x is here and how we are arriving at the given equation? Thanks in advance!!
I described how to arrive at the equation in the complete solution, it basically means we move the $$$i$$$-th sequence, $$$x_i$$$ times(i.e. add $$$x_i$$$ to all the elements in the $$$i$$$-th sequence). If it's possible to find $$$x_i$$$-s such that the sum of resulting set of sequences is $$$0$$$, then they will satisfy the equation. Also the other way around. (i.e. if it's possible to find such $$$x_i$$$-# that the equation holds, then the resulting set of sequences after moving the $$$i$$$-th sequence $$$x_i$$$ times, satisfies the second property in the statement)
Here are the video Solutions to the first 4 problems of the round in case you prefer that.
problem H was given 2100 rated tag(its a mistake ig). Anyone know how problem rating works.
who can explain the problem D,the solution can't understand。
Thanks for pointing out the typos.
Problem I is just the normal Hackenbush problem on a graph with cycles .
You can turn a cycle into a node using "Fusion Principle". And implement it using Heuristic Merging of sets in O(nlog^2) .
submission:136731363
My ideology for the first who have any problem -> as in question we have given that computer hide some cells and on query (suppose k) are done and it will return the k values that will be the distance of hidden cells from the cells that are done by user as query
manhattam formula is important-> |a1-a2| + |b1-b2|;Max value is k==2 (Think yourself)
when n=1 and m=1 this means grid is having just one cells so no query is required by user !! (obviously that will be hidden).
when m==1 or n==1 this means the grid is of only one row || one column in that case only one query means k==1 require as by manhattam formula abs(x2-x1) + abs(y2-y1)=value return by computer when user select some cells and in this case x1==1 or y1==1 depend on grid ,and hence only a single cell query is needed;
if (n and m)!=1 this means now we require at least two equation from formula and hence we take k==2 as user that is two cells (0,0) and n-1,m-1 as both are known from these we can make two equations and can predict the hidden cells .
..
Is there a way to solve problem F using Euler cycle/Euler path idea?
can anybody give link/info on why the solution to $$$x_1.c_1 + x_2.c_2 ... x_n.c_n - \ \sum_{i=1}^{n} c_i.(c_{i - 1} - 1)/2 = 0$$$ is when $$$g = gcd(c_1, c_2 ... c_n)$$$ divides $$$c_i.(c_{i-1})/2$$$ as specified on Hint 4 of Problem D
Search this on google "Linear Diophantine Equation". you will get that.
[deleted]
Have no idea how to prove it, can someone help? Also, how does it help proving that this exact grundy number is not reachable?
Can anyone explain the solution of F?? I can not understand the editorial.
So ci(ci−1)/2 has a reminder equal to (2^l) − 1 modulo (2^l). All the other terms ci(ci−1)/2 were divisible by (2^l) except these, so if the number of such ci-s is even, then their reminders sum up to 0 modulo (2^l) then c is good, and not otherwise.
Not able to understand this line in editorial of problem D can anybody help?
DeadlyCritic if gcd(c1,c2,…,ck)=g, then if g divides s, the array is good, otherwise it's not. Can you explain the prove or just the name of this theoram. I am unable to prove it.
https://codeforces.com/blog/entry/97179?mobile=false#comment-861044
AliShahali1382 errr.... I think on problem F there seems to be no input with $$$n,m > 100000$$$. I submitted a hack with $$$n=m=300000$$$ and the validator says $$$n \leq 100000$$$. I think the statement has wrong constraints....
Oh, damn! Yes, it was supposed to be 100000. It was a mistake in problem statement :(( However, that doesn't affect the solutions.
The explanation for D looks so complex for a 2000-rated problem
I'm so shocked the official solution of F is not Euler cycle!
For every (x,y,w), we can add an edge $$$(x,y)$$$ if w=1 or $$$(x+n,y+n)$$$ otherwise. Then we can find all odd-degree vertex, and the number of them must be even. If x and x+n are both odd-degree, add (x,x+n). Then connect remaining odd vertexes with a virtual vertex. It can be easily seen everyone is even now, and Euler cycle just construct a valid answer.
code
Btw, the inspiration comes from this AGC problem
First of all, I want to apologize for bringing this old blog into the recent post tab.
Now, My Question is what is the difference between the approaches for WA submission and AC submission (code differ in only pal() function) for the problemB.
I have commented in the code itself. Thanks in advance.
Helping in the approach might help you too. To know some dark side of palindromic arrays.
P.S: I have already read the editorial, and what worries me is that editorial say the same approach as my WA submission :(
Something to do with Java's Integer caching, apparently.
The editorial of problem H has wan my applause.
Good job!
Actually I have a much simpler approach to problem H.
Link
And if you implement the nlog lca in my code with the Method of Four Russians you will get a solution with O(n) time complexity.
I now have a method to improve my code to O(n) without even calculating the lca.
We only need to find the successor of the x in the path from x to y where x is the ancestor of y, which can be done in O(n) time complexity with dfs.
I have no idea why I didn't discover such a simple optimization the first time.
Here 's my code.
It's currently the fastest solution on CF.
for problem I, it seems like that we break the tree in two parts:
1.consider node u, if there's no pinned node in its subtree, then we make grundy^=grundy(u)
2.otherwise, the grundy is the parity of number of black edges
however, in 1., why we can take the subtree of a grey edge out and consider it singly?
could anyone please explain it for me?thanks in advance.
why we are just checking the first ith element why not all the elaments for the problem B
i think you need to share the prove