awoo's blog

By awoo, history, 9 days ago, translation, In English

1473A - Replacing Elements

Idea: BledDest, adedalic

Tutorial
Solution (Neon)

1473B - String LCM

Idea: BledDest

Tutorial
Solution (Neon)

1473C - No More Inversions

Idea: adedalic

Tutorial
Solution (adedalic)

1473D - Program

Idea: BledDest

Tutorial
Solution (awoo)

1473E - Minimum Path

Idea: Neon

Tutorial
Solution (Neon)

1473F - Strange Set

Idea: BledDest

Tutorial
Solution (BledDest)

1473G - Tiles

Idea: Neon, adedalic

Tutorial
Solution (Neon)

Read more »

 
 
 
 
  • Vote: I like it
  • +125
  • Vote: I do not like it

By awoo, history, 11 days ago, translation, In English

Hello Codeforces!

On Jan/14/2021 17:35 (Moscow time) Educational Codeforces Round 102 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Hey Codeforces and Happy New Year!

To kick off 2021, we want to introduce you to new opportunities!

Undoubtedly, Harbour.Space is always happy to see Codeforces participants among our students! Young talents who are eager to learn, challenge themselves, seek continuous development are our top priority.

That’s why we want to announce our amazing apprenticeship program.

Our mission is to spark positive impact cycles between promising young talent, the tech industry, and innovative educators. We continuously work on finding the perfect match between talent and companies.

Check out a success story from one of our first apprenticeship program students.

David is a UX/UI specialist from Georgia who received a full scholarship from venture capital fund, OneRagtime.

But there are plenty more apprenticeship opportunities coming in the fields of technology, entrepreneurship, and design. Interested? Keep in touch and follow us on LinkedIn for more fantastic opportunities.

Good luck on your round, and see you next time!

Harbour.Space University

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 jiangly 7 201
2 hank55663 7 210
3 BigBag 7 282
4 Lawali 7 283
5 FluffyT 7 306

Congratulations to the best hackers:

Rank Competitor Hack Count
1 ariloc 35:-1
2 smax 34:-9
3 mrkarlo 27:-5
4 VTifand 19
5 BlueGagosipda 21:-22
242 successful hacks and 872 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Geothermal 0:01
B Geothermal 0:02
C SSRS_ 0:09
D Alfalfa_w 0:09
E _FlyingColor_ 0:16
F Apsara 0:40
G tfg 0:48

UPD: Editorial is out

Read more »

 
 
 
 
  • Vote: I like it
  • +278
  • Vote: I do not like it

By awoo, history, 4 weeks ago, translation, In English

1469A - Regular Bracket Sequence

Idea: BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (BledDest)

1469B - Red and Blue

Idea: BledDest and adedalic

Tutorial
Solution 1 (Ne0n25)
Solution 2 (pikmike)

1469C - Building a Fence

Idea: adedalic

Tutorial
Solution (adedalic)

1469D - Ceil Divisions

Idea: adedalic

Tutorial
Solution (adedalic)

1469E - A Bit Similar

Idea: BledDest

Tutorial
Solution (BledDest)

1469F - Power Sockets

Idea: adedalic

Tutorial
Solution (pikmike)

Read more »

 
 
 
 
  • Vote: I like it
  • +121
  • Vote: I do not like it

By awoo, history, 4 weeks ago, translation, In English

Hello Codeforces!

On Dec/28/2020 17:35 (Moscow time) Educational Codeforces Round 101 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 jiangly 6 121
2 Geothermal 6 138
3 neal 6 138
4 kotatsugame 6 165
5 tute7627 6 177

Congratulations to the best hackers:

Rank Competitor Hack Count
1 dorijanlendvaj 72:-13
2 star_xingchen_c 56:-1
3 ubc_123 26:-5
4 yash_daga 21
5 lsantire 20:-2
321 successful hacks and 593 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A WuBullMe 0:01
B Geothermal 0:02
C I_love_Tanya_Romanova 0:08
D abc864197532 0:12
E Kerim.K 0:18
F jiangly 0:42

UPD: Editorial is out

Read more »

 
 
 
 
  • Vote: I like it
  • +365
  • Vote: I do not like it

By awoo, history, 5 weeks ago, translation, In English

1463A - Dungeon

Idea: adedalic

Tutorial
Solution (Ne0n25)

1463B - Find The Array

Idea: BledDest

Tutorial
Solution (Ne0n25)

1463C - Busy Robot

Idea: KAN

Tutorial
Solution (pikmike)

1463D - Pairs

Idea: adedalic

Tutorial
Solution 1 (adedalic)
Solution 2 (adedalic)

1463E - Plan of Lectures

Idea: BledDest

Tutorial
Solution (pikmike)

1463F - Max Correct Set

Idea: Neon

Tutorial
Solution (Ne0n25)

Read more »

 
 
 
 
  • Vote: I like it
  • +90
  • Vote: I do not like it

By awoo, history, 6 weeks ago, translation, In English

Hello Codeforces!

