Разбор Educational Codeforces Round 91

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Разбор

Решение (Ne0n25)

#include <bits/stdc++.h>

using namespace std;

const int N = 1000;

int n;
int a[N];

void solve() {
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 1; i < n - 1; ++i) {
		if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
			cout << "YES" << endl;
			cout << i << ' ' << i + 1 << ' ' << i + 2 << endl;
			return;
		}
	}
	cout << "NO" << endl;
}

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

1380B - Universal Solution

Идея: adedalic

Разбор

Решение (adedalic)

fun main() {
    val winBy = mapOf('R' to 'P', 'S' to 'R', 'P' to 'S')
    repeat(readLine()!!.toInt()) {
        val s = readLine()!!
        val maxCnt = s.groupingBy { it }.eachCount().maxBy { it.value }!!.key
        println("${winBy[maxCnt]}".repeat(s.length))
    }
}

1380C - Create The Teams

Идея: Roms

Разбор

Решение (Roms)

for _ in range(int(input())):
    n, x = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    res, cur = 0, 1
    for s in a:
        if s * cur >= x:
            res += 1
            cur = 0
        cur += 1
    print(res)

1380D - Berserk And Fireball

Идея: Roms

Разбор

Решение (Roms)

#include <bits/stdc++.h>

using namespace std;

const int N = int(2e5) + 9;

int n, m;
long long x, k, y;
int a[N];
int b[N];

bool upd(int l, int r, long long &res) {
    if (l > r) return true;
    bool canDel = false;
    int mx = *max_element(a + l, a + r + 1);
    int len = r - l + 1;
    if (l - 1 >= 0 && a[l - 1] > mx) canDel = true;
    if (r + 1 < n && a[r + 1] > mx) canDel = true;
    if (len < k && !canDel) return false;
    
    int need = len % k;
    res += need * y;
    len -= need;
    
    if (y * k >= x) {
        res += len / k * x;
    } else if(canDel) {
        res += len * y;
    } else {
        res += (len - k) * y + x;
    }
    
    return true;
}

int main(){
    scanf("%d %d", &n, &m);
    scanf("%lld %lld %lld", &x, &k, &y);
    for (int i = 0; i < n; ++i) scanf("%d", a + i);
    for (int i = 0; i < m; ++i) scanf("%d", b + i);
    
    long long res = 0;
    int lst = -1, posa = 0, posb = 0;
    while (posb < m) {
        while(posa < n && a[posa] != b[posb]) ++posa;
        if (posa == n) {
            puts("-1");
            return 0;
        }
        
        if (!upd(lst + 1, posa - 1, res)) {
            puts("-1");
            return 0;
        }
        
        lst = posa;
        ++posb;
    }
    
    if (!upd(lst + 1, n - 1, res)) {
        puts("-1");
        return 0;
    }
    
    printf("%lld\n", res);
    
    return 0;
}

1380E - Merging Towers

Идея: Roms и BledDest

Разбор

Решение 1 (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;
const int L = 20;

vector<int> g[2 * N];
int p[2 * N];
int up[2 * N][L];
int idx[N];
int psum[N];
int cur[N];
int tin[2 * N];
int tout[2 * N];
int T = 0;

void dfs(int x, int y)
{
	tin[x] = T++;
	p[x] = y;
	up[x][0] = y;
	for(int i = 1; i < L; i++)
		up[x][i] = up[up[x][i - 1]][i - 1];
	for(auto z : g[x])
		dfs(z, x);
	tout[x] = T++;
}

bool is_ancestor(int x, int y)
{
	return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int lca(int x, int y)
{
	if(is_ancestor(x, y))
		return x;
	for(int i = L - 1; i >= 0; i--)
		if(!is_ancestor(up[x][i], y))
			x = up[x][i];
	return p[x];
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &idx[i]);
		idx[i]--;
	}
	for(int i = 0; i < m; i++)
		cur[i] = i;
	for(int i = 0; i < m - 1; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		--x;
		--y;
		int nidx = m + i;
		g[nidx].push_back(cur[x]);
		g[nidx].push_back(cur[y]);
		cur[x] = nidx;
	}
	int root = m * 2 - 2;
	dfs(root, root);
	for(int i = 0; i < n - 1; i++)
	{
		int t = lca(idx[i], idx[i + 1]);
		if(t < m)
			psum[0]++;
		else
			psum[t - m + 1]++;
	}
	for(int i = 0; i < m - 1; i++)
		psum[i + 1] += psum[i];
	for(int i = 0; i < m; i++)
		printf("%d\n", n - 1 - psum[i]);
}

