Разбор Educational Codeforces Round 170

№	Пользователь	Рейтинг
Нет данных

№	Пользователь	Вклад
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 - Два экрана

Разбор

Решение (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 - Биномиальные коэффициенты, ну типа

Идея: adedalic

Разбор

Решение (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 - Новая игра

Идея: fcspartakm

Разбор

Решение (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 - Проверка характеристик

Идея: adedalic

Разбор

Решение 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;
}

Решение 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 - Карточная игра

Идея: BledDest

Разбор

Решение (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 - Выбери свои запросы

Идея: BledDest

Разбор

Решение (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 - Переменный урон

Идея: BledDest

Разбор

Решение (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())

Комментарии (24)

Написать комментарий?

sarodesparsh

4 часа назад, # |

Finally

→ Ответить

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 часа назад, # ^ |

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 часа назад, # |

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 часа назад, # ^ |

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

115 минут назад, # ^ |

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 часа назад, # |

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

108 минут назад, # |

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

92 минуты назад, # |

285923775 can someone explain why its giving TLE at test case 24 , in the contest the code was accepted but then it showed TLE, Thanks in advance

90 минут назад, # |

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

32 минуты назад, # ^ |

bc of this

Spoiler

78 минут назад, # |

← Rev. 5 →

zrnstnsr

77 минут назад, # |

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

68 минут назад, # |

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

44 минуты назад, # ^ |

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