On Dec/17/2020 17:35 (Moscow time) Educational Codeforces Round 100 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Also thanks to Nikolay KAN Kalinin for one of the problems' ideas.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Hey Codeforces!

It’s almost the Holiday season, and this year, we have an extra reason to celebrate — this December marks Harbour.Space’s 5-year anniversary!

Looking back, we’re especially thankful for the wonderful partnerships that have made our university what it is today.

Codeforces has been one of our key partners since the beginning, and we would like to thank the community for growing with us for the past 5 years.

You guys are rock stars, and we’re excited to see where the future takes us both.

Best,
Harbour.Space University

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 heno239 6 174
2 Geothermal 6 178
3 stevenkplus 6 238
4 hank55663 5 87
5 neal 5 121

Congratulations to the best hackers:

Rank Competitor Hack Count
1 3.141592653 49:-3
2 sheaf 48:-17
3 adnan_toky 32:-2
4 _Backl1ght 30:-2
5 star_xingchen_c 27:-1
1083 successful hacks and 1034 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A I_love_Anya_Prokopyeva 0:01
B MikMirzoyanov 0:03
C Geothermal 0:11
D peti1234 0:06
E CoderAnshu 0:23
F heno239 1:13

UPD: Editorial is out

Read more »

 
 
 
 
  • Vote: I like it
  • +422
  • Vote: I do not like it

By awoo, history, 2 months ago, translation, In English

1455A - Strange Functions

Idea: BledDest

Tutorial
Solution (Ne0n25)

1455B - Jumps

Idea: adedalic

Tutorial
Solution (adedalic)

1455C - Ping-pong

Idea: Neon

Tutorial
Solution (Ne0n25)

1455D - Sequence and Swaps

Idea: BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (adedalic)

1455E - Four Points

Idea: adedalic

Tutorial
Solution 1 (adedalic)
Solution 2 (adedalic)

1455F - String and Operations

Idea: Neon

Tutorial
Solution (Ne0n25)

1455G - Forbidden Value

Idea: MrPaul_TUser и BledDest

Tutorial
Solution (pikmike)

Read more »

 
 
 
 
  • Vote: I like it
  • +66
  • Vote: I do not like it

By awoo, history, 2 months ago, translation, In English

Hello Codeforces!

On Nov/30/2020 17:35 (Moscow time) Educational Codeforces Round 99 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 neal 7 223
2 jiangly 7 224
3 tute7627 6 190
4 nocriz 6 195
5 noimi 6 213

Congratulations to the best hackers:

Rank Competitor Hack Count
1 MarcosK 41:-6
2 dapingguo8 34:-2
3 jerdno 12:-4
4 ARTpositive 10:-1
5 halyavin 9:-1
357 successful hacks and 769 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A edickLPM 0:00
B SSRS_ 0:03
C corol 0:03
D pajenegod 0:08
E neal 0:29
F jiangly 0:55
G jiangly 1:17

UPD: Editorial is out

Read more »

 
 
 
 
  • Vote: I like it
  • +146
  • Vote: I do not like it

By awoo, history, 2 months ago, translation, In English

1452A - Robot Program

Idea: BledDest

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

using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int x, y;
        cin >> x >> y;
        int ans = max(x, y) * 2 - 1;
        if(x == y) ans++;
        cout << ans << endl;
    }
}

1452B - Toy Blocks

Idea: adedalic

Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(' ').map { it.toLong() }

        val k = maxOf(a.max()!!, (a.sum() + n - 2) / (n - 1))
        println(k * (n - 1) - a.sum())
    }
}

1452C - Two Brackets

Idea: BledDest

Tutorial
Tutorial is loading...
Solution (pikmike)
def calc(s, x, y):
	bal, cnt = 0, 0
	for c in s:
		if c == y:
			if bal > 0:
				bal -= 1
				cnt += 1
		elif c == x:
			bal += 1
	return cnt

for _ in range(int(input())):
	s = input()
	print(calc(s, '(', ')') + calc(s, '[', ']'))

1452D - Radio Towers

Idea: BledDest

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

using namespace std;

const int MOD = 998244353;

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int ans = 1;
    while(y > 0)
    {
        if(y % 2 == 1)
            ans = mul(ans, x);
        x = mul(x, x);
        y /= 2;
    }
    return ans;
}

int divide(int x, int y)
{
    return mul(x, binpow(y, MOD - 2));
}

int main()
{
    int n;
    cin >> n;
    vector<int> fib(n + 1);
    fib[0] = 0;
    fib[1] = 1;
    for(int i = 2; i <= n; i++)
        fib[i] = add(fib[i - 1], fib[i - 2]);
    cout << divide(fib[n], binpow(2, n)) << endl;    
}

1452E - Two Editorials

Idea: BledDest

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

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

