Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
for t in range(int(input())):
n = int(input())
print(2 if n == 2 else (n & 1))
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
for t in range(int(input())):
print('NO' if len(set(input()) & set(input())) == 0 else 'YES')
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
fun calc(p: IntArray, len: Int, x: Int, a: Int, y: Int, b: Int): Long {
var ans = 0L
var (cX, cY, cXY) = listOf(0, 0, 0)
for (i in 1..len) {
if (i % a == 0 && i % b == 0) cXY++
else if (i % a == 0) cX++
else if (i % b == 0) cY++
}
for (i in 0 until cXY)
ans += p[i] * (x + y)
for (i in 0 until cX)
ans += p[cXY + i] * x
for (i in 0 until cY)
ans += p[cXY + cX + i] * y;
return ans
}
fun main() {
val q = readLine()!!.toInt()
for (ct in 1..q) {
val n = readLine()!!.toInt()
val p = readLine()!!.split(' ').map { it.toInt() / 100 }
.sortedDescending().toIntArray()
var (x, a) = readLine()!!.split(' ').map { it.toInt() }
var (y, b) = readLine()!!.split(' ').map { it.toInt() }
val k = readLine()!!.toLong()
if (x < y) {
x = y.also { y = x }
a = b.also { b = a }
}
var lf = 0; var rg = n + 1
while (rg - lf > 1) {
val mid = (lf + rg) / 2
if (calc(p, mid, x, a, y, b) >= k)
rg = mid
else
lf = mid
}
if (rg > n) rg = -1
println(rg)
}
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
const int INF = int(1e9) + 99;
int t, n;
int a[N];
int l[N], r[N];
int dp[N];
int main() {
scanf("%d", &t);
for(int tc = 0; tc < t; ++tc){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
l[i] = INF;
r[i] = -INF;
dp[i] = 0;
}
vector <int> v;
for(int i = 0; i < n; ++i){
scanf("%d", a + i);
--a[i];
v.push_back(a[i]);
l[a[i]] = min(l[a[i]], i);
r[a[i]] = max(r[a[i]], i);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int res = n;
for(int i = v.size() - 1; i >= 0; --i){
if(i + 1 == v.size() || r[v[i]] >= l[v[i + 1]]) dp[i] = 1;
else dp[i] = 1 + dp[i + 1];
res = min(res, int(v.size())- dp[i]);
}
printf("%d\n", res);
}
return 0;
}
```

Idea: Neon

**Tutorial**

Tutorial is loading...

**Solution (Ne0n25)**

```
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int N = 500 * 1000 + 13;
int n, k;
vector<pair<int, int>> g[N];
long long dp[N][2];
void calc(int v, int p = -1) {
long long cur = 0;
vector<long long> adds;
for (auto it : g[v]) {
int to = it.x;
int w = it.y;
if (to == p)
continue;
calc(to, v);
cur += dp[to][0];
adds.pb(dp[to][1] + w - dp[to][0]);
}
sort(all(adds), greater<long long>());
forn(i, min(sz(adds), k)) if (adds[i] > 0)
cur += adds[i];
dp[v][0] = dp[v][1] = cur;
if (k <= sz(adds) && adds[k - 1] > 0)
dp[v][1] -= adds[k - 1];
}
long long solve() {
scanf("%d%d", &n, &k);
forn(i, n) g[i].clear();
forn(i, n - 1) {
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
--x; --y;
g[x].pb(mp(y, w));
g[y].pb(mp(x, w));
}
calc(0);
return dp[0][0];
}
int main() {
int q;
scanf("%d", &q);
forn(i, q) printf("%lld\n", solve());
}
```

1223F - Stack Exterminable Arrays

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
int t, n;
int a[N];
int nxt[N];
int dp[N];
map<int, int> nxtX[N];
int main() {
scanf("%d", &t);
for(int tc = 0; tc < t; ++tc){
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d", a + i);
for(int i = 0; i < n + 2; ++i){
nxt[i] = -1;
nxtX[i].clear();
dp[i] = 0;
}
for(int i = n - 1; i >= 0; --i){
if(nxtX[i + 1].count(a[i])){
int pos = nxtX[i + 1][a[i]];
assert(pos < n && a[pos] == a[i]);
nxt[i] = pos;
swap(nxtX[i], nxtX[pos + 1]);
if(pos < n - 1)
nxtX[i][a[pos + 1]] = pos + 1;
}
nxtX[i][a[i]] = i;
}
long long res = 0;
for(int i = n - 1; i >= 0; --i){
if(nxt[i] == -1) continue;
dp[i] = 1 + dp[nxt[i] + 1];
res += dp[i];
}
printf("%lld\n", res);
}
return 0;
}
```

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
int n;
vector<int> a;
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
fore(i, 0, n)
cin >> a[i];
return true;
}
template<class A>
pair<A, A> upd(const pair<A, A> &mx, const A &val) {
return {max(mx.x, val), max(mx.y, min(mx.x, val))};
}
vector<int> cnt, sum;
vector<int> prv;
li getSum(int l, int r) {
return sum[r] - sum[l];
}
li ans, rx, ry;
void updAns(li x, li y) {
if (x < 2 || y < 2)
return;
if (ans >= x * y)
return;
ans = x * y;
rx = x, ry = y;
}
inline void solve() {
cnt.assign(*max_element(all(a)) + 1, 0);
fore(i, 0, n)
cnt[a[i]]++;
sum.assign(sz(cnt) + 1, 0);
fore(i, 0, sz(cnt))
sum[i + 1] = sum[i] + cnt[i];
prv.assign(sz(cnt), -1);
fore(i, 0, sz(prv)) {
if(i > 0)
prv[i] = prv[i - 1];
if(cnt[i] > 0)
prv[i] = i;
}
ans = 0;
fore(y, 2, sz(cnt)) {
li cntY = 0;
for(int i = 0; y * i < sz(cnt); i++)
cntY += i * 1ll * getSum(i * y, min((i + 1) * y, sz(cnt)));
pair<pt, pt> mx = {{-1, -1}, {-1, -1}};
int lf = (sz(cnt) - 1) / y * y, rg = sz(cnt);
while(lf >= 0) {
int cntMore = (mx.x.x >= 0) + (mx.y.x >= 0);
int val1 = prv[rg - 1];
if (val1 >= lf) {
mx = upd(mx, pt{val1 % y, val1});
if (cnt[val1] == 1)
val1 = prv[val1 - 1];
if (val1 >= lf)
mx = upd(mx, pt{val1 % y, val1});
}
if (mx.x.x >= 0) {
li x = (lf + mx.x.x) / 2;
li cur = cntY - lf / y;
updAns(min(cur, x), y);
}
if (mx.y.x >= 0) {
li x = lf + mx.y.x;
li cur = cntY - 2 * (lf / y);
updAns(min(cur, x), y);
if(cntMore + (mx.x.y < rg) >= 2) {
x = lf + mx.x.x;
cur--;
updAns(min(cur, x), y);
}
}
rg = lf;
lf -= y;
}
}
cout << ans << endl;
cerr << rx << " " << ry << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cerr << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution (arsijo)**

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 101;
const int MAX_M = 1001;
int n, m, k;
vector<pair<int, int> > v[MAX_N];
int w[MAX_N];
int a[MAX_M], b[MAX_M], c[MAX_M], color[MAX_M];
set<pair<int, int> > s[MAX_N], s2;
int deg[MAX_N][MAX_M];
inline pair<int, int> get_s2(int i){
return {s[i].begin()->first - s[i].rbegin()->first, i};
}
inline void change_edge_color(int edge, int d){
int pos1 = a[edge];
int pos2 = b[edge];
assert(s[pos1].find({deg[pos1][color[edge]], color[edge]}) != s[pos1].end());
s[pos1].erase({deg[pos1][color[edge]], color[edge]});
s[pos2].erase({deg[pos2][color[edge]], color[edge]});
deg[pos1][color[edge]] += d;
deg[pos2][color[edge]] += d;
s[pos1].insert({deg[pos1][color[edge]], color[edge]});
s[pos2].insert({deg[pos2][color[edge]], color[edge]});
}
inline void change_color(int edge, int col){
if (edge == 0 || edge > m || color[edge] == col)
return;
int pos1 = a[edge];
int pos2 = b[edge];
s2.erase(get_s2(pos1));
s2.erase(get_s2(pos2));
change_edge_color(edge, -1);
color[edge] = col;
change_edge_color(edge, 1);
s2.insert(get_s2(pos1));
s2.insert(get_s2(pos2));
}
vector<pair<int, int> > v2[MAX_N];
int deg2[MAX_N];
vector<int> vertices;
int used[MAX_N];
void dfs2(int pos){
used[pos] = 2;
for (auto e : v2[pos]){
if (used[e.first] != 2){
dfs2(e.first);
}
}
vertices.push_back(pos);
}
int _col[2];
set<int> used3;
int i;
vector<int> euler;
void dfs3(int pos, int prev = -1, int pr2 = 0){
while(!v2[pos].empty()){
int ind = v2[pos].back().second;
int to = v2[pos].back().first;
v2[pos].pop_back();
if (used3.find(ind) != used3.end()){
continue;
}
used3.insert(ind);
dfs3(to, ind, pos);
}
if (prev != -1){
euler.push_back(prev);
}
}
void stabilize_two_colors(const vector<int> &e, int col1, int col2){
assert(!e.empty());
v2[0].clear();
for (auto edge : e){
v2[a[edge]].clear();
v2[b[edge]].clear();
deg2[a[edge]] = 0;
deg2[b[edge]] = 0;
used[a[edge]] = 0;
used[b[edge]] = 0;
}
for (auto edge : e){
v2[a[edge]].push_back({b[edge], edge});
v2[b[edge]].push_back({a[edge], edge});
}
vertices.clear();
int u = m;
for (auto edge : e){
if (used[a[edge]] != 2){
int k = (int) vertices.size();
dfs2(a[edge]);
bool find = false;
for (int i = k; i < (int) vertices.size(); i++){
int v = vertices[i];
if (v2[v].size() % 2 == 1){
find = true;
++u;
v2[v].push_back({0, u});
v2[0].push_back({v, u});
}
}
if (!find){
int v = vertices[k];
for (int j = 0; j < 2; j++){
++u;
v2[v].push_back({0, u});
v2[0].push_back({v, u});
}
}
}
}
used3.clear();
euler.clear();
dfs3(0);
for (int a : euler){
change_color(a, col1);
swap(col1, col2);
}
}
void stabilize(const vector<int> &e){
s2.clear();
for (int i = 1; i <= n; i++){
s[i].clear();
for (int j = 1; j <= k; j++){
deg[i][j] = 0;
}
}
for (int edge : e){
deg[a[edge]][color[edge]]++;
deg[b[edge]][color[edge]]++;
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= k; j++){
s[i].insert({deg[i][j], j});
}
s2.insert(get_s2(i));
}
while(-s2.begin()->first > 2){
int ind = s2.begin()->second;
int col1 = s[ind].begin()->second;
int col2 = s[ind].rbegin()->second;
vector<int> e2;
for (int edge : e){
if (color[edge] == col1 || color[edge] == col2){
e2.push_back(edge);
}
}
stabilize_two_colors(e2, col1, col2);
}
}
void make_random(vector<int> e){
random_shuffle(e.begin(), e.end());
for (int i = 0; i < (int) e.size(); i++){
color[e[i]] = i % k + 1;
}
stabilize(e);
}
int change[MAX_N];
void build(vector<int> e){
if ((int) e.size() <= n * k){
make_random(e);
return;
}
random_shuffle(e.begin(), e.end());
vector<int> e1, e2;
int s = (int) e.size() / 2;
for (int i = 0; i < (int) e.size(); i++){
if (i < s){
e1.push_back(e[i]);
}else{
e2.push_back(e[i]);
}
}
build(e1);
build(e2);
vector<pair<int, int> > v1(k), v2(k);
for (int i = 1; i <= k; i++){
v1[i - 1].first = v2[i - 1].first = 0;
v1[i - 1].second = v2[i - 1].second = i;
}
for (int edge : e1){
v1[color[edge] - 1].first++;
}
for (int edge : e2){
v2[color[edge] - 1].first++;
}
sort(v1.rbegin(), v1.rend());
sort(v2.begin(), v2.end());
for (int i = 0; i < k; i++){
change[v1[i].second] = i + 1;
}
for (int edge : e1){
color[edge] = change[color[edge]];
}
for (int i = 0; i < k; i++){
change[v2[i].second] = i + 1;
}
for (int edge : e2){
color[edge] = change[color[edge]];
}
stabilize(e);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
srand(time(NULL));
#ifdef LOCAL
freopen("/Users/antontsypko/tsypko/input.txt", "r", stdin);
#endif
cin >> n >> m >> k;
for (int i = 1; i <= n; i++){
cin >> w[i];
}
ll sum = 0;
vector<int> e;
for (int i = 1; i <= m; i++){
cin >> a[i] >> b[i];
sum += w[a[i]] + w[b[i]];
e.push_back(i);
}
build(e);
for (int i = 1; i <= m; i++){
assert(color[i]);
cout << color[i] << endl;
}
}
```

My solution of F:

SpoilerWe add edges one by one.

That is E bro

We can build a bipartite graph with $$$2n$$$ vertexs.

Here,we build an edge connect $$$x$$$ and $$$y+n$$$ if there is a match with team $$$x$$$ and $$$y$$$,$$$(x<y)$$$.

we can try to find an edge coloring plan in the bipertite graph,which fix that for each vertex x,$$$\max a_{xi}-\min a_{xi} \leq 1$$$.Here $$$a_{xi}$$$ means the number of edges from x,which have color y.

If there exist plan,then it can be an answer.Because in the original graph,the absolute difference between $$$s_{xc_1},s_{xc_2}$$$ is smaller then two times of the absolute difference between $$$a_{xc_1},a_{xc_2}$$$.So the plan is avaliable.

There is already same problem on codeforces:Link,and it can be solved by using bipartite graph edge coloring or network-flow.

You can prove that your solution is correct by bi-coloring the graph. If you can't color (u,v) with A in the end, it means the bi-partite graph has an odd loop, which is obviously wrong.

Can someone explain the dp part in problem D a bit more clearly.

Here is my (very similar) approach, with identical DP part.

Let $$$X$$$ = input array, and let $$$Unique()$$$ be removing all duplicates and $$$Sorted()$$$ be sorting. Here are the key steps:

Non-DP part1) All numbers can be split in 3 groups: $$$A$$$ (ones that were moved to the beginning), $$$B$$$ (ones that were not moved at all), and $$$C$$$ (ones that were moved to the end). The resulting sequence in the end would then look like $$$Sorted(X)$$$ =

`(some permutation of A)(original order of B)(some permutation of C)`

2) In other words, some prefix of $$$Sorted(X)$$$ will contain all members of $$$A$$$, and some suffix of $$$Sorted(X)$$$ will contain all members of $$$C$$$. The rest in the middle will be equal to $$$B$$$. The answer would then be equal to $$$|Unique(A)| + |Unique(C)| = |Unique(X)| - |Unique(B)|$$$. So, we need to maximize the number of unique elements in $$$B$$$.

Formally, find the biggest sub-array of $$$Sorted(Unique(X))$$$ such that its elements stand in non-descending order in $$$X$$$.

DP-part3) First we iterate through $$$X$$$ and note the first and the last occurrence of each number ($$$X_i \le N$$$, so it is $$$O(N)$$$).

4) Then we iterate through $$$Sorted(Unique(S))$$$ and each time check: if the last occurrence of $$$i$$$-th element goes before the first occurrence of $$$i+1$$$-th element, we increment the length of current satisfying sub-array; otherwise we reset the length of current sub-array to 1.

Detailed explanationLet $$$dp[i]$$$ be the longest sub-array of $$$Sorted(Unique(S))$$$ ending at $$$i$$$-th element and satisfying aforementioned condition (its elements stand in non-descending order in X). Then, if the last occurrence of $$$i$$$-th element goes before the first occurrence of $$$i+1$$$-th element (meaning that the condition is satisfied for these two elements), $$$dp[i + 1] = dp[i] + 1$$$. Otherwise condition is not satisfied, meaning that the biggest such sub-array ending at $$$i+1$$$-th element is this element itself.

The answer would be then the maximum value of all $$$dp[i]$$$. In fact, you do not need to remember all DP values, just the last one and the maximum one.

Super-detailed explanationConsider

`X = (1 4 2 3 5 1 2 9 7)`

and`Sorted(Unique(S)) = (1 2 3 4 5 7 9)`

.Current sub-array size = 1 (1). Max sub-array size = 1 (1).

Do 1 and 2 stand in the ascending order in X? No (1 2 1 2). Reset current sub-array!

Current sub-array size = 1 (2). Max sub-array size = 1 (1).

Current sub-array size = 1 (2). Max sub-array size = 1 (1).

Do 2 and 3 stand in the ascending order in X? No (2 3 2). Reset current sub-array!

Current sub-array size = 1 (3). Max sub-array size = 1 (1).

Current sub-array size = 1 (3). Max sub-array size = 1 (1).

Do 3 and 4 stand in the ascending order in X? No (4 3). Reset current sub-array!

Current sub-array size = 1 (4). Max sub-array size = 1 (1).

Current sub-array size = 1 (4). Max sub-array size = 1 (1).

Do 4 and 5 stand in the ascending order in X? Yes (4 5). Update current sub-array!

Current sub-array size = 2 (4 5). Max sub-array size = 2 (4 5)

Current sub-array size = 2 (4 5). Max sub-array size = 2 (4 5).

Do 5 and 7 stand in the ascending order in X? Yes (5 7). Update current sub-array!

Current sub-array size = 3 (4 5 7). Max sub-array size = 3 (4 5 7).

Current sub-array size = 3 (4 5 7). Max sub-array size = 3 (4 5 7).

Do 7 and 9 stand in the ascending order in X? No (9 7). Reset current sub-array!

Current sub-array size = 1 (9). Max sub-array size = 3 (4 5 7)

Mega-detailed explanationCouldn't come up with.

The answer is $$$|Unique(S)| -$$$(size of the biggest found sub-array). 62057262

Thanks for the nice explanation .

comments like these help a lot while upsolving. thanks!

I had another solution, which is a bit slower and more complicated, but should pass TL. Actually we need to find something like LIS, but with two inserting cordinates.

Can you add the link to your solution.

it doesn't work, i've just checked (or bug maby)

In div 1 F, are these random solutions hackable? 62022214 62023134

What is the complexity of the model solution to F? Is it possible to prove that it has a reasonable time complexity, or is it just "No idea of the complexity, but it seems to work fast enough"

What is the time complexity of the model solution for F?

Or maybe I should have started by asking: why does this algorithm always terminate?

Let's calculate $$$P(coloring) = \sum_{v} \sum_{c} deg_{vc}^{2}$$$ where $$$deg_{vc}$$$ is number of edges of color $$$c$$$ incident to vertex $$$v$$$. One can see that $$$0 \le P(coloring) \le 2VE$$$ always holds, and this function strictly decreases after one transform (if something was bad in at least one vertex). Therefore, number of iterations is at most $$$2VE$$$, one iteration can be done in $$$O(V+E)$$$ time (finding euler cycle), and total complexity is $$$O(VE(V+E))$$$.

If you assign colors randomly in the beginning, then for vertex of degree $$$d$$$ expected value of P (restricted to that vertex) is $$$d+d(d-1)/k=d^{2}/k+d(1-1/k)$$$ while theoretical minimum is $$$k(d/k)^{2}=d^{2}/k$$$. So, expected number of iterations is $$$O(E)$$$.

Solved 1223F - Stack Exterminable Arrays in a more straightforward way in $$$\mathcal{O}(n \cdot log^2(n))$$$.

Let's use divide and conquer and count number of subarrays that are going through the middle of array. We can simulate process of elimination with stack for each suffix of left part and for each prefix of right part. We can notice that some left part matches with some right part if and only if they have the same stacks. We can use hashes to quickly compare stacks and use maps, hash-maps or merging sorted lists of hashes to count the result.

Not really optimized solution 62025172 works in $$$732 \; ms$$$.

If we know

`We can notice that some left part matches with some right part if and only if they have the same stacks.`

, we can just count the number of pairs of the same stacks by storing hashes in a map instead of doing divide-and-conquer. The complexity will be $$$O(n \log n)$$$In my solution I am building left and right parts from some middle point, that's why I actually need D&C to cover everything. But your solution just calculates all the stacks from the beginning and says that the answer is

$$$\sum_{distinct \; stacks} \binom{number \; of \; occurences}{2}$$$

That makes further observation that is "if we are at some position $$$l$$$ and we have added all elements from $$$a_{l \cdots r}$$$ and stack configuration did not change so $$$a_{l \cdots r}$$$ defines stack-exterminable subarray." So we can take any pair of positions with the same stack-from-beginning configuration as endpoints of correct stack-exterminable subarray. That is quite nice and simplifies things a lot. Thanks.

That's what I did too, but without hashes. Instead, I store the sequence of all stack states when adding elements to the left as a trie and to the right as a second trie. Then, I just find the tries' intersection (e.g. by basic DFS), count the number of states from the left part and from the right part corresponding to each vertex of this intersection and get the sum of their products. It's completely deterministic and with the same complexity when I store the edges from the tries in a

`map`

(using a hashmap instead actually slows down the program).it gave MLE if the memory wasn't freed for the nodes(of trie). My question is, do you'll always free memory for nodes after its use? Since it is done on the expense of time...

It's not at the expense of time unless you consider allocator/processor magic. For every

`malloc()`

, you need a corresponding`free()`

.Immediately cleaning up variables you don't need is a good thing for your memory (both computer and head).

Alternate approach for D. observations: which element will we choose if we were to perform only one left operation, we will definitely choose the smallest element. same way if we had only one right operation we will choose the largest element.

In general if we had x left operations we will choose the smallest x elements. Let us try to find out the minimum right operations needed if we could only perform L left operation. Let L be the number of left operations allowed and R be the number of right operations. We will find minimum of L + R where L will vary from 0 to N.

For 0 left operations(i.e. only right ops allowed), if there exists a number X in the array such that Y is a number greater than X but is to the left of X we need to move this Y to the right end and since we move this Y to the right end we need to move all elements larger than Y to the right end as well. Hence find smallest such Y and move all elements to the right end that are greater than equal to Y. We can find number of elements greater than equal to Y in logN time which will be required ops R.

Similarly for 1 left operation you may consider the same procedure only that the smallest element may be considered absent. for L left operations allowed consider 1st L smallest elements absent.

https://codeforces.com/contest/1223/submission/62028221

Hi all, my greedy idea for E was to simply sort the edges in non-increasing edge weight, then greedily take the largest edges as long as both of its vertices have enough in-degree to accept this edge. The intuition is similar to the greedy idea in Kruskal's MST algo. Can anyone poke a hole in this idea? I get WA on test case 3. (link to my code 62028517)

The answer for this should be 10 but your code outputs 6.

thanks!

In 1223F — Stack Exterminable Arrays, why $$$nxtX_{nxt_i + 1}$$$ will never be used again so that we can use swap?

I'm pretty sure it's provable that no 2 indices will have the same R value.

It's not like you could stop that anyway. Good luck distinguishing between $$$O(A\log^2 A)$$$ and $$$O(A\log A)$$$ where the extra factor is binsearch — you can't even use huge $$$A$$$ without requiring insane constant factors from optimal solutions too. I implemented that and my solution runs in half a second without trivial optimisations like "stop binsearch when it's clear you can't improve the answer".

So it was a strategically wise decision.

For 1223C/Div2C — Save the Nature, count(len) can be calculated in constant time by precalculating the prefix sum of sorted p. Then we don't need to do a binary search on the answer. This is my accepted solution https://codeforces.com/contest/1223/submission/62030690

Can anyone help me finding what's wrong in my code of Paint the Tree, https://codeforces.com/contest/1240/submission/62017811

It seems I was the only one who failed pretest 5, I did the same as mentioned in tutorial (just my notation is opposite, so dp[node][0] means node has taken atmost k-1 edges)

I take pair of child's dp[child][0] + edge , dp[child][1] , and sort them by (p.F — p.S) > (q.F-q.S)

then I iterate and take first k-1 pairs in both where x.F > x.S and one more for dp[cur][1],

If x.S >= x.F or i already took the required edges, i take x.S

in C++, comparators should return false when element are equal !!!

Woaah..!! It got accepted. I would never think that this can cause the problem. Can you please elaborate or give a link describing why it causes an error ??

I used to think that when elements are same, it doesnt matter if comparator gives true or false. (If two elements have same order, it wont matter which gets placed first

EDIT : Got it thanks for your help.

Please tell why it causes an error.

The compare function simply models a "less than" operator. Consider how the < operator works for primitive types like int:

int a = 1, b = 2; a < b == true a is less than b

int a = 2, b = 1; a < b == false a is not less than b, because a is greater than b

int a = 1, b = 1; a < b == false a is not less than b, because a equals b

Returning true means you want a to be ordered before b. So return false if that is not the case, either because you want b to be ordered before a, or because their order doesn't matter.

If you return true when the arguments are equal, then you are saying that you want a to come before b and you want b to come before a, which is a contradiction.

Copied from this link : https://stackoverflow.com/questions/45929474/why-must-stdsort-compare-function-return-false-when-arguments-are-equal

Still confused.

say a=b, and you return a<=b.

so I want a before b. (or b before a. it wont matter, right? since a=b)

what's the problem here?

so sorting process never ends

D is really nice.

Can anyone explain more this part of the editorial of problem D ?

"For each integer l we want to find the maximum index dpl=r such that we can sort sequence a without moving elements in range l…r. We can do it with dynamic programming.

Let's consider all integers occurring in sequence a in descending order s1,s2,…,st (si−1>si for each i from 2 to t). If maxInd(si)<minInd(si+1) then dpi=dpi+1+1, otherwise dpi=1."

Hello！ I would fain help you. (Sorry for my poor English.)

First of all, the size of the specific value is meaningless.

So we can reduce its value to $$$[1,t]$$$ and all the numbers in the $$$[1,t]$$$ appear at least once.

The answer is obviously constructed as follows ：

We can put $$$ l, l-1, l-2, ..., 1$$$ one by one at the beginning of the sequence at the cost of $$$1$$$.

After that , We should put $$$ r,r+1,r+2,...,t$$$ one by one at the end of the sequence at the cost of $$$1$$$.

If such a scheme is legal, then it must be guaranteed that the numbers in the middle are in order.

However, the time complexity of such an algorithm is $$$O(n^3)$$$

So, we can first determine the ordered interval in the middle, and then calculate the answers to the answers on both sides.

We can define $$$dp[i]$$$ for each i.

This means one of the biggest extensions length which let $$$ i-dp[i]+1 , i-dp[i]+2 ... i$$$ are ordered in the sequence.

To calculate $$$dp[i]$$$ , we should calculate MinInd[i] MaxInd[i] ($$$i \in [1,t]$$$) .

First of all , $$$ dp[1] = 1 $$$

if $$$ MinInd[i] > MaxInd[i-1]$$$ then $$$ dp[i] = dp[i-1]+1$$$ else $$$dp[i] = 1$$$

So , The answer is the minimum value of $$$t-dp[i]$$$ ($$$i \in [1,t]$$$)

Now, the time complexity of the algorithm is $$$O(n)$$$

My Code

what a beautiful solution !

It seems in problem D should be: "Let's consider all integers occurring in sequence a in descending order st,st-1,…,s1 (si+1>si for each i from t-1 to 1). If maxInd(si)<minInd(si+1) then dpi=dpi+1+1, otherwise dpi=1."

The editorial of problem Div2 D seems to have a mistake. You first call $$$dp_l$$$, the index $$$r$$$, s.t. we can sort the sequence without moving elements $$$[l .. r]$$$. But, in the recurrence, you have taken $$$dp_l$$$ to be the length of the sequence $$$[l .. r]$$$

Roms can you please correct it? It might be a difficulty for people who try to solve this problem later by reading the editorial

Fixed, thank you

For 1223C Solve the Nature, I am not satisfied with the fact that we need to check only if x>y.The terms a and b should also have a role.It can be that b is very small as compared to a.In that case even if x is smaller than y we would wish to allot greater ticket price to y% contributed tickets because they appear for every multiple of b which is very large as compared to a based on our assumption. I think in the solution suggested above it has been considered that a is smaller than b. Do correct me if i am wrong!

Well,

x>yory>x,a>b orb>a, all this stuff does matter only for easier implementation. I'll try to explain the main idea in pictures. I think it's easier to understand.Let's consider the particular case:

Data that we haveSo, let we already sold

ntickets. Than we gotmfor the Nature andmis the maximum value.How to find the

m?If our segment has

aandbblocks, than put the most expensive tickets there. After that, put the remaining tickets intoaifx>yorbifx<yand so on.Best distribution for fixed length, case(length = 7)Let function

cont(n) = mThe answer will be suchnthatcont(n) >= kandnis minimal. So we need to findcont(n)for everynin rangelen(tickets).In our case it's 7.

cont(n) from 0 to 7Well, in this case the answer will be 4, becuse

k=240andcont(3)=200,cont(4)=250.But we can notice that

cont(n)is monotonous, because asnrisescont(n)rises.That's why the array

[cont(1), cont(2), ... cont(len(tickets))]will be already sorted.And we want to find such element that will be

>=kand its index will be minimal, what is the best way to do it?Of course it's left binary search.

Thanks for the explanation!Now i get it.

Hi,

In problem E — Paint the Tree, I don't understand why I can use dp[v][k] since v and f can be up to 3 * 10^5. The solution of the Tutorial would be O(n * k), wouldn't?

Thank you, Rosklin

$$$f$$$ is boolean flag ($$$f \in \{0,1\}$$$). So, we have

`dp[n][2]`

, where`dp[x][0]`

is optimal painting of subtree $$$x$$$ not including edge to the parent,`dp[x][1]`

is optimal painting of subtree $$$x$$$ including edge to the parent.The editorial solution for D fails on this simple test.

Please change it.

Your test is incorrect. All $$$a_i$$$ must not exceed $$$n$$$.

sometimes i feel like a wet pile of crap

Here's my solution for D (lol, it took about an hour to figure this one out):

Firstly, in any legal sequence of operations all numbers moved to the

leftmust be less than all numbers moved to theright(otherwise the resulting array is not sorted).So let's fix a number

`k`

, such that all numbers moved to the left are less than or equal to`k`

, while all numbers moved to the right are greater than`k`

. Some numbers may not be moved at all, for example if part of our array is`3 1 4 2`

and we move all of them to the left, then we only need to move numbers`2`

and`3`

, in that order.First we calibrate the array such that all numbers used are consecutive integers. Another way would be to declare arrays

`prev`

and`next`

, and that's OK, since the numbers are relatively small.Now, let's say that we've fixed this

`k`

, and we need to decide how many numbers we need to move to the left so that the elements`1, 2, ..., k`

are sorted. It can be noticed that if there exists a sequence`k - c, ..., k - 1, k`

(in that order), we do not need to do any operations with those numbers, since they are already relatively sorted! So we only have to move numbers`1`

through`k - c - 1`

.To find the longest such sequence (which results in the

smallestnumber of elements that we need to move), we create an array`up`

.`up[i]`

— the length of the longest sequence of consecutive numbers (possibly, with intermediary ones) ending in`i`

(sorted in increasing order). We can do this with a linear pass through the array.So, given a fixed

`k`

, the number of elements we need to move to the left, given that elements 1 through`k`

must be sorted afterwards, is equal to`k - up[k]`

.We tackle the other case similarly.

`down[i]`

— the length of the longest sequence of consecutive numbers (again, sorted in increasing order)startingin`i`

. So, the number of elements we need to move to theright, given that elements`k + 1`

through`mark`

— the maximum number in the array must be sorted afterwards, is equal to`(mark - k) - down[k + 1]`

.For a given

`k`

, we sum those two values and receive the local answer. There's one catch, if there is an occurrence of`k`

laterthan an occurrence of`k + 1`

, we have to sort one of the pieces of the array entirely. We simply choose which one gives the minimum number of total operations.In this way, the answer is simply the minimum of local answers from 1 to

`mark - 1`

.By the way, it's only 80 lines of code in Java :)

Div1 D can also be solved by creating, for each $$$x \in [1,n]$$$ a random vector $$$b_i$$$ in 3D, setting $$$z_0$$$ to a random 3D point, and then setting $$$z_{i+1}$$$ to be the reflection of the point $$$z_i$$$ along the direction of $$$b_{a_i}$$$. Then a segment (0-indexed) $$$[l,r)$$$ of the array is stack exterminable iff $$$z_l = z_r$$$. Code

I laughed very hard when i read this:

You are an environmental activist at heart but the reality is harsh and you are just a cashier in a cinema.

Maybe i'm already dead inside.

update: got it.

I solved Div-2 D with two pointer + BIT. Maybe it was an overkill, but quite intuitive, cause we need to maximize the range of numbers with no inversions between themselves.

Brief explanationLet, inv = inversions between current two pointers. pos[i] = vector saving positions of all i in a. When shifting right pointer from r-1 to r, inv += bit.rangeSum(pos[r]+1,n). When shifting left pointer from l to l+1, inv -= bit.prefixSum(pos[l]-1)

My solution: 62025259

Can someone summarize Div2 E? I can't understand the statement.

Can anyone suggest more problems like D?

Hi all! How can I accelerate my code? I think my input is very slow 62119639

My code showing correct output but on submitting the results change .Am i doing something wrong while input or is it something else. P.S-I am new here:) My code to 'Save the nature' https://codeforces.com/contest/1241/submission/62256956

In Div1 D, instead of swapping the maps $$$nxtX_i$$$ and $$$nxtX_{nxt_i+1}$$$, it is also possible to move $$$nxtX_{nxt_i+1}$$$ to $$$nxtX_i$$$ using

`std::move`

in $$$O(1)$$$ time by doing`nxtX[i] = move(nxtX[nxt[i] + 1])`

.Hello,

In problem E (Paint The Tree) is there any benefit to using a DP array? I was able to solve it without one, in this submission https://codeforces.com/contest/1223/submission/62262784

D is very similar to AtCoder Grand Contest 24 — B: [](https://atcoder.jp/contests/agc024/tasks/agc024_b)

Hello,

Can anyone help me with 1223C? Here is my submission. What I'm doing:

`preSum`

Create a function

`check`

that takes $$$preSum,x,a,y,b$$$ and the number of tickets to sell $$$n$$$.Working of

`check`

: Find`an`

: number of tickets within`n`

that have the`x%`

scheme Similarly, find`bn`

for the`y%`

scheme.`cn`

for the tickets that have both the schemes applicable. Tickets with max values should be placed at positions which have both theschemes applicable. Their contribution would be the presum of first

`cn`

items * (x+y) Then assuming that allocating the higher tickets to ath positions will yield a better result, we can find (presum of $$$a_n$$$ items — presum of $$$c_n$$$ items) $$$\times (x)$$$ (as`cn`

items are already taken from`an`

). The rest is allocated to`bn`

by: (presum of $$$a_n+b_n-c_n$$$ items- presum of $$$a_n$$$ items) $$$\times y $$$ (as we only need $$$b_n-c_n$$$ items next to the already used $$$a_n$$$ items. Then doing the same assuming $$$b^{th}$$$ positions will yield better results as compared to the $$$a^{th}$$$ positions.The maximum of these two + $$$x+y$$$ contribution is returned.

$$$Finally$$$ a binary search is done over $$$[1,n]$$$. For the middle element, we use the

`check`

function, which yields the maximum sum for the middle element. If the sum is more than or equal to`k`

, then it is saved in the variable`ans`

. Once the search is complete,`ans`

is printed.I do not understand where am I going wrong in here. Any help is appreciated!

Div 2D and E are just amazing!

can anybody tell me C

C can be done in linear time using prefix sum https://codeforces.com/contest/1223/submission/81961631

Problem C can also be solved using number theory. So, (number theory) tag can be added to the problem

To anyone(from the future) who is looking for Problem D's solution, I have a much easier logic for this problem.

Hint 1: It is mentioned that in one operation we can take all occurences of a particular element and place it in beginning or the end. So does it really matter to actually do this operation?

Key observation: We can reduce the problem to a longest increasing subsequence problem ,and if we know the longest ascending subsequence we can just subtract it from distinct elements to get the answer. Note: here we will actually look for the just previous element while making the longest increasing subsequence .eg: lets say we have 2 3 4 in our array in some order ,so we while we are at 4 we will just take 3 into account for updating our ans .

After the above observation we can easily do this problem by using map data structure.

https://codeforces.com/contest/1241/submission/144912141