Решение 2 (pikmike)

#include <bits/stdc++.h>

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

using namespace std;

int n, m;
vector<int> p;
vector<vector<int>> val;
vector<int> who;

int getp(int a){
	return a == p[a] ? a : p[a] = getp(p[a]);
}

int main(){
	scanf("%d%d", &n, &m);
	p.resize(m);
	val.resize(m);
	who.resize(n);
	int ans = n - 1;
	forn(i, m)
		p[i] = i;
	forn(i, n){
		int x;
		scanf("%d", &x);
		--x;
		who[i] = x;
		ans -= (i && who[i] == who[i - 1]);
		val[who[i]].push_back(i);
	}
	printf("%d\n", ans);
	forn(i, m - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		v = getp(v - 1), u = getp(u - 1);
		if (val[v].size() < val[u].size())
			swap(v, u);
		for (int x : val[u]){
			if (x) ans -= who[x - 1] == v;
			if (x < n - 1) ans -= who[x + 1] == v;
		}
		for (int x : val[u]){
			val[v].push_back(x);
			who[x] = v;
		}
		p[u] = v;
		printf("%d\n", ans);
	}
	return 0;
}

1380F - Strange Addition

Идея: Roms

Разбор

Решение 1 (pikmike)

#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 998244353;
const int N = 500 * 1000 + 13;

string s;

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

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

struct node{
	int val[4], len;
};

node merge(const node &a, const node &b, int l, int r){
	node c;
	int na = a.len == 1 ? 0 : 1;
	int nb = b.len == 1 ? 0 : 2;
	c.len = a.len + b.len;
	c.val[0] = mul(a.val[na], b.val[nb]);
	c.val[1] = mul(a.val[na], b.val[3]);
	c.val[2] = mul(a.val[3], b.val[nb]);
	c.val[3] = mul(a.val[3], b.val[3]);
	if (l == 1){
		na = a.len == 1 ? 2 : 0;
		nb = b.len == 1 ? 1 : 0;
		c.val[na + nb] = add(c.val[na + nb], mul(mul(a.val[0], b.val[0]), 19 - (l * 10 + r)));
		c.val[1 + na] = add(c.val[1 + na], mul(mul(a.val[0], b.val[1]), 19 - (l * 10 + r)));
		c.val[2 + nb] = add(c.val[2 + nb], mul(mul(a.val[2], b.val[0]), 19 - (l * 10 + r)));
		c.val[3] = add(c.val[3], mul(mul(a.val[2], b.val[1]), 19 - (l * 10 + r)));
	}
	return c;
}

node t[4 * N];

void build(int v, int l, int r){
	t[v].len = r - l;
	if (l == r - 1){
		t[v].val[0] = 1;
		t[v].val[3] = s[l] + 1;
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m, r);
	t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]);
}

void upd(int v, int l, int r, int x, int val){
	if (l == r - 1){
		s[l] = val;
		t[v].val[3] = s[l] + 1;
		return;
	}
	int m = (l + r) / 2;
	if (x < m)
		upd(v * 2, l, m, x, val);
	else
		upd(v * 2 + 1, m, r, x, val);
	t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]);
}