struct seg{
	int l, r;
};

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<seg> a(m);
	forn(i, m){
		cin >> a[i].l >> a[i].r;
		--a[i].l;
	}
	sort(a.begin(), a.end(), [](const seg &a, const seg &b){
		return a.l + a.r < b.l + b.r;
	});
	vector<int> su(m + 1);
	forn(i, n - k + 1){
		int cur = 0;
		for (int j = m - 1; j >= 0; --j){
			cur += max(0, min(i + k, a[j].r) - max(i, a[j].l));
			su[j] = max(su[j], cur);
		}
	}
	int ans = su[0];
	forn(i, n - k + 1){
		int cur = 0;
		forn(j, m){
			cur += max(0, min(i + k, a[j].r) - max(i, a[j].l));
			ans = max(ans, cur + su[j + 1]);
		}
	}
	cout << ans << endl;
	return 0;
}

1452F - Divide Powers

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 x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
	return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
	out << "[";
	fore(i, 0, sz(v)) {
		if(i) out << ", ";
		out << v[i];
	}
	return out << "]";
}

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

int n, q;
vector<li> cnt;

inline bool read() {
	if(!(cin >> n >> q))
		return false;
	cnt.assign(n, 0);
	fore (i, 0, n)
		cin >> cnt[i];
	return true;
}

inline void solve() {
	fore (qs, 0, q) {
		int tp, pos;
		li val;
		cin >> tp >> pos >> val;
		if (tp == 1) {
			cnt[pos] = val;
		} else {
			li small = 0, cur = 0;
			fore (i, 0, pos + 1) {
				small += cnt[i] * ((1ll << i) - 1);
				val -= cnt[i];
			}
			if (val <= 0) {
				cout << 0 << '\n';
				continue;
			}
			
			int id = pos + 1;
			while (id < n) {
				li add = 1ll << (id - pos);
				li need = min(val / add, cnt[id]);
				cur += need * (add - 1);
				val -= need * add;
				small += need * add * ((1ll << pos) - 1);
				
				if (need == cnt[id])
					id++;
				else
					break;
			}
			if (val <= 0) {
				cout << cur << '\n';
				continue;
			}
			if (id >= n) {
				cout << (val > small ? -1 : cur + val) << '\n';
				continue;
			}
			
			li ans = INF64;
			while (id > pos) {
				if (small >= val)
					ans = min(ans, cur + val);
				cur++;
				id--;
				li add = 1ll << (id - pos);
				if (val >= add) {
					cur += add - 1;
					val -= add;
					small += add * ((1ll << pos) - 1);
				}
			}
			assert(val <= 0);
			cout << min(ans, cur) << 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;
}

1452G - Game On Tree

Idea: adedalic

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

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int n;
vector<vector<int>> g;

vector<int> h, pcd, d;
vector<vector<int>> st, vals;
vector<int> a;
 
int dfs(int v, int s, int &cd, int p = -1){
	int sum = 1;
	for (int u : g[v]) if (h[u] == -1 && u != p)
		sum += dfs(u, s, cd, v);
	if (cd == -1 && (2 * sum >= s || p == -1))
		cd = v;
	return sum;
}
 
void build(int v, int s, int d, int p = -1){
	int cd = -1;
	dfs(v, s, cd);
	h[cd] = d;
	pcd[cd] = p;
	for (int u : g[cd]) if (h[u] == -1)
		build(u, s / 2, d + 1, cd);
}

vector<char> cur;

void calcd(int v, int p = -1){
	for (int u : g[v]) if (u != p && cur[u]){
		d[u] = d[v] + 1;
		calcd(u, v);
	}
}

vector<vector<int>> dist;

void init(){
	a.resize(n, -1);
	int k;
	scanf("%d", &k);
	queue<int> q;
	forn(i, k){
		int v;
		scanf("%d", &v);
		--v;
		q.push(v);
		a[v] = 0;
	}
	while (!q.empty()){
		int v = q.front();
		q.pop();
		for (int u : g[v]) if (a[u] == -1){
			a[u] = a[v] + 1;
			q.push(u);
		}
	}
	h.resize(n, -1);
	pcd.resize(n);
	build(0, n, 0);
	st.resize(n);
	vector<int> nd(n);
	forn(v, n){
		int u = v;
		while (u != -1){
			st[u].push_back(v);
			if (pcd[u] != -1)
				nd[pcd[u]] = max(nd[pcd[u]], nd[u] + 1);
			u = pcd[u];
		}
	}
	cur.resize(n);
	vals.resize(n);
	dist.resize(n);
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&nd](int x, int y){
		return nd[x] < nd[y];
	});
	d.resize(n);
	for (int v : ord){
		for (int u : st[v]) cur[u] = true;
		d[v] = 0;
		calcd(v);
		int mx = 0;
		for (int u : st[v]) mx = max(mx, d[u]);
		vals[v].resize(mx + 1, 0);
		for (int u : st[v]) vals[v][d[u]] = max(vals[v][d[u]], a[u]);
		forn(j, mx) vals[v][j + 1] = max(vals[v][j + 1], vals[v][j]);
		for (int u : st[v]) cur[u] = false;
		for (int u : st[v]) dist[u].push_back(d[u]);
	}
}

bool check(int v, int x){
	for (int i = 0, u = v; u != -1; u = pcd[u], ++i)
		if (x - dist[v][i] >= 0 && vals[u][min(int(vals[u].size()) - 1, x - dist[v][i])] > x)
			return true;
	return false;
}

