Разбор Codeforces Round #574 (Div. 2)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Подготовка: budalnik

Разбор

Решение

// Created by Nikolay Budin

#ifdef LOCAL
#  define _GLIBCXX_DEBUG
#else
#  define cerr __get_ce
#endif
#include <bits/stdc++.h>
#define ff first
#define ss second
#define szof(x) ((int)x.size())

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }


void solve() {
	int n, k;
	cin >> n >> k;
	map<int, int> have;
	for (int i = 0; i < n; ++i) {
		int num;
		cin >> num;
		have[num]++;
	}
	int cnt = 0;
	int ans = 0;
	for (pii p : have) {
		cnt += p.ss % 2;
		ans += p.ss / 2 * 2;
	}
	ans += (cnt + 1) / 2;
	cout << ans << "\n";
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}
	
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

1195B - Спортивная мафия

Идея: ?

Подготовка: MikeMirzayanov и cdkrot

Разбор

Решение (бинарный поиск)

#include <iostream>
#include <cmath>

int main() {
    long long n, k;
    std::cin >> n >> k;
    long long l = -1, r = n + 1;
    while (r - l > 1) {
        long long m = (l + r) / 2;
        if ((n - m) * (n - m + 1) / 2 - m > k)
            l = m;
        else
            r = m;
    }
    std::cout << r;
    return 0;
}

Решение (формула)

#include <iostream>
#include <cmath>

int main() {
    long long n, k;
    std::cin >> n >> k;
    std::cout << static_cast<long long>(round(n + 1.5 - sqrt(2 * (n + k) + 2.75)));
    return 0;
}

1195C - Баскетбольная зарядка

Идея: meshanya

Подготовка: tsarn

Разбор

Решение

// Created by Nikolay Budin

#ifdef LOCAL
#  define _GLIBCXX_DEBUG
#else
#  define cerr __get_ce
#endif
#include <bits/stdc++.h>
#define ff first
#define ss second
#define szof(x) ((int)x.size())

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }


void solve() {
	int n;
	cin >> n;
	vector<vector<int>> inp;
	for (int i = 0; i < 2; ++i) {
		inp.push_back(vector<int>());
		for (int j = 0; j < n; ++j) {
			int num;
			cin >> num;
			inp[i].push_back(num);
		}
	}

	pll d = {0, 0};

	for (int i = 0; i < n; ++i) {
		pll next = {max(d.ff, d.ss + inp[0][i]), max(d.ss, d.ff + inp[1][i])};
		d = next;
	}

	cout << max(d.ff, d.ss) << "\n";
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}
	
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

1195D1 - Подводная лодка в Рыбинском море (упрощённая редакция)

Идея: MikeMirzayanov

Подготовка: MikeMirzayanov

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

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 len;
vector<int> pw10;

int f(int a) {
	int pos = 0;
	int res = 0;
	while (a > 0) {
		int cur = a % 10;
		a /= 10;
		res = add(res, mul(cur, pw10[2 * pos]));
		res = add(res, mul(cur, pw10[2 * pos + 1]));
		++pos;
	}
	return res;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	pw10 = vector<int>(30);
	pw10[0] = 1;
	for (int i = 1; i < 30; ++i) {
		pw10[i] = mul(pw10[i - 1], 10);
	}
	
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		int a;
		cin >> a;
		len = to_string(a).size();
		ans = add(ans, mul(n, f(a)));
	}
	
	cout << ans << endl;
	
	return 0;
}

1195D2 - Подводная лодка в Рыбинском море (усложнённая редакция)

Идея: meshanya

Подготовка: sava-cska

Разбор

Решение

// Created by Nikolay Budin

#ifdef LOCAL
#  define _GLIBCXX_DEBUG
#else
#  define cerr __get_ce
#endif
#include <bits/stdc++.h>
#define ff first
#define ss second
#define szof(x) ((int)x.size())

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }

const int MOD = 998244353;

void add(int& a, int b) {
	a += b;
	if (a >= MOD) {
		a -= MOD;
	}
}

int sum(int a, int b) {
	add(a, b);
	return a;
}

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

