Kuroni's blog

By Kuroni, history, 13 months ago,

Hello everyone, this is the editorial for Codeforces Round #616 (Div. 1) and Codeforces Round #616 (Div. 2)! Along with the solution to each problem, we will have the theme and easter egg solution as well! I hope you all enjoyed our problems ( ´ ▽  )b

1291A - Even But Not Even

Author: 265918

Tutorial
Implementation
#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
int odd = 0;
for (char c : s) if ((c - '0') & 1) odd++;
if (odd <= 1) { cout << "-1\n"; continue; }
int cnt = 0;
for (char c : s) {
if ((c - '0') & 1) { cout << c; cnt++; }
if (cnt == 2) break;
}
cout << '\n';
}
return 0;
}

1291B - Array Sharpening

Author: hugopm

Tutorial
Implementation
#include <bits/stdc++.h>
using namespace std;

int main()
{
ios::sync_with_stdio(false); cin.tie(0);

int nbTests; cin >> nbTests;
while (nbTests--) {
int nbElem; cin >> nbElem;
vector<int> tab(nbElem);

for (int i = 0; i < nbElem; ++i)
cin >> tab[i];

int prefixEnd = -1, suffixEnd = nbElem;

for (int i = 0; i < nbElem; ++i) {
if (tab[i] < i) break;
prefixEnd = i;
}
for (int i = nbElem-1; i >= 0; --i) {
if (tab[i] < (nbElem-1)-i) break;
suffixEnd = i;
}

if (suffixEnd <= prefixEnd) // Non-empty intersection
cout << "Yes\n";
else
cout << "No\n";
}
}

1290A - Mind Control

Author: Ari

Tutorial
#include <bits/stdc++.h>
using namespace std;

int main()
{
ios::sync_with_stdio(false); cin.tie(0);

int nbTests; cin >> nbTests;
while (nbTests--) {
int nbElem, pos, nbControl;
cin >> nbElem >> pos >> nbControl;

int before = pos-1, behind = nbElem-pos;
nbControl = min(nbControl, before);

vector<int> tab(nbElem);
for (int i = 0; i < nbElem; ++i) cin >> tab[i];

int bestStrategy = 0;

for (int orderFirst = 0; orderFirst <= nbControl; ++orderFirst) {
int strategyAns = (int)(1e9) + 5;
for (int opponentFirst = 0; opponentFirst <= before-nbControl; ++opponentFirst) {
int caseAns = max(tab[orderFirst + opponentFirst], tab[orderFirst + opponentFirst + behind]);
strategyAns = min(strategyAns, caseAns);
}
bestStrategy = max(bestStrategy, strategyAns);
}

cout << bestStrategy << "\n";
}
}
Implementation (linear)
#include <bits/stdc++.h>
using namespace std;

void solve() {
int n, m, k;
cin >> n >> m >> k;
k = min(k, m - 1);
vector<int> a(n);
for(auto &x : a)
cin >> x;
vector<int> b;
for(int i = 0; i < m; i++)
b.push_back(max(a[i], a[i + n - m]));
int sz = m - k;
int ans = 0;
deque<int> q;
for(int i = 0, j = 0; i + sz - 1 < m; i++) {
while(q.size() && q.front() < i)
q.pop_front();
while(j < i + sz) {
while(q.size() && b[q.back()] >= b[j])
q.pop_back();
q.push_back(j++);
}
ans = max(ans, b[q.front()]);
}
cout << ans << '\n';
}

int main() {
int t;
cin >> t;
while(t--)
solve();
}

1290B - Irreducible Anagrams

Author: Ari

Tutorial
Implementation
#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

char s[N];
int n, q, l, r, sum[N][26];

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> (s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 26; j++) {
sum[i][j] = sum[i - 1][j];
}
sum[i][s[i] - 'a']++;
}
cin >> q;
while (q--) {
cin >> l >> r;
int cnt = 0;
for (int i = 0; i < 26; i++) {
cnt += (sum[r][i] - sum[l - 1][i] > 0);
}
if (l == r || cnt >= 3 || s[l] != s[r]) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}

1290C - Prefix Enlightenment

Author: hugopm

Tutorial
Implementation (preprocess with DFS)
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int lim = 1000*1000 + 5;
int nbElem, nbSub;
vector<int> subset[lim];
int side[lim];
int isIn[lim][2];
string ini;
int rep = 0;

int drepr[lim];
int dsz[lim];
int cnt[lim][2];

int dfind(int x)
{
if (drepr[x] != x) drepr[x] = dfind(drepr[x]);
return drepr[x];
}

void add(int cc, int s0, int s1)
{
cc = dfind(cc);
rep -= min(cnt[cc][0], cnt[cc][1]);
cnt[cc][0] = min(lim, cnt[cc][0] + s0);
cnt[cc][1] = min(lim, cnt[cc][1] + s1);
rep += min(cnt[cc][0], cnt[cc][1]);
}

void dmerge(int a, int b)
{
a = dfind(a); b = dfind(b);
if (a == b) return;
if (dsz[a] < dsz[b]) swap(a,b);
dsz[a] += dsz[b];
drepr[b] = a;
}