int main() {
	scanf("%d", &n);
	g.resize(n);
	forn(i, n - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	init();
	forn(v, n){
		int res = 0;
		int l = 0, r = n;
		while (l <= r){
			int m = (l + r) / 2;
			if (check(v, m)){
				res = m + 1;
				l = m + 1;
			}
			else{
				r = m - 1;
			}
		}
		printf("%d ", res);
	}
	puts("");
}
Solution 2 (BledDest)
#include<bits/stdc++.h>

using namespace std;

const int N = 200043;
const int LN = 18;

vector<int> g[N];
vector<int> dist[N];
int sz[N];
int par[N];
bool used[N];
int max_dist[N];
vector<int> val[N];

int calc_size(int x, int p = -1)
{
    sz[x] = 1;
    for(auto y : g[x])
        if(y != p && !used[y])
            sz[x] += calc_size(y, x);
    return sz[x];   
}

int find_centroid(int x, int p, int s)
{
    int ans = -1;
    bool good = true;
    for(auto y : g[x])
        if(y != p && !used[y])
            good &= sz[y] * 2 <= s;
        else if(y == p && !used[y])
            good &= (s - sz[x]) * 2 <= s;
    if(good)
        ans = x;
    for(auto y : g[x])
        if(y != p && !used[y])
            ans = max(ans, find_centroid(y, x, s));
    return ans;
}

void calc_dist(int x, int p, int d, int s)
{
    dist[x].push_back(d);
    for(auto y : g[x])
        if(y != p && !used[y])
            calc_dist(y, x, d + 1, s);
    max_dist[s] = max(max_dist[s], d);  
}

int decomposition(int v)
{
    calc_size(v);
    int c = find_centroid(v, v, sz[v]);
    used[c] = true;
    for(auto y : g[c])
        if(!used[y])
        {
            par[decomposition(y)] = c;
        }
    used[c] = false;
    calc_dist(c, c, 0, c); 
    return c;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n - 1; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    decomposition(0);
    for(int i = 0; i < n; i++)
        val[i].resize(max_dist[i] + 1);    
    int k;
    scanf("%d", &k);
    vector<int> d(n, int(1e9));
    queue<int> q;
    for(int i = 0; i < k; i++)
    {
        int x;
        scanf("%d", &x);
        --x;
        q.push(x);
        d[x] = 0;
    }
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(auto y : g[x])
            if(d[y] > d[x] + 1)
            {
                q.push(y);
                d[y] = d[x] + 1;
            }
    }
    for(int i = 0; i < n; i++)
    {
        if(d[i] == 0) continue;
        
        int curc = i;
        for(int j = 0; j < dist[i].size(); j++)
        {
            int dd = dist[i][j];
            if(dd > d[i] - 1)
            {
                curc = par[curc];
                continue;
            }
            dd = d[i] - 1 - dd;
            if(dd >= val[curc].size())
                dd = val[curc].size() - 1; 
            val[curc][dd] = max(val[curc][dd], d[i]);
            curc = par[curc];
        }
    }
    for(int i = 0; i < n; i++)
        for(int j = max_dist[i]; j >= 1; j--)
            val[i][j - 1] = max(val[i][j], val[i][j - 1]);
    for(int i = 0; i < n; i++)
    {
        int ans = 0; 
        int curc = i;
        for(int j = 0; j < dist[i].size(); j++)
        {
            int dd = dist[i][j];
            ans = max(ans, val[curc][dd]);
            curc = par[curc];
        }
        if(d[i] == 0)
            ans = 0;
        printf("%d%c", ans, " \n"[i == n - 1]);
    }
}

Read more »

 
 
 
 
  • Vote: I like it
  • +98
  • Vote: I do not like it

By awoo, history, 2 months ago, translation, In English

Hello Codeforces!

On Nov/19/2020 17:35 (Moscow time) Educational Codeforces Round 98 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 dlalswp25 6 205
2 Ormlis 6 207
3 Tlatoani 6 214
4 yokozuna57 6 232
5 peti1234 6 235

Congratulations to the best hackers:

Rank Competitor Hack Count
1 racsosabe 80:-17
2 Elo 33:-4
3 peti1234 24
4 STUPID_JUSTIN 26:-7
5 xiaofan7 25:-10
605 successful hacks and 888 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Geothermal 0:01
B SSRS_ 0:04
C Valera_Grinenko 0:02
D SSRS_ 0:10
E Akulyat 0:38
F Suiseiseki 0:58
G rainboy 0:42

UPD: Editorial is out

Read more »

 
 
 
 
  • Vote: I like it
  • +272
  • Vote: I do not like it

By awoo, history, 3 months ago, translation, In English

1437A - Marketing Scheme

Idea: adedalic

Tutorial
Solution (adedalic)

1437B - Reverse Binary Strings

Idea: adedalic

Tutorial
Solution (adedalic)

1437C - Chef Monocarp

Idea: BledDest

Tutorial
Solution 1 (pikmike)
Solution 2 (pikmike)