int f(vector<int> const& a, int l) {
	int res = 0;
	int p = 1;
	for (int i = 0; i < max(szof(a), l); ++i) {
		if (i < l) {
			p = mult(p, 10);
		}
		if (i < szof(a)) {
			add(res, mult(a[i], p));
			p = mult(p, 10);
		}
	}
	return res;
}

int f(int l, vector<int> const& b) {
	int res = 0;
	int p = 1;
	for (int i = 0; i < max(l, szof(b)); ++i) {
		if (i < szof(b)) {
			add(res, mult(b[i], p));
			p = mult(p, 10);
		}
		if (i < l) {
			p = mult(p, 10);
		}
	}
	return res;
}

void solve() {
	int n;
	cin >> n;
	vector<int> arr;
	const int MAXL = 11;
	vector<int> of_len(MAXL);
	for (int i = 0; i < n; ++i) {
		int num;
		cin >> num;
		arr.push_back(num);
		int l = 0;
		int tmp = num;
		while (tmp) {
			++l;
			tmp /= 10;
		}
		of_len[l]++;
	}
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		vector<int> digits;
		int tmp = arr[i];
		while (tmp) {
			digits.push_back(tmp % 10);
			tmp /= 10;
		}
		for (int l = 1; l < MAXL; ++l) {
			int sum = f(digits, l);
			add(ans, mult(sum, of_len[l]));


			sum = f(l, digits);
			add(ans, mult(sum, of_len[l]));
		}
	}

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


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}
	
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

1195E - OpenStreetMap

Идея: budalnik

Подготовка: ima_ima_go

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

long long n, m, a, b, g, x, y, z;
vector<deque<long long> > deq;
vector<vector<long long> > mi;
vector<int> power;
const long long MAX_V = 1000000000000000ll;

void ins(deque<long long>& de, long long val) {
    while(!de.empty() && de.back() > val) {
        de.pop_back();
    }
    de.push_back(val);
}

void del(deque<long long>& de, long long val) {
    if (!de.empty() && de.front() == val) {
        de.pop_front();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    cin >> a >> b;
    cin >> g >> x >> y >> z;
    mi.resize(n);
    deq.resize(m);
    for (int i = 0; i < n; i++) {
        mi[i].resize(m);
        for (int j = 0; j < m; j++) {
            mi[i][j] = g;
            g = (g * x + y) % z;
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < a; j++) {
            ins(deq[i], mi[j][i]);
        }
    }
    deque<long long> real_deq;
    for (int i = 0; i < b; i++) {
        ins(real_deq, deq[i].front());
    }
    long long ans = 0;
    ans += real_deq.front();
    for (int i = b; i < m; i++) {
        del(real_deq, deq[i - b].front());
        ins(real_deq, deq[i].front());
        ans += real_deq.front();
    }
    for (int i = a; i < n; i++) {
        for (int j = 0 ; j < m; j++) {
            ins(deq[j], mi[i][j]);
            del(deq[j], mi[i - a][j]);
        }
        deque<long long> real_d;
        for (int j = 0; j < b; j++) {
            ins(real_d, deq[j].front());
        }
        ans += real_d.front();
        for (int j = b; j < m; j++) {
            del(real_d, deq[j - b].front());
            ins(real_d, deq[j].front());
            ans += real_d.front();
        }
    }
    cout << ans << "\n";
}

1195F - Клуб анонимных геометров

Идея: craborac

Подготовка: budalnik

Разбор

Решение

// Created by Nikolay Budin

#ifdef LOCAL
#  define _GLIBCXX_DEBUG
#else
#  define cerr __get_ce
#endif
#include <bits/stdc++.h>
#define ff first
#define ss second
#define szof(x) ((int)x.size())

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }

struct point {
	int x, y;
	point(int _x, int _y) : x(_x), y(_y) {}

	point operator-(point const& other) const {
		return point(x - other.x, y - other.y);
	}

	point& operator/=(int num) {
		x /= num;
		y /= num;
		return *this;
	}

	bool operator<(point const& other) const {
		return x < other.x || (x == other.x && y < other.y);
	}
};

