Codeforces Round 1123 (Div. 2) Editorial

#	User	Rating
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

#	User	Contrib.
1	Qingyu	155
2	nik_exists	150
2	maspy	150
4	Um_nik	142
5	Errichto	139
6	adamant	137
7	AmShZ	136
8	BledDest	132
9	maroonrk	131
10	qwexd	129

Thanks a lot for participating!

Idea: KluydQ
Solution + Editorial: KluydQ

Solution

Implementation

#include <bits/stdc++.h>

using namespace std;

signed main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        char c; cin >> c;
        string s; cin >> s;
        int ans = 0;
        for (int i = 0; i < n / 2; ++i) {
            if (s[i] == s[n - i - 1]) continue;
            if (s[i] == c || s[n - i - 1] == c) ans++;
            else ans+=2;
        }
        cout << ans << '\n';
    }
}

Did you like the problem?

2267B - Fashionable Array

Idea: YF_YUSUF
Solution + Editorial: YF_YUSUF, KluydQ

Solution

Implementation

#include <bits/stdc++.h>

using namespace std;

int n, a[101], cnt[101];

void solve()
{
	cin >> n;
	
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
		cnt[a[i]] ++;
	}
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 100; j >= 1; j --)
		{
			if(cnt[j] >= i) cout << j << ' ';
		}
	}
	for(int i = 1; i <= n; i ++) cnt[a[i]] = 0;
	
	cout << '\n';
}
int main()
{
	int t;
	cin >> t;
	while(t --) solve();
}

Did you like the problem?

2267C - GCD Treasury

Idea: Dibamboo
Solution + Editorial: KluydQ

Solution

Implementation

#include <bits/stdc++.h>
#define ll long long

const int N = 3e5 + 12;
using namespace std;

int n, x, a[N], p[N];
ll cnt[N];

vector <int> vc[N];

void solve()
{
	cin >> n >> x;
	
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
		int r = a[i];
		a[i] = __gcd(a[i], x);
		
		for(auto j : vc[a[i]])
		{
			cnt[j] += r;
		}
	}
	ll ans = 0;
	
	for(auto j : vc[x])
	{
		ans = max(ans, cnt[j]);
	}
	for(int i = 1; i <= n; i ++)
	{
		for(auto j : vc[a[i]]) cnt[j] = 0;
	}
	cout << ans << '\n';
}
signed main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	for(int i = 2; i <= N - 12; i ++)
	{
		if(!p[i])
		{
			for(int j = i; j <= N - 12; j += i)
			{
				p[j] = 1;
				vc[j].push_back(i);
			}
		}
	}
	int test = 0;
	if(!test) cin >> test;
	while(test --) solve();
}
// solved by KluydQ

Did you like the problem?

2267D - Backrooms Hill

Idea: Aldk
Solution + Editorial: Aldk, KluydQ

Solution

Implementation

#include <bits/stdc++.h>

using namespace std;

void solve()
{
	int n;
	cin >> n;
	
	int a[n + 5];
	int pos[n + 5];
	
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
		pos[a[i]] = i % 2;
	}
	int balance = 0;
	
	for(int x = n; x > 0; x --)
	{
		if(pos[x] % 2 == 0) balance ++;
		if(pos[x] % 2 == 1) balance --;
		
		if(abs(balance) > 1)
		{
			cout << "NO\n";
			return;
		}
	}
	cout << "YES\n";
}
int main()
{
	int t;
	cin >> t;
	while(t --) solve();
}

Did you like the problem?

2267E - Clean Substrings

Idea: KluydQ
Solution + Editorial: KluydQ

Solution

Implementation

#include <bits/stdc++.h>

#define int long long
#define sz(x) (int)(x.size())
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )

using namespace std;

const int N = 2e5 + 12;
const int mod = 1e9 + 7;

int n, q, ans, cnt0, cnt1, pr[N];
string s;

