Educational Codeforces Round 170 Editorial

#	User	Rating
No items

#	User	Contrib.
1	maomao90	164
2	Um_nik	163
3	cry	159
3	atcoder_official	159
5	adamant	157
5	awoo	157
5	-is-this-fft-	157
8	nor	154
9	TheScrasse	153
10	Dominater069	152

2025A - Two Screens

Tutorial

Solution (BledDest)

for _ in range(int(input())):
	s = input()
	t = input()

	lcp = 0
	n = len(s)
	m = len(t)
	for i in range(1, min(n, m) + 1):
		if s[:i] == t[:i]:
			lcp = i
	print(n + m - max(lcp, 1) + 1)

2025B - Binomial Coefficients, Kind Of

Idea: adedalic

Tutorial

Solution (adedalic)

#include<bits/stdc++.h>

using namespace std;

const int MOD = int(1e9) + 7;

int main() {
	int t; cin >> t;
	vector<int> ks(t);
	for (int _ = 0; _ < 2; _++)
		for (int i = 0; i < t; i++)
			cin >> ks[i];
	
	vector<int> ans(1 + *max_element(ks.begin(), ks.end()), 1);
	for (int i = 1; i < (int)ans.size(); i++)
		ans[i] = (2LL * ans[i - 1]) % MOD;
	
	for (int k : ks)
		cout << ans[k] << '\n';
	return 0;
}

2025C - New Game

Idea: fcspartakm

Tutorial

Solution (awoo)

for _ in range(int(input())):
	n, k = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	j = 0
	for i in range(n):
		j = max(i, j)
		while j + 1 < n and a[j + 1] - a[j] <= 1 and a[j + 1] - a[i] < k:
			j += 1
		ans = max(ans, j - i + 1)
	print(ans)

2025D - Attribute Checks

Idea: adedalic

Tutorial

Solution 1 (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())
 
typedef long long li;
 
const int INF = int(1e9);
const li INF64 = li(1e18);
 
int n, m;
vector<int> rs;
 
bool read() {
	if(!(cin >> n >> m))
		return false;
	rs.resize(n);
	fore (i, 0, n)
		cin >> rs[i];
	return true;
}
 
struct LazySum {
	vector<int> ps;
	LazySum(int n) : ps(n, 0) {}
	
	//[l, r]
	void add(int l, int r, int val) {
		if (l > r) return;
		ps[l] += val;
		ps[r + 1] -= val;
	}
	void pushToAndClear(vector<int> &d) {
		int sum = 0;
		fore (i, 0, sz(ps)) {
			sum += ps[i];
			ps[i] = 0;
			if (i < sz(d))
				d[i] += sum;
		}
	}
};
 
void solve() {
	LazySum ls(m + 2);
	vector<int> d(m + 1, -INF);
	d[0] = 0;
 
	int cntP = 0;
	for (int r : rs) {
		if (r == 0) {
			ls.pushToAndClear(d);
			for (int i = m; i > 0; i--)
				d[i] = max(d[i], d[i - 1]);
			cntP++;
			continue;
		}
		if (r > 0)
			ls.add(r, m, 1);
		else
			ls.add(0, cntP + r, 1);
	}
	ls.pushToAndClear(d);
	cout << *max_element(d.begin(), d.end()) << endl;
}
 
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

Solution 2 (adedalic)

n, m = map(int, input().split())
rs = map(int, input().split())

d = [-int(1e9)] * (m + 1)
d[0] = 0
add = [0] * (m + 2)
def addSegment(l, r):
    if l <= r:
        add[l] += 1
        add[r + 1] -= 1

def pushAll():
    sum = 0
    for i in range(m + 1):
        sum += add[i]
        d[i] += sum
    for i in range(m + 2):
        add[i] = 0

cntPoints = 0
for r in rs:
    if r == 0:
        pushAll()
        for i in range(m, 0, -1):
            d[i] = max(d[i], d[i - 1])
        cntPoints += 1
    else:
        lf, rg = 0, 0
        if (r > 0):
            lf = min(r, m + 1)
            rg = m
        else:
            lf = 0
            rg = max(-1, cntPoints + r)
        addSegment(lf, rg)
pushAll()
print(max(d))

2025E - Card Game

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
 
int add(int x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  return x;
}
 
int mul(int x, int y) {
  return x * 1LL * y % MOD;
}
 