void solve() {
	int n;
	cin >> n;
	vector<vector<point>> polys;
	vector<point> vecs;
	vector<int> borders;
	borders.push_back(0);
	for (int i = 0; i < n; ++i) {
		int k;
		cin >> k;
		borders.push_back(borders.back() + k);
		polys.push_back({});
		for (int j = 0; j < k; ++j) {
			int x, y;
			cin >> x >> y;
			polys.back().push_back(point(x, y));
		}

		for (int j = 0; j < k; ++j) {
			int next = (j + 1) % k;
			point v = polys[i][next] - polys[i][j];
			int tmp = __gcd(abs(v.x), abs(v.y));
			v /= tmp;
			vecs.push_back(v);
		}
	}

	vector<int> arr;
	map<point, int> inds;
	for (auto v : vecs) {
		if (!inds.count(v)) {
			int tmp = szof(inds);
			inds[v] = tmp;
		}
		arr.push_back(inds[v]);
	}

	vector<int> next(szof(vecs));
	vector<int> last(szof(inds), INF);
	for (int i = szof(vecs) - 1; i >= 0; --i) {
		next[i] = last[arr[i]];
		last[arr[i]] = i;
	}


	vector<vector<pii>> here(szof(vecs));
	int q;
	cin >> q;
	vector<int> ans(q);
	for (int i = 0; i < q; ++i) {
		int l, r;
		cin >> l >> r;
		--l;
		l = borders[l];
		r = borders[r];
		here[l].push_back({r, i});
	}

	int bpv = 1;
	while (bpv < szof(vecs)) {
		bpv *= 2;
	}

	vector<int> segtree(bpv * 2);

	function<void(int, int)> segtree_set = [&](int pos, int val) {
		pos += bpv;
		segtree[pos] = val;
		pos /= 2;
		while (pos) {
			segtree[pos] = segtree[pos * 2] + segtree[pos * 2 + 1];
			pos /= 2;
		}
	};

	function<int(int, int, int, int, int)> segtree_get = [&](int v, int vl, int vr, int l, int r) {
		if (vr <= l || r <= vl) {
			return 0;
		}
		if (l <= vl && vr <= r) {
			return segtree[v];
		}
		int vm = (vl + vr) / 2;
		return segtree_get(v * 2, vl, vm, l, r) + segtree_get(v * 2 + 1, vm, vr, l, r);
	};

	for (int i = 0; i < szof(inds); ++i) {
		segtree_set(last[i], 1);
	}

	for (int i = 0; i < szof(vecs); ++i) {
		for (auto p : here[i]) {
			ans[p.ss] = segtree_get(1, 0, bpv, i, p.ff);
		}
		segtree_set(i, 0);
		if (next[i] != INF) {
			segtree_set(next[i], 1);
		}
	}

	for (int num : ans) {
		cout << num << "\n";
	}
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}
	
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

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

Показать архивные | Написать комментарий?

rotavirus

5 лет назад, # |

+22

в идеале я бы хотел чтобы стандартных задач не было на регулярных ранудах

→ Ответить

BerserkVl

5 лет назад, # ^ |

подскажи, что значит стандартные задачи?

+19

это когда в разборе авторы указывают, что это довольно стандартная задача

AkshajK

← Rev. 3 →

For G, can you explain how "count the number of distinct values on the given segment of the given array" can be solved with persistent segment tree?

vovuh

+33

I googled "the number of distinct values on segment persistent segment tree" right now and the answer is in the first link.

Geothermal

As an aside, we can actually solve this problem offline using a standard segment tree. Sort the queries (L, R) in increasing order of R. Then, we apply a similar idea to two pointers. The segment tree stores the number of values we've seen most recently within the range corresponding to each segment. (That is, position i in the segment tree contains the number of values we've seen most recently in polygon i, and based on this data we can compute the remaining values as a standard sum segment tree.)

For each query, start by updating the tree for any polygons up to position R that we haven't processed yet (i.e. with index greater than the R of the last query we processed). For each value in the polygon, subtract 1 from the segment tree position corresponding to this value's last appearance and add 1 to the node corresponding to the polygon's location. Then, we can get the answer by performing query(L, R) on the segment tree, as this computes the number of values we've seen at least once at or after position L.

+21

Yes, this idea was used in two author's solutions and actually you can replace segment tree with BIT (fenwick tree) as far as I know.