void solve()
{
	cin >> n >> q >> s;
    ans = cnt0 = cnt1 = 0;
	
	FOR(i, 1, n - 1, 1)
	{
		pr[i] = 0;
		
		if(s[i - 1] != s[i])
		{
			pr[i] = 1;
			ans += i * (n - i);
		}
	}
	FOR(i, 0, n - 1, 1)
	{
	    if(s[i] == '0') cnt0 ++;
	    if(s[i] == '1') cnt1 ++;
	}
	cout << (ans + cnt0 * cnt1) / 2 << ' ';
	
	FOR(i, 1, q, 1)
	{
		int pos;
		cin >> pos;
		
		if(pos != 1)
		{
			if(pr[pos - 1] == 0) pr[pos - 1] = 1, ans += (pos - 1) * (n - pos + 1);
			else pr[pos - 1] = 0, ans -= (pos - 1) * (n - pos + 1);
		}
		if(pos != n)
		{
			if(pr[pos] == 0) pr[pos] = 1, ans += pos * (n - pos);
			else pr[pos] = 0, ans -= pos * (n - pos);
		}
		if(s[pos - 1] == '0') cnt0 --, cnt1 ++, s[pos - 1] = '1';
		else cnt1 --, cnt0 ++, s[pos - 1] = '0';
		
		cout << (ans + cnt0 * cnt1) / 2 << ' ';
	}
	cout << '\n';
}
signed main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	int t = 0;
	if(!t) cin >> t;
	while(t --) solve();
}

Did you like the problem?

2267F1 - XOR Transformations (Easy Version)

Idea: KluydQ
Solution + Editorial: KluydQ

Solution

Implementation

#include <bits/stdc++.h>

using namespace std;

const int N = 2048;
int n, m, tim, a[N], cnt[N], ans[N];

void transform()
{
	vector <int> v;
	
	for(int i = 1; i <= n; i ++)
	{
		for(int j = i + 1; j <= n; j ++)
		{
			v.push_back(a[i] ^ a[j]);
		}
	}
	sort(v.begin(), v.end());
	for(int i = 1; i <= n; i ++) a[i] = v[i - 1];
}
void solve()
{
	cin >> n >> m;
	
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	int lim = 0;
	
	ans[lim] = a[n] - a[1];
		
	while(a[n] != 0)
	{
		lim ++, transform();
		ans[lim] = a[n] - a[1];
	}
	for(int i = 1; i <= m; i ++)
	{
		int x;
		cin >> x;
		
		if(x >= lim) cout << ans[lim] << '\n';
		else cout << ans[x] << '\n';
	}
}
signed main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	int test = 0;
	if(!test) cin >> test;
	while(test --) solve();
}

Did you like the problem?

2267F2 - XOR Transformations (Hard Version)

Idea: KluydQ
Solution + Editorial: KluydQ

Solution

Implementation

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 12;

int n, m, tim, a[N], cnt[N], ans[N];
int t[N * 30], son[N * 30][2];

void update(int x, int v = 1)
{
	t[v] ++;
	
	for(int i = 29; i >= 0; i --)
	{
		if((x >> i) & 1)
		{
			if(!son[v][1]) son[v][1] = ++ tim;
			v = son[v][1];
		}
		else
		{
			if(!son[v][0]) son[v][0] = ++ tim;
			v = son[v][0];
		}
		t[v] ++;
	}
}
int get(int x, int k, int v = 1)
{
	int res = 0;
	
	for(int i = 29; i >= 0; i --)
	{
		int b = (x >> i) & 1;
		
		if(t[son[v][b]] >= k) v = son[v][b], res += (1 << i) * b;
		else k -= t[son[v][b]], v = son[v][b ^ 1], res += (1 << i) * (b ^ 1);
	}
	return res ^ x;
}
void transform()
{
	for(int v = 1; v <= tim; v ++) t[v] = son[v][0] = son[v][1] = 0;
	set <pair <int, int>> st; tim = 1;
	
	for(int i = 1; i <= n; i ++) update(a[i]), cnt[i] = 2;
	for(int i = 1; i <= n; i ++) st.insert({get(a[i], 2), i});
	
	vector <int> upd;
	
	for(int _ = 1; _ <= 2 * n; _ ++)
	{
		auto it = st.begin();
		int i = (*it).second;
		
		upd.push_back((*it).first);
		st.erase(it), cnt[i] ++;
		
		if(cnt[i] > n) continue;
		st.insert({get(a[i], cnt[i]), i});
	}
	for(int i = 1; i <= n; i ++) a[i] = upd[(i - 1) * 2];
}
void solve()
{
	cin >> n >> m;
	
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	int lim = 0;
	
	ans[lim] = a[n] - a[1];
	
	while(a[n] != 0)
	{
		lim ++, transform();
		ans[lim] = a[n] - a[1];
	}
	for(int i = 1; i <= m; i ++)
	{
		int x;
		cin >> x;
		
		if(x >= lim) cout << ans[lim] << '\n';
		else cout << ans[x] << '\n';
	}
}
signed main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	int test = 0;
	if(!test) cin >> test;
	while(test --) solve();
}

Did you like the problem?

2267G - New LRT

Idea: Aldk
Solution + Editorial: Aldk, KluydQ

Solution

Implementation

#include <bits/stdc++.h>

#define sz(x) (int)(x.size())
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )

