awoo's blog

Educational Codeforces Round 92 Editorial
By awoo, history, 7 months ago, translation, In English

1389A - LCM Problem

Idea: BledDest

Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
    l, r = map(int, input().split())
    if l * 2 > r:
        print(-1, -1)
    else:
        print(l, l * 2)

1389B - Array Walk

Idea: Roms

Tutorial
Tutorial is loading...
Solution 1 (pikmike)
for _ in range(int(input())):
	n, k, z = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 0
	s = 0
	mx = 0
	for t in range(z + 1):
		pos = k - 2 * t
		if pos < 0:
			continue
		mx = 0
		s = 0
		for i in range(pos + 1):
			if i < n - 1:
				mx = max(mx, a[i] + a[i + 1])
			s += a[i]
		ans = max(ans, s + mx * t)
	print(ans)
Solution 2 (pikmike)
for _ in range(int(input())):
	n, k, z = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 0
	s = 0
	mx = 0
	for i in range(k + 1):
		if i < n - 1:
			mx = max(mx, a[i] + a[i + 1])
		s += a[i]
		if i % 2 == k % 2:
			tmp = (k - i) // 2
			if tmp <= z:
				ans = max(ans, s + mx * tmp)
	print(ans)

1389C - Good String

Idea: BledDest

Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>

using namespace std;

#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)

int solve(const string& s, int x, int y) {
	int res = 0;
	for (auto c : s) if (c - '0' == x) {
		++res;
		swap(x, y);
	}
	if (x != y && res % 2 == 1)
		--res;
	return res;
}

void solve() {
	string s;
	cin >> s;
	int ans = 0;
	forn(x, 10) forn(y, 10)
		ans = max(ans, solve(s, x, y));
	cout << sz(s) - ans << endl;
}

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

1389D - Segment Intersections

Idea: adedalic

Tutorial
Tutorial is loading...
Solution (adedalic)
import kotlin.math.*

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(' ').map { it.toLong() }
        val (l1, r1) = readLine()!!.split(' ').map { it.toLong() }
        val (l2, r2) = readLine()!!.split(' ').map { it.toLong() }

        var ans = 1e18.toLong()
        if (max(l1, l2) <= min(r1, r2)) {
            val rem = max(0L, k - n * (min(r1, r2) - max(l1, l2)))
            val maxPossible = n * (abs(l1 - l2) + abs(r1 - r2))
            ans = min(rem, maxPossible) + max(0L, rem - maxPossible) * 2
        } else {
            val invest = max(l1, l2) - min(r1, r2)
            for (cntInv in 1..n) {
                var curAns = invest * cntInv
                val maxPossible = (max(r1, r2) - min(l1, l2)) * cntInv
                curAns += min(k, maxPossible) + max(0L, k - maxPossible) * 2
                ans = min(ans, curAns)
            }
        }
        println(ans)
    }
}

1389E - Calendar Ambiguity

Idea: BledDest

Tutorial
Tutorial is loading...
Solution (pikmike)
fun gcd(a: Long, b: Long): Long {
	if (a == 0L) return b
	return gcd(b % a, a)
}

fun main() {
	repeat(readLine()!!.toInt()) {
		val (m, d, w) = readLine()!!.split(' ').map { it.toLong() }
		val w2 = w / gcd(d - 1, w)
		val mn = minOf(m, d)
		var cnt = mn / w2
		println((2 * (mn - w2) - w2 * (cnt - 1)) * cnt / 2)
	}
}

1389F - Bicolored Segments

Idea: Roms

Tutorial
Tutorial is loading...
Solution 1 (Ne0n25)
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)

typedef pair<int, int> pt;

const int N = 200 * 1000;