int main(){
	int n, m;

	scanf("%d%d", &n, &m);
	static char buf[N];
	scanf("%s", buf);
	s = buf;
	forn(i, n) s[i] -= '0';
	
	memset(t, 0, sizeof(t));
	build(1, 0, n);
	
	forn(i, m){
		int x, v;
		scanf("%d%d", &x, &v);
		--x;
		upd(1, 0, n, x, v);
		printf("%d\n", t[1].val[3]);
	}
}

Решение 2 (Roms)

#include <bits/stdc++.h>

using namespace std;

const int N = int(5e5) + 9;
const int MOD = 998244353;

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

void add(int &a, int x) {
    a += x;
    a %= MOD;
}

int bp(int a, int n) {
    int res = 1;
    for (; n > 0; n >>= 1) {
        if (n & 1) res = mul(res, a);
        a = mul(a, a);
    }
    return res;
}

int inv(int a) {
    int ia = bp(a, MOD - 2);
    assert(mul(a, ia) == 1);
    return ia;
}

int n, m;
string s;
int dp[N][10];
int idp[N][10];
set <pair<int, int> > lr;
int res = 1;

void updRes(int l, int r, int c) {
    assert(l <= r);
    if (c == 1) {
        assert(!lr.count(make_pair(l, r)));
        lr.insert(make_pair(l, r));
        res = mul(res, dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']);
    } else {
        assert(lr.count(make_pair(l, r)));
        lr.erase(make_pair(l, r));
        res = mul(res, inv(dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']));
    }
}

void getLR(int &l, int &r, int pos) {
    l = r = -1;
    auto it = lr.lower_bound(make_pair(pos, n));
    if(it == lr.begin()) return;
    --it;
    if(!(it->first <= pos && pos <= it->second)) return;
    l = it->first, r = it->second;
}

char buf[N];
int main(){
    scanf("%d %d\n", &n, &m);
    scanf("%s", buf);
    s = string(buf);
    for (int i = 0; i <= 9; ++i) {
        dp[0][i] = i + 1; //idp[0][i] = inv(dp[0][i]);
        dp[1][i] = 2 * (i + 1) + (9 - i); //idp[1][i] = inv(dp[1][i]);
    }
    for (int i = 2; i < N; ++i)
        for (int j = 0; j <= 9; ++j) {
            dp[i][j] = (2LL * dp[i - 1][j] + 8LL * dp[i - 2][j]) % MOD;
            //idp[i][j] = inv(dp[i][j]);
        }
    for (int i = 0; i < N; ++i) for(int j = 0; j < 10; ++j) assert(dp[i][j] != 0);
    for (int l = 0; l < n; ) {
        int r = l;
        while(r < n && s[r] == '1') ++r;
        res = mul(res, dp[r - l - (r == n)][r == n? 1 : s[r] - '0']);
        if (l != r) lr.insert(make_pair(l, r - 1));
        l = r + 1;
    }
    
    for (int i = 0; i < m; ++i) {
        int pos;
        char x;
        scanf("%d %c\n", &pos, &x);
        --pos;
        if (x == '1') {
            if (s[pos] != '1'){ 
                int l1, r1, l2, r2;
                getLR(l1, r1, pos - 1);
                getLR(l2, r2, pos + 1);
                
                int l = pos, r = pos;
                if (l1 != -1) {
                    assert(r1 == pos - 1);
                    updRes(l1, r1, -1);
                    l = l1;
                } else {
                    res = mul(res, inv(dp[0][s[pos] - '0']));
                }
                
                if (l2 != -1) {
                    assert(l2 == pos + 1);
                    updRes(l2, r2, -1);
                    r = r2;
                } else {
                    if (pos + 1 != n) res = mul(res, inv(dp[0][s[pos + 1] - '0']));
                }
                
                s[pos] = x;
                updRes(l, r, 1);
            }
        } else {
            if (s[pos] != '1') {
                if (pos - 1 >= 0 && s[pos - 1] == '1') {
                    int l, r;
                    getLR(l, r, pos - 1);
                    updRes(l, r, -1);
                    s[pos] = x;
                    updRes(l, r, 1);
                } else {
                    res = mul(res, dp[0][x - '0']);
                    res = mul(res, inv(dp[0][s[pos] - '0']));
                    s[pos] = x;
                }
            } else {
                int l, r;
                getLR(l, r, pos);
                assert(l != -1 && r != -1);
                
                updRes(l, r, -1);
                s[pos] = x;
                if (l == r) {
                    res = mul(res, dp[0][s[pos] - '0']);
                    if (pos + 1 < n) res = mul(res, dp[0][s[pos + 1] - '0']);
                } else if (pos == l) {
                    res = mul(res, dp[0][s[pos] - '0']);
                    updRes(l + 1, r, 1);
                } else if (pos == r) {
                    if (pos + 1 != n) res = mul(res, dp[0][s[pos + 1] - '0']);
                    updRes(l, r - 1, 1);
                } else {
                    updRes(l, pos - 1, 1);
                    updRes(pos + 1, r, 1);
                }
            }
            
        }
        printf("%d\n", res);
    }
}

1380G - Circular Dungeon

Идея: BledDest

Разбор

Для начала, скажем, что математическое ожидание равно среднему значению дохода по всем позициям и равно сумме значений дохода по всем позициям, деленной на $$$n$$$. Поэтому перейдем к минимизации суммы.

Научимся решать для фиксированного $$$k$$$. Возьмем некоторую расстановку и повернем комнаты так, чтобы последняя комната содержала мимика. Тогда у нас стоят $$$cnt_1$$$ обычных сундуков, затем один мимик, $$$cnt_2$$$ обычных сундуков, один мимик, $$$\dots$$$, $$$cnt_k$$$ обычных сундуков, один мимик. Все $$$cnt_i \ge 0$$$ и $$$\sum \limits_{i=1}^{k} cnt_i = n - k$$$.

Взглянем на один из таких интервалов длины $$$cnt_i$$$. Последний сундук на интервале взят из $$$cnt_i$$$ начальных позиций, второй с конца — $$$cnt_i - 1$$$ раз и так далее.

Найдем оптимальный способ выбрать $$$cnt_i$$$. Зафиксируем некоторые значения $$$cnt_i$$$. Взглянем на наименьшее из них и на наибольшее. Пусть их значения будут равны $$$x$$$ и $$$y$$$. Если они отличаются хотя бы на $$$2$$$ ($$$x \le y - 2$$$), то результат всегда можно сделать лучше, если подвинуть один обычный сундук из большего интервала в меньший.

Доказательство

Теперь все значения $$$cnt_i$$$ выставлены. Осталось только присвоить сундуки оптимальным способом. Выпишем объединение всех последовательностей коэффициентов интервалов $$$\bigcup \limits_{i=1}^{n-k} [1, \dots, cnt_i-1, cnt_i]$$$ и отсортируем в неубывающем порядке. Легко показать, что сундуки должны быть отсортированы в невозрастающем порядке (очень стандартная штука, можно доказать опять же показав, что другая расстановка легко может быть улучшена).

Это позволяет нам написать решение за $$$O(n^2)$$$. Отсортируем все сундуки в самом начале, а затем для любого $$$k$$$ домножим значение $$$i$$$-го сундука на $$$\lfloor \frac{i}{k} \rfloor$$$ и сложим результаты.

Наконец, ускорим решение с помощью префиксных сумм. Заметим, что первые $$$k$$$ значений домножаются на $$$0$$$, вторые $$$k$$$ значений — на $$$1$$$ и так далее. Если $$$n$$$ не делится на $$$k$$$, то последний блок имеет длину меньше $$$k$$$. Тогда можно посчитать ответ для любого $$$k$$$ за $$$O(\frac{n}{k})$$$. А это равно $$$O(\sum \limits_{k=1}^{n} \frac{n}{k})$$$ = $$$O(n \log n)$$$.

Асимптотика решения: $$$O(n \log n)$$$.

Решение (pikmike)

#include <bits/stdc++.h>

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

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 binpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

vector<int> pr;

int main() {
	int n;
	scanf("%d", &n);
	vector<int> c(n);
	forn(i, n)
		scanf("%d", &c[i]);
	sort(c.begin(), c.end(), greater<int>());
	pr.push_back(0);
	forn(i, n)
		pr.push_back(add(pr.back(), c[i]));
	
	int invn = binpow(n, MOD - 2);
	for (int k = 1; k <= n; ++k){
		int ans = 0;
		for (int i = 0, j = 0; i < n; i += k, ++j)
			ans = add(ans, mul(j, add(pr[min(n, i + k)], -pr[i])));
		printf("%d ", mul(ans, invn));
	}
	puts("");
	
	return 0;
}

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

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

infinite_dive

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

-13

Fastest editorial for an educational round I think.

→ Ответить

+14

nagasawa

+15

Btw, in E merging without “smallest to biggest” optimization somehow passes the tests :)

Adamenko

4 года назад, # ^ |

Nothing surprising. There is even such a heuristic: randomly connecting sets. It works for O(nlog(n)).

Oh, that makes sense, thanks

tribute_to_Ukraine_2022

+16

No it's not $$$O(n \log n)$$$. Let's say we have $$$n$$$ one element sets and in $$$i$$$-th round we merge $$$i+1$$$-st set to su of first $$$i$$$. Then on $$$i$$$-th turn we have $$$\frac 12$$$ probability to do one insert, and $$$\frac 12$$$ to do $$$i$$$ inserts, which means on avearge $$$O(i)$$$ inserts on $$$i$$$-th turn, which adds to aveeage of $$$O(n^2)$$$ inserts.

That's one way to look at the probabilistic formulation. If you have broader probability space, for example, if operations are also chosen randomly, then the probability of big set being in the operation can be small, and I think it won't be O(n^2). I'm not sure how to show it, but my solution passed in the beginning, until they added a counterexample as yours, so if tests were generated using random at first, I think it shows that average complexity is not so bad.

KnightKnight

I am not able to convince myself that if there is some answer, we can find an index j such that aj−1aj+1 ? Can anybody explain it better maybe :)

← Rev. 2 →

If you are asking about A, then:

Take ai < aj > ak

Lets shrink the distance between i and j. If i = j — 1, its done. Otherwise if aj < a(j-1), do j = j — 1, its still correct solution, and continue the loop. Otherwise take i = j — 1, and exit the loop, so we’ve done that.

So if there exist a solution, then there is a solution with i = j — 1. Take the set of such solutions and take with the smallest distance between j and k. If it is not one, then all elements between j and k are greater than aj. But then we can take i’=j, j’=j+1 and k’=k. So its distance is smaller then that is a contradiction

durmanko

Мне кажется, что в разборе задачи D есть опечатка. Это:

поэтому при l<x и r<x решения нет. Нужно заменить на: поэтому при l<p и r<p решения нет.

lait1103

В любом случае спасибо за раунд и быстрый разбор!)))

