Разбор Educational Codeforces Round 98

Разбор

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

Идея: adedalic

Разбор

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

Идея: BledDest

Разбор

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

Идея: 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;
}

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

Идея: BledDest

Разбор

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

Идея: adedalic

Разбор

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

Идея: adedalic

Разбор

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

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

ll a[n]; ll mx = 0 ; for (ll i= 0;i<n;i++) { cin>>a[i] ; mx = max(mx, a[i]); } if (n==2) { cout<<0<<endl; return ; } ll sum = accumulate(a , a+n , 0) ; ll temp = mx*(n-1)*(1ll) ; if (sum == temp) cout<<0<<endl; else if(sum <temp) cout<<abs(sum-temp)<<endl; else { for (ll i=1;i<=100000;i++) { if (((n-1)*i*(1ll)) == sum) { cout<<0<<endl; return ; } else if (((n-1)*i*(1ll)) > sum) { cout<<(abs(n-1)*i*(1ll) - sum)<<endl; return; } } }

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

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

mr_practice001

5 лет назад, скрыть # |

+18

What about rating updates?

→ Ответить

darthrevenge

+28

I think, in tutorial G, Alice and Bob had been swapped. It's Alice who has one starting vertex, and it's Bob who chases her, not vice versa.

awoo

5 лет назад, скрыть # ^ |

← Rev. 2 →

+10

Oh, indeed. I've been told the problem with them reversed and I haven't read the actual statement haha. Will fix in a sec, thanks.

lovetiger

why i get tle in test case 20 of problem E

my submission : 99017296

logic

Comparator for sorting should follow strict weak ordering. If $$$a=b$$$ then it should always return false, otherwise it's undefined behavior.

thanks it work now .

habibie.lukman

man

MARK42092

← Rev. 3 →

+14

If anyone didn't understand B. Here is an easy solution-

For solution to exist let us consider an element any index i. Then, for solution to exist we should be able to increment all values at all indexes to the max value in the array because we can't decrement the max value anyway.

Thus, a[i]>=(a[max]-a1)+(a[max]-a2)......(a[max]-a[max])
or, a[i]>=a[max]*n-1-(S-a[i]) where S is total sum of all elements.
or, S>=a[max]*n-1;

So solution boils down to two cases-

1. When S<a[max]*n-1 then the answer is just the difference of these two.

2. If S>a[max]*n-1 then (S-a[max]*n-1) should be equally divisible by (n-1), so just increment S until divisible by (n-1) and the answer is difference of the two.

You can look at my submission here

put_peace

I had exactly same thought process, https://mirror.codeforces.com/contest/1452/submission/98940264.

Yes, exactly we both used the same logic and so I thought it may help some people if they were thinking this logic but couldn't get it properly. Did I explain it clearly?

Dev_Manus

Nicely explain . Thanks

Ankit_12

-39

My code gives me wrong answer in test case 3 any one help Question no B

void solve() { ll n; cin>>n;

}

Thallium54

use spoiler please

epsilon_573

Try using 0ll, in std:: accumulate, otherwise it gives integer overflow.

fan_balae

Proof by Induction for problem D is great but can someone tell me if there is a mathematical proof for that?

practicener

If we have a tower with power p, it will cover 2p-1 spots, thus the length of the subsegment covered by a tower is always odd.Now we need to find a way to divide a length of n into a number of odd length subsegments. This can be done via dynammic programming, which reduces to finding the nth Fibonacci number. In the end , just divide this by 2^n.

I'm sorry but I didn't need the proof for the solution to this problem. I was wondering how did that function get reduced to just finding the Fibonacci number for a particular input.(which was proved by Induction by the Editorialist)

GoatTamer

+19

f(n) = f(n-1) + f(n-3) + f(n-5) + .... f(n-2) = f(n-3) + f(n-5) + .... thus f(n) = f(n-1) + f(n-2) Is this what you were looking for?

Yeah exactly, thanks for putting it that way. Made it so easy to understand.

lazomaniac

i didnt get it, can you explain how that comment helped you? i m still confused

Just look at what he wrote:

f(n)= f(n-1) + f(n-3) + f(n-5) + .... The above equation should be sufficient to tell you why is this the answer to the problem. You can occupy 1,3,5 ... positions at a time let us call it k and question is reframed as finding the solution to the remaining f(n-k) values which is what the equation above tells.