vaibhavsingh100070

I'm unable to understand the tutorial provided for problem C.

rehpiC

I am sorry to say but it is very unlikely for most people to understand that editorial unless you are already comfortable with the concept of dynamic programming and already know how to apply dynamic programming to solve problems. It takes some time to understand dynamic programming. Like you must have taken some time to really understand recursion. Dynamic programming is one step ahead of recursion. I would say dynamic programming is unleashing the true power of recursion. So, I would suggest you to learn and practice some dynamic programming problems before trying to solve the problem C. :)

MasterTaster

Let h[1][x] be the height of the x-th student in the first row, and h[2][y] be the height of the y-th student in the second row (x, y <= n)(our arrays are 1-indexed). Let we see what we'll have to do if we already have maximal sum for the first i-1 columns. What can we do in the i-th column? So, we can add h[1][i] if and only if we took the element from the second row (h[2][i-1]) or we didn't take any element from the previous column. Similarly, we can add h[2][i] if and only if we took the element from the first row (h[2][i-1]) or we didn't take any element from the previous column. Or, we can only skip the i-th column(we do not take any element from the i-th column). That can be done using dp method. Let dp[0][i] be the maximal sum for the first i columns, if we didn't use any elements in the i-th column, dp[1][i] be the maximal sum for the first i columns, if we took an element from the first row in the i-th column, and dp[2][i] be the maximal sum for the first i columns, if we took an element from the second row in the i-th column. Now, we can only iterate through the all possible values of i (from 1 to n) and do the following: 1. dp[0][i]=max(dp[0][i-1], dp[1][i-1], dp[2][i-1]) 2. dp[1][i]=max(dp[0][i-1], dp[2][i-1])+h[1][i] 3. dp[2][i]=max(dp[0][i-1], dp[1][i-1])+h[2][i] Our final result wil be max(dp[0][n], dp[1][n], dp[2][n]). So, we can do this in time complexity O(N), and memory O(1), but memory O(N) (with the dp array, which I used here) is also good.

Vovkaez

Thanks for your great explanation! But I still have one small question left. You said, that we can take h[1][i] if we didn't take nothing in the previous column (and same for h[2][i]), but how is that if we can't take 2 players from the same row? Clearly we can take h[1][i] if and only if the last taken player is h[2][j] and vice versa for h[2][i]. How can we be sure that after adding h[1 or 2][i] to dp[0][i-1] our rule to choose from different rows won't break?

I am not sure what you are exactly asking about, but I can try to explain: We can take h[1][i] if we did take h[2][i-1] or if we did not take any elements from the previous column (if our last taken element is from the j-th column, where j<=(i-2)). The same thing with h[2][i]. We are sure that we didn't breach the rules because, in dp[0][j] we store the maximal sum for the first j columns, but we did not take any element from the j-th column.In dp[1][j] we store the max sum for the first j columns but we took the first element from the j-th column in our maximal value (we took h[1][j]), and vice versa for dp[2][j]. If I didn't answer on your question, sorry, please try to explain it better, I'll try to answer.

soul_voyage

← Rev. 2 →

For F I am trying following — First I calculated number of distinct slopes till i'th polygon. Then for each slope store the polygons which contains this slope using stack such that lower index are at top. Solve queries offline in increasing order of left endpoint of queries with the help of segment tree which does operations — 1. Subtract on a segment & 2. Query for a point. When we reach a polygon we answer queries just by quering point and after that subtract -1 from [i,next_id] where next_id = next polygon which contain same slope as that of current polygon.

I recieved TL 5 for that solution which I think is O(qlog + nklog). Can someone help in finding the complexity of my algo — 57289296

UPD: ACed it. Just store the next index with same slope.

whiteshadow98

In (c), I took a two state dp where dp[i][1] shows that last element included is i and is from 1st row. dp[i][2] shows the similar thing for row2. Now dp[1][1]=arr1[1]//first element of first row dp[2][1]=arr2[1]//first element of second row. Then //L1 if(dp[i-1][1]+arr2[i]>dp[i-1][2]) dp[i][2]=dp[i-1][1]+arr2[i] else dp[i][2]=dp[i-1][2]// I simply excluded that element //L4 Implemented similar thing for dp[i][1] and I got an AC. But now looking at the editorial and other topcoders' solution,everybody implemented using 3 different states, I am confused. Was my implementation correct or the test cases weren't strong enough?