int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> ways(m + 1, vector<int>(m + 1));
  ways[0][0] = 1;
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j <= i; ++j) {
      ways[i + 1][j + 1] = add(ways[i + 1][j + 1], ways[i][j]);
      if (j) ways[i + 1][j - 1] = add(ways[i + 1][j - 1], ways[i][j]);
    }
  }
  
  vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  dp[0][0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= m; ++j) {
      for (int k = 0; k <= m; ++k) {
        int nj = i ? j - k : j + k;
        if (0 <= nj && nj <= m) {
          dp[i + 1][nj] = add(dp[i + 1][nj], mul(dp[i][j], ways[m][k]));
        }
      }
    }
  }
  cout << dp[n][0] << '\n';
}

2025F - Choose Your Queries

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
const int N = 300043;
 
string choice = "xy";
string sign = "+-";
 
int qs[N][2];
string ans[N];
int n, q;
vector<int> g[N];
int color[N];
 
void pair_queries(int q1, int q2)
{
 	if(q1 > q2) swap(q1, q2);
 	for(int i = 0; i < 2; i++)
 		for(int j = 0; j < 2; j++)
 			if(qs[q1][i] == qs[q2][j])
 			{
 			 	ans[q1] = { choice[i], sign[0] };
 			 	ans[q2] = { choice[j], sign[1] };
 			 	return;
 			}
}
 
bool dfs(int v, int pe = -1)
{
 	// return true if parent edge still exists
 	color[v] = 1;
 	vector<int> edge_nums;
 	for(auto e : g[v])
 	{
 		int u = v ^ qs[e][0] ^ qs[e][1];
 		if(color[u] == 1) continue;
 		if(color[u] == 0)
 		{
 			if(dfs(u, e))
 				edge_nums.push_back(e);
 		}
 		else
 			edge_nums.push_back(e);
 	}
 	bool res = true;
 	if(edge_nums.size() % 2 != 0)
 	{
 		if(pe != -1) edge_nums.push_back(pe);
 		else edge_nums.pop_back();
 		res = false;
 	}
 	for(int i = 0; i < edge_nums.size(); i += 2)
 		pair_queries(edge_nums[i], edge_nums[i + 1]);
 	color[v] = 2;
 	return res;
}
 
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 0; i < q; i++)
	{
	 	cin >> qs[i][0] >> qs[i][1];
	 	--qs[i][0];
	 	--qs[i][1];
	 	g[qs[i][0]].push_back(i);
	 	g[qs[i][1]].push_back(i);
	 	ans[i] = "x+";
	}
	for(int i = 0; i < n; i++)
		if(color[i] == 0)
			dfs(i);
	for(int i = 0; i < q; i++) cout << ans[i] << endl;
}

2025G - Variable Damage

Idea: BledDest

Tutorial

Solution (awoo)

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
struct query{
	int t, v;
};
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int m;
	cin >> m;
	vector<query> q(m);
	forn(i, m) cin >> q[i].t >> q[i].v;
	
	vector<pair<int, int>> xs;
	forn(i, m) xs.push_back({q[i].v, i});
	sort(xs.rbegin(), xs.rend());
	forn(i, m) q[i].v = xs.rend() - lower_bound(xs.rbegin(), xs.rend(), make_pair(q[i].v, i)) - 1;
	
	const int p = sqrt(m + 10);
	const int siz = (m + p - 1) / p;
	
	vector<int> tp(m);
	vector<int> val(m);
	vector<vector<long long>> dp(p, vector<long long>(2 * siz + 1));
	vector<int> blbal(p);
	
	auto upd = [&](const query &q){
		tp[q.v] = q.t;
		val[q.v] = xs[q.v].first;
		blbal[q.v / siz] += q.t == 1 ? 1 : -1;
	};
	
	auto recalc = [&](int b){
		dp[b].assign(2 * siz + 1, 0);
		int bal = 0;
		for (int i = b * siz; i < m && i < (b + 1) * siz; ++i){
			if (tp[i] == 1){
				dp[b][0] += val[i];
				dp[b][0] += val[i];
				dp[b][-bal + siz] -= val[i];
				++bal;
			}
			else if (tp[i] == 2){
				dp[b][-bal + 1 + siz] += val[i];
				--bal;
			}
		}
		forn(i, 2 * siz){
			dp[b][i + 1] += dp[b][i];
		}
	};
	
	auto get = [&](int b, int bal){
		bal += siz;
		if (bal < 0) return dp[b][0];
		if (bal >= 2 * siz + 1) return dp[b].back();
		return dp[b][bal];
	};
	
	for (auto it : q){
		upd(it);
		recalc(it.v / siz);
		int bal = 0;
		long long ans = 0;
		for (int i = 0; i * siz < m; ++i){
			ans += get(i, bal);
			bal += blbal[i];
		}
		cout << ans << '\n';
	}
	
	return 0;
}