1437D - Minimal Height Tree

Idea: adedalic

Tutorial
Solution (adedalic)

1437E - Make It Increasing

Idea: Neon

Tutorial
Solution (Ne0n25)

1437F - Emotional Fishermen

Idea: BledDest

Tutorial
Solution (BledDest)

1437G - Death DBMS

Idea: BledDest

Tutorial
Solution 1 (pikmike)
Solution 2 (pikmike)

Read more »

 
 
 
 
  • Vote: I like it
  • +88
  • Vote: I do not like it

By awoo, 3 months ago, translation, In English

Hello Codeforces!

On Oct/27/2020 17:35 (Moscow time) Educational Codeforces Round 97 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Um_nik 7 149
2 jiangly 7 193
3 hank55663 7 214
4 neal 7 231
5 uwi 7 250

205 successful hacks and 712 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Drew_is_me 0:01
B Drew_is_me 0:03
C IgorI 0:03
D xb0nS 0:09
E phathnv202 0:17
F SunshinePie 0:28
G tfg 0:13

UPD: Editorial is out

Read more »

 
 
 
 
  • Vote: I like it
  • +356
  • Vote: I do not like it

By awoo, history, 4 months ago, translation, In English

1418A - Buying Torches

Idea: vovuh

Tutorial
Solution (vovuh)

1418B - Negative Prefixes

Idea: BledDest

Tutorial
Solution (Ne0n25)

1418C - Mortal Kombat Tower

Idea: vovuh

Tutorial
Solution (vovuh)

1418D - Trash Problem

Idea: vovuh

Tutorial
Solution (vovuh)

1418E - Expected Damage

Idea: Roms

Tutorial
Solution (Roms)

1418F - Equal Product

Idea: adedalic

Tutorial
Solution (adedalic)

1418G - Three Occurrences

Idea: BledDest and Roms

Tutorial
Solution 1 (pikmike)
Solution 2 (pikmike)

Read more »

 
 
 
 
  • Vote: I like it
  • +165
  • Vote: I do not like it

By awoo, history, 4 months ago, translation, In English

Hello Codeforces!

On Sep/14/2020 17:35 (Moscow time) Educational Codeforces Round 95 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 dzh_loves_mjy 7 204
2 neal 7 231
3 WZYYN 7 250
4 noimi 7 357
5 Um_nik 7 384

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Kirill22 0:01
B dzh_loves_mjy 0:04
C SSerxhs 0:05
D gleb.astashkin 0:17
E Pigbrain 0:19
F WZYYN 0:54
G OnlyG 0:16

UPD: Due to the issues with problems A and B the round is unrated.

UPD: Editorial is out

Read more »

 
 
 
 
  • Vote: I like it
  • -544
  • Vote: I do not like it

By awoo, history, 5 months ago, translation, In English

1400A - String Similarity

Idea: BledDest

Tutorial
Solution (adedalic)

1400B - RPG Protagonist

Idea: adedalic

Tutorial
Solution (adedalic)

1400C - Binary String Reconstruction

Idea: Roms

Tutorial
Solution (Roms)

1400D - Zigzags

Idea: adedalic

Tutorial
Solution (adedalic)

1400E - Clear the Multiset

Idea: Roms

Tutorial
Solution (Roms)

1400F - x-prime Substrings

Idea: BledDest and Roms

Tutorial
Solution (pikmike)

1400G - Mercenaries

Idea: BledDest and Roms

Tutorial
Solution (BledDest)

Read more »

 
 
 
 
  • Vote: I like it
  • +204
  • Vote: I do not like it

By awoo, history, 5 months ago, translation, In English

Hello Codeforces!

On Aug/25/2020 17:35 (Moscow time) Educational Codeforces Round 94 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 neal 7 179
2 tmwilliamlin168 7 210
3 jiangly 7 235
4 kmjp 7 236
5 LayCurse 7 245

Congratulations to the best hackers:

Rank Competitor Hack Count
1 orz 54:-1
2 anuragsingh804 31
3 Loveforever 20:-3
4 dapingguo8 16
5 celestialcoder 15

401 successful hacks and 778 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A neal 0:01
B jiangly 0:05
C gleb.astashkin 0:07
D balakrishnan 0:06
E aibark 0:04
F rainboy 0:43
G rainboy 0:19

UPD: Editorial is out

Read more »

 
 
 
 
  • Vote: I like it
  • +281
  • Vote: I do not like it

By awoo, history, 5 months ago, translation, In English

1398A - Bad Triangle

Idea: Roms

Tutorial
Solution (Roms)

1398B - Substring Removal Game

Idea: BledDest

Tutorial
Solution (Ne0n25)

1398C - Good Subarrays

Idea: Roms

Tutorial
Solution (Roms)

1398D - Colored Rectangles

Idea: BledDest

Tutorial
Solution (pikmike)

1398E - Two Types of Spells

Idea: Roms and BledDest

Tutorial
Solution (Roms)

1398F - Controversial Rounds

Idea: Roms

Tutorial
Solution (Roms)

