1691A - Beat The Odds
Video Editorial
Idea: amul_agrawal
Problem Setting: menavlikar.rutvij JadeReaper rahulgoel amul_agrawal
Editorial: menavlikar.rutvij rahulgoel
Video Editorial: rahulgoel
Sum of two odd numbers is even and sum of two even numbers is also even.
If all consecutive pairs have even sum, can we generalize something about the sequence using the above hint?
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
int num_odd = 0;
for (auto x : a)
if (x & 1)
num_odd++;
cout << min(num_odd, n - num_odd) << endl;
}
return 0;
}
1691B - Shoe Shuffling
Video Editorial
Idea: amul_agrawal
Problem Setting: rahulgoel menavlikar.rutvij JadeReaper
Editorial: menavlikar.rutvij rahulgoel
Video Editorial: JadeReaper
What happens to other people when a person receives a shoe greater his size?
What happens when a person has a unique shoe size?
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef vector<ll> vll;
#define io \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
int main()
{
io;
ll tc;
cin >> tc;
while (tc--)
{
ll n;
cin >> n;
vll s(n), p(n);
for (ll i = 0; i < n; ++i)
cin >> s[i];
ll l = 0, r = 0;
bool ans = true;
for (ll i = 0; i < n; ++i)
p[i] = i + 1;
while (r < n)
{
while (r < n - 1 and s[r] == s[r + 1]) // get range [l,r] with equal values
++r;
if (l == r)
ans = false;
else
rotate(p.begin() + l, p.begin() + r, p.begin() + r + 1); // rotate right in range [l,r]
l = r + 1;
++r;
}
if (ans)
{
for (auto &x : p)
cout << x << " ";
cout << endl;
}
else
cout << -1 << endl;
}
return 0;
}
1691C - Sum of Substrings
Video Editorial
Idea: amul_agrawal
Problem Setting: rahulgoel amul_agrawal
Editorial: amul_agrawal rahulgoel
Video Editorial: amul_agrawal
What is the contribution of each 1
?
At what position would 1
contribute less?
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
string s;
cin >> s;
int ones = 0, p1_first = n, p1_last = -1;
for (int p = 0; p < n; p++) {
if (s[p] != '1')
continue;
ones += 1;
if (p1_first == n)
p1_first = p;
p1_last = p;
}
int add = 0;
// moving the last one to last position
if (ones > 0 and (n - 1 - p1_last) <= k) {
k -= (n - 1 - p1_last);
add += 1;
ones -= 1;
}
// moving the first one to first position
if (ones > 0 and p1_first <= k) {
k -= (p1_first);
add += 10;
ones -= 1;
}
cout << 11 * ones + add << "\n";
}
return 0;
}
1691D - Max GEQ Sum
Video Editorial
Idea: amul_agrawal
Problem Setting: fangahawk amul_agrawal rahulgoel keyurchd_11
Editorial: fangahawk rahulgoel
Video Editorial: fangahawk
If we have a list of subarrays where the element at index $$$i$$$ is the max, which subarrays should we check to be sufficient?
Checking subarrays which end or start at index $$$i$$$ is sufficient, so we can optimize our solution with this observation as the basis.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll ninf = -1e15;
vector<int> nextGreater(vector<ll>& arr, int n) {
stack<int> s;
vector<int> result(n, n);
for (int i = 0; i < n; i++) {
while (!s.empty() && arr[s.top()] < arr[i]) {
result[s.top()] = i;
s.pop();
}
s.push(i);
}
return result;
}
vector<int> prevGreater(vector<ll>& arr, int n) {
stack<int> s;
vector<int> result(n, -1);
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && arr[s.top()] < arr[i]) {
result[s.top()] = i;
s.pop();
}
s.push(i);
}
return result;
}
ll query(vector<ll> &tree, int node, int ns, int ne, int qs, int qe) {
if (qe < ns || qs > ne) return ninf;
if (qs <= ns && ne <= qe) return tree[node];
int mid = ns + (ne - ns) / 2;
ll leftQuery = query(tree, 2 * node, ns, mid, qs, qe);
ll rightQuery = query(tree, 2 * node + 1, mid + 1, ne, qs, qe);
return max(leftQuery, rightQuery);
}
int main() {
int t;
cin >> t;
while (t--) {
int n, _n;
cin >> n;
vector<ll> arr(n, 0);
for (auto& a : arr)
cin >> a;
// Round off n to next power of 2
_n = n;
while (__builtin_popcount(_n) != 1) _n++;
// Prefix sums
vector<ll> prefixSum(n, 0), suffixSum(n, 0);
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
suffixSum[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
suffixSum[i] = suffixSum[i + 1] + arr[i];
}
// Two max-segtress, one on the prefix sums, one on the suffix sums
vector<ll> prefixTree(2 * _n, ninf), suffixTree(2 * _n, ninf);
for (int i = 0; i < n; i++) {
prefixTree[_n + i] = prefixSum[i];
suffixTree[_n + i] = suffixSum[i];
}
for (int i = _n - 1; i >= 1; i--) {
prefixTree[i] = max(prefixTree[2 * i], prefixTree[2 * i + 1]);
suffixTree[i] = max(suffixTree[2 * i], suffixTree[2 * i + 1]);
}
vector<int> ng = nextGreater(arr, n);
vector<int> pg = prevGreater(arr, n);
bool flag = true;
for (int i = 0; i < n; i++) {
ll rightMax = query(prefixTree, 1, 0, _n - 1, i + 1, ng[i] - 1) - prefixSum[i];
ll leftMax = query(suffixTree, 1, 0, _n - 1, pg[i] + 1, i - 1) - suffixSum[i];
if (max(leftMax, rightMax) > 0) {
flag = false;
break;
}
}
if (flag)
cout << "YES\n";
else
cout << "NO\n";
}
}
1691E - Number of Groups
Video Editorial
Idea: amul_agrawal
Problem Setting: akcube keyurchd_11 rahulgoel amul_agrawal
Editorial: akcube rahulgoel keyurchd_11 Video Editorial: akcube
We can iterate over the starting and ending points of all segments.
Is it necessary to connect all segments which can be connected?
Can we make observations which would reduce the number of connections we actually make?
For each group formed, it is enough to store the blue segment with maximum ending point, and red segment with maximum ending point.
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(x) (int)(x).size()
#define fastio cin.tie(0) -> sync_with_stdio(0)
struct DSU{
vi dsu, szx;
DSU() = default;
DSU(int n) : dsu(n), szx(n, 1) {
for(int i=0; i<n; i++) dsu[i] = i;
}
int parent(int i){
if(dsu[i]==i) return i;
else return dsu[i] = parent(dsu[i]);
}
int size(int i) { return szx[parent(i)]; }
int operator[](int i){ return parent(i); }
int num_comps(){
int ct = 0;
for(int i=0; i<sz(dsu); i++) if(dsu[i] == i) ct++;
return ct;
}
void unify(int a, int b){
a = parent(a);
b = parent(b);
if(szx[a] < szx[b]) swap(a, b);
if(a!=b) dsu[b] = a, szx[a] += szx[b];
}
};
struct Point{
int t, p, pc, id;
bool close;
bool operator<(Point &other){
if(p == other.p) return close < other.close;
return p < other.p;
}
};
void solve(){
int n; cin>>n;
vector<Point> points;
for(int i=0; i<n; i++){
int t, l, r; cin>>t>>l>>r;
points.pb({t, l, r, i, false});
points.pb({t, r, l, i, true});
}
sort(all(points));
DSU dsu(n);
vector<set<pii>> open(2); // {r, id}
for(auto &p:points){
if(p.close) open[p.t].erase({p.p, p.id});
else{
open[p.t].insert({p.pc, p.id});
while(sz(open[p.t ^ 1]) > 1){
auto [r, id] = *open[p.t ^ 1].begin();
dsu.unify(p.id, id);
open[p.t ^ 1].erase({r, id});
}
if(sz(open[p.t ^ 1]) == 1) dsu.unify(p.id, open[p.t ^ 1].begin()->second);
}
}
cout<<dsu.num_comps()<<endl;
}
int main(){
fastio;
int t;
cin >> t;
while (t--) solve();
}
darkkcyan's solution without using sets in python.
from sys import stdin
def solve_case():
n = int(stdin.readline())
segs = [tuple(map(int, stdin.readline().split())) + (i, ) for i in range(n)]
segs.sort(key=lambda x: x[1])
par = [-1] * n
cnt_comp = n
def find_set(u):
p = u
while par[p] >= 0:
p = par[p]
while u != p:
t = par[u]
par[u] = p
u = t
return p
def join(u, v):
nonlocal cnt_comp
nonlocal par
u = find_set(u)
v = find_set(v)
if u == v:
return
if -par[u] < -par[v]:
u, v = v, u
par[u] += par[v]
par[v] = u
cnt_comp -= 1
hp = [[], []]
for col, l, r, id in segs:
for elm in hp[1 - col]:
if elm[0] < l:
continue
join(elm[1], id)
if len(hp[1 - col]):
hp[1 - col] = [max(hp[1 - col])]
hp[col].append((r, id))
return cnt_comp
for testcase in range(int(stdin.readline())):
print(solve_case())
TheScrasse's $$$nlog^3n$$$ solution for E using Boruvka and Mergesort tree :D
#include <bits/stdc++.h>
using namespace std;
#define nl "\n"
#define nf endl
#define ll int
#define pb push_back
#define _ << ' ' <<
#define tm gfewnignefgo
#define INF (int)1e9
#define mod 998244353
#define maxn 200010
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll c[maxn], l[maxn], r[maxn], pr[maxn], sz[maxn];
ll tm, df[maxn];
vector<ll> adj[maxn];
vector<array<ll, 2>> nd;
vector<array<ll, 3>> cm;
priority_queue<array<ll, 2>> fn[2][maxn];
ll find(ll x) {
if (x == pr[x]) return x;
return pr[x] = find(pr[x]);
}
bool same(ll a, ll b) {
return (find(a) == find(b));
}
void onion(ll a, ll b) {
a = find(a); b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
pr[b] = a; sz[a] += sz[b];
}
void upd(ll c, ll p, ll x, ll id) {
while (p < maxn) {
fn[c][p].push({x, id}); p += (p & (-p));
}
}
void nts(ll c, ll p, ll r, ll st) {
ll wn = -1;
for (; p > 0; p -= (p & (-p))) {
while (!fn[c][p].empty()) {
auto [rr, id] = fn[c][p].top();
if (!df[id]) {
fn[c][p].pop(); continue;
}
if (rr < r) break;
wn = id; break;
}
if (wn != -1) {
nd.pb({st, wn}); break;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#if !ONLINE_JUDGE && !EVAL
ifstream cin("input.txt");
ofstream cout("output.txt");
#endif
// today I'm overkilling everything
// tl;dr mst with boruvka and merge sort tree, O(n*log^3(n)), let's hope it gets ac
cin >> t;
while (t--) {
cin >> n;
for (i = 1; i <= 2 * n; i++) {
while (!fn[0][i].empty()) fn[0][i].pop();
while (!fn[1][i].empty()) fn[1][i].pop();
}
for (i = 1; i <= n; i++) {
cin >> c[i] >> l[i] >> r[i];
pr[i] = i; sz[i] = 1;
}
cm.clear(); cm.pb({-INF, 0, 0});
for (i = 1; i <= n; i++) {
cm.pb({l[i], i, 0}); cm.pb({r[i], i, 1});
}
sort(cm.begin(), cm.end());
for (i = 1; i <= 2 * n; i++) {
if (i == 1 || cm[i][0] != cm[i - 1][0]) k = i;
if (cm[i][2] == 0) l[cm[i][1]] = k;
else r[cm[i][1]] = k;
}
for (i = 1; i <= n; i++) {
upd(c[i], l[i], r[i], i); df[i] = true;
}
while (true) {
nd.clear();
for (i = 1; i <= n; i++) adj[i].clear();
for (i = 1; i <= n; i++) adj[find(i)].pb(i);
for (i = 1; i <= n; i++) {
for (auto u : adj[i]) df[u] = false;
for (auto u : adj[i]) nts(c[u] ^ 1, r[u], l[u], u);
for (auto u : adj[i]) {
df[u] = true; upd(c[u], l[u], r[u], u);
}
}
if (nd.empty()) break;
for (auto [a, b] : nd) onion(a, b);
}
res = 0;
for (i = 1; i <= n; i++) {
if (find(i) == i) res++;
}
cout << res << nl;
}
return 0;
}
1691F - K-Set Tree
Video Editorial
Idea: ltc.groverkss
Problem Setting: ltc.groverkss amul_agrawal rahulgoel
Editorial: rahulgoel
Video Editorial: rahulgoel
Can we root the tree and find the partial answer for a paticular root?
The counting problem for a fixed root can be solved using combinatorics.
Can we find the answer for other roots using the calculations involved in finding answer for a fixed root in Hint 1?
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
struct Comb {
vector<ll> fac;
vector<ll> invfac;
ll n;
Comb(ll n)
{
this->n = n;
fac.resize(n + 1, 0);
invfac.resize(n + 1, 0);
fac[0] = 1;
for (ll i = 1; i <= n; i++)
fac[i] = (fac[i - 1] * i) % MOD;
invfac[n] = power(fac[n], MOD - 2);
for (ll i = n - 1; i >= 0; i--)
invfac[i] = (invfac[i + 1] * (i + 1)) % MOD;
}
static ll power(ll x, ll y)
{
ll ret = 1;
while (y) {
if (y & 1)
ret = (ret * x) % MOD;
y >>= 1;
x = (x * x) % MOD;
}
return ret;
}
ll nCr(ll n, ll r)
{
if (n < 0 or r < 0 or n < r)
return 0;
ll ans = (fac[n] * ((invfac[r] * invfac[n - r]) % MOD)) % MOD;
return ans;
}
};
vector<vector<int> > adj;
vector<int> sz;
vector<ll> cnt;
vector<ll> cntsz;
Comb C(2e5 + 5);
ll cur_ans = 0;
ll ans = 0;
void dfs1(int v, int p, int k)
{
sz[v] = 1;
ll sub = 0;
for (int u : adj[v]) {
if (u != p) {
dfs1(u, v, k);
sz[v] += sz[u];
sub = (sub + C.nCr(sz[u], k)) % MOD;
}
}
cnt[v] = (C.nCr(sz[v], k) - sub + MOD) % MOD;
cntsz[v] = (cnt[v] * sz[v]) % MOD;
cur_ans = (cur_ans + cntsz[v]) % MOD;
}
void dfs2(int v, int p, int k)
{
ans = (ans + cur_ans) % MOD;
for (int u : adj[v]) {
if (u != p) {
// store
int store_v_sz = sz[v];
ll store_v_cnt = cnt[v];
ll store_v_cntsz = cntsz[v];
int store_u_sz = sz[u];
ll store_u_cnt = cnt[u];
ll store_u_cntsz = cntsz[u];
ll store_cur_ans = cur_ans;
// recalculate size[v], size[u]
sz[v] -= sz[u];
sz[u] = sz.size();
// recalculate cnt[v]
cnt[v] = (cnt[v] - C.nCr(store_v_sz, k) + MOD) % MOD;
cnt[v] = (cnt[v] + C.nCr(sz[v], k)) % MOD;
cnt[v] = (cnt[v] + C.nCr(store_u_sz, k)) % MOD;
// recalculate cnt[u]
cnt[u] = (cnt[u] - C.nCr(store_u_sz, k) + MOD) % MOD;
cnt[u] = (cnt[u] + C.nCr(sz[u], k)) % MOD;
cnt[u] = (cnt[u] - C.nCr(sz[v], k) + MOD) % MOD;
// recalculate cntsz
cntsz[v] = (cnt[v] * sz[v]) % MOD;
cntsz[u] = (cnt[u] * sz[u]) % MOD;
// recalculate cur_ans
cur_ans = (cur_ans - store_v_cntsz - store_u_cntsz + MOD + MOD) % MOD;
cur_ans = (cur_ans + cntsz[v] + cntsz[u]) % MOD;
dfs2(u, v, k);
// restore
sz[v] = store_v_sz;
cnt[v] = store_v_cnt;
cntsz[v] = store_v_cntsz;
sz[u] = store_u_sz;
cnt[u] = store_u_cnt;
cntsz[u] = store_u_cntsz;
cur_ans = store_cur_ans;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
adj.resize(n);
sz.resize(n);
cnt.resize(n);
cntsz.resize(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs1(0, 0, k);
dfs2(0, 0, k);
cout << ans << endl;
return 0;
}