using namespace std;

const int N = (1 << 20) + 5;
const int mod = 1e9 + 7;

int n, m, c[N], dp[N], cnt[N], st[N][21];

void add(int &x, int y)
{
    x += y;
    if(x >= mod) x -= mod;
}
void solve()
{
	cin >> n >> m;
	
	FOR( i, 1, m, 1 )
	{
		cin >> c[i];
	}
	dp[0] = cnt[0] = 1;
	
	FOR( i, 1, n, 1 )
	{
		st[i][0] = 0;
		
		FOR( j, 0, 19, 1 )
		{
			st[i][j + 1] = st[i][j];
			if(!((m >> j) & 1) || i < (1 << j)) continue;
			
			else
			{
			    add(st[i][j + 1], st[i - (1 << j)][j]);
			    add(st[i][j + 1], dp[i - (1 << j)]);
			}
		}
		dp[i] = st[i][20];
	}
	FOR( i, 1, n, 1 )
	{
		st[i][0] = 0;
		
		FOR( j, 0, 19, 1 )
		{
		    st[i][j + 1] = st[i][j];
			if(!((m >> j) & 1) || i < (1 << j)) continue;
			
			else
			{
			    add(st[i][j + 1], st[i - (1 << j)][j]);
			    add(st[i][j + 1], cnt[i - (1 << j)]);
			}
		}
		cnt[i] = st[i][20];
		add(cnt[i], dp[i]);
	}
	int ans = 0;
	
	FOR( i, 1, m, 1 )
	{
		if((m & i) == i) add(ans, c[i] * 1ll * cnt[n - i] % mod);
	}
	cout << ans << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    
	int t = 0;
	if(!t) cin >> t;
	while(t --) solve();
}

Did you like the problem?

Comments (18)

Write comment?

KluydQ

3 hours ago, hide # |

Auto comment: topic has been updated by KluydQ (previous revision, new revision, compare).

→ Reply

zeyd1234

ORZ round. But in my opinion, C is harder than D.

ish4an

3 hours ago, hide # ^ |

Same, didn't even prove my approach for C, just went ahead with intuition.

Krish-006-19

Was able to do A and B

waidfj

45 minutes ago, hide # ^ |

C really gave me a hard time

swastik_P

i should have worked on D instead of C...

albertting

F1 let me know that brute force is sometimes the solution

KebiXCat

2 hours ago, hide # |

you didn't link the editorial in the original blog post

psgqwq111

← Rev. 2 →

I feel like the problems in this round, except for G (which I couldn't solve), weren't that good.

Also, the extension from F1 to F2 is essentially an existing problem (https://qoj.ac/problem/2995), with an even better time complexity.

23 minutes ago, hide # ^ |

It has the same time complexity, isn’t it? Moreover, the crux of the problem was to understand that there is not more that $$$\log(A)$$$ transformations. Because of the fact that we need to do transformations +-9 times gives you greater time complexity.

vidanovic

I had a simpler solution for D.

Let's assume the array has an even length. Visually, if we "unfold" the hill and place it's elements in order it's gonna put all the outermost pairs A[i] and A[n-1-i] next to each other. This means that if we sort the initial array, in every pair A[2k] and A[2k+1] there must be one at an even position and one at an odd position, as one of them is gonna go to the left side and one to the right side, and their positions will have opposite parity. If the array has an odd length, we can just skip over the first element and solve for the rest of the array.

All you have to do in the implementation is sort the array and go through every pair where A[2k], A[2k+1] and check that their parities don't match. Fits in 15 lines.

zerefx

106 minutes ago, hide # |

shouldn't the Time Complexity of $$${C}$$$ be $$${O(n\cdot\sqrt[3]{x}+\sqrt{x})}$$$ ?

83 minutes ago, hide # ^ |

actually code works for $$$O(n\log(n) + 6n)$$$

46 minutes ago, hide # ^ |

oh your implementation is different, my bad!

DarkDevilVaqif

85 minutes ago, hide # |

No idea how my solution worked on F1, but I'm not complaining

ujjwxl.exe

79 minutes ago, hide # |

C was much harder than D

Wax

67 minutes ago, hide # ^ |

C was simple: if gcd(v[i],x)>1 then we can take full of v[i] as v[i] will continously decresed by the gcd and it will remain same through this process...and if u think internally gcd will always be one of the divisor of x..and each divisor will give answer independently...so bruteforcing over each divisor individually and try to take as much as elements which are divisable as sum....ans will be the maximum sum

aryanc403

42 minutes ago, hide # |

Also, my post-contest discussion stream for all problems is here

KluydQ's blog