int n;
int l[N], r[N], t[N];
set<pt> st[2];

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d%d%d", &l[i], &r[i], &t[i]), --t[i];
	
	vector<pair<int, pt>> ev;
	forn(i, n) {
		ev.pb(mp(l[i], mp(0, i)));
		ev.pb(mp(r[i], mp(1, i)));
	}

	sort(all(ev));
	
	int ans = 0;
	for (auto it : ev) {
		int i = it.y.y;
		if (it.y.x) {
			int j = t[i];
			int k = j ^ 1;
			if (st[j].count(mp(r[i], i)) && !st[k].empty()) {
				++ans;
				st[k].erase(st[k].begin());
			}
			if (st[j].count(mp(r[i], i))) st[t[i]].erase(mp(r[i], i));
		} else {
			st[t[i]].insert(mp(r[i], i));
		}
	}
	
	printf("%d\n", n - ans);
}
Solution 2 (Ne0n25)
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define mp make_pair
#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)

typedef pair<int, int> pt;

const int INF = 1e9;
const int N = 200 * 1000;

int n;
vector<pt> a[2];

struct segtree {
	int n;
	vector<int> t, ps;
	segtree(int n) : n(n) {
		t.resize(4 * n, -INF);
		ps.resize(4 * n, 0);
	}
	
	void push(int v, int l, int r) {
		if (l + 1 != r) {
			ps[v * 2 + 1] += ps[v];
			ps[v * 2 + 2] += ps[v];
		}
		t[v] += ps[v];
		ps[v] = 0;
	}
	
	void upd(int v, int l, int r, int pos, int val) {
		push(v, l, r);
		if (l + 1 == r) {
			t[v] = val;
			return;
		}
		int m = (l + r) >> 1;
		if (pos < m) upd(v * 2 + 1, l, m, pos, val);
		else upd(v * 2 + 2, m, r, pos, val);
		t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
	}
	
	void add(int v, int l, int r, int L, int R, int val) {
		push(v, l, r);
		if (L >= R) return;
		if (l == L && r == R) {
			ps[v] += val;
			push(v, l, r);
			return;
		}
		int m = (l + r) >> 1;
		add(v * 2 + 1, l, m, L, min(m, R), val);
		add(v * 2 + 2, m, r, max(m, L), R, val);
		t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
	}
	
	int get(int v, int l, int r, int L, int R) {
		push(v, l, r);
		if (L >= R) return -INF;
		if (l == L && r == R) 
			return t[v];
		int m = (l + r) >> 1;
		int r1 = get(v * 2 + 1, l, m, L, min(m, R));
		int r2 = get(v * 2 + 2, m, r, max(m, L), R);
		t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
		return max(r1, r2);
	}
	
	void upd(int pos, int val) {
		return upd(0, 0, n, pos, val);
	}
	
	void add(int l, int r, int val) {
		return add(0, 0, n, l, r, val);
	}
	
	int get(int l, int r) {
		return get(0, 0, n, l, r);
	}
};

int main() {
	scanf("%d", &n);
	forn(i, n) {
		int l, r, t;
		scanf("%d%d%d", &l, &r, &t);
		a[t - 1].pb(mp(r, l));
	}
	
	forn(i, 2) sort(all(a[i]), [](pt a, pt b) {
		if (a.x == b.x) return a.y > b.y;
		return a.x < b.x;
	});
	
	segtree t1(sz(a[0]) + 1), t2(sz(a[1]) + 1);
	t1.upd(0, 0);
	t2.upd(0, 0);
		
	int ans = 0;
	for (int i = 0, j = 0; i + j < n; ) {
		if (i < sz(a[0]) && (j == sz(a[1]) || a[0][i].x <= a[1][j].x)) {
			int pos = upper_bound(all(a[1]), mp(a[0][i].y, -INF)) - a[1].begin() + 1; 
			int cur = t2.get(0, pos) + 1;
			ans = max(ans, cur);
			t1.upd(i + 1, cur);
			t2.add(0, pos, 1);
			++i;
		} else {
			int pos = upper_bound(all(a[0]), mp(a[1][j].y, -INF)) - a[0].begin() + 1; 
			int cur = t1.get(0, pos) + 1;
			ans = max(ans, cur);
			t2.upd(j + 1, cur);
			t1.add(0, pos, 1);
			++j;
		}
	}
	
	printf("%d\n", ans);
}

1389G - Directing Edges

Idea: BledDest

Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>

using namespace std;

typedef long long li;

const int N = 300043;