void dfs(int nod)
{
cnt[nod][side[nod]] = 1;
for (int elem : subset[nod]) {
if (isIn[elem][1] == -1) continue;
int oth = isIn[elem][0] + isIn[elem][1] - nod;
if (side[oth] == -1) {
side[oth] = side[nod] ^ (ini[elem] == '0');
dfs(oth);
}
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> nbElem >> nbSub;
cin >> ini;
fill(side,side+lim,-1);
iota(drepr,drepr+lim,0);
fill_n(&isIn[0][0], 2*lim, -1);

for (int sub = 0; sub < nbSub; ++sub) {
int st; cin >> st;
subset[sub].resize(st);
for (int pos = 0; pos < st; ++pos) {
int elem; cin >> elem; --elem;
subset[sub][pos] = elem;
if (isIn[elem][0] == -1) isIn[elem][0] = sub;
else isIn[elem][1] = sub;
}
}

for (int sub = 0; sub < nbSub; ++sub) {
if (side[sub] == -1) {
side[sub] = 0;
dfs(sub);
}
}

for (int elem = 0; elem < nbElem; ++elem) {
int n0 = isIn[elem][0], n1 = isIn[elem][1];
if (n0 != -1 && n1 == -1) {
int destroy = side[n0] ^ (ini[elem] == '0');
if (destroy == 1) add(n0, 0, lim);
else add(n0, lim, 0);
} else if (n0 != -1) {
dmerge(n0, n1);
}
cout << rep << "\n";
}
}
Implementation (dynamic bipartite DSU)
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N = 1E6 + 5, K = 1E6 + 5, INF = 1E9 + 7;

int n, k, c, v, ans = 0, dsu[K];
char s[N];

struct node {
int l, r, xo;

node(int _l = 0, int _r = 0, int _xo = 0) : l(_l), r(_r), xo(_xo) {}

int get() {
return min(l, r);
}

inline void operator+=(node oth) {
l = min(INF, l + oth.l);
r = min(INF, r + oth.r);
}
} val[K];

pair<int, int> trace(int u) {
if (dsu[u] < 0) {
return {u, 0};
} else {
pair<int, int> tmp = trace(dsu[u]);
dsu[u] = tmp.fi;
val[u].xo ^= tmp.se;
return {dsu[u], val[u].xo};
}
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> (s + 1);
for (int i = 1; i <= k; i++) {
dsu[i] = -1;
val[i] = node(1, 0, 0);
cin >> c;
while (c--) {
cin >> v;
}
}
for (int i = 1; i <= n; i++) {
int typ = (s[i] - '0') ^ 1;
if (ans != -1) {
if (adj[i].size() == 1) {
pair<int, int> u = trace(adj[i][0]);
ans -= val[u.fi].get();
val[u.fi] += node((u.se == typ) * INF, (u.se != typ) * INF);
ans += val[u.fi].get();
} else if (adj[i].size() == 2) {
pair<int, int> u = trace(adj[i][0]);
pair<int, int> v = trace(adj[i][1]);
if (u.fi != v.fi) {
ans -= val[u.fi].get() + val[v.fi].get();
if (dsu[u.fi] > dsu[v.fi]) {
swap(u, v);
}
if (u.se ^ v.se ^ typ) {
swap(val[v.fi].l, val[v.fi].r);
val[v.fi].xo = 1;
}
dsu[u.fi] += dsu[v.fi];
dsu[v.fi] = u.fi;
val[u.fi] += val[v.fi];
ans += val[u.fi].get();
}
}
}
cout << ans << '\n';
}
}

1290D - Coffee Varieties (hard version)

Author: hugopm

Tutorial
Implementation
#include <bits/stdc++.h>
using namespace std;

{
cout << "? " << pos+1 << endl << flush;
char c; cin >> c;
if (c == 'E') exit(0);
return (c == 'Y');
}

int main()
{
int nbElem, memSize, nbBlocks;
cin >> nbElem >> memSize;
nbBlocks = nbElem / memSize;

vector<bool> isAlive(nbElem, true);

for (int startBlock = 0; startBlock < nbBlocks; ++startBlock) {
int delta = 0;
cout << "R" << endl << flush;
for (int iDo = 0; iDo < nbBlocks; ++iDo) {
int curBlock = (startBlock+delta+nbBlocks) % nbBlocks;
int st = curBlock*memSize;
for (int elem = st; elem < st+memSize; ++elem) {
if (isAlive[elem]) {
if (ask(elem)) isAlive[elem] = false;
}
}

if (delta >= 0) ++delta;
delta = -delta;
}
}

int nbAlive = count(isAlive.begin(), isAlive.end(), true);
cout << "! " << nbAlive << endl << flush;
}

1290E - Cartesian Tree

Author: gamegame

Tutorial
Implementation
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+1;
const int ts=1<<21;
int n;
ll mx[ts],se[ts],mxc[ts];//max, 2nd max, max count
int sz;
ll ch[N];//which values are changed
ll df[N];//change in frequency
void pass(int id,int c){
if(mx[c]>mx[id]) mx[c]=mx[id];
}
void push(int id){
pass(id,id*2);
pass(id,id*2+1);
}
void pull(int id){
mx[id]=max(mx[id*2],mx[id*2+1]);
mxc[id]=0;
if(mx[id]==mx[id*2]) mxc[id]+=mxc[id*2];
if(mx[id]==mx[id*2+1]) mxc[id]+=mxc[id*2+1];
se[id]=max(se[id*2],se[id*2+1]);
if(mx[id*2]!=mx[id]) se[id]=max(se[id],mx[id*2]);
if(mx[id*2+1]!=mx[id]) se[id]=max(se[id],mx[id*2+1]);
}
void upd(int id,int l,int r,int ql,int qr,int v){
if(l>qr || r<ql || mx[id]<=v) return;
if(ql<=l && r<=qr && se[id]<v){
ch[++sz]=mx[id];df[mx[id]]-=mxc[id];
mx[id]=v;
ch[++sz]=mx[id];df[mx[id]]+=mxc[id];
return;
}
push(id);
int mid=(l+r)/2;
upd(id*2,l,mid,ql,qr,v);
upd(id*2+1,mid+1,r,ql,qr,v);
pull(id);
}
void upd2(int id,int l,int r,int p,int v){
if(l==r){
ch[++sz]=mx[id];df[mx[id]]-=mxc[id];
mx[id]=v;
ch[++sz]=mx[id];df[mx[id]]+=mxc[id];
return;
}
push(id);
int mid=(l+r)/2;
if(p<=mid) upd2(id*2,l,mid,p,v);
else upd2(id*2+1,mid+1,r,p,v);
pull(id);
}
void build(int id,int l,int r){
mx[id]=0;mxc[id]=r-l+1;se[id]=-1e9;
if(l==r) return;
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
/////////////////////////////////////////////////
ll bit1[N],bit2[N];
void bupd1(int id,ll v){
for(int i=id; i<=n ;i+=i&-i) bit1[i]+=v;
}
void bupd2(int id,ll v){
for(int i=id; i<=n ;i+=i&-i) bit2[i]+=v;
}
ll bqry1(int id){
ll res=0;
for(int i=id; i>=1 ;i-=i&-i) res+=bit1[i];
return res;
}
ll bqry2(int id){
ll res=0;
for(int i=id; i>=1 ;i-=i&-i) res+=bit2[i];
return res;
}
int a[N],p[N];
ll ans[N];
set<int>s,t;
void magic(int mg){
s.clear();t.clear();build(1,1,n);
for(int i=1; i<=n ;i++) bit1[i]=bit2[i]=0;
s.insert(p[1]);//set of existed elements
t.insert(p[1]);//set of l that maxr[] is not null
bupd1(p[1],1);
int mx=p[1];//largest existed position
upd2(1,1,n,p[1],p[1]);
bupd2(p[1],-1);
ll tot=-1;
for(int i=2; i<=n ;i++){
int cur=p[i];
auto it=s.lower_bound(cur);
bool rm=(it==s.end());//new element is rightmost
int nxt=0;
if(!rm) nxt=*it;//next
if(it==s.begin()){//new element is leftmost
tot-=bqry1(cur);bupd2(cur,-1);
t.insert(cur);
upd2(1,1,n,cur,mx);
}
else{
int prv=*(--it);
upd(1,1,n,1,prv,prv);
if(rm) mx=cur;
else{
upd2(1,1,n,nxt,mx);
if(t.find(nxt)==t.end()){
tot-=bqry1(nxt);bupd2(nxt,-1);
t.insert(nxt);
}
}
upd2(1,1,n,*s.begin(),mx);
}
s.insert(cur);
tot+=bqry2(n)-bqry2(cur-1);
bupd1(cur,1);
for(int j=1; j<=sz ;j++){
if(ch[j]!=0 && df[ch[j]]!=0){
tot+=df[ch[j]]*bqry1(ch[j]);
bupd2(ch[j],df[ch[j]]);
df[ch[j]]=0;
}
}
sz=0;
ans[i]+=tot;
}
}
void solve(){
for(int i=1; i<=n ;i++){
p[a[i]]=i;ans[i]=0;
}
magic(1);
for(int i=1; i<=n ;i++) p[i]=n+1-p[i];
magic(0);
for(int i=1; i<=n ;i++) ans[i]+=1;
for(int i=1; i<=n ;i++) cout << ans[i] << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin >> n;
for(int i=1; i<=n ;i++) cin >> a[i];
solve();
}

1290F - Making Shapes

Author: Kuroni

Tutorial
Implementation
#include <bits/stdc++.h>
using namespace std;

const int N = 5, MX = 4 * N, LG = 31, MOD = 998244353;

int n, m, x[N], y[N];
int px[1 << N], nx[1 << N], py[1 << N], ny[1 << N];
int dp[LG][MX][MX][MX][MX][2][2];

void add(int &x, int y) {
x += y;
if (x >= MOD) {
x -= MOD;
}
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}
for (int msk = 0; msk < (1 << n); msk++) {
for (int i = 0; i < n; i++) {
if (msk >> i & 1) {
(x[i] < 0 ? nx : px)[msk] += abs(x[i]);
(y[i] < 0 ? ny : py)[msk] += abs(y[i]);
}
}
}
int mpx = max(1, px[(1 << n) - 1]);
int mpy = max(1, py[(1 << n) - 1]);
int mnx = max(1, nx[(1 << n) - 1]);
int mny = max(1, ny[(1 << n) - 1]);
dp[0][0][0][0][0][0][0] = 1;
for (int lg = 0; (1 << lg) <= m; lg++) {                                // bit position
for (int cpx = 0; cpx < mpx; cpx++) {                               // carry of positive x
for (int cpy = 0; cpy < mpy; cpy++) {                           // carry of positive y
for (int cnx = 0; cnx < mnx; cnx++) {                       // carry of negative x
for (int cny = 0; cny < mny; cny++) {                   // carry of negative y
for (int sx = 0; sx < 2; sx++) {                    // is the suffix of x greater than the suffix of m
for (int sy = 0; sy < 2; sy++) {                // is the suffix of y greater than the suffix of m
for (int msk = 0; msk < (1 << n); msk++) {  // iterating over the mask of the current bit position
int spx = cpx + px[msk];
int spy = cpy + py[msk];
int snx = cnx + nx[msk];
int sny = cny + ny[msk];
if (((spx ^ snx) & 1) || ((spy ^ sny) & 1)) {
continue;
}
int bx = spx & 1, by = spy & 1;
int nsx = (bx < (m >> lg & 1) ? 0 : bx > (m >> lg & 1) ? 1 : sx);
int nsy = (by < (m >> lg & 1) ? 0 : by > (m >> lg & 1) ? 1 : sy);
add(dp[lg + 1][spx / 2][spy / 2][snx / 2][sny / 2][nsx][nsy], dp[lg][cpx][cpy][cnx][cny][sx][sy]);
}
}
}
}
}
}
}
}
cout << (dp[__lg(m) + 1][0][0][0][0][0][0] + MOD - 1) % MOD << '\n';
}

Theme and easter eggs

Spoilers

Oh boi this is gonna be interesting ( ͡° ͜ʖ ͡°)

The theme of the contest can be found by concatenating the first letter of each paragraph of the announcement ( ͡° ͜ʖ ͡°) From now on, we will refer to six-digit codes found in each problem statement as "sauce". ( ͡° ͜ʖ ͡°)

For 1291A - Even But Not Even, the obvious sauces are $177013$ and $265918$. Along with this, break down the really long number in the sample input, you will get 4 sauces: $222373$, $204424$, $185217$, and $171912$.

For 1291B - Array Sharpening, the sauces are $282865$, $256988$ (found as inline examples for non-sharpened arrays), and $248618$ (found in the sample input).

For 1290A - Mind Control, the sauces are $292385$ and $213604$ (found in the sample input).

For 1290B - Irreducible Anagrams, look at the second sample input. There are 6 queries, concatenate $l$ and $r$ of all queries to get $122153$ and $242975$.

For 1290C - Prefix Enlightenment, the binary string of the last sample input encodes a sauce into binary. Decode it into decimal to get $299782$. Fun side note, while developing this problem, the intended sauce was $299742$, but I typed in the wrong code to the binary converter. It turned out to be better btw. ( ͡° ͜ʖ ͡°)

For 1290D - Coffee Varieties (hard version), the ? queries of the second sample output gives you $264525$. Additionally, the ! query gives you page $6$ of the sauce. ( ͡° ͜ʖ ͡°)

For 1290E - Cartesian Tree , the permutation of the second sample input gives you $124563$.

For 1290F - Making Shapes, the third sample output gives you the sauce $296161$.

UPD: As I write these lines, $300000$ has been born. So unironically, the constraints of 1291B - Array Sharpening and 1290C - Prefix Enlightenment are now sauces. ( ͡° ͜ʖ ͡°)

Hope you have fun with the easter eggs we provided. ( ͡~ ͜ʖ ͡°)

• +239

 » 13 months ago, # |   +156 Thanks for the easter eggs, now my next few nights would be sleepless. :)
 » 13 months ago, # |   +13 can you please share the test case generator for Div2-E problem?
•  » » 13 months ago, # ^ | ← Rev. 4 →   -11 It's easy. Just assign every number from $1$ to $n$ at most 2 different numbers from $1$ to $k$ , which means which set the number should belong to.
 » 13 months ago, # |   +26 One of the best contest it was !
 » 13 months ago, # | ← Rev. 3 →   +8 Nice problems and fast AF editorial and good pretests.Thanks man. :)
 » 13 months ago, # |   +28 WOW! VERY quick editorial! Thanks)
 » 13 months ago, # |   +31 thanks for the fast editorial
 » 13 months ago, # |   +13 Thank You very much for the problems.Learnt to think for basic things first in easy problems rather than taking cases and complicating.
 » 13 months ago, # |   +58 Thank you for samples in C.
 » 13 months ago, # |   +14 Div1 BCD are really good, thanks!
 » 13 months ago, # |   +10 Thanks for the fast editorial.
 » 13 months ago, # | ← Rev. 3 →   0 Doubt For Mind Control Problem 1290A :->In the editorial it is mentioned that iterate over y. But why ?Say my k = 3 and m = 6 for some n then say i force 1 guy to take first element and rest 2 to take last. Now the three people i have no control over can choose first element or not. i.e i cannot guarantee that the next three elements (after the first one is chosen by the guy i forced) will be my element all the time. but i can say for sure is that:the element at fourth index i.e after 3 elements can be my answer. This will of course be compared with the number obtained from the end.so basically for each person i force to pick firt element say i and y ppl i cannot force. The only element i can pick is (i + y + 1) from the start. We will get one answer from last as well.So should i just iterate over i from 0 to k. calculate the expected number from first and last. Take their minimum compare globalmaximum with minimum obtainedprint globalmaximumPlz Help
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 I'm not so clear about your doubt, so here let me try to explain one insight without $y$ ... Observe the array below $[2, 9, 2, 3, 8, 5]$Consider when $k=0, m=4$All possible final states will be like these sub-arries: $[2, 9, 2], [9, 2, 3], [2, 3, 8], [3, 8, 5]$For every states, the answer is: $[2], [9], [8], [5]$So you can find in the worst situation, the player will get 2 as his final number.Now consider how does "k force times" affect the answer. Actually it you can force some opponents to avoid some prefix or suffix states. (you can't avoid one state in the middle, sorry I can't explain this point.)In the case above if k=2, you force 2 opponents to take the "2" in the front and the "5" in the back.Then all possible final states will be like these sub-arries: $[9, 2, 3], [2, 3, 8]$For every states, the answer is: $[9], [8]$After this force, the worst anwser gets greater, right?The focus is to find the globalmaximum for every possible states' answer.Hope this can help you understand this solution better.Nice round anyway. lol
•  » » » 13 months ago, # ^ |   0 Thank you.
•  » » » 13 months ago, # ^ |   0 How can we say that we can only force some opponents to take first element? I am really confused with this question please help although your explanation was very good but this part that i mentioned is yet not clear.
•  » » » » 13 months ago, # ^ |   0 Maybe this means in some stage of the whole process, you are allow to force someone make specific choice. Like in a case when the i-th opponent take the front might make the lowest answer worse (leave some small numbers in the back), then you force him to take smaller number in the the back. Could this help?
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   0 @Rajat16 I have the same doubt. Is this clear to you now?
•  » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 yes sure! Actually we are not making people choose only first element but we are checking for all possible cases. example 1 2 3 4 5 6 7 8 9 be the array, M=4,K=1.K is some number of controllable people(C) and Total before me (TB) = position(M)-1 now, some more variables we need, number of uncontrollable (NC) = ( TB — C ) now run a loop k=0 to k=K.when k = 0: and i=0 to <= (NC): carefully see what happens !! these are the possible subarrays: [1,2,3,4,5,6] , [2,3,4,5,6,7],[3,4,5,6,7,8]. You can see that [4,5,6,7,8,9] was not included because this is a case when we will force the last person to choose 9th element(i.e the last element)!! Now when k= 1: we will have [2,3,4,5,6,7],[3,4,5,6,7,8],[4,5,6,7,8,9] here we didn't have [1,2,3,4,5,6] because we forced the guy to choose 1st element.so basically I misunderstood the editorial that I only choose the person to take first element where as I am finding all possible cases and taking the optimal answer. Hope that helps.Read the code this way: run a loop (i=0 to i<=K) for number of guys you force to take 1st element. so when i is let's say 3 and K given is 7 this should be read as we choose first 3 guys to taken first elements and remaining(7-3) to take last elements, now iterate through for all possible i simple!!
•  » » » » » » 10 months ago, # ^ |   0 Thanks.
•  » » » 7 months ago, # ^ |   0 when m=2 and my position=4,why the answer for [2,9,2,3,8,5] isn't always 9? because if 1st person take 2 ,i will force 2nd and 3rd person to take last element. and if 1st person take last element,i will force 2nd person to take 1st element and 3rd person to take last element. thus i always get 9.
•  » » » » 7 months ago, # ^ |   0 what if first person take 5? because you cannot bound first person to take only 2 if he takes 5 then answer changes and you have to tell the maximum of worst case.
•  » » » 6 months ago, # ^ |   0 if K=3 then what should be remove next???????????
 » 13 months ago, # |   +7 did anyone else solved c with binary search?
•  » » 13 months ago, # ^ |   0 Me, but it seems unnecessary. :(I rather overthought.
 » 13 months ago, # |   -8 I learned a lot from Div.1 C even though I was not able to solve it during the contest. Thank you for making such good problems!
•  » » 10 months ago, # ^ |   0 bro people toxic af u didn't even say anything bad and -8
 » 13 months ago, # |   +28 The six digit codes...how are they more than just random 6 digit numbers? What makes them an easter egg?
•  » » 13 months ago, # ^ |   +195
•  » » » 13 months ago, # ^ |   +19 Dude.. page 6 of 264525 actually made a pretty good wallpaper
•  » » » » 13 months ago, # ^ |   0 I know right <3
•  » » » » » 13 months ago, # ^ |   +37 Hate to say this, but 185217's a real solid one. Here we go again.
•  » » 13 months ago, # ^ |   +8 honestly, I regret looking this up at urbandictionary... :)
•  » » » 13 months ago, # ^ |   +49 That's slightly hard to believe after seeing your username. :)
•  » » » » 13 months ago, # ^ |   +5 Now I regret not pointing out this irony in the original comment
•  » » 13 months ago, # ^ |   +1
•  » » » 13 months ago, # ^ |   0 Thanks ;)Unfortunatly my company blocked that website for a given reason :/
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   0 Sure they did. It's not something you should be browsing in the office. :)
•  » » » 13 months ago, # ^ |   0 raw lol
•  » » 13 months ago, # ^ |   -23 Read my comment and think about it for a moment.
 » 13 months ago, # |   -8 For Div. 2 B. I consider the following:Just consider all indices that contain the max value in the array. Then, for each, try to find if all the elements to its left can be made strictly decreasing. Then do similarly with the elements to its right: try to make them strictly decreasing. If you could find one such index then the answer is true. Why do I get WA here...?
•  » » 13 months ago, # ^ |   +1 Take $[1, 2, 1, 3]$ for example. Your algorithm will give NO, but a possible sharpened array generated from this could be $[1, 2, 1, 0]$.
•  » » » 13 months ago, # ^ |   0 Thanks! I got obfuscated believing that if there's a YES answer, it MUST be when a[k] = MAX(a) :-(Good lesson!
 » 13 months ago, # |   0 FASTEST editorial in the WEST!! ^_^
 » 13 months ago, # |   +13 Thanks for the fast editorial and an interesting D!
 » 13 months ago, # |   -10 For div-2 D,I think atleast two different character is sufficient instead of three.. Pls give any counter example.
•  » » 13 months ago, # ^ |   0 aabba
•  » » » 13 months ago, # ^ |   0 Consider t = bbaaa
•  » » » » 13 months ago, # ^ |   +3 aabb|a bbaa|a
•  » » » » » 13 months ago, # ^ |   0 Oh thanks..
•  » » » » » » 13 months ago, # ^ |   0 Cheer up and good night :(((...
•  » » 13 months ago, # ^ |   0 Any two-distinct-character string with both ends having the same character will have a reducible anagram. Proof is pretty trivial.
 » 13 months ago, # |   0 Its seems too early for the tutorials. Good Job Guys!
 » 13 months ago, # | ← Rev. 2 →   +4 can some one explain how monotonic dequeue has been used in Mind Control (Div2 C / Div1 A) to solve the problem in O(n).
•  » » 13 months ago, # ^ | ← Rev. 3 →   +8 First, calculate b[] in O(n)Then, use a min queue. Start by pushing the first m-k values into the queue, and define ans = 0.Then perform the following steps k+1 times: Query v = min in queue, and set ans = max(ans, v) Add the next value of b into the queue Pop a value off the front of the queue
•  » » » 13 months ago, # ^ |   0 THANKS
 » 13 months ago, # | ← Rev. 2 →   -21 ignore this comment, it is wrong.
•  » » 13 months ago, # ^ |   0 This wont work. They do not take maximum, the take that ends that the max of the remaining two elements will be minimum.Same true for your k choices, you do not take minimum, you take that what maximizes the possible result at the end.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 yeah, it is wrong, just find a simple counterbut for the remaining M — K people isn't it optimal to take max? because if no one take it, i will take it in the end and the answer will better for me
•  » » » » 13 months ago, # ^ |   0 If you take max, the next element could be even bigger. So, what counts is what is left after you take them, not what you take.
 » 13 months ago, # |   +36 Waiting for the rating update. Wish to see blue tag in my own profile for the very first time. Thanx to the whole CF community for making me this kind of eager for competitive programming.
•  » » 13 months ago, # ^ |   +26 And now you have it! Congratulations!!!
•  » » 13 months ago, # ^ |   +4 Congratulations !
•  » » 13 months ago, # ^ |   +4 Actually I won't be able to explain, how much happy I have become right now.Once it was just a dream for me. But it just became true.Wish to become PINK soon. Pray for me. Thanks to the whole community.
•  » » 13 months ago, # ^ |   +3 Congratulations !
 » 13 months ago, # | ← Rev. 3 →   0 i didn't get the last case For D's Editoral:s="abaababba"Can't we do take all character of s[n] together abd add rest character.t="aaaaabbbb"in this way upto length n-1 there will be difference of prefix of S and t for last Character (in this case 'a')Correct me if i am wrongPs:I got it
 » 13 months ago, # |   +13 Binary search tag D?!
•  » » 13 months ago, # ^ |   +8 To know how many distinct characters in range [L,R], you can for each character do a binary search to get the first occurrence for this character greater than or equal to L,if it was smaller than R then you know that this character exists in the range .
•  » » 13 months ago, # ^ |   0 Sure, you can store the position of each time a character appears on the string and find the number of times the character $c$ appears in the range $[l,r]$ as $upperbound_c(r) - lowerbound_c(l)$. That technique could be useful in other problems. You can check this code to know how to implement it.
 » 13 months ago, # |   0 feels like i would remain pupil forever
 » 13 months ago, # |   +36 tourist back to 1. Finally bug on codeforces resolved.
•  » » 13 months ago, # ^ |   +10 it really was a bug...!
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 It was not bug ! Check again now.
 » 13 months ago, # | ← Rev. 3 →   -28 .
 » 13 months ago, # |   0 From 1290C Sol: "Since the answer exists for i=n, there exists a such partition of the graph (into "red" and "blue" nodes). We can find it with usual dfs, and keep it for lower values of i"Why is this coloring still optimal for i < n? What if there is a more optimal coloring? Can someone give me a proof for why we can still use the same coloring for lower values of i?
•  » » 13 months ago, # ^ |   +8 From the full graph to the graph representing the state $i  » 13 months ago, # | -15 Are there some strong folks who can explain how the "Cartesian" tree from div1 E actually constucted. Preferably, explanation of the first example, sequences of length 4 and more. What is the step of recursion. Why for length 4 from example numbers from left and right parts of MAX are mixed. Can't grasp at all.  » 13 months ago, # | 0 why do we do strategyAns = min(strategyAns, caseAns); and not max pls help(Div2C) •  » » 13 months ago, # ^ | 0 because we want to take the maximum minimum of the numbers left. The first sample case was well explained: 2 9 2 3 8 5 The first one was forced to take 5 2 9 2 3 8 The second one was forced to take 2 9 2 3 8 and One guy left, he could take 8 so we can take 9, but if he took 9 then we can take 8. so we just took the maximum minimum, and that is the least maximum number that we could take.  » 13 months ago, # | +66 I think I have a bit simpler implementation for Div1 C.I use an ordinary DSU, with representing each original node$x$with two nodes, one that represents that$x$will be chosen and the other one representing that$x$will not be chosen, let's call them$x_{true}$and$x_{false}$.Also, each root has a cost, which is the cost to choose that root. Initially, the cost of each root is$1$if it is a$true$node and$0$otherwise.I also create a dummy node representing the$nochoice$. The cost of its$true$node is$0$, and the cost of its$false$node is$OO$.To merge two nodes$x$and$y$, if they must take the same value, then$join(x_{true}, y_{true})$and$join(x_{false}, y_{false})$, else$join(x_{true}, y_{false})$and$join(x_{false}, y_{true})$.To force a node to be$true$or$false$, then join it with the$nochoice$node.The solution maintains the total cost and updates it upon merging in a similar manner to the tutorial's solution. The dummy node makes it unnecessary to care for overflows or minimize the costs with$OO$, since that$OO$will only be counted once, in the dummy node.Code: 70098404 •  » » 13 months ago, # ^ | 0 Had similar idea, the approach is kind of a 2-SAT (Boolean Satisfiability)  » 13 months ago, # | -8 Thanks for the useful tutorial <3 Have a nice day <3  » 13 months ago, # | 0 Regarding D, In the problem: partition the graph having directed edges$(i, j)$for all$i < j$into edge-disjoint paths,Isn't it possible to prove using Hall's theorem that number of disjoint paths must be$ \geq $about$ \frac{n^2}{4} $?This means that$1.5$is the best possible factor for the above approach. How do you get a factor of$1.2$in randomized DFS then? •  » » 13 months ago, # ^ | +13 The graph is not directed. As long as we visit vertices$i$and$j$consecutively in a path in any order we will be able to remove all equalities. The only difference is which of the blocks will have elements deleted.  » 13 months ago, # | ← Rev. 2 → 0 I Failed on 1291B because i thought that operation must be done on only a single element not any element... need to read question next time Lol  » 13 months ago, # | 0 Thanks for the fast editorial.Is here a guy who knows a different solution of Irreducible Anagrams? •  » » 13 months ago, # ^ | ← Rev. 2 → 0 I interested on it because Irreducible Anagrams has binary search, data structures, strings, two pointers problem tags . •  » » » 13 months ago, # ^ | ← Rev. 3 → +12 There are quite a few other solutions to Irreducible Anagrams, differing on how the third condition is handled. I believe the one in the editorial is the most straightforward, but some other possible solutions we intended to pass include: Find for each left endpoint$l$the maximum$x$such that$s[l, x]$contains at most two different characters. After preprocessing this allows us to answer queries in$O(1)$. This can be done in$O(n)$using a somewhat straight forward two pointers algorithm, for a final complexity of$O(n + q)$. One can use any of the standard solutions for the classic "count number of distinct values in a range" problem, such as Mo's Algorithm in$O(n\sqrt{q})$, or Sorting + Fenwick Tree in$O(q \log (n))$. Some other silly solutions also passed, such as using segment trees instead of prefix sums to find whether a substring contains a certain character, which results in$O(26 \log n)$per query. This is a rather strange thing to do, but some people did actually pass with solutions like this ¯\_(ツ)_/¯. I'm sure there's many other solutions that could get accepted in this problem, as constraints were low enough to allow basically everything that isn't straight up quadratic to pass. •  » » » » 13 months ago, # ^ | 0 Your solution is understandable readable. thanks ;) •  » » » » 9 months ago, # ^ | 0 Ari Can you explain a little more about your approach to use monotonic deque in Div. 1 A? Like why it works for this problem? Thanks.  » 13 months ago, # | ← Rev. 2 → +8 Nice and clear problems with good pretests. Liked it very much!! :)  » 13 months ago, # | 0 Thanks for the contest (And I won't definitely sleep a few nights)!  » 13 months ago, # | +11 Eurrghhhh... I just realize what the easter eggs mean...I'd never trust weebs ever again >: (  » 13 months ago, # | ← Rev. 2 → +3 hard version of question Div2-C is when you can chose from all numbers(not just from end or front) and your friends must chose from front or end.i misunderstood and spent about two hours to solve it and after solving i got that i misunderstoodhowever i solved question C and learnt many thingone of them is check test-cases before solving question •  » » 13 months ago, # ^ | ← Rev. 2 → 0 I don't fully understand how this is harder, tbh? let dp[i][j][k] be the answer for the subarray from i to j with k people for you to manipulate. Then dp[i][j][k] = max(dp[i+1][j][k-1], dp[i][j-1][k-1]). When k = 0, suppose there are p people left to pick who you cannot manipulate. Then you know that they will leave some contiguous subarray of length (j — i + 1 — p). You can iterate over all subarrays of such length and pick the minimum of the maximum of all subarrays. I did exactly this except instead of picking the min of max of all subarrays, i picked the min of max of all (first element/last element) of subarrays. 70060565  » 13 months ago, # | 0 So fast  » 13 months ago, # | ← Rev. 2 → -10 I tried to understand the statement of Div1E (Cartesian Tree), but failed. If someone understood and can clarify one thing in construction of the tree, i will be very grateful.In the very first example, given the sequence 4, 2, 7, 3, 5, 6, 1. According to algorithm, we should take maximum, 7 in this case, so position x = 3(is it correct?). Then we construct trees for [4, 2] (left tree) and [3, 5, 6, 1] (right tree) (again, any missunderstand?). Then, due to step 5, left and right constructed trees become left and right subtrees and the root is temporary removed number. And it maximum, 7 in this case. But in example the resulting tree has root that is not 7 and 1 and 2 in the same subtree, while they were in different parts after breaking the sequence.Where am I wrong?P. S. I see that it is ordered as BST, and what i do is a mess. That's why i ask for some help. •  » » 13 months ago, # ^ | +1 The announcment for problem E says: "In the notes to samples, the nodes in the tree are labeled by indices, while the tree in the explanation is labeled by value. Sorry for the inconvenience caused. The problem doesn't change."That's why the root of sample tree isn't "7". It labeled "3" because 7 is third element of the array (x = 3). Also 1 and 2 are in the same subtree due to they're indicies of 4 and 2 (a[1] = 4 and a[2] = 2). •  » » » 13 months ago, # ^ | 0 Thaks a lot! Short and clear explanation. Finally I can enjoy the beaty!  » 13 months ago, # | 0 I want to know that if the problem C has a better solution. •  » » 13 months ago, # ^ | 0 What kind of "better" do you want. We have a linear solution already.  » 13 months ago, # | ← Rev. 3 → 0 Div.2 B. What is test case 2: 109th line? It seems I'm wrong with my solution, but I can't hack myself. I prepare pyramide-like triangle of "minimal possible values", and then check if all values of an array are higher (70047658).UPD. Solved. My "pyramide" should be sharper at a top in case of even number of elements! •  » » 13 months ago, # ^ | 0 did almost same and getting the same problem  » 13 months ago, # | +5 whats wrong in my code i check for min number at respective indices of array for n = 4 it should be 0 1 2 0 or 0 2 1 0 and similarly for other n values (problem 2 ) •  » » 13 months ago, # ^ | 0 Thanks. I found my mistake by looking at your examples.Ok. How do you expand "pyramide" of higher N? E.g. n == 6. •  » » » 13 months ago, # ^ | 0 0 1 2 3 1 0 or 0 1 3 2 1 0 this is how  » 13 months ago, # | ← Rev. 4 → +26 Thanks for the problems, I really enjoyed them. Here's an alternate solution for C.We will find the answer for each$i$by iterating from$1$to$n$. For each set, we associate a cost of picking that set. Initially this cost is$1$for every set.If$i$is currently off, then we pick the lowest cost set that contains$i$. We are going to keep transforming the sets and costs so that doing this produces the correct answer. If$i$is off, then in this and all future iterations exactly one of the sets that contains$i$should be selected. If there is only one set containing$i$, we remove it. If there are two, say$S$and$T$where$S$was selected in the current iteration, then we want to have the ability to unselect$S$and select$T$instead in later iterations. The set of positions that get flipped by doing this is$U = S \text{ xor } T$and the cost of doing this is$cost(T) - cost(S)$. So we can enforce this by removing$S$and$T$and adding this new set$U$with this cost. (this is kind of similar to residual edges in Ford-Fulkerson; here U is a residual set)If position$i$is already on, then if it is contained in exactly one set, this set should never be picked hereafter, so just remove it. If it is contained in two sets$S$and$T$, then in all future iterations either they should both be picked or neither. We can accomplish this by removing$S$and$T$and adding$U = S \text{ xor } T$with cost$cost(S) + cost(T)$.70094066  » 13 months ago, # | -10 what is the reason behind comparing the vallues with array indexes?? in B cant get this:) •  » » 13 months ago, # ^ | 0 Because the array wont be strictly increasing if the values of array are less than the sequence 0,1,2,3,..,n that is similar to array indexes.  » 13 months ago, # | 0 In Div2 C why having more control is optimal ? Any kind of proof would be helpful ?  » 13 months ago, # | 0 Can someone explain me how to approach Problem A . I am stuck I am new to comp prog feeling depressed after going through this contest . •  » » 13 months ago, # ^ | 0 if we take even numbered odd digits then we can easily get the evne numbers described in A.if we take only two odd numbers it can be one of the evne numbers.  » 13 months ago, # | 0 Can someone explain the div2.E's the way to maintain the number of the red and blue nodes,I can not understand the code's defining of l,r...  » 13 months ago, # | 0 I have a doubt in Div1A/Div2C: Why should I select the control the first$k$persons in the queue, and not in some other order: like why not first$m-1-k$can select randomly, and the last$k$elements should select the element I forced them too. Please help. •  » » 13 months ago, # ^ | ← Rev. 3 → 0 we will choose the first K cause we want the answer for the person in the mth position to be maximum after he chooses he will leave so the people after him will have no effect on the value X but I didn't understand exactly the intuition behind how to get the optimal answer •  » » » 13 months ago, # ^ | 0 Please don't answer questions you don't understand: I am asking about which$k$people to choose for controlling. •  » » 13 months ago, # ^ | 0 I have the same question. How to choose which k person to control? The first k? Or others? •  » » 13 months ago, # ^ | +9 Basically, in order to know what element that$m-$th person picks, you need to know after$m-1$persons picks the elements themselves, what the remaining subarray is. And the remaining subarray only depends on the number of persons choosing the head element (or equivalently, the amount choosing the tail element) in$m-1$persons. It indicates that the order is not important, and you can pick any$k\$ persons to control.
 » 13 months ago, # |   0 i didn't understand div 2 C solution can anyone explain it in a more intuitive level thanks in advance
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Brute force on the persuade people by taking two-pointer one starting from 0 index(say left) and one at n-min(k,m-1)-1 (say right), then for each pair of left and right, find the minimum element you can get by brute-forcing from left to right with the same approach of taking two-pointer one starting from left(say l) and another at n-m+left(say r), then find minimum from max(a[l], a[r], r till right.Do the same for all the values of left and right. And the maximum of all the values will be the answer.70354436
 » 13 months ago, # |   0 Can you help me to find the time complexity of my submission with explanation for Div2 C problem 70354436
 » 13 months ago, # |   0 Can someone please explain me how is the color of the each node is being maintained in div 1 C. I tried to understand it so much but I couldn't. Is it some kind of common trick that I am unaware of? val[v.fi].xo = 1; What is this line actually doing?
•  » » 13 months ago, # ^ |   0 That is maintaining the parity equality between u and dsu[u]. If u and dsu[u] are colored with the same color, val[v.fi].xo = 0, else val[v.fi].xo = 1.
 » 13 months ago, # |   0 For Div 2 C.Mind Control, Why it is always optimal to persuade first k people?
 » 13 months ago, # |   0 Could You please explain me clearly the question Array Sharpening , B ?Thank you .
 » 13 months ago, # |   0 Can anyone explain 1291B tutorial?
 » 13 months ago, # | ← Rev. 2 →   0 [deleted]
 » 10 months ago, # |   0 Ur name is like Korona :D
 » 10 months ago, # |   0 please...can anyone explane how to solve B?..I cant understand the logic
 » 9 months ago, # |   0 What is wrong with my solution ? I m not getting the case where my solution fails So please help meDIV2/Csolution link : https://codeforces.com/contest/1291/submission/82024558
 » 9 months ago, # |   0 Hello! I have a doubt in the irreducible anagram question. I know I am way too late for this but please help me out. I don't understand why do we have to check the first and the last character in the string? Its not directly explained in the tutorial and I am new to this and I can't understand it by my own. I kind of understand the solution but then, I also don't. I have other doubts as well but that would just make it too long
 » 8 months ago, # |   0 Why can't we assign our k(effective) friends after rest random friends. I think we can get better number if we do that . for eg:6 4 22 9 2 3 8 5here, 1 -> random and 2 -> friend [9 2 3 8 5] or [2 9 2 3 8] and we get 9 as our answer.correct me if I'm wrong.
•  » » 8 months ago, # ^ |   +4 You have to choose what to do with the people you control before the process starts. In this case, what you do with the 2 controlled people is different depending on what the first person does; that's not allowed.
•  » » » 8 months ago, # ^ |   0 Thanks, It's clear for me now.
 » 8 months ago, # |   0 I have spent days on Div2C. I have read all the comments. I dont get either the editorial or any comment's approach. If anyone can explain it in simple words, Please help me!I have to say this, "This is one of the most unclear Editorials I have ever seen."Here's my TLE code for a very simple and direct brute force I tried.This is recursion based. If I have any k type people left, I take them in 2 ways:-> force him to select first->force him to select second.Then I take maximum of these above 2 case.If I have k=0 left, Then for the remaining m, We check all possible cases and find out the minimum. (I believe my solution is correct, but gives TLE.)
•  » » 8 months ago, # ^ | ← Rev. 2 →   +3 Yes, your solution seems to be correct for me. But i think the reason for TLE is it's exponential complexity.I will explain you my approach -let 6 4 2 2 9 2 3 8 5 n = 6, m = 4; k = 2first loop take care of number of controlled friends in the left ( 0 to k)second loop take number of random in the left( starting from zero to (m-1-k) )and then we can take minimum of available left and right number in first loop and finally take maximum in first loopfor eg: 1) 2 9 2 3 2 9 2 or 9 2 3 min( max(3, 9), max(2, 2) ) --> 2 2) 9 2 3 8 9 2 3 or 2, 3, 8 min( max(9, 3), max(8, 2) ) --> 8 3) 2 3 8 5 2 3 8 or 3 8 5 min( max(2, 8), max(3, 5) ) --> 5 maximum in all three is 8. Link to my code
•  » » 8 months ago, # ^ | ← Rev. 2 →   +4 I also have read editorial and comments after solving this with dp but have not got anything clearly . And your solution is correct . Just memorize the answers of each state . Here is my Dp solution 87047732
•  » » 8 months ago, # ^ |   0 Thanks! Got it!
 » 7 months ago, # |   0 Hi, i can't understand why my code gives me an unknown error on test 10 — 1291AHere's my code: def sumthedigits(stringa): a = 0 for x in range(len(stringa)): a += int(stringa[x]) return ac = -1 t = int(input()) for x in range(t): n = int(input()) s = input() bul = False #print(s) if n == 1: print(-1) continue while int(s) % 2 == 0: s = s[:c] n -= 1 if n == 1: print(-1) bul = True break if bul: continue while sumthedigits(s) % 2 == 1: for x in range(n): if int(s[x]) % 2 == 1: s = s[:x] + s[x + 1:] break else: print(-1) bul = True break if bul: break if not bul: print(int(s))`
 » 7 months ago, # |   0 This problem can also be solved by dp (which is not in the tag section), if anyone is interested, here's my solution: Code
 » 5 months ago, # |   +10 Didn't knew codeforces had people of culture ( ͡° ͜ʖ ͡°)
 » 5 months ago, # |   0 Can someone explain a DP approach for C(Mind Control)? I was thinking dp[no. of people controlled][left/right] but i'm not sure if it'll work. Can someone explain the DP?My question is that is it even sufficient to check the i-1th state alone to predict dp[i]?i planned to control the last k people to get me the best possible outcome and finding the worst case scenario for the first m-k people.
 » 4 months ago, # | ← Rev. 2 →   0 For the problem Div1 B, Can anybody give a proper proof for the third condition i.e. s[1]=s[n] and s has at least three different characters. Thanks in advance. EDIT: Don't bother, I got it.
 » 6 weeks ago, # |   0 in problem 1291A - Even But Not Even how greedy help ?