# 1691A - Beat The Odds

**Video Editorial****Idea:** amul_agrawal**Problem Setting:** menavlikar.rutvij JadeReaper rahulgoel amul_agrawal**Editorial**: menavlikar.rutvij rahulgoel**Video Editorial**: rahulgoel

**Hint 1**

Sum of two odd numbers is even and sum of two even numbers is also even.

**Hint 2**

If all consecutive pairs have even sum, can we generalize something about the sequence using the above hint?

**Solution**

**C++ Code**

```
#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

**Hint 1**

What happens to other people when a person receives a shoe greater his size?

**Hint 2**

What happens when a person has a unique shoe size?

**Solution**

**C++ Code**

```
#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

**Hint 1**

What is the contribution of each `1`

?

**Hint 2**

At what position would `1`

contribute less?

**Solution**

**C++ Code**

```
#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

**Hint 1**

If we have a list of subarrays where the element at index $$$i$$$ is the max, which subarrays should we check to be sufficient?

**Hint 2**

Checking subarrays which end or start at index $$$i$$$ is sufficient, so we can optimize our solution with this observation as the basis.

**Solution**

**C++ Code**

```
#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

**Hint 1**

We can iterate over the starting and ending points of all segments.

**Hint 2**

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?

**Hint 3**

For each group formed, it is enough to store the blue segment with maximum ending point, and red segment with maximum ending point.

**Solution**

**C++ Code**

#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.

**Python code**

```
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

**Code**

```
#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

**Hint 1**

Can we root the tree and find the partial answer for a paticular root?

**Hint 2**

The counting problem for a fixed root can be solved using combinatorics.

**Hint 3**

Can we find the answer for other roots using the calculations involved in finding answer for a fixed root in Hint 1?

**Solution**

**C++ Code**

```
#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;
}
```

It was a very nice contest.

PS: O(n) Solution for D

here's my python DP O(n) solution for D O(n) DP solution for D

An even more simple o(n) solution for D

Can you explain how this works? It looks much simpler than what i did. Also, how did you get this thought process.

hey your code is giving "yes" for the input 10 -6 1 1 -6 10 but answer for this case should be "no"

week testcases !!!!

Testers please look

I tried something like sliding window but seems the testcases are weak hence it passed.

yes many other participants also did similar thing and their submission is passed in system testing.

I also saw some submissions with O(n*n) complexity, but still accepted very weak test cases.

It gives WA when using this algo

My friends solution for D O(N), a <= the input array prefix_a <= prefix sum a[0] + ... + a[i] = prefix_a[i]

a_ngt <= next greater value pre_ngt <= next greater value

now for i in 0 to n-1,

if pre_ngt[i] < a_ngt[i] return false;

why because for subarray starting at index i and ending at pre_ngt[i], will have max value a[i] and a[i+1] + ... a[pre_ngt[i]] >0, since pre_ngt[i] is the index where prefix_a[ ngt] > prefix[i].

Then just reverse the main array A and apply the same check. You can check his implementation over 159050281.

awesome

Explaination about the solution using next element max index

https://codeforces.com/contest/1691/submission/159050281

To check, we try to find if there exists a subarray l..r so that max(l..r) < sum(l..r)

Let i is the index of maximum value in the subarray

sum(l..r) = sum(l..i-1) + arr[i] + sum(i+1..r) > arr[i] <=> sum(l..i-1) + sum(i+1..r) > 0

So for each index i, we check if there exists index r>i so that max(i+1..r) <= arr[i] and sum(i+1..r) > 0, then reverse the array and do the same

For each index i, to find r so that max(i+1..r) <= arr[i], we use next element max index. If next element max index of i is j, then all element from i+1..j-1 <= arr[i]

sum(1+1..r) > 0 <=> sum(0..r) — sum(0..i) > 0 <=> sum(0..r) > sum(0..i), so we use next element max index on the prefix sum. If next element max index of the prefix sum at i is r then sum(i+1..r) > 0

If r<j, there exists a subarray not satisfying the constraint.

What F*ckhead created problem C ?

First of all, that language is not ok in a public forum. Secondly, accounts of setters are given with each problem.

says the guy who only solves A and B in contests (NO OFFENCE)

A very smart guy.

I was really panicking when I saw no error in my C, but just after the contest I saw the test case finally and I mishandled the case with only single '1'. Really such problems test our patience, but you can use it to improve your temperament.

I think problem E can be solved using segment tree, is that right?

Yes

Yes, the thing you can do is pretty similar to my solution. If two segments

`[l1; r1]`

,`[l2; r2]`

do intersect, it means that either:`l2 <= l1 <= r2`

`l2 <= r1 <= r2`

`l1 <= l2 <= r2 <= r1`

