Разбор Educational Codeforces Round 141

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

№	Пользователь	Вклад
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
7	SecondThread	150
9	orz	146
10	pajenegod	145

Разбор

Решение (BledDest)

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    if a[0] == a[n - 1]:
        print('NO')
    else:
        print('YES')
        print(a[n - 1], end = ' ')
        print(*(a[0:n-1]))

1783B - Matrix of Differences

Идея: BledDest

Разбор

Решение (Neon)

#include <bits/stdc++.h>

using namespace std;

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

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    int l = 1, r = n * n, t = 0;
    forn(i, n) {
      forn(j, n) {
        if (t) a[i][j] = l++;
        else a[i][j] = r--;
        t ^= 1;
      }
      if (i & 1) reverse(a[i].begin(), a[i].end());
    }
    forn(i, n) forn(j, n) cout << a[i][j] << " \n"[j == n - 1];
  }
}

1783C - Yet Another Tournament

Идея: BledDest

Разбор

Решение (Neon)

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    auto b = a;
    sort(b.begin(), b.end());
    int ans = 0;
    for (int i = 0; i < n && b[i] <= m; ++i) {
      m -= b[i];
      ++ans;
    }
    if (ans != 0 && ans != n && m + b[ans - 1] >= a[ans]) ++ans;
    cout << n + 1 - ans << '\n';
  }
}

1783D - Different Arrays

Идея: BledDest

Разбор

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

const int ZERO = 100000;

int dp[2][ZERO * 2];

void recalc(int x)
{
    for(int i = 0; i < ZERO * 2; i++)
        dp[1][i] = 0;

    for(int i = 0; i < ZERO * 2; i++)
    {
        if(dp[0][i] == 0) continue;
        int nx = x + i;
        dp[1][nx] = add(dp[1][nx], dp[0][i]);
        if(nx != ZERO)
            dp[1][2 * ZERO - nx] = add(dp[1][2 * ZERO - nx], dp[0][i]);
    }

    for(int i = 0; i < ZERO * 2; i++)
        dp[0][i] = dp[1][i];
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    dp[0][ZERO] = 1;
    for(int i = 1; i + 1 < n; i++)
        recalc(a[i]);
    int ans = 0;
    for(int i = 0; i < ZERO * 2; i++)
        ans = add(ans, dp[0][i]);
    cout << ans << endl;
}

1783E - Game of the Year

Идея: BledDest

Разбор

Решение (BledDest)

#include <bits/stdc++.h>

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

using namespace std;


int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int n;
		scanf("%d", &n);
		vector<int> a(n), b(n);
		forn(i, n) scanf("%d", &a[i]);
		forn(i, n) scanf("%d", &b[i]);
		vector<int> dx(n + 1);
		forn(i, n) if (b[i] < a[i]){
			++dx[b[i]];
			--dx[a[i]];
		}
		forn(i, n) dx[i + 1] += dx[i];
		vector<int> ans;
		for (int k = 1; k <= n; ++k){
			bool ok = true;
			for (int nk = k; nk <= n; nk += k)
				ok &= dx[nk] == 0;
			if (ok)
				ans.push_back(k);
		}
		printf("%d\n", int(ans.size()));
		for (int k : ans) printf("%d ", k);
		puts("");
	}
	return 0;
}

1783F - Double Sort II

Идея: BledDest

Разбор