1398G - Running Competition

Idea: BledDest

Tutorial
Solution (BledDest)

Read more »

 
 
 
 
  • Vote: I like it
  • +76
  • Vote: I do not like it

By awoo, history, 5 months ago, translation, In English

Hello Codeforces!

On Aug/14/2020 17:35 (Moscow time) Educational Codeforces Round 93 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Um_nik 7 111
2 tmwilliamlin168 7 119
3 neal 7 144
4 Farhod_Farmon 7 167
5 Proszek_na_ludka 7 178

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Amir_Reza 13:-6
2 dcordb 3
3 KnightKnight 4:-4

85 successful hacks and 696 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A MikMirzoyanov 0:01
B tamahom1 0:02
C IAKWF 0:02
D shinigami11 0:09
E dorijanlendvaj 0:20
F nikolapesic2802 0:08
G tfg 0:22

UPD: Editorial is out

Read more »

 
 
 
 
  • Vote: I like it
  • +478
  • Vote: I do not like it

By awoo, history, 6 months ago, translation, In English

1389A - LCM Problem

Idea: BledDest

Tutorial
Solution (BledDest)

1389B - Array Walk

Idea: Roms

Tutorial
Solution 1 (pikmike)
Solution 2 (pikmike)

1389C - Good String

Idea: BledDest

Tutorial
Solution (Ne0n25)

1389D - Segment Intersections

Idea: adedalic

Tutorial
Solution (adedalic)

1389E - Calendar Ambiguity

Idea: BledDest

Tutorial
Solution (pikmike)

1389F - Bicolored Segments

Idea: Roms

Tutorial
Solution 1 (Ne0n25)
Solution 2 (Ne0n25)

1389G - Directing Edges

Idea: BledDest

Tutorial
Solution (BledDest)

Read more »

 
 
 
 
  • Vote: I like it
  • +127
  • Vote: I do not like it

By awoo, history, 6 months ago, translation, In English

Hello Codeforces!

On Jul/29/2020 17:35 (Moscow time) Educational Codeforces Round 92 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Hey Codeforces!

We hope you’ve been doing well these past couples of weeks.

This week, we wanted to share a blog post about two of our students. As you might know, Harbour.Space has a unique approach to education — besides classwork and exams, we encourage our students to develop their skills with hands-on projects or even create their startups, so that they’re ready for the workforce when they graduate.

That’s exactly what Jonathan and Khaled, two of our Data Science students, did.

After working hard on their Machine Learning-based startup, they were selected by the European Organization for Nuclear Research (CERN) for a 5 Week Student Entrepreneurship Programme, and are now preparing to travel to Geneva in October. We summarized the story of how they went from data scientists to startup founders in this article.

We hope it inspires you to pursue your passions, and work collaboratively to improve the world for those around you.

Good luck on your round, and see you next time!

Read article→
Rank Competitor Problems Solved Penalty
1 Um_nik 7 245
2 Proszek_na_ludka 7 255
3 kefaa2 7 267
4 Egor 7 293
5 Farhod_Farmon 7 364

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Joney 20:-2
2 applese 19:-1
3 FelixArg 7:-2
4 liouzhou_101 10:-10
116 successful hacks and 492 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A noimi 0:00
B noimi 0:05
C Ari 0:04
D HanaYukii 0:17
E kefaa2 0:22
F nitixkrai 0:23
G MyK_00L 1:05

UPD: Editorial is out

Read more »

 
 
 
 
  • Vote: I like it
  • +413
  • Vote: I do not like it

By awoo, history, 6 months ago, translation, In English

1380A - Three Indices

Idea: BledDest

Tutorial
Solution (Ne0n25)

1380B - Universal Solution

Idea: adedalic

Tutorial
Solution (adedalic)

1380C - Create The Teams

Idea: Roms

Tutorial
Solution (Roms)

1380D - Berserk And Fireball

Idea: Roms

Tutorial
Solution (Roms)

1380E - Merging Towers

Idea: Roms and BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (pikmike)

1380F - Strange Addition

Idea: Roms

Tutorial
Solution 1 (pikmike)
Solution 2 (Roms)

1380G - Circular Dungeon

Idea: BledDest

Tutorial
Solution (pikmike)

Read more »

 
 
 
 
  • Vote: I like it
  • +135
  • Vote: I do not like it

By awoo, history, 6 months ago, translation, In English

Hello Codeforces!

On Jul/12/2020 17:45 (Moscow time) Educational Codeforces Round 91 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: The contest is delayed by 10 minutes.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Geothermal 7 341
2 natsugiri 7 362
3 LayCurse 7 387
4 GyojunYoun 7 415
5 Proszek_na_ludka 7 430

Congratulations to the best hackers:

Rank Competitor Hack Count
1 celestialcoder 15:-2
2 dapingguo8 9
3 kamer 6:-2
4 WiwiHo 3:-1
5 FelixArg 4:-3
48 successful hacks and 88 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A bekzhan29 0:01
B LUV 0:08
C H.A.R.D 0:09
D duyenn_khong_ngu 0:32
E dorijanlendvaj 0:45
F bekzhan29 0:36
G Geothermal 0:59