bool is_bridge[N];
int w[N];
int c[N];
int v[N];
vector<pair<int, int> > g[N];

vector<pair<int, int> > g2[N];
int comp[N];
li sum[N];
li dp[N];
int cnt[N];
int fup[N];
int tin[N];
int T = 0;
li ans[N];
int v1[N], v2[N];

int n, m, k;

int dfs1(int x, int e)
{
	tin[x] = T++;
	fup[x] = tin[x];
	for(auto p : g[x])
	{
		int y = p.first;
		int i = p.second;
		if(i == e)
			continue;
		if(tin[y] != -1)
			fup[x] = min(fup[x], tin[y]);
		else
		{
			fup[x] = min(fup[x], dfs1(y, i));
			if(fup[y] > tin[x])
				is_bridge[i] = true;
		}
	}
	return fup[x];
}

void dfs2(int x, int cc)
{
	if(comp[x] != -1)
		return;
	comp[x] = cc;
	cnt[cc] += v[x];
	sum[cc] += c[x];
	for(auto y : g[x])
		if(!is_bridge[y.second])
			dfs2(y.first, cc);
}

void process_edge(int x, int y, int m, int weight)
{
	li add_dp = dp[y];
	if(cnt[y] > 0 && cnt[y] < k)
		add_dp = max(0ll, add_dp - weight);
	
	cnt[x] += m * cnt[y];
	dp[x] += m * add_dp;
}

void link(int x, int y, int weight)
{
	process_edge(x, y, 1, weight);
}

void cut(int x, int y, int weight)
{
	process_edge(x, y, -1, weight);
}

void dfs3(int x, int p)
{
    dp[x] = sum[x];
	for(auto e : g2[x])
	{
		int i = e.second;
		int y = e.first;
		if(y == p)
			continue;
		dfs3(y, x);
		link(x, y, w[i]);
	}
}

void dfs4(int x, int p)
{
	ans[x] = dp[x];
	for(auto e : g2[x])
	{
		int i = e.second;
		int y = e.first;
		if(y == p)
			continue;
		cut(x, y, w[i]);
		link(y, x, w[i]);
		dfs4(y, x);
		cut(y, x, w[i]);
		link(x, y, w[i]);
	}
}

int main()
{
	scanf("%d %d %d", &n, &m, &k);
	for(int  i = 0; i < k; i++)
	{
		int x;
		scanf("%d", &x);
		--x;
		v[x] = 1;
	}
	for(int i = 0; i < n; i++)
		scanf("%d", &c[i]);
	for(int i = 0; i < m; i++)
		scanf("%d", &w[i]);
	for(int i = 0; i < m; i++)
	{
		scanf("%d %d", &v1[i], &v2[i]);
		--v1[i];
		--v2[i];
		g[v1[i]].push_back(make_pair(v2[i], i));
		g[v2[i]].push_back(make_pair(v1[i], i));
	}
	
	for(int i = 0; i < n; i++)
	{
		tin[i] = -1;
		comp[i] = -1;
	}
	dfs1(0, -1);
	int cc = 0;
	for(int i = 0; i < n; i++)
		if(comp[i] == -1)
			dfs2(i, cc++);
	for(int i = 0; i < m; i++)
		if(is_bridge[i])
		{
			g2[comp[v1[i]]].push_back(make_pair(comp[v2[i]], i));
			g2[comp[v2[i]]].push_back(make_pair(comp[v1[i]], i));
		}
	dfs3(0, 0);
	dfs4(0, 0);
	for(int i = 0; i < n; i++)
		printf("%lld ", ans[comp[i]]);
	puts("");
}
 
 
 
 
  • Vote: I like it
  • +127
  • Vote: I do not like it

Comments Comments (98)
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Super Fast!!

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it +45 Vote: I do not like it

    Day by day I feel like nobody is getting the humor anymore they are just downvoting every comment.

    → Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In the Tutorial of Problem E: I think you mean yd + x instead of xd + y as the index of the x-day of the y-month in the year.

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    xd+y means index y-th day of x-th month which is corresponding pair of x-th day of y-th month whose index is yd+x.

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why my solution for D fails? I simply decide whether to gain intersection by joining two new segments or expanding others which already cover themselves totally. Counter-examples are especially appreciated.