Решение (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int N = 5043;

vector<int> g[N];
int mt[N];
int u[N];
vector<vector<int>> cycle[2];
vector<int> a[2];
int n;
int vs[2];
vector<vector<int>> inter;

bool kuhn(int x)
{
    if(u[x]) return false;
    u[x] = true;
    for(auto y : g[x])
    {
        if(mt[y] == x) continue;
        if(mt[y] == -1 || kuhn(mt[y]))
        {
            mt[y] = x;
            return true;
        }
    }
    return false;
}

int find_intersection(const vector<int>& x, const vector<int>& y)
{
    for(auto i : x)
        for(auto j : y)
            if(i == j)
                return i;
    return -1;
}

int main()
{
    scanf("%d", &n);
    for(int k = 0; k < 2; k++)
    {
        a[k].resize(n);
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &a[k][j]);
            a[k][j]--;
        }    
    }

    for(int k = 0; k < 2; k++)
    {
        vector<bool> used(n);
        for(int i = 0; i < n; i++)
        {
            if(used[i]) continue;
            vector<int> cur;
            int j = i;
            while(!used[j])
            {
                cur.push_back(j);
                used[j] = true;
                j = a[k][j];            
            }
            cycle[k].push_back(cur);
        }
        vs[k] = cycle[k].size();
    }

    inter.resize(vs[0], vector<int>(vs[1]));

    for(int i = 0; i < vs[0]; i++)
        for(int j = 0; j < vs[1]; j++)
        {
            inter[i][j] = find_intersection(cycle[0][i], cycle[1][j]);
            if(inter[i][j] != -1)
                g[i].push_back(j);
        }

    for(int i = 0; i < vs[1]; i++)
        mt[i] = -1;
    for(int i = 0; i < vs[0]; i++)
    {
        for(int j = 0; j < vs[0]; j++)
            u[j] = false;
        kuhn(i);
    }
    
    set<int> res;
    for(int i = 0; i < n; i++) res.insert(i);
    for(int i = 0; i < vs[1]; i++)
        if(mt[i] != -1)
            res.erase(inter[mt[i]][i]);

    printf("%d\n", res.size());
    for(auto x : res) printf("%d ", x + 1);
    puts("");
}

1783G - Weighed Tree Radius

Идея: BledDest

Разбор

Решение 1 (adedalic)

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#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) {
	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;

const int LOG = 18;
const int N = int(2e5) + 55;

int n;
vector<int> a;
vector<int> g[N];

inline bool read() {
	if(!(cin >> n))
		return false;
	a.resize(n);
	fore (i, 0, n)
		cin >> a[i];
	fore (i, 0, n - 1) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	return true;
}

int p[LOG][N];
int h[N], tin[N], tout[N], T = 0;

void precalcLca(int v, int pr) {
	tin[v] = T++;
	h[v] = 0;
	if (pr != v)
		h[v] = h[pr] + 1;
	p[0][v] = pr;
	fore (pw, 0, LOG - 1)
		p[pw + 1][v] = p[pw][p[pw][v]];

	for (int to : g[v]) {
		if (to == pr)
			continue;
		precalcLca(to, v);
	}
	tout[v] = T;
}

bool isParent(int l, int v) {
	return tin[l] <= tin[v] && tout[v] <= tout[l];
}

int lca(int u, int v) {
	if (isParent(u, v))
		return u;
	if (isParent(v, u))
		return v;
	
	for (int pw = LOG - 1; pw >= 0; pw--) 
		if (!isParent(p[pw][v], u))
			v = p[pw][v];
	assert(!isParent(v, u));
	assert(isParent(p[0][v], u));
	return p[0][v];
}

int getFarthest(int s) {
	vector<int> used(n, 0);
	queue<int> q;

	used[s] = 1;
	q.push(s);
	int v;
	while (!q.empty()) {
		v = q.front(); 
		q.pop();
		for (int to : g[v]) {
			if (used[to])
				continue;
			used[to] = 1;
			q.push(to);
		}
	}
	return v;
}

int getDist(int u, int v) {
	return h[u] + h[v] - 2 * h[lca(u, v)];
}

const int M = int(2e5);
vector<pt> ops[4 * M];

void setOp(int v, int l, int r, int lf, int rg, const pt &op) {
	if (l >= r || lf >= rg) return;
	if (l == lf && r == rg) {
		ops[v].push_back(op);
		return;
	}
	int mid = (l + r) / 2;
	if (lf < mid)
		setOp(2 * v + 1, l, mid, lf, min(mid, rg), op);
	if (rg > mid)
		setOp(2 * v + 2, mid, r, max(lf, mid), rg, op);
}

void updDiam(int &s, int &t, int &curD, const pt &op) {
	int v = op.x;
	a[v] = op.y;

	int ns = s, nt = t, nD = curD;

	vector<pt> cds = {{s, v}, {v, t}, {v, v}};
	for (auto &c : cds) {
		int d1 = getDist(c.x, c.y);
		if (nD < a[c.x] + d1 + a[c.y]) {
			nD = a[c.x] + d1 + a[c.y];
			ns = c.x, nt = c.y;
		}
	}
	s = ns;
	t = nt;
	curD = nD;
}