import sys # defined functions for fast input input = sys.stdin.readline readListInts = lambda type_="int", sep=" ": list( map(eval(type_), input().strip().split(sep)) ) # defined functions for fast output output = lambda x: sys.stdout.write(str(x) + "\n") outputString = lambda x: sys.stdout.write(x + "\n") def main(): for _ in range(int(input())): s = input() t = input() lcp = 0 n = len(s) m = len(t) for i in range(1, min(n, m) + 1): if s[:i] == t[:i]: lcp = i output(n + m - max(lcp, 1) + 1) if __name__ == "__main__": main()

from collections import deque from sys import stdin input = lambda: stdin.readline().rstrip() def solve(): n, k = map(int, input().split()) a = list(map(int, input().split())) hs = {} for i in a: if hs.get(str(i)) is None: hs[str(i)] = 0 hs[str(i)] += 1 mapLi = [] mx = 0 for i in hs: mx = max(mx, hs[i]) mapLi.append([i, hs[i]]) mapLi.sort(key=lambda i: (int(i[0]), -i[1])) ans = 0 queue = deque([]) cnt = 0 for i, v in mapLi: ans = max(ans, cnt) while queue and len(queue) >= k: cnt -= queue.popleft()[1] ans = max(ans, cnt) while queue and abs(int(queue[-1][0]) - int(i)) > 1: cnt -= queue.pop()[1] ans = max(ans, cnt) queue.append((i, v)) cnt += v ans = max(ans, cnt) ans = max(ans, cnt) return ans for _ in range(int(input())): print(solve())

from collections import deque from sys import stdin input = lambda: stdin.readline().rstrip() def solve(): n, k = map(int, input().split()) a = list(map(int, input().split())) hs = {} for i in a: if hs.get(i) is None: hs[i] = 0 hs[i] += 1 mapLi = [] mx = 0 for i in hs: mx = max(mx, hs[i]) mapLi.append([i, hs[i]]) mapLi.sort(key=lambda i: (int(i[0]), -i[1])) ans = 0 queue = deque([]) cnt = 0 for i, v in mapLi: ans = max(ans, cnt) while queue and len(queue) >= k: cnt -= queue.popleft()[1] ans = max(ans, cnt) while queue and abs(int(queue[-1][0]) - int(i)) > 1: cnt -= queue.pop()[1] ans = max(ans, cnt) queue.append((i, v)) cnt += v ans = max(ans, cnt) ans = max(ans, cnt) return ans for _ in range(int(input())): print(solve())

Comments (22)

Write comment?

sarodesparsh

4 hours ago, # |

Finally

→ Reply

commonashishw

← Rev. 2 →

Hii everyone can anyone help me D problem?

https://mirror.codeforces.com/contest/2025/my

this was my solution

i would keep count of zeros till i

then our s could range from 0 to zeros

so my state is dp[s] which will have max check passed, so my time complexity was 5000*2*10^6

3 hours ago, # ^ |

https://mirror.codeforces.com/contest/2025/submission/286105592

here i have reduced most of the redudant operations still i get tle

what i am thinking is to have a vector which stores starting and ending point of zeros if more than 1 then i would just increment my of zeros to difference between start and end their by saving some more time am i going in the right direction?

i would be using a unordered map to store my records.

darthrevenge

3 hours ago, # |

For those, who interested in combinatorial way for problem E, using something similar to Catalan numbers: I wrote a post about it

papa-ka-para

2 hours ago, # ^ |

Awesome.

Heis_nberg

Does Problem D fall under some Dp pattern saw this pattern of pushAndClear in many submissions it didn't click to me at all.

puupil

isn't the code in problem A's solution $$$ O(n^2) $$$ due to string slicing?

SuperMo

← Rev. 4 →

say_yas

for Problem c , can anyone tell why this solution is giving wrong answer on test 4 (i used binarysearch to solve this): https://mirror.codeforces.com/contest/2025/submission/285946605 thanks in advance !!

_wei933703

117 minutes ago, # ^ |

By binary research, you can only find the position of the last card which number is less than $$$(x+k-1)$$$, but you are not able to know if there are some numbers missing (between $$$x$$$ and the number of the last card). It’s the reason why you get wrong answer.