UPD: Editorial is out

Read more »

 
 
 
 
  • Vote: I like it
  • +515
  • Vote: I do not like it

By awoo, history, 7 months ago, translation, In English

1373A - Donut Shops

Idea: Roms

Tutorial
Solution (pikmike)

1373B - 01 Game

Idea: Roms

Tutorial
Solution (Roms)

1373C - Pluses and Minuses

Idea: Roms

Tutorial
Solution (Roms)

1373D - Maximum Sum on Even Positions

Idea: vovuh

Tutorial
Solution (vovuh)

1373E - Sum of Digits

Idea: BledDest

Tutorial
Solution 1 (BledDest)
Solution 2 (pikmike)

1373F - Network Coverage

Idea: adedalic

Tutorial
Solution 1 (adedalic)
Solution 2 (Ne0n25)

1373G - Pawns

Idea: Roms and BledDest

Tutorial
Solution (Roms)

Read more »

 
 
 
 
  • Vote: I like it
  • +98
  • Vote: I do not like it

By awoo, history, 7 months ago, translation, In English

Hello Codeforces!

On Jun/25/2020 17:35 (Moscow time) Educational Codeforces Round 90 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Geothermal 7 130
2 ksun48 7 143
3 300iq 7 147
4 vepifanov 7 168
5 Radewoosh 7 175

Congratulations to the best hackers:

Rank Competitor Hack Count
1 EduPeres 40
2 Grey_Matter 39:-3
3 lx430621 26:-1
4 killa_vanilla 25:-5
5 checkingagain 17:-1
351 successful hacks and 375 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Geothermal 0:01
B ksun48 0:01
C ksun48 0:03
D Noureldin 0:09
E Geothermal 0:22
F ElOrdyh 0:15
G dario2994 0:29

UPD: Editorial is out

Read more »

 
 
 
 
  • Vote: I like it
  • +550
  • Vote: I do not like it

By awoo, history, 7 months ago, translation, In English

1366A - Shovels and Swords

Idea: Roms

Tutorial
Tutorial is loading...
Solution (Roms)
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(min(l, r, (l + r) // 3))

1366B - Shuffle

Idea: Roms

Tutorial
Tutorial is loading...
Solution (Roms)
for _ in range(int(input())):
    n, x, m = map(int, input().split())
    l, r = x, x
    for _ in range(m):
        L, R = map(int, input().split())
        if max(l, L) <= min(r, R):
            l = min(l, L)
            r = max(r, R)
            
    print(r - l + 1)

1366C - Palindromic Paths

Idea: BledDest

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

using namespace std;

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int> > a(n, vector<int>(m));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> a[i][j];
	vector<vector<int> > cnt(n + m - 1, vector<int>(2));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cnt[i + j][a[i][j]]++;
	int ans = 0;
	for(int i = 0; i <= n + m - 2; i++)
	{
		int j = n + m - 2 - i;
		if(i <= j) continue;
		ans += min(cnt[i][0] + cnt[j][0], cnt[i][1] + cnt[j][1]);
	}
	cout << ans << endl;
}

int main() {
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
		solve();
}

1366D - Two Divisors

Idea: adedalic

Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(' ').map { it.toInt() }

    val minDiv = IntArray(1e7.toInt() + 2) { it }
    for (i in 2 until minDiv.size) {
        if (minDiv[i] != i)
            continue
        for (j in i until minDiv.size step i)
            minDiv[j] = minOf(minDiv[j], i)
    }

    fun getPrimeDivisors(v: Int): ArrayList<Int> {
        val ans = ArrayList<Int>()
        var curVal = v
        while (curVal != 1) {
            if (ans.isEmpty() || ans.last() != minDiv[curVal])
                ans.add(minDiv[curVal])
            curVal /= minDiv[curVal]
        }
        return ans
    }

    val d1 = IntArray(n)
    val d2 = IntArray(n)
    for (id in a.indices) {
        val list = getPrimeDivisors(a[id])
        if (list.size < 2) {
            d1[id] = -1
            d2[id] = -1
        } else {
            d1[id] = list[0]
            list.removeAt(0)
            d2[id] = list.reduce { s, t -> s * t }
        }
    }
    println(d1.joinToString(" "))
    println(d2.joinToString(" "))
}

1366E - Two Arrays

Idea: Roms

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

using namespace std;

const int N = 200005;
const int MOD = 998244353;

int mul(int a, int b) {
    return (a * 1LL * b) % MOD;
}

int n, m;
int a[N], b[N];