Here's the submission: https://codeforces.com/contest/1389/submission/88410212.

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Waiting for Div 3 :) After so many difficult rounds to increase rating :(

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is Event Processing I see it here and there but never find some concise tutorial on it.

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain this logic of problem B (solution 2): if i % 2 == k % 2: tmp = (k — i) // 2

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can we do the problem B with kadane algorithm in which I will find the max present in the first k position of the array, and then after reaching towards the max, I will choose whether to go beyond or go back ?

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think we can just go through 45 combinations for C instead of the 100 given in the tutorial.

TLDR:

0101010 has both a 101010 and a 010101 type strings in it.

DETAILED:

Let us say the string we get after removing all other numbers but two be some 011100001001010.....

Then for the above we want it to reduce to the form : 01010101... Note, that if the reduced string ends with 1 then the answer is: size(original string)-size(reduced string). Else, the answer is: size(original string)-{size(reduced string)-1}.

→ Reply
»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone explain the dynamic programming approach to problem E?

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem E doesn't use dynamic programming. It's just math and number theory.

    → Reply
»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Cool contest!Though I've lost some points :(

→ Reply
»
7 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

.

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Firstly.

    What does these numbers mean? Test containing 4 numbers, but u give 6. It's not 1 test and not 2.

    Secondly

    X can't be negative.

    In both pairs {l, r} l <= r, so max(r1, r2) >= max(l1, l2) => max(r1, r2) >= min(l1, l2)

    I hope you understand

    → Reply
»
7 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Why this code is giving TLE? https://ideone.com/wXdX3A

→ Reply
»
7 months ago, # |
← Rev. 10   Vote: I like it 0 Vote: I do not like it

Hey @adedalic I have one doubt in D, You have said,

In the case of non-intersecting [l1,l2] and [r1,r2], we should at first "invest" some number of steps in each pair to make them intersect. So let's iterate over the number of segments to "invest" cntInv. We should make cntInv⋅(max(l1,l2)−min(r1,r2)) steps to make segments touch. Now, cntInv segments touch so we can use almost the same formulas for them as in the previous case.

But consider case where input is,
5 16
1 4
8 12 
In this case should we invest time in joining all pairs or just invest time in joining one pair 
and complete operations using only that pair.
So steps for joining = 4
Steps to make both equal size = 11 , remaining k = 5.
So instead of joining all pairs just invest in first joined pair.
Remaining steps = 5*2 = 10.
Ans = 4 + 11 + 10.


Why should we invest in joining all pairs ? 
Am I missing something ?
Community, Please help !!!

EDIT: Now I get it, u have used a for loop (i to n), that checks by joining first i pairs and compares it with minimum each time . Thanks.

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just iterate over n and find mininum value.

    ans = INF
for i in :n
    temp = cost of getting K intersection with i segments joined.
    ans = min(ans,temp)
    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wrote a recursive solution using memoization where I checked for each I it's i-1 and i+1 and updated my answer with maximum sum Does my solution not violate the condition given in the question :. " you can't perform two or more moves to the left in a row" Can anyone please explain this that how my function goes for 2 or more left moves in a row if z is>=2 and does not violate this and gets accepted

__88418038

→ Reply
»
7 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Could anyone please explain the dp with segment tree approach for problem F?

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Here's how I understand it (I did not solve in contest), feel free to correct me if I'm wrong or there is an easier way to think about this.

    First, let us sort all segments in increasing order of their right endpoints in the list $$$segs$$$. Split the segments based on type and sort them in the same fashion in the lists $$$s[t]$$$. Let $$$dp[i][j][t]$$$ be the answer assuming that the problem is restricted to the first $$$j$$$ segments in $$$segs$$$, along with the condition that we can only select the first $$$i$$$ segments in $$$s[t]$$$, and that we have used segment $$$i$$$ in $$$s[t]$$$ in our solution.

    Now, to transition to $$$segs[j+1]$$$ , assuming $$$segs[j+1]$$$ is of type 1 and is the $$$k+1$$$'th segment in $$$s[1]$$$, we have the following:

    • $$$dp[i][j+1][2] = dp[i][j][2] + 1$$$ if there is no touching between segment $$$k+1$$$ of $$$s[1]$$$ and segment $$$i$$$ of $$$s[2]$$$, and $$$dp[i][j+1][2] = dp[i][j][2]$$$ otherwise.
    • $$$dp[i][j+1][1] = dp[i][j][1]$$$ for all $$$i <= k$$$, and $$$dp[k+1][j+1][1]$$$ is the max of $$$dp[i][j+1][2]$$$ for all segments $$$i$$$ in $$$s[2]$$$ that do not touch with segment $$$k+1$$$ in $$$s[1]$$$.
    In other words, the dp table is largely unchanged, except that we try to add $$$s[1][k+1]$$$ to everything that we can, which must be optimal. The transition for where the new segment is of type 2 is very similar. Our answer is the maximum over the whole dp table.

    Now, notice that for any new segment, the segments that do not touch it must be a prefix of the sorted segment list. Thus, these transitions are exactly range add modifications and maximum queries on two segment trees. We can easily find what range to add by using a binary search. Finally, we can eliminate the 2nd dimension with $$$j$$$ just by directly modifying the segment trees.

    See my submission for implementation details.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      So, for implementation purpose, we can ignore the $$$2nd$$$ dimension of the dp state you mentioned, right? So our dp state will be:

      $$$dp(i,j): $$$ maximum segments if we have only considered till the ith segment of type $$$j$$$ and this one is included. And we traverse the segments on the sorted order of their right endpoints.

      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Yes, exactly. When I was trying to figure the solution out based on other people's code, I found the 3 dimensions to be easier (as a solution that I could actually come up with), but you have it exactly right.

        → Reply
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Okay, sounds good. Thanks a lot.

          → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1389/submission/88444945 Why my code is wrong? Can anyone help? for length = odd, I check for the most frequent character. for length = even, I iterate i,j and the pattern is i,j,i,j, .... ,i, j ( end with j )

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because you don't need to start with p1=0 & p2=0 Try this example char1: 3 4 9 13 15 char2: 5 7 11 18 Your algorithm will answer 2 ( 3, 5 ) But the correct answer is 6 ( 4,7,9,11,13,18 ) You can see that it doesn't need to always start with p1 = 0. Thanks to myself ! I do this beacuse I can't delete my comment.

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am trying to hack 88307545 solution during the hacking phase. By input data was

2
1 25
100 250

The code will output (on local PC and on online compiler):

12 24
25 5
25 5
25 5
25 5
125 250

I write the second test case to make codeforces think "the first line is for the first test case and the others are for the second", but I got unsuccessful attempt. I didn't understand why this happens? Can someone explain to me?

Thanks in Advance!

→ Reply
»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

O(1) solution for D 88447760

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could somebody please explain the dp approach to B?

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Dp approach of B will be like that we have two choices at every index either we can move left or right, we will explore the moves and the maximum between these two options will be considered. base cases are:

    1 . when we don't have any moves left (k==0), in this case, we will return the current index value.

    2 . when the last move taken were left or we don't have any left moves remained or we are at the starting index of the array, then we have only one option to move right at this index.

    3.else we have two option to move right and left, and take the maximum among those to the answer. you can check my solution for more clarity, 88714266.

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      anurag122898 could you please have a look at this? With the same approach, I'm getting two different results just because I'm swapping the two options' sequence. I never knew something like this could make a difference. I'm putting the SS of the comparison between 92397103 and 92402059 for convenience.

      → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did you decide the states to cache? because here index,prev etc also change in every state...

      → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with my code for Problem C ? Getting a Wrong Answer.

def func():
	cnst = "01233456789"

	test = input()

	ans = 1000000000

	for i in cnst:
		for j in cnst:
			c1 = 0
			c2 = 0
			for k in range(len(test)):
				if (i != j and len(test) % 2 == 1 and k == len(test) - 1):
					continue
				elif (k%2 == 0):
					if (test[k] == i):
						c1 += 1
				else:
					if (test[k] == j):
						c2 += 1

			c111 = c1 + c2
			ans = min (len(test) - c111,ans)

	print (ans)


t = int(input())
for i in range(t):
	func()
 
→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code is checking if i is at even and j is at odd positions, which is wrong. You need to find the longest SUBSEQUENCE of alternating i and j of even length. INPUT: 1 2025 YOUR OUTPUT: 1 CORRECT OUTPUT : 2

    → Reply
»
7 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

Same approach as Editorial still can't be accepted in python3 due to TLE on test 2 , what is this?

1389C-Good String 88530443

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    First: Submit in PyPy instead of CPython

    Second: Convert the input to a list of ints once instead of converting it in each iteration.

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

O(1) solution for problem D Segment Intersections.

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If anyone is interested in the explanation then comment.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      interested

      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        There can only be three initial configurations for the two intervals:

        1> One completely overlaps the other.

        2> There is some partial intersection b/w them.

        3> They are disjoint.

        Now, let us tackle them one by one.

        1>> We will have an initial I which can be calculated easily, thereafter if the current I is smaller than k we can increase the intersection length by one for all n pair of segments in just 1 step and we can do this untill all the pairs have become equal It is obvious that we cannot increase I by more than 1 in a single operation, So this is optimal. Now if still I is less than k we only have one way to increase I by increasing the segment lengths of a pair this will give us a +1 for each 2 step. Also, we can do this indefinitely.

        2>> Its the same as the first one except that the initial I has to be calculated differently.

        3>> Initial I=0 , Now how can we increase I? we first have to make a pair of segment meet each other while doing this our I remains the same, lets call this cost as gap. Now as soon as the segments meet we can start having a bunch of +1s . Let us calculate how many +1s we can get in a row, Suppose the worst case when initially both segments are points, then we will have no of +1s equal to the no of +0s (we used to fill the gap) . And in every other case the no of +1s will be greater than +0s , Remember this. Now let us see what choice do we have after using up these two operations , At this point we reach a situation analogous to one explained earlier in 1>> where we will be getting +1 for every 2 steps. We have all the tools ready . Let us expand this for n. I claim that in an optimal final solution we will have a situation where x of the n segments are completely overlapping and at most 1 pair of segments which has been extended by a 2 step operation or has a partial overlap , Also x will be maximum. Suppose a case where x is not the maximum then we have a case where x-1 segments have complete overlap and 1 segment with a partial overlap or an extended 2 step operation segment. We can simply rule out the first case because we can never compensate for the loss of one completely overlapping segment with a partial one. As for the other case the no of 2 step operation will be greater than the complete overlap of the segments as compensation. This is where we use the fact we proved earlier, that we can get a complete overlapping with total no of steps less than or equal to twice the size of the segments, which will always be at least as efficient as the +2 step operation and hence we can carve out a completely overlapping segment from this segment without loosing optimality (for the lack of better word).

        → Reply
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Thanks, man for the effort! stating 3rd case more mathematically -

          suppose we have to make 'rem' out of 'n' segs, let 'ex' be the amount to 'activate' the seg (= max(l1,l2)-min(r1,r2)), and 'tot' (= max(r2,r1)-min(l1,l2)) we can get by doing 1 inc per 1 move operation (+1/1 ops) after 'activation'.

          Its oBvious that we have to 'activate' the 1st seg and do +1/1 ops If still we have something remaining (let it be 'x')

          now if 'x' >= 'tot' then its better to activate another seg and get tot why? because 'tot'+'ex' <= 'tot'*2 as 'ex' <= 'tot'

          if 'x' < 'tot' then we decide on the basis of which is bigger, 'x'+'ex' or 'x'*2

          so how is this o(1) -> after the 1st activation, we can activate segs until reqd amount < 'tot' and then we decide between 'activation'+'+1/1 ops' and '+1/2 ops' for the last one.

          → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is in no way a criticism, but I am indeed slightly surprised to find 3 different languages in the implementation section.

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain the second solution code of problem B?

→ Reply
»
7 months ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

88381812

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Try to write the code in the code snippet. Yours is very unreadable and takes a lot of space in the comments

    for(int i = 0: i < n; i++) {
    likeThis();
}

    EDIT: For your problem, a string is good if it has all same characters in case or even length, or same parity indexed characters are same in case of odd length.

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A rather random question though, for the explanation for question B, it says any position between 1 and k-2(t) + 1 will be visited. But if k == 4 and t == 2, supposedly i can visit position 1 and 2, but the formulas will suggest I only visit between 1 and {4 — 2(2) + 1}, which means visit between 1 and 1?

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in the div2 b problem whats the intution for this"it is optimal to choose exactly the same i for all the pairs (right, left). And that i should be such that ai+1+ai is maximum possible."

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the dp approach for B?

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we do the problem B with kadane algorithm in which I will find the max present in the first k position of the array, and then after reaching towards the max, I will choose whether to go beyond or go back ?

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really nice editorial for Problem B really liked it

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide the Test case 2 — 19th input for task B. Most people had this error "expected 218 found 216". If not exact same test case, then maybe something similar?

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't know the exact test case but you should also handle for the case k=0 explicitly because my solution got accepted after I make a case for k==0.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In that case the answer would be just the 0th element which I've handled. Thanks for the help!

      → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Man, I am getting confused in problem A editorial. It says if 2l>r then its not possible else its l and 2*l. Then how can in the example l=1 and r=1337 produce an output of 6 and 7. Can anyone please explain?

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem B, the tutorial assumes that the left steps will always be accompanied by right steps as they have been taken in pairs but it may so happen that the last step will be a left step, so in that case the tutorial fails and so does the solution in the following test case

18 11 4 11 19 18 19 19 5 14 15 17 4 10 9 8 17 9 2 15 10

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The tutorial assumes left steps are always preceded by a right step; Hence the order (right,left).

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh thanks... i had misunderstood it

      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        hey can you help me in this i'm trying it since last 7 hours 

         def solve(arr,z):  maxm=0  for i in range(len(arr)-1):  maxm=max(maxm,arr[i]+arr[i+1])  z=min(z,5)  i=1  ans=0  moves=len(arr)  flag=0  for i in range(len(arr)):  ans+=arr[i]  moves-=1  if i>=1 and (arr[i]+arr[i-1])==maxm:  break  f=True  #(left , right )  while z!=0 and moves!=0:  if f:  ans+=arr[i-1]  z-=1  moves-=1  f=False  if f==False and moves!=0:  ans+=arr[i]  moves-=1  f=True

        if z==0 and moves!=0:
    print(arr[i+1:i+moves+1])
    ans+=sum(arr[i+1:i+moves+1])
return ans
        for _ in range(int(input())):  n,k,z=map(int,input().split())  arr=list(map(int,input().split()))[:k+1]  print(solve(arr,z))
        → Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The idea of G is quite similar to this problem Museum Tour

Very interesting:

Undirected Graph -> find Bridges -> Tree -> Can be solved using DP

Directed Graph -> find SCC -> DAG -> Can be solved using DP

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The *2100 Prob. D seems much more difficult than the *2200 Prob. E.

→ Reply
»
7 months ago, # |
← Rev. 9   Vote: I like it -10 Vote: I do not like it

I'm trying the array walk since 7 hours still not able to get it can someone please help me with this code where i'm making mistake seriously i just wanted to solve it at any cost please help!!!!


def solve(arr,z):

    maxm=0 #store maximum(sum of ajecent pair )
    for i in range(len(arr)-1):
        maxm=max(maxm,arr[i]+arr[i+1])

    z=min(z,5)#z cannot be greater than 2
    i=1
    ans=0
    moves=len(arr)
    flag=0
    for i in range(len(arr)):
        ans+=arr[i]
        moves-=1
        if i>=1 and (arr[i]+arr[i-1])==maxm: #ossilating condition
            break

    f=True
    while z!=0 and moves!=0:
        if f:
            ans+=arr[i-1]
            z-=1
            moves-=1
            f=False
        if f==False and moves!=0:
            ans+=arr[i]
            moves-=1
            f=True
    
    if z==0 and moves!=0:
        print(arr[i+1:i+moves+1])
        ans+=sum(arr[i+1:i+moves+1])
    return ans
for _ in range(int(input())):
    n,k,z=map(int,input().split())
    arr=list(map(int,input().split()))[:k+1]
    print(solve(arr,z))
→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain the dp approach to problem B?

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    there are things on youtube which explains the dp approach of B, you just type codeforces educational round 92 then you will get what you want :)

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the Good String question: I read the tutorial and worked on it myself for practice. Below is my solution in C++. It passes the test 1. But for test 2. my output is wrong for some cases. Could you please let me know where is wrong? Thanks a lot!