BTW, if you choose to check through the whole interval between $$$x$$$ and $$$(x+k-1)$$$ to make sure there are no missing numbers, the time complexity would be something like $$$O(N^2)$$$ in worst case and fails the time limit.

Therefore, I don’t think it’s possible to use binary research to solve this problem.

LorenzoRaed02

Note about Problem A ( or any other problem concerning strings ) if you use Python and fast IO like: input = sys.stdin.readline then make sure to strip the string from whitespace and newlines.

this code was tested in Windows fine:

However, the judges are based on POSIX systems and newlines are treated differently between the two systems. So I needed to make this small adjustment:

 s = input().strip()
 t = input().strip()

A small detail that may cost you a submission.

I guess for veteran competitive programmers this is trivial but it cost me some time and a wrong submission on an easy problem.

Adith082

Problem B Binomial Coefficients Kind of Video Editorial Link: https://youtu.be/y_b2Khyk28w?si=Ku5V5m1jtT8EtA1e

← Rev. 3 →

Honestly, instead of doing this video... up solve next time.

Or may be just downvote this comment and rant over it.

Not that anyone asked, but felt like sharing constructive feedback.

Hadivai_CE23044

_i want to know,would anyone please tell me why rating going back;

alpha1215

2 hours ago, # |

my solution to D is a little different and it does not require bs or lazysum.

let $$$dp[i]$$$ denotes the $$$max \ score$$$ we can get if we are at index $$$j$$$ and have total $$$i$$$ intelligence points
if $$$A[i] == 0$$$ we will update dp values as follows.
let $$$cnt1[x] \ and \ cnt2[x]$$$ stores no. of checks with values x of intelligence and strength respectively.

if we choose to increase intelligence points then we are sure that we will pass all the intelligence checks having value $$$<=$$$ to our current intelligence values and because all the checks with value $$$<$$$ $$$current intelligence$$$ are already covered we will need to calculate how many values = current intelligence are there on the right on the right of index i and this value is stored in cnt1[current intelligence].

$$$dp[i] \ = \ max(dp[i] \ + \ cnt2[s - i], \ dp[i - 1] \ + \ cnt1[i])$$$
here $$$i$$$ is $$$current_intelligence$$$ and s is $$$current total score = intelligence + strength$$$

here is the 285916766 to explain better (ignore the code above solve function).

feel free to ask me if you have any queries. Thanks!

soham_c04

109 minutes ago, # |

E can be solved using DP + OEIS sequence A050155.

Define $$$g(m,k)$$$: Number of ways to choose $$$(m+k)/2$$$ elements for Player 1 out of m cards in a given suit such that Player 1 wins as given in Problem.

Write a brute force for function $$$g$$$ -> generate the sequence and paste on OEIS -> Find the formula $$$g(m,k)$$$ given in OEIS link above -> Precompute it -> Multiply $$$g(m,j-k)$$$ with $$$DP[i-1][k]$$$ and then sum over all values of $$$0\leq k\leq j$$$ to find $$$DP[i][j].$$$ $$$1\leq i\leq n,0\leq j\leq m$$$.

vidhanagarwal2001

91 minute(s) ago, # |

Can someone explain why its showing TLE in this submission in problem C , in the contest it got accepted but later on it came out to be TLE 285923775 in test case 24

saelcc03

33 minutes ago, # ^ |

bc of this

Spoiler

80 minutes ago, # |

← Rev. 5 →

zrnstnsr

79 minutes ago, # |

E is a typical problem that requires $$$y-x\ge k$$$ on a path from $$$(0,0)$$$ to $$$(m,n)$$$. See here for more details.

szpu_ark

69 minutes ago, # |

In Problem C, I have an issue:

I have two pieces of code. The first one:

The second one:

I submitted the second piece of code to Codeforces Edu Round 170, Problem C, but it resulted in a Time Limit Exceeded (TLE). Then, I submitted the first piece of code, and it passed successfully. Is this an issue with the judging system, or is there a problem with my code? Can someone explain the reason? I would be very grateful!

link1:https://mirror.codeforces.com/contest/2025/submission/286123006 link2:https://mirror.codeforces.com/contest/2025/submission/286122969

If this problem is solved, you will get one of Python's optimization ticks!!!!!

45 minutes ago, # ^ |

Avoid using dict or set in an open-hack round as they're to be easily hacked. If you have to, write your own hash function.

By using str(i) instead of i as the key, you actually define another hash function for $$$i$$$ so you pass the test.

awoo's blog