vector<int> ans;

void calcDiams(int v, int l, int r, int s, int t, int curD) {
	for (auto &op : ops[v])
		updDiam(s, t, curD, op);
	if (r - l > 1) {
		int mid = (l + r) / 2;
		calcDiams(2 * v + 1, l, mid, s, t, curD);
		calcDiams(2 * v + 2, mid, r, s, t, curD);
	}
	else
		ans[l] = (curD + 1) / 2;
	
	for (auto &op : ops[v])
		a[op.first] = 0;
}

inline void solve() {
	precalcLca(0, 0);
	int s = getFarthest(0);
	int t = getFarthest(s);

	int m;
	cin >> m;
	vector<int> lst(n, 0);
	fore (i, 0, m) {
		int v, x;
		cin >> v >> x;
		v--;

		setOp(0, 0, m, lst[v], i, {v, a[v]});
		lst[v] = i;
		a[v] = x;
	}
	fore (v, 0, n)
		setOp(0, 0, m, lst[v], m, {v, a[v]});

	ans.resize(m, -1);
	a.assign(n, 0);
	calcDiams(0, 0, m, s, t, getDist(s, t));

	fore (i, 0, m)
		cout << ans[i] << '\n';
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

Решение 2 (adedalic)


#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) {
	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;

const int LOG = 18;
const int N = int(2e5) + 55;

int n;
vector<int> a;
vector<int> g[N];

inline bool read() {
	if(!(cin >> n))
		return false;
	a.resize(n);
	fore (i, 0, n)
		cin >> a[i];
	fore (i, 0, n - 1) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	return true;
}

struct Lca {
	vector<int> log2, tin;
	vector< vector<int> > hs;
	int T = 0;

	void dfs(int v, int p, int cdepth) {
		tin[v] = T++;
		hs[0][tin[v]] = cdepth;
		for (int to : g[v]) {
			if (to == p)
				continue;
			dfs(to, v, cdepth + 1);
			hs[0][T++] = cdepth;
		}
	}

	void init() {
		log2.assign(2 * n, 0);
		fore (i, 2, sz(log2))
			log2[i] = log2[i / 2] + 1;
		hs.assign(log2.back() + 1, vector<int>(2 * n, INF));

		tin.assign(n, 0);
		T = 0;

		dfs(0, -1, 0);
		assert(T < 2 * n);

		fore (pw, 0, sz(hs) - 1) {
			fore (i, 0, T - (1 << pw))
				hs[pw + 1][i] = min(hs[pw][i], hs[pw][i + (1 << pw)]);
		}
	}

	int getMin(int u, int v) {
		if (tin[u] > tin[v])
			swap(u, v);
		int len = log2[tin[v] + 1 - tin[u]];
		int d = min(hs[len][tin[u]], hs[len][tin[v] + 1 - (1 << len)]);
//		cerr << u << " " << v << ": " << d << endl;
		return d;
	}
	inline int getH(int v) {
		return hs[0][tin[v]];
	}
} lcaST;

int getFarthest(int s) {
	vector<int> used(n, 0);
	queue<int> q;

	used[s] = 1;
	q.push(s);
	int v;
	while (!q.empty()) {
		v = q.front(); 
		q.pop();
		for (int to : g[v]) {
			if (used[to])
				continue;
			used[to] = 1;
			q.push(to);
		}
	}
	return v;
}

int getDist(int u, int v) {
	return lcaST.getH(u) + lcaST.getH(v) - 2 * lcaST.getMin(u, v);
}

const int M = int(2e5);
vector<pt> ops[4 * M];

void setOp(int v, int l, int r, int lf, int rg, const pt &op) {
	if (l >= r || lf >= rg) return;
	if (l == lf && r == rg) {
		ops[v].push_back(op);
		return;
	}
	int mid = (l + r) / 2;
	if (lf < mid)
		setOp(2 * v + 1, l, mid, lf, min(mid, rg), op);
	if (rg > mid)
		setOp(2 * v + 2, mid, r, max(lf, mid), rg, op);
}

void updDiam(int &s, int &t, int &curD, const pt &op) {
	int v = op.x;
	a[v] = op.y;

	int ns = s, nt = t, nD = curD;

	vector<pt> cds = {{s, v}, {v, t}, {v, v}};
	for (auto &c : cds) {
		int d1 = getDist(c.x, c.y);
		if (nD < a[c.x] + d1 + a[c.y]) {
			nD = a[c.x] + d1 + a[c.y];
			ns = c.x, nt = c.y;
		}
	}
	s = ns;
	t = nt;
	curD = nD;
}

vector<int> ans;

void calcDiams(int v, int l, int r, int s, int t, int curD) {
	for (auto &op : ops[v])
		updDiam(s, t, curD, op);
	if (r - l > 1) {
		int mid = (l + r) / 2;
		calcDiams(2 * v + 1, l, mid, s, t, curD);
		calcDiams(2 * v + 2, mid, r, s, t, curD);
	}
	else
		ans[l] = (curD + 1) / 2;
	
	for (auto &op : ops[v])
		a[op.first] = 0;
}

inline void solve() {
	lcaST.init();
	int s = getFarthest(0);
	int t = getFarthest(s);

	int m;
	cin >> m;
	vector<int> lst(n, 0);
	fore (i, 0, m) {
		int v, x;
		cin >> v >> x;
		v--;

		setOp(0, 0, m, lst[v], i, {v, a[v]});
		lst[v] = i;
		a[v] = x;
	}
	fore (v, 0, n)
		setOp(0, 0, m, lst[v], m, {v, a[v]});

	ans.resize(m, -1);
	a.assign(n, 0);
	calcDiams(0, 0, m, s, t, getDist(s, t));

	fore (i, 0, m)
		cout << ans[i] << '\n';
}

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;
}

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

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