Lets forget about the third case for a moment. We take, for example, red segments. Then we make two arrays. One of them stores right ends of red segments. Another one stores left ends. We sort the arrays.

Then we iterate through blue segments

`[l; r]`

and for each we find all the right ends`l <= r1 <= r`

and all the left ends`l <= l1 <= r`

. It's obvious that all the l1s make a continuous segment in left ends array. The same thing works for the right ends. That means that we can find the smallest`l1`

(`r1`

) and the greatest one. Then we want to unite all the segments between them and the blue segment we are looking at. Using the seg tree, we will mark whether the segment should be united with the previous one in left (right) ends order.Back for the third case, it's obvious that

`l1 <= l2 <= r2 <= r1`

also means that`l1 <= l2 <= r1`

. So to count all the intersections from the third case, you basically just need to use the solution above two times with different colors.P.S. The part with the seg tree can be done easily without it. Our task is to add on some segments and then find the modified array. There is a nice trick to do it. We will count difference array

`d[]`

. To increase by x on segment`[l; r]`

, we need to add`x`

to`d[l]`

and substract`x`

from`d[r + 1]`

. Then, after we applied all the operations, to get the modified array we simply need to calc prefix sums on this array.My solution:159060471

The same idea came to my mind during the contest, unfortunately, time wasn't on my side.

Thank you so much for the explanation.

i m not getting how to use segment tree here could u please explain how are u planning to implement

You basically need to mark that you need to add an edge between

`i`

th and`(i-1)`

th vertex for each`i`

between`l`

and`r`

. That means you want to set value`1`

on some segment, you can do this using mass segment tree.With video editorials and hints for each problem. You cannot argue that these are not one of the best editorials to be seen in a while on CF.

D admits an O(n) solution. It is sufficient to check that the sums of the subarrays between any positive integer and the next/previous greater (or equal) integer, are negative and greater in absolute value than the positive integer itself. If this holds for all positive integers, then we return yes.

Intuitively this makes sure that no positive integer can contribute positively to some other positive integer which is greater than it.

word

Hi, i think i have done something similar. don't know whats wrong https://codeforces.com/contest/1691/submission/159059179

I try to prove your solution. (edit: earlier proof was wrong)

Suppose a subarray which violate the condition be $$$a[i:k]$$$ and let the index of maximum element in this subarray $$$i$$$. Also let us say wlog, that the subarray extends towards the right, ie, $$$[a_i, a_{i+1}, ... a_{k}]$$$. Let us say that the element just smaller than $$$a_i$$$ be at index $$$j$$$ in this subarray.

$$$[a_i, \color{red}{ a_{i+1}, a_{i+2} ... }, \color{turquoise}{ a_j,} \color{blue} {a_{j+1}, a_{j+2}...a_{k}}]$$$

If the sum of blue subarray, ie, $$$a[j+1:k]$$$ is positive, then, we find new subarray which violates the condition to be $$$a[j:k]$$$ of the same structure as $$$a[i:k]$$$ and repeat the process on this subarray

Otherwise if sum of $$$a[j+1: k]$$$ is not positive, then we safely discard this subarray, and here we end up with $$$a[i:j]$$$ as violating subarray, which we check in your solution. (because if $$$a[i+1:k]$$$ is positive and $$$a[j+1:k]$$$ is non positive then $$$a[i+1:j]$$$ is positive)

it it correct or there is some flaw

The way I verified it myself before writing it was very similar; I also tried to demonstrate that you can safely chop off the sides and condense the violating subarray to one which is sandwiched between these two particular elements.

I think it is sound.

That's wrong proof bro. You are saying if sum of blue array will be positive then you'll have a smaller subarray violating this condition. You're totally wrong here.

Case: 2, -1, 1, -1, 2

[0,4] is the smallest one. [2,4] has sum > 0 but it is not the smallest.

blue subarray was just to the right of second smallest element, in this case it would be empty.

Earlier proof was wrong but this was not the issue, please check now

How do you find the "nearest" greater element than $$$a_i$$$ for each $$$i$$$ in linear time?

Its a very famous stack problem bro. https://youtu.be/NXOOYYwpbg4

10 -4 3 -4 10 should be "NO" and your solution will give "YES" if I understand correctly

Edited my comment to say we search for nearest greater than or equal integer, not strictly greater. Doing that, between 10 and 10 we have-4+3-4 is not less than -10, hence allowing the 10 to connect with the other 10 positively, violating the condition and giving us a NO.

can the person who added the

`binary search`

tag forD, share his approach?I think, in segment tree you use some kind of binary search, and intended solution for D uses segment trees :)

You can find closest greater on right/left using the binary search and some data structure like segment tree or sparse table.

It was nice round! I really liked problem D, I hope to see more similar problems in future rounds :)

The best way of editorial. Loved it!