4rt3xp0

+135

francotirador

First time solving a div 2D in a contest and this happens :(

gjy5885

Haha!

bitch_house

+22

In the solution of problem E, visualising the towers and its merged states as tree is quite impressive. Thanks for the LCA solution.

To me, Small-to-large merge sounds like a greedy approach. It would be helpful if you can elaborate the alternate solution.

mohitsamant

+13

If you are looking for dsu solution.... If you always merge smaller set to larger set then it is o(n log(n))... Because a single element will not change it set more than log(n) time..... Let say we have a element 'a' which is in set 1 of size x we merge set 1 to set 2 of size greter than x suppose y.... Than we have atleast 2*x element which get in same set as y>x..whenever we are merging we are atleast doubling the size of. set

_siummy

Statement of problem B was difficult to understand until watching the image at last as didn't know about the game.

roshan_mehta

+10

Seriously! You don't know stone paper scissor! LOL!

stocke777

r u patrick living under a rock?

bit_2

Can anyone explain to me why greedy works in C? It was kind of intuitive to me, I coded it up and it passed but I still can't figure out that why's it optimal?

smax

It's always optimal to take more skilled programmers over less skilled ones, and there is no advantage to expanding the team size once you've reached the minimum requirement of $$$x$$$ (since you risk adding a low-skill programmer that decreases the overall team skill below $$$x$$$, and you take programmers who could have otherwise formed more teams and improved the answer).

niteshchaurasia30

https://mirror.codeforces.com/contest/1380/submission/86713545

Can you please explain why i am getting memory limit exceeded on this solution of problem A?

sanju_rajora

I am trying some different approach,can anyone please tell me what is wrong in this approach. https://mirror.codeforces.com/contest/1380/submission/86678593

Sadakant

you are sorting it in non-decreasing order, sort it in non-increasing order

i_am_solaiman

I don't understand problem-B.Anyone help me to understand..And I don't know about this game.

gnudgnaoh

Seriously bro? There is an image explaining it at the end of the problem. If you still don't understand : wiki page

MarkZuckerberg

Why are submissions low on problems? Were they hard, imo first 3 were pretty easy?

-9

pavit_1809

+17

You didn't even gave the round......Better first participate in the live round and then give your wishful verdict on whether the problems were easy or tough and why there are more or less submissions on a particular problemset

-12

Do you even realize that this is an alt/troll handle

Geothermal

+21

Codeforces was down for the first half-hour of the round; by the time it came back up, the round was declared unrated and many competitors left.

jokerwyt

problem G. 'Let the values be x and y. If they differ by at least 2 (x≤y−2), then the smaller result can always be achieved by moving a regular chest from the larger one to the smaller one.' I could not understand the proof below. I indeed turn a coefficient y into a smaller one (x + 1), but how can I assign every regular chest to the old value, with the changes of this two interval lengths?

Sorry for the misread of the statement. Every chest's position can be changed.

spectre_gd

Can someone explain why the second solution for problem A works?

MikeTheCoder

Can someone explain in problem B why picking the greedy ci for the most frequent will somehow work for the rest of string?

How does that make sense? Can't there be a value in the string where ci fails?

spookywooky

Your choice string is played agains the given string on every position. This means, all positions of the two Strings are paired once. Or, in other words, it does not matter in which order you put the symbols into the choice string.

Since the order does not matter, every single position in your string conributes independend of any other position. Finally, for a single position it is obvious that the best choice is based on the frequency of the symbols.

harshilbhatia2001

My Video Solution of B and C where i have tried to explain my thought process and why the solution worked .

faisal_sohail

← Rev. 3 →

-6

hi,
problem D:
how to select a segment?
like for k=3,x=1,y=100,n=9
a=1,2,2,3,3,3,3,3,4
b=1,3,4

Trinadh724

It is given that elements are distinct

harry_122

yaswanth

I suppose it can be done in many ways. Store the index of each element occurring in a. Let's call it apos. Also make a copy of array a. Let's call it astrip (I know the naming is bad). Now while iterating with b, mark all positions in strip where this number occurred. astrip[apos[b[i]]] = some_identifier. Because all elements are unique, this'll work. Now just iterate through array astrip and figure out the segments. Along with this you also need to make sure apos[b[i]] > apos[b[i - 1]] because you want b to be a subsequence of a.

86693530

a.a.d.i.tya

Elements are pairwise distinct. Doesn't that mean something like 1,2,1,2,1,2 could be a possible test case?

My bad :(

aficio.nado

in question E merge towers: for the given test case [[5,1],[2],[7,4,3],[6]] are the towers before any query on merging tower 1 and 3 according to me it should be done like: from tower [5,1] ,1 goes to tower 3-> [5],[7,4,3,1] -> 1st operation from tower [7,4,3,1] , 1,3 and 4 goes to tower 1 -> [5,4,3,1],[7] -> 2nd operation from tower [5,4,3,1], 5,4,1 and 3 goes to 3rd tower -> [],[7,5,4,3,1] -> 3rd operation it can be done in three operation but it shows 5 as a result . Where am i wrong?

Put some clothes on and format the question ;)

The result must be one tower [7,6,5,4,3,2,1]. Somehow you are loosing the 2 and 6.

The rule for merging is fairly simple: Take the top segment from the tower where the 1 is, and put the whole segment onto the tower where it fits. The moved segments in the example would be:

[1]
[1,2]
[1,2,3,4]
[1,2,3,4,5]
[1,2,3,4,5,6]

The last move creates the complete tower.

CoderAnshu

We can also solve F by matrix-DP .. First we calculate the matrix for every dp transition .. then we just need the product of these matrices .. (To simplify append 0 at the begining and 9 at the end ) and build segTree in [0,n] and then remains only two point updates at index(x) and index(x-1) .. (Make sure to have dp[n+1]=1 (even if its nine ))

There's another solution O(n) for A.

As per the given condition, we can see that the element with value n will definitely satisfy this condition as middle element and the ends of the array as first and last element. (Because n will be bigger than anything and that's what we want here).
If n is at the ends of the array, then n can't be the answer. We ignore that element, update ends of the array and do the same thing again. The highest element in the array is now n - 1 and if it's somewhere in the middle, that should be the answer.
We'll keep trying the same for all elements and we'll know if the answer exists at all.

86668426

Can also be done with prefix and suffix max in 0(n)

d_tect

can anyone please explain what is this line doing in problem D solution res += (len - k) * y + x; . this line will be executed when we cannot perform berserk because one of the elements in segment is greater than both l and r and cost of berserk is lesser than fireball to delete everything. i thought this should have been res+=len/k*x so that we delete everything remaining using fireball. Thank you!!

The tutorial does the operations in irritating order. However, if the biggest monster is bigger than l and r we need to use Fire at least once. And independend of anything else, we need to use Berserk on at least len%k elements. The order of these two operations or the others operations does not matter.

NaimSS

In problem G why can we ignore the initial order of chests and sort? I was thinking on a case like 4 40 400 400 600 and k=1. Where can I put the mimic so that the answer gives 330 (as it does with the editorial solution)?

tfg

You misread the problem: "Print n integers — the k -th value should be equal to the minimum possible expected value of players earnings if the chests are placed into the rooms in some order and exactly k of the chests are mimics."

"the chests are placed into the rooms in some order and exactly k of the chests are mimics." so you can choose any order.

Oh. Now It makes sense. Ty

shahil_005

In B ,what if there is an extra constraint that "You will lose point if the bot's choice is superior",So doing the same thing which we actually did for the original problem,would it be still optimal ?

For Ex :"RRSP" ,and output "PPPP",
Win(1),Win(2),Win(3),Win(4)= (+1)+(+1)+(-1)+(0) = 1;
Avg = 1

It is still the case that every position is played against any other position. So the order of the symbols in the choosen string does not matter. Since the order does not matter it is still optimal to use one symbol for the whole string. As a pragmatic solution, just try all three possibilities and choose the best.

agrawal117

Anyone please explain the update part in problem F .
how we are doing updates ?

disgrace_2k

Just curious:

Does there exist some kind of dp solution for D?

Ahmadsm2005

Constraints are too high for a DP solution for problem C(assuming you mean by DP is to brute force and use dynamic programming to decrease number of total operations made).

vjvjain0

Disclaimer: It is a little messy because I tried to code as fast I could and submit it during contest.

Here you go! 87810909

Explanation

lakshay05

problem C is enjoyable

3141somethingpi

86766761 Can someone help me identify what did I do wrongly here on problem C?

31901271

If you start small, you are guilty of waste. M = 8, for example,,2,7,7,7,7,7,7 [1]; Instead of [7.7][7.7][7.7] [7.7] As for the answer greater than correct, if m=10,[4,4]; You only need 10/4=2, but (10/4)*2=8 does not equal 10

iabhishek15

In C I miss read the question and was thinking that each team should have a product at least x. can anyone tell how to solve if this was the question ??

rocww

In this case also, just sort the array and keep two variables. One containing the product of the present array and one containg the count of number of arrays. The code will look something like this: https://pastebin.com/zL2pxcfZ

← Rev. 4 →

I don't think it's that easy. here is the testcase

6 12
2 2 2 10 10 10

answer : 3 your code output: 2

Ya, it's not easy. Sorry for the wrong explanation. Need a better approach for this.

goingOn

I think the correct answer would be: 1. Because only the minimum element of the group and the size of the group matters. if I'm wrong I would be happy if u correct me.

I think i am not asking problem C. how about you read my comment again.

Jdee

Can anybody help me with Problem D Berserk and Fireball I am facing some implementation issues? My submission — 86799781 Thanks

-10

Do you really expect a meaningful answer to such a vague question?

Can you help me with my submission?

You noticed the diagnostics at the end of testcase 7?

Diagnostics
...runtime error: addition of unsigned offset to 0x13201820 overflowed to 0x13201818...

Haa But I couldn't make out the error like what does it mean?

I cannot spot the bug either. But I see some ways to greatly simplify your code.

Do not use a set for index. The values you are inserting are distinct and sorted, just use vector.

Additionally put a -1 as first element into that vector, and a n as last. So you can delete the copy of the main loops body.

The first loop where you collect index is unnice. Still not sure if there is an off by one somehow. You better loop over a[i] and check every index if a[i]==b[j]. If yes insert i and increment j.

tcapeta

upd:done

ay2306

awoo can you explain what 0,1,2,3 represent in the solution of problem F. Thank you.

awoo

0 = 00 — neither is taken
1 = 01 — leftmost isn't taken, rightmost is taken
2 = 10 — leftmost is taken, rightmost isn't taken
3 = 11 — both taken

dhruv_garg

@pikmike Can you please explain me the problem -e test case when we merge the 3 and 1 tower how the ans coming out to be 4 instead of 3 . Ok I can tell you how i got 3.

1st tower contain — 5 1 and 3rd tower contain — 7 4 3

1st move — you shift (1) from tower 1 to tower 3 now 3rd tower contain — 7 4 3 1 and 1st tower conatin — 5

2nd move — you shift (4 3 1) from tower 3 to tower 1 now tower 3 contain -7 and tower 1 conatin — 5 4 3 1

3rd move — now you shift (5 4 3 1) from tower 1 to tower 3 now tower 3 contain — 7 5 4 3 1 and tower 1 conatin nothing .So my answer coming out to be 3 instead of 4 . I know i am missing something could you please point out.Thankyou.

BledDest

Reread the problem statement carefully.

We are not calculating the number of operations needed to merge the towers in the query. Instead, after each query, we want to calculate the number of operations required to merge all current towers into one.

TShT

In problem E it is not at all clear how to achieve these answers.

sumit_gaurav

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

https://www.youtube.com/playlist?list=PLrT256hfFv5UUIBTJBUL7ZlZVHaWWEmGB

ivan100sic

Was F inspired by this meme?

cote

I still don't understand the tutorial for F.

Specifically, I don't understand how a segment tree could optimize this dp. What will the nodes store and what the merging looks like. I get the part about the dp but become totally confused when they start talking about segment tree.

Can anyone explain it for me? Maybe some visual example would help. Thanks in advance.

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