Sayachyan

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

finally

→ Ответить

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

Ай-яй-яй, забыла переключать язык.

Heap_OverFlow

Thanks for the lightning fast editorial ✪ω✪ When will systesting take place? It hasn't been done yet also there are unjudged hacks.

+37

Thanks for the lightning fast editorial ✪ω✪ When will systesting start?

YocyCraft

+11

There's some bug of hacking system. Waiting for admins to fix it.

Muhammad_Aneeq

I really enjoyed this Educational Codeforces Round 141 (Rated for Div. 2) and its quite fun giving this contest. I am anxiously waiting for next Educational round.So please make it quick.Thankyou!!

PYD1

Is it possible to use "centroid decomposition tree" to solve problem G?

BledDest

You can use it, but it's a bit difficult and annoying to implement. The main idea of solution is similar to the one described in the official editorial.

Basically, you need to be able to process the following query: for a vertex $$$v$$$, find a vertex $$$u$$$ such that $$$a_u + d_v(u)$$$ is the maximum possible. You can iterate on their common centroid $$$c$$$, and, for that centroid, query the vertex with maximum possible value of $$$a_u + d_c(u)$$$ in the subtree of that centroid. The difficult thing is that our query should exclude the vertices which have some deeper common centroid with $$$v$$$ than $$$c$$$, because for those vertices, $$$c$$$ may not be on the path from $$$u$$$ to $$$v$$$, and $$$d_v(u) \ne d_c(v) + d_c(u)$$$. To handle that, in each centroid, let's sort the vertices according to the first vertex on the path from the centroid to them; when we query the centroid $$$c$$$ from vertex $$$v$$$, we exclude the segment containing "bad" vertices from our query, so it is a combination of prefix maximum query + suffix maximum query. So, a maximum segment tree in each centroid does the trick.

bmerry

+26

I managed to write a centroid decomposition solution after the contest which I think is different to BledDest's solution. It uses the diameter idea from the editorial, but not the offline DCP trick. My implementation is offline but it could easily be converted to an online algorithm at the expense of some memory.