Samarth12

Can someone explain the formula used in problem D2 ??

aayush_bhat1999

it tells you to calculate the contribution of each number for each length by creating the number which would have been made if the given number was present on left side of the function and also if the number was present at the right side of the function. the difference arises in condition when length is not equal.you will have to create that number by getting the example in the question

BaturaDima

Problems were fairly standard, except last one, but I liked it. Good test samples with edge tests.

I think F is also fairly standard for people who knows Minkowski sums. I just opened Berg's Computational geometry and it contains the algorithm to solve that problem.

arthurconmy

+13

F is standard too: https://en.wikipedia.org/wiki/Minkowski_addition#Two_convex_polygons_in_the_plane (which is really easily easy to find) spoils the fact that you can reduce the problem down to distinct values in a range, and then that too is google-able :/

I even did not try search the solution. I do it almost never during contest. But it is good problem for self solving.

GrandDaddy

I think there's a typo in the explanation of B. It should be $$$\frac{x(x+1)}{2}-(n-x)$$$ instead of adding $$$(n-x)$$$.

StevenZhu

In Problem G, why does not this situation appear: In the resulting polygon, three(or even more) sides intersect at one point so that the number of points decreases by 1.

Can anyone give an explanation? Thanks in advance.

gamer37

it will never happen as Minkowski addition always does vector addition of sides of two or more convex polygons in a manner such that the resulting polygon is always convex. you can read more about Minkowski addition here for more clear understanding.

TrickmanOff

IMHO, this round really looks like the educational one: formula, dynamic programming, binary search, "quite typical task" with minimums.

ChenYibai

In problem B, the second solution(fomula) should be

round(n + 1.5 - sqrt(2 * (n + k) + 2.25))

It should be 2.25, not 2.75

Answer = n - (-3 + sqrt(9 + 8(k+n))) / 2  
       = n + 1.5 - sqrt(2.25 + 2(k+n))

Dejokz

how did you come up with this formula: Answer = n — (-3 + sqrt(9 + 8(k+n))) / 2

and how did this result in _ = n + 1.5 — sqrt(2.25 + 2(k+n))_

From the formula given in the tutorial:

  x(x + 1) / 2 - (n - x) = k
        x(x + 1) / 2 + x = k + n
       (x² + x + 2x) / 2 = k + n
                 x² + 3x = 2(k + n)
      x² + 3x - 2(k + n) = 0

Using the formula

 x = (-b ± sqrt(b² - 4ac)) / 2a

We can get

 x = (-3 + sqrt(9 + 8(k+n))) / 2

brave_here

I WASTED LIKE 5 MINUTES THINKING ABOUT THIS

pr0PM

Can't see the Tutorial B :"Unable to parse markup [type=CF_MATHJAX]"

testingmyluck

Can someone explain D solution? I don't get it at all

best1234567

i solved problem B C D1 D2, still reading problem A and still don't understand.please translate me.

Hacheylight

Interesting Problem E

gmh77

Is Problem F's description of the example wrong?

IF_IR_A_1_IR

решил задачу E используя декомпозицию, разбил матрицу на подматрицы a*b и посчитал в каждой из них префиксные минимумы начиная от каждого угла

PebbleChrist

Can somebody help me with the precision on F? I am getting WA on test 3 and my answers are pretty far off.

Spheniscine

Problem E: OpenStreetMap is tough on the JVM architecture. The boxing of integers inherent in STL lists and deques will cause TLE. I basically had to implement my own deque, backed by primitive arrays, in order to pass, but once I did, I easily pass in <900 ms

beast_pirate

Can't the problem Div2 E be done using two pointers and a c++ stl set. we put element and remove element from set in same way as described by queue

Darshann

3 года назад, # |

Can someone why my code for C is failing? I think I've used the same logic as the editorial, using memoization instead of tabulation.

117470118

Ylandolsi

9 месяцев назад, # ^ |

use long long instead of int

Блог пользователя vovuh