If you are/were getting a

WA/REverdict on problems from this contest, you can get thesmallestpossiblecounter examplefor your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

Can you please help me in finding where I am wrong for Problem D, I checked on cfstress but its not finding any test cases. Please help.

Solution link : 159144970

Thank you in advance

Sure, take a look at Ticket 9649 for a simple counter example.

Thanks a lot

Can you please help me find where I am wrong in problem D 159462704. Thank you

Sure, take a look at Ticket 10434 which contains an array of length 3 with all negative numbers. Naturally it'd satisfy the conditions, but your code prints NO.

Thank you very much

here's my python DP O(n) solution for D O(n) DP solution for D

Explain please

HI boys Can anyone explain why am I getting a Runtime Error here 159082911

For n == 1 you're not taking the input array (a single element) which is becoming n for next inputs which is causing RTE.

In problem c I didn't get how all middle ones contribute to 11?? Can anyone help with this

Ohh i think si-1.si -->Di-1 si.si+1 -->Di

[Si-1*10 + (Si ]+ [ 10*Si) + Si+1] --> Si-1*10 + Si+1 + Si(11) Total contribution is 11 Got it

great contest and solutions too!!

x

Sorry but your solution is hacked.

D was doable with a classic algorithm called cses. So you maintain a segtree which returns the maximum subarray sum of the entire array. You insert the values in in increasing order of

`arr[i]`

. At every stage, if the maximum subarray sum is > the value inserted, the answer is NO, otherwise it is YES. Let's say the current value inserted is x. Since the values are inserted in increasing order, the maximum value in the entire array cannot exceed x, so the maximum subarray sum will be greater than any possible "max value of a subarray" if it is greater than x.Can anyone tell the time complexity of this code? That code seems to be O(n^2), but this code got accepted in problem D . Please check. Submission link: https://codeforces.com/contest/1691/submission/159084501

The tests in problem D are weak. Actually for the worst case it works in O(n^2) and it is hacked now.

What is the

1213thcase in the7thtest of D? I am getting WA. Here is my submission.I will be really obliged if someone finds the error. Thanks in advance.

Failing testcase: Ticket 9078Thanks a lot.

I am getting a run time error on my submission can anyone chech why that is https://codeforces.com/contest/1691/submission/159039369 thanks in advance!!

Here's a testcase on which your code gets WA: Ticket 9111. Not sure if it contains the reason for RE as well, but it should be a good starting point.

Really liked the editorial with hints, and video solutions make this editorial to next level. Thanks for such a great editorial

There is another solution of F. It is simiral to editorial, but a bit shorter. We can fix a root of the sub-tree $$$v$$$, then for each edge $$$e$$$ between $$$v$$$ and $$$u$$$ let's calculate

$$$\sum\limits_{R \in subtree_u} \sum\limits_{S \subseteq V, |S| = k}f(R, S) = (cnt(v) - {size_u \choose k}) * (n - size_u) * size_u$$$

where $$$subtree_u$$$ — vertexes if the sub-tree of $$$u$$$ if $$$v$$$ is the root of the tree, and $$$w$$$ is connected to $$$v$$$. $$$size_u$$$ is a number of roots of the tree, $$$n - size_u$$$ is size of the sub-tree, $$$cnt(v) - {size_u \choose k}$$$ is a number of subsets of size $$$k$$$ such that sub-tree of $$$v$$$ is the minimum-size sub-tree covering it entirely and $$$R \in subtree_u$$$

`The remaining 1s can stay where they are as they will anyways be contributing a value of 10 no matter which position they take.`

There should be 11 instead of 10 in the above sentence.

Thanks! The editorial is fixed. Please wait a little bit for it to reload.

Isn't Hint 2 of problem D Editorial of no use at all?

Thanks for the fast editorial as well as making this round, enjoyed it a lot!!!

where are video editorials?

Their links are under the title of each problem.

Video link is not there .. can you give here please

Click

`Video Editorial`

letters.Or link.

thanks bro

I do not get it, is there some more hidden edgecase in C?

Why my 159111480 fails?

for this test case your code is failing

test case :1

6 2

001000

answer is 10 but your code is giving 11 which we will get by shifting 1 to leftmost point

tnx

Problem D can be solved in $$$O(n)$$$ operations, in a quite straight-forward manner with a monotonic stack, without any special consideration for positive/negative values, etc: 159111942.

similar with mine. I stored maximum range sum on the left and right side of each i with monotonic stack, and check if it is larger than 0. 159026276

can you explain what are elements in vllc vector deontes , or the approach

A solution for problem E using only vectors:

First, consider the segments that are completely inside another segment of the same color. Let's call these "islands".