Now, Just replace n by n-2 in the above equation and we get,
f(n-2) = f(n-3) + f(n-5) + .... This is just the same as f(n) without the f(n-1) part.

thus f(n) = f(n-1) + f(n-2)

PurpleCrayon

Here's the intuitive proof I came up with while upsolving.

First let's solve it like a normal dp problem (forgetting about the fibonacci numbers). We sweep from left to right. Let $$$dp[i]$$$ mean the number of ways to cover only the first $$$i$$$ positions.

How do our transitions work? First, $$$dp[0] = 1$$$ because there is one way to cover the first $$$0$$$ positions (don't have any towers at all). Now loop over all i's (from left to right).

Consider the current $$$dp[i]$$$. We can cover some range with exactly one tower if and only if the length of the segment is odd (so we can put the tower in the midpoint). So $$$dp[i]$$$ is equal to the sum of all dp values where the index has a different parity than i (so $$$dp[i] = dp[i-1]+dp[i-3]+dp[i-5]...$$$). Though this would work, it runs in $$$O(n^2)$$$, so it needs to be optimized.

The optimization is pretty simple. Because you don't care about the actual values of all previous dp's but just the parity. So instead of storing the whole dp array, just have it store 2 values, $$$dp[0]$$$ and $$$dp[1]$$$. $$$dp[0]$$$ stores the numbers of ways to cover an even prefix, and $$$dp[1]$$$ stores the number of ways to cover an odd prefix.

You still loop from 1 to n but the transitions are now $$$dp[i \mod 2] = dp[i \mod 2] + dp[1-(i \mod 2)]$$$. This is exactly the Fibonacci recurrence.

Hope this was helpful! Thanks!

That's a really nice way to think about it. Thanks.

tanishq_code_c

hey thanks for sharing your idea . I have implemented the same idea with bottom up DP. but i am not able to do the same with top down DP. Can you please help me with that ?

chick_magnet

I had a different approach to this problem which is quite intuitive imo. We are effectively choosing a subset out of $$$n$$$ towers such that the sum of powers of those towers cover the entire range $$$1-n$$$.This is equivalent to number of odd integral solutions of the equation $$$ p_1 + p_2 + ... + p_r = n $$$.This can be found out easily by converting it to the form $$$ (2*x_1 + 1) + (2*x_2 + 1) + .. + (2*x_r + 1) = n $$$ and finding non negative integral solution for $$$x_1 , x_2 ,... x_r$$$. Multiply this with the probability of choosing $$$r$$$ towers = $$$1/{2^{n}}$$$ to get the required answer solution

nagaraj41

Thank you very much! It's a great solution.

Samaun

i am sorry, this might sound dumb but in you solution , ncr(d+x-1,x-1) here what are you actually choosing and from what

number of non negative integral solutions of the equation $$$x_1 + x_2 + ... +x_r=d$$$ is $$$d+r-1\choose r-1$$$

Focus_2000

great solution

PauloMiranda98

Why this Solution do not get TLE in problem G? I solved only with bfs/dfs. There is some property?

jinmingli

As in Tutorial, this solution is at most $$$O(nlog^2n)$$$

makki24

In Problem D Editorial

How this statement is true?

Covering all towns can be expressed as splitting n into the sum of several positive odd integers

Anyone, Please Explain.

jimm89

Each town that has power must power itself, and an equal number of towns either side of it.

Suppose it powers K towns to its left, then it must also power K towns to its right. So in total it powers 2*K+1 towns.

All the towers together power N towns, and the set is partitioned such that no town is powered twice. As such,

N = sum (i = 1 to j) (2*Ki + 1), where there are j towns receiving power directly, and the ith town powers Ki either side of it.

The numerator of the answer is the number of unique sets of j and K1,...,Kj such that the equality holds.

Thanks a lot. I got it now.

kariyeno

What is the logic of taking max of the array in calculation of k for B?

We need an end state where each of the n-1 boxes has exactly (TOTAL)/(n-1). Suppose we choose one of the non-max boxes to redistribute: then all the boxes must have at least the max starting value, since we cannot take any away. Therefore max*(n-1) is a lower bound for the total number.

yeah but why would there be atleast max in each box?

Because if there is one box with max, we can't take any out of this box (if redistributing from any of the others). So that box must finish with at least max, and we require all the boxes to finish with the same number, so they must also have at least max.

code_SWAMI

IN PROBLEM B Why (a.sum() + n — 2) / (n — 1) and not (a.sum()) / (n — 1) i didn't get it

guddu75

the formula to get ceil of(x/y) is (x+(y-1))/y

Okk. But when I write ceil function, ceil(x/y), it throws an error, but writing (x+y-1)/y goes successful.

ligaydima

Maybe you forgot to cast long double/float/double type to this fraction. For example: ceil(5 / 2) = ceil(2) = 2, but ceil(5.0 / 2) = ceil(2.5) = 3.

rgnerdplayer

But actually you should never try to use floating point numbers then use ceil, always opt to integer operations if possible.

MadhuramJ

Can anybody pls help me.

I am getting index out of bounds even though it looks correct.

Problem E.

My idea is mostly the same.

Sorting based on l+r. Storing count of tasks upto ith task in pref.

table[i][j] stores sum of tasks of first j (li,ri) pairs for k consecutive tasks = [i,i+k-1].

finally all pairs from 1 to ind-1 go to [i,i+k-1] and rest to [j,j+k-1] [ind is index where l+r > i+j+k-1 ... (r-j > i+k-1-l)]

danish_imam

-13

Why does this give same results, in modular exponentiation?

ll powe(ll x, ll y){
x = x%mod, y=y%(mod-1);
ll ans = 1;
while(y>0){
if (y&1){
ans = (1ll * x * ans)%mod;
}
y>>=1;
x = (1ll * x * x)%mod;
}
return ans;
}

than this

ll powe(ll x, ll y){
x = x%mod;
ll ans = 1;
while(y>0){
if (y&1){
ans = (1ll * x * ans)%mod;
}
y>>=1;
x = (1ll * x * x)%mod;
}
return ans;
}

The only difference is we do y=y%(mod-1) in the first function.

Edit: figured it out its fermat's theorem, thanks everyone

its_Atrap

Why don't people use spoiler while commenting there code?

Isn't your question obvious, let say we want to compute 2^123097521478997542 mod m, then what do you think will be faster computing 2^123097521478997542 mod m or first compute y mod m-1 which will be smaller than equal to y, then compute power?

The answer is obvious, but I remember there was a problem in which the input size it self exceeds mod-1 and everyone who did pow=pow%(mod-1) in advance got WA, be careful.

JNU_dh_AK_WF

Why solutions with complexity O(nmk) can get AC for problem E? The example are below: submission 1 and submission 2

upd: submission 2 has been hacked with the result of WA. But no one could made it TLE during the hacking phase.

code_warrior

Can someone explain problem E's solution a bit more.Thanks in advance! xD!!

jszz

Problem E,why the solution is right?I spend a long time understanding the code,but can't prove it's correctness.The tutorial seems to ignore this.

nubir345

you may think that algorithm is incorrect because of prefix and suffix and that one of them may contain some element which should have been in the other one but it doesn't matter because answer for cases like this will not be the final answer anyway because we are considering all possibilities and final answer will be the case where the conditions are satisfied.

oh!miaoa~zhenbuchuo!thank you for your reply!

leviosa317

Why i get tle for B?

submission : 99050069

whatever error you meet,you can see the data,the data you tle has sum=5e9,and n-1=4,and ma=1e9,your ma should add many times before you can break,so you tle

BRAINIAC77

There is another nice approach to Problem D using combinatorics.

M1rflowatmo0

cin >> a >> b; cout << a + b + abs(a — b) — (a ^ b ? 1 : 0) << endl;

kaons

Please don't add codes like this

Veraph

Why the divide function in problem D is mul(x, binpow(y, MOD — 2)) ? I understand the idea behind mul() and binpow(), but why they can perform the divide operation?

hat

It uses Fermat's little theorem to calculate Modular multiplicative inverse.

rahul0906

Can anyone please tell me what's wrong in my solution for problem C. Submission : 99756850

AmirrzwM

Consider this case: )()( your solution will return 0 although the answer is 1; and cuz find() is O(n), it also will get TLE in huge cases.

nothing!

towrist

I have a $$$O(nm)$$$ solution for problem E. Basically, we do scanline. For each participant, we brute force over the left author, and see when can we have the left author as a winner for that participant, and then we do the same for right author. It's really cool IMO. 100792298

Hassan111

4 года назад, скрыть # |

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

№	Пользователь	Вклад
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

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