int main() {	
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", a + i);
    for (int i = 0; i < m; ++i) scanf("%d", b + i);
    
    reverse(a, a + n);
    reverse(b, b + m);
    a[n] = -1;
    
    int mn = a[0];
    int pos = 0;
    while (pos < n && mn > b[0]) {
        ++pos;
        mn = min(mn, a[pos]);
    }
    
    if (pos == n || mn < b[0]) {
       puts("0");
       return 0;
    }
    
    assert(mn == b[0]);
    int res = 1;
    int ib = 0;
    while (true) {
        assert(mn == b[ib]);
        if (ib == m - 1){
            if(*min_element(a + pos, a + n) != b[ib]) {
               puts("0");
               return 0;
            }
            break;
        }
        
        bool f = true;
        int npos = pos;
        while (npos < n && mn != b[ib + 1]) {
            ++npos;
            mn = min(mn, a[npos]);
            
            if (f && mn < b[ib]){
                f = false;
                res = mul(res, npos - pos);
            }
        }
        
        if (npos == n || mn != b[ib + 1]) {
            puts("0");
            return 0;
        }
        
        ++ib;
        pos = npos;
    }
    
    printf("%d\n", res);
    return 0;
}

1366F - Jog Around The Graph

Idea: Neon

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

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const long long INF = 1e18;
const int MOD = 1000'000'007;
const int inv2 = (MOD + 1) / 2;

struct edge{
	int v, u, w;
};

struct frac{
	long long x, y;
	frac(long long a, long long b){
		if (b < 0) a = -a, b = -b;
		x = a, y = b;
	}
};

bool operator <=(const frac &a, const frac &b){
	return a.x * b.y <= a.y * b.x;
}

struct line{
	long long m, c;
	frac intersectX(const line &l) { return frac(c - l.c, l.m - m); }
};

int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	if (a < 0)
		a += MOD;
	return a;
}

int mul(int a, int b){
	return a * 1ll * b % MOD;
}

int calc(int a1, int d, int n){
	assert(n >= 0);
	return mul(mul(n, inv2), add(mul(2, a1), mul(add(n, -1), d)));
}

int main() {
	int n, m;
	long long q;
	scanf("%d%d%lld", &n, &m, &q);
	vector<edge> e(m);
	vector<int> hv(n);
	forn(i, m){
		scanf("%d%d%d", &e[i].v, &e[i].u, &e[i].w);
		--e[i].v, --e[i].u;
		hv[e[i].v] = max(hv[e[i].v], e[i].w);
		hv[e[i].u] = max(hv[e[i].u], e[i].w);
	}
	
	int ans = 0;
	vector<long long> d(n, -INF), nd(n);
	d[0] = 0;
	forn(val, m){
		long long mx = 0;
		forn(i, n)
			mx = max(mx, d[i]);
		if (val)
			ans = add(ans, mx % MOD);
		nd = d;
		forn(i, m){
			nd[e[i].v] = max(nd[e[i].v], d[e[i].u] + e[i].w);
			nd[e[i].u] = max(nd[e[i].u], d[e[i].v] + e[i].w);
		}
		d = nd;
	}
	
	vector<line> fin;
	forn(i, n) fin.push_back({hv[i], d[i]});
	sort(fin.begin(), fin.end(), [](const line &a, const line &b){
		if (a.m != b.m)
			return a.m < b.m;
		return a.c > b.c;
	});
	fin.resize(unique(fin.begin(), fin.end(), [](const line &a, const line &b){
		return a.m == b.m;
	}) - fin.begin());
	
	vector<line> ch;
	for (auto cur : fin){
		while (ch.size() >= 2 && cur.intersectX(ch.back()) <= ch.back().intersectX(ch[int(ch.size()) - 2]))
			ch.pop_back();
		ch.push_back(cur);
	}
	
	long long prv = 0;
	q -= m;
	forn(i, int(ch.size()) - 1){
		frac f = ch[i].intersectX(ch[i + 1]);
		if (f.x < 0) continue;
		long long lst = min(q, f.x / f.y);
		if (lst < prv) continue;
		ans = add(ans, calc((ch[i].c + ch[i].m * prv) % MOD, ch[i].m % MOD, lst - prv + 1));
		prv = lst + 1;
	}
	ans = add(ans, calc((ch.back().c + ch.back().m * prv) % MOD, ch.back().m % MOD, q - prv + 1));
	
	printf("%d\n", ans);
	return 0;
}

1366G - Construct the String

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 forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)

const int INF = 1e9;
const int N = 10010;

int n, m;
string s, t;
int dp[N][N];
int nxt[N];

int main() {
	cin >> s >> t;
	n = sz(s), m = sz(t);
	
	forn(i, n) if (s[i] != '.') {
		int bal = 0;
		nxt[i] = -1;
		fore(j, i, n) {
			if (s[j] == '.') --bal;
			else ++bal;
			if (bal == 0) {
				nxt[i] = j;
				break;
			}
		}
	}
	
	forn(i, n + 1) forn(j, m + 1)
		dp[i][j] = INF;
	dp[0][0] = 0;
	
	forn(i, n) forn(j, m + 1) {
		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
		if (j < m && s[i] == t[j])
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
		if (s[i] != '.' && nxt[i] != -1)
			dp[nxt[i] + 1][j] = min(dp[nxt[i] + 1][j], dp[i][j]);
	}
	
	cout << dp[n][m] << endl;
}

Read more »

 
 
 
 
  • Vote: I like it
  • +113
  • Vote: I do not like it