If an island intersects with any segment of the other color, we can completely ignore it — because any connection chain involving the island can use the bigger segment instead. If the island does NOT intersect with any segment of the other color, then it is its own connected component — so it contributes 1 to the answer but can otherwise be ignored.

Processing the islands can be done with sorting and the two-pointer technique (or binary search).

Now, for the rest of the segments. Sort the segments of each color separately (note: since we got rid of the islands, sorting by left endpoint is the same as sorting by right). Now, go left to right, keeping track of the rightmost point reached with each color. If it's possible to intersect the next interval of either color with this point, do so. Otherwise add 1 to the result.

Clever idea! For ones for whom it is a bit subtle how to check island intersections with two pointers, you can sort out all islands in one array and non-islands in the other. Then take islands and non-islands of different colors, sort islands increasing right-end and non-islands increasing left ends. Then processing current island $$$I_c$$$ you may take the most-right non-island $$$NI_c$$$ starting before (or at) the current island right border. Checking that right border of $$$NI_c$$$ is inside $$$I_c$$$ answers whether there is any intersection. The subtleness here is that should we have sorted islands increasing left-ends the check would not have worked. Example islands [1...5], [2...3] and non-island [4...6]. We see [1...5] intersects with [4...6], but then standing in [2...3] we've already moved our non-island pointer too far and now it starts after [2...3] end.

Wrong answer in 4957th token, what's the testcase? 159113795

Don't know about that testcase but this your solution will fail on many testcases.

Example1

5

2 -1 1 -1 2

Answer should be "NO" but your code will output "YES"

damn, thx bro

Someone, please tell me why I am getting TLE on B My Solution on test case 30. I think it is just O(n).

For E we can also run dfs and extract edges using segtree/merge sort tree.

For problem B, can anyone tell me why I am getting TLE on this 159020121 when I submit using GNU G++ 17 7.3.0 but the same solution gets accepted when I submit using GNU G++ 14 6.4.0 (159121654)

In problem 1691E — Number of Groups, I implement using the way as editorial did

Why is the set solution getting WA while the vector solution getting AC where I used the same custom comparator in both submissions?

You first solution using set is failing on the following test case: CF Stress

it isn't enjoyable ..XD

the wrong answer expected NO, found YES [4957th token]can someone tell me/(give any tc) where it's failing? 159139893

Your code is failing on the following test case: Ticket 9678

Here is my O(n log n) solution, but it's much shorter and simplier to understand than in editorial. The main idea is that we iterate through elements in increasing order, then we should look for the segment that has the maximum possible sum and contains our element as maximum. How do we do that? Let's mark elements in the array if we have already looked at them. Also let's store segments of continious marked elements. In these segments we will store sum, starting and ending point of segment, maximum prefix sum and maximum suffix sum (it can be zero). For simplicity we will store segments in array. If we have array

`[l, r]`

we will store it only in`a[l]`

and`a[r]`

. Imagine we have element`x`

in position`i`

, then we should look for the segments which are stored at`a[i - 1]`

and`a[i + 1]`

(if it is possible and they are marked). Then we count maximum sum, it is`(i ? a[i - 1].suf : 0) + x + (i + 1 < n ? a[i + 1].pref : 0)`

, if it's greater than x, then answer is`NO`

. Then we update sum, pref, suf and store new segment in`a[a[i - 1].start]`

and`a[a[i + 1].end]]`

. Here is code 159141199.PS: sorry for bad english)

Why in F you asked for answer for only one k, and not sum over all? Solution doesn't change I think but implementation becomes easier a bit

Thanks

In the problem B the solution is not correct ! The corner test case :

INPUT.TXT 1 4 2 1 2 1

OUPUT.TXT 3 4 1 2

But the result of the tutorial solution is -1

According to the constraint, s[i] <= s[i + 1].

Oh, sorry, sorry ! I didn't see that .

Remove you eye patch for better clarity

Thanks , bro !

Can we do problem E with dfs? I have tried but I'm not understanding what is wrong.

I have separately sorted red and blue according to 1) start points, 2) end points.

And then found the range of other color which will lie within the same color range. and visited the segments using DFS. I have considered the dfs as bipartite graph.

codeAnyone, pls help

How weak are tests in D? My check was that no two adjacent elements are positive, and then run a kadane's starting from indices [0, 20). That passed XD

I was thinking it's some randomized argument but I can't prove it. Someone please hack me and put me out of my misery

Alternate solution for E using segment tree and coordinate compression:

https://codeforces.com/contest/1691/submission/198382960

Why am I getting WA on C? My idea is same as the one mentioned it the tutorial. Submission: 198856079.

Spoilervariety-jones?

Well, why are you pinging me? You can as well purchase a subscription if you need instant help. Or better, improve your debugging skills.

Take a look at Ticket 16774 from

CF Stressfor a counter example.