using namespace std;

int main(int argc, char** argv) {

int i, j, cases, x, y, temp, tempX, tempY, ans, maxAns = -1;
string s;
cin >> cases;
for(i = 0; i < cases; i++)
{
    cin >> s;
    for(x = 0; x <= 9; x++)
        for(y = 0; y <= 9; y++)
        {
            ans = 0;
            tempX = x;
            tempY = y;

            for(j = 0; j < s.length(); j++)
            {
                if((s[j] - '0') == tempX){
                    ans++;
                    temp = tempX;
                    tempX = tempY;
                    tempY = temp;
                }
            }
            if((ans % 2 == 1) && (x != y))   ans--;
            if (ans > maxAns) maxAns = ans;
        }
   cout << (s.length() - maxAns) << endl;
}
return 0;

}

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B editorial

"You have t pairs of moves (right, left) to insert somewhere inside the sequence of k-2t moves to the right."

Why k — 2*t ?

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Not expecting DP in second problem.

→ Reply
»
7 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

88352400 for probblem C , can someone please tell me what's wrong in my code?

Spoiler
→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, Can somebody please help in problem B, I am getting TLE. I have used DP.

Submission Link

→ Reply
»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I have tried to make editorial for questions A-E . please have a look. Language :- Hindi

https://www.youtube.com/watch?v=S_-BaaH7P80&list=PLrT256hfFv5X1GNpiqEh5njN_WJmQu8Q6

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why in Problem G we have to find biconnected components? Any counterexamples to SCC?

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In Problem B, Solution 1. Why are they adding arr[i+1] to the maximum pair sum. I mean we can go till pos, so we can add the pairs till pos but because of arr[i+1] pair , the last iteration will also add arr[pos+1]. Also, if we need to add that, why they not added (arr[i+1]) into the 's' variable.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me what the line "Also, you can't perform two or more moves to the left in a row" in the problem 1389B-Array Walk, is meant to be? Can anyone elaborate this line, please?

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I used a dynamic programming approach to problem $$$B$$$, but I get an output of $$$18$$$ instead of $$$19$$$ for the inputs

5 4 1
1 5 4 3 2

Here is my code

cin >> t;
while(t--) {

	cin >> n >> k >> z;
	for(int i = 0; i < n; i++) cin >> a[i];
	
	memset(dp, -INF, sizeof(dp));

	dp[1][0] = a[0] + a[1];
	for(int i = 2; i <= k; i++) {
		dp[i][0] = dp[i - 1][0] + a[i];
		for(int j = 1; 2 * j <= i && j <= z; j++) {
			dp[i][j] = max(dp[i - 1][j - 1] + a[i - j], 
				dp[i - 1][j] + a[i - j]);
		}
	}

	int ans = 0;
	for(int i = 0; i <= z; i++) ans = max(ans, dp[k][i]);

	cout << ans << "\n";
		
}

I don't know why this is happening, since for every possible number of total moves and left moves, we could have previously had one less left move or the same number of left moves. This is the main logic in my idea. Any hints or help would be appreciated.

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, if we are using brute force, for all 100 combinations it is O(n) then it becomes overall O(100*n) which is O(10^7) and with that we have 1000 test cases also, so how does it even work? At first i didn't do it because i thought maybe it will cause TLE, but I realized that they have done the same thing.

→ Reply