For each centroid tree, and for each subtree of the root of that centroid tree, keep a multiset of $$$a_u + d_v(u)$$$ (where $$$v$$$ is the centroid). For each the centroid tree, keep a multiset of the maximums of the per-subtree multisets. That lets you find a potential diameter (but only considering the paths that pass through the centroid), by taking the two largest elements from that multiset. Each update requires $$$O(\log^2 n)$$$ time (each vertex belongs to $$$O(\log n)$$$ trees in the decomposition, and updating multisets requires an extra factor of $$$O(\log n)$$$).

aryanc403

+19

G can be solved using Shame Cube Algorithm

G
G but with simplified problem statement
G but with simplified solution

tushaar9876

n^1.5 solution also works for E, https://codeforces.com/contest/1783/submission/188632405 Here is my solution, it is similar to the solution mentioned in the tutorial. (PS systesting hasn't started so not sure if n root(n) solution will work for system test case but it should theoretically)

aditm

← Rev. 4 →

So to solve E, first we come to the conclusion just like mentioned in the editorial that if k is a valid solution then $$$\forall \ i$$$, such that $$$a_i>b_i$$$ and there shouldn't exist any multiple of k in the range $$$[b_i,a_i)$$$ (or $$$[b_i,a_i-1]$$$ ), more formally $$$\forall \ x,\ b_i\leq x < a_i$$$ , $$$x\ \% \ k\ !=0$$$.

Note that for i's such that $$$a_i\leq b_i$$$ any $$$k$$$ could be valid number to kill the i'th boss, so they are not our point of interests.

Thus the question is now simplified to the following problem, we are given certain forbidden ranges, where k's any multiple if lies, then it can't be the valid solution.

And to track these ranges we use range updates using difference array concept. We can build an array (suppose called pre) initialised with 0, and do $$$pre[b_i]$$$+=1 and $$$pre[(a_i-1)+1]$$$+=-1 and then do the prefix sum on this array. After this $$$pre[i]$$$ would store the count of forbidden ranges in which i lies. Thus now we can check $$$\forall \ k$$$, $$$1 \leq k \leq n$$$ , whether k is a valid solution or not in a sieve manner. Time complexity : $$$O(n\log{}n)$$$ Implementation

+12

Your solution sounds exactly the same as the editorial. I don't see where you get $$$O(n\log \log n)$$$ from; it look like $$$O(n\log n)$$$ to me.

← Rev. 3 →

Segment tree can also solve E. Although it's more complicated but time complexity is same O(n*log(n))

I used segment tree too, but I failed. Can you help me reviewing?my submission...

← Rev. 2 →

The code need to be rewritten. I even cannot understand how it passed first 10 tests.

In fact, you just need to update range [b[i], a[i]-1] where a[i]>b[i]. And for each k, if any multiple of k is in any such range, k is bad.

Thanks! I have found my mistake through your inspiration.

Oops my bad, I wrongly calculated sieve's complexity, when only primes factors are traversed then it is nloglogn. Thanks for pointing it out

tgp07

Can someone help me figure out why this submission for problem E TLE's? I'm pretty sure that the time complexity is O(nlogn)

188635530

sergeev.PRO

There is another sol for E. At first delete all pairs, where ai <= bi(now we need check is it true that ai / k == bi / k for all k). After that we will iterate over all k and for ki iterate over all x, that n / ki <= x. And count the number of pairs, that ai / ki = x and bi / ki = x(its not hard to calculate with scanline and fenwik). Its easy to see, that ki can be answer if and only if the sum of all x will be cnt of pairs. Now we check this parameter and calculate answer Time complexity will be O(nlog(2)nlog(f)n) Submission

OMG_wc

+18

A-F video editorial for Chinese:

BiliBili

Epilogue

Nice contest but I only solved A :V

drdilyor

E can be solved without using any brain with static range max :) 188486103

rshao19

Did roughly the same thing, except I didn't know how to implement sparse table so I just used segment tree :)

Taha

Can you explain further?

Is problem A still solvable if a[i] can be negative?

RDDCCD

I think it is, but we need lots of disscusion after sorting.

Or random_shuffle can be a way, it's impossible to hack random_shuffle solutions I think, but pay attention to 0.

epsilon_573

Video Solution for Problem C and Problem D.

skytyf

I used unordered_map in D during contest and I feel so lucky to Accepted with 1996ms time. 188483495

Kalosmi

Neon Thanks for solution to problem B, Very nice implementation, Learnt a lot.

battle_beast

Can anyone explain the solution of the problem F? I don't understand the editorial

NeoYL

← Rev. 9 →

why does my page shows that i am unrated for this round??????????????

_AIH_

Is this contest is unrated? Because contest is showing unrated now.

alreadyselfish

Is this contest unrated now? If so, why does this happen?

rcht

Rating changes are rolled back temporarily sometimes, but they always come back after being updated.

Roronoa__Zoro

why is rating still not updated. In morning it showed rating but after few hours it is again removed

Southernwood

Can we solve E by delete potential answer?
Like, for every a[i] > b[i], delete all k that a[i] <= k < b[i], count how many element had been deleted, and printf all those remains?
Still , I can't figure out what's wrong with my idea or my code , can anybody help me? 188823323

Sinocchi

Not sure what's the mistake here, this solution should give the correct answer.

However, it will most likely TLE as it's $$$O(n^2)$$$ complexity

Twits

For problem C If i use this test case,the ans should be 1?

test case

Win against 2 4 4 = 3 win

2 have 0 win
2 have 1 win
3 have 3 win
4 have 3 win
4 have 3 win

Editorial code output is 2

IKn0wYou

last index will have 4 wins here as (number of i<j=4)

Why 4 not 3?

Last index(index 4) win only against index 0,1,2

We beat index 0,3,4 so last index lose against us

As in your case we won against indexes {0,3,4} so will have 3 wins. 1. index 0 = (indexes<0) + 0(lost against us) = 0 wins. 2. index 1 = (indexes<1) + 1(win against us) = 2 wins. 3. index 2 = (indexes<2) + 1(win against us) = 3 wins. 4. index 3 = (indexes<3) + 0(lost against us) = 3 wins. 5. index 4 = (indexes<4) + 0(lost against us) = 4 wins. index 4 will have 4 wins but we only have 3 wins so ans is 2.

Ahh i see i misunderstood the condition i thought win condition is ai<aj not i<j. Thx bro

Socrates1232

I really like to know how to solve problems like G in contests. I spent almost half an hour trying to grasp the concept of "wp(x,y)" and doing all the provement myself and yet still unable to understand why to construct such variate at the first place. In my opinion, there can be many different variates to construct and each with so many properties that might contribute to solving the problem. For me, even if I managed to construct this "wp(x,y)", I can't bring myself to actually exam all its features and not to mention figuring out which one among them is the cruial one. So anyone who solved this problem by themselves willing to share some insights?

kaihong

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

1
3 0
1 1 0

If this is the test case for problem C what will be the answer? The editorial answer output is 3, but isn't it should be 2? BledDest

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

We can only win against the opponent $$$3$$$. So, we have $$$1$$$ win, but both the opponent $$$3$$$ and the opponent $$$2$$$ have $$$2$$$ wins each ($$$3$$$ wins against $$$2$$$ and $$$1$$$, $$$2$$$ wins against $$$1$$$ and us). So, two players are above us, and our place is the $$$3$$$-rd.

forelax

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

In tutorial for G, at the first bullet point, please change the wording to

There is a vertex v on diameter path (x,y)...

Thank you.

SuperMo

7 недель назад, # |

problem c

this test case is saying that it should be 1 can someone tell me how

2 0
1 0

if I win against the 0 then the 1 will win on me and will win on the zero so he is 2 and i'm one so he is the first place and i'm the second so what is going on here ??

AvaraKedavra

6 недель назад, # ^ |

Note — I am assuming 1 indexing. Player 1 is at index 1 and player 2 is at index 2.

Since, you have 0 energy, you can only win against player 2. So, player 1 will beat you. Since player 2 is at higher index (index 2) than player 1 (index 1), he will beat player 1.

Thus total wins of each player are —
You — 1 (You beat player 2)
Player1 — 1 (He beats you)
Player2 — 1 (He beats player 1)

Now, rank = No of players whose score is strictly greater than your score + 1

No, player has score strictly greater than you.

Hence, rank = 0+1 = 1

yes I mis read the statement I thought player can win over another if his points are higher, but thanks any way

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