Blog entries - Codeforces

#	User	Rating
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

#	User	Contrib.
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

Osama_Alkhodairy's blog

Does Codeforces Need All These Testcases?

By Osama_Alkhodairy, 5 years ago, In English

Codeforces now has 342281 testcases. But how many of these are actually relevant?

Let's call a test redundant if nobody has ever submitted a solution that failed on that test. Here's a graph showing what percentage of testcases are redundant over all rounds.

Turns out to be that 173195 tests out of the 342281 tests are actually redundant — no verdict would change if these tests were never there. That's around 50%. I actually expected more, but still, a lot of testcases are redundant.

Here is another representation of data, where the y-axis shows how many problems of each percentage of redundancy.

Codeforces can take advantage of this and save resources by not running these tests at all. But how long should we wait before deciding that the current non-redundant testcases are enough?

As you can see a lot of problems get saturated in the first month. But many others don't; however, don't treat these non-redundant testcases as absolutely essential because a solution failing at one of them doesn't mean that it passes all others (for example, all problems have solutions failing at the first testcase).

How many testcases, do you think, does a problem need on average if we were to pick them the most optimal way?

Thanks zoooma13 for sharing ideas and helping collecting the data.

Full text and comments »

testcases, optimization, data

+282

Osama_Alkhodairy
5 years ago
19

[Insight] Number of Topological Orderings of a Directed Tree

By Osama_Alkhodairy, history, 5 years ago, In English

I was checking this problem on csacademy, and I came up with the dp combinatorics solution to calculate the number of topological orderings of a directed tree with a fixed root.

First, let me explain this solution. Let's root the tree at node $$$1$$$ and calculate $$$sz_v$$$ = size of the subtree rooted at $$$v$$$. Let $$$dp_v$$$ be the number of possible topological orderings of the subtree rooted at $$$v$$$. To calculate $$$dp_v$$$, let's imagine $$$v$$$ has only two children: $$$x$$$ and $$$y$$$. We can see quite easily that $$$dp_v = dp_x * dp_y * {sz_x+sz_y \choose sz_x}$$$. That's because any valid topological ordering of the subtree of $$$v$$$ will begin with $$$v$$$ itself and then $$$sz_x+sz_y$$$ nodes, and because the nodes of $$$x$$$'s and $$$y$$$'s subtrees are independent, all possible combinations between them are possible. So, we will choose $$$sz_x$$$ spots of the $$$sz_x+sz_y$$$ spots and put in them all the nodes form $$$x$$$'s subtree and put on the rest the nodes from $$$y$$$'s subtree. Of course, after assigning how we will combine the two subtrees, we can permute the nodes in these spots as long as these permutations are valid; that's why we are multiplying by $$$dp_x*dp_y$$$. What if $$$v$$$ has more than two children? We will loop over them and do the same thing accumulatively. The final expression after some reductions looks like this: $$$dp_v = \frac{(sz_v-1)!}{\prod sz_u!} * \prod dp_u$$$, where $$$u$$$ is a child of $$$v$$$. Actually we can reduce this further to $$$dp_v = \frac{sz_v!}{\prod sz_u}$$$, where $$$u$$$ will loop over all nodes in $$$v$$$'s subtree.

I felt really unsatisfied after all these reductions because the final expression didn't make sense on its own. But here's a simpler way to think about it without going through all of this.

The number of valid orderings for the whole tree is $$$dp_1 = \frac{n!}{\prod_{v=1}^{n} sz_v}$$$. Here, $$$n!$$$ represents all possible permutations. Of course, not all of them are valid. For example, the first element of any valid permutation must be $$$1$$$ (the root), and that's why we are dividing by $$$sz_1$$$. More generally, let's go through the subtrees from the largest to the smallest and perform the division. When considering a subtree, the root of that subtree must appear before all the other nodes from the subtree in the permutation. As we are going over the subtrees from the largest to the smallest, all the permutations of the current subtree contribute to the answer. However, not all of them are valid; we want to fix the root of the subtree in the beginning, so we divide by $$$sz_v$$$, so that, now, the current subtree is contributing to the answer by a factor of $$$(sz_v-1)!$$$, instead of a factor of $$$sz_v!$$$ (because we are fixing one of the nodes).

I found this way of thinking about it much more insightful than the way with reductions, so I wanted to share it with you.

Full text and comments »

topological sort, directed tree, intuition

Osama_Alkhodairy
5 years ago
17

Codeforces Round #613 (Div. 2) Editorial

By Osama_Alkhodairy, 5 years ago, In English

Tutorial is loading...

code

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n;
string s;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;
    cout << n + 1 << endl;
}

Tutorial is loading...

code

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n;
vector <int> a;

bool solve(){
    cin >> n;
    a.resize(n);
    for(auto &i : a) cin >> i;
    ll sum = 0;
    for(int i = 0 ; i < n ; i++){
        sum += a[i];
        if(sum <= 0) return 0;
    }
    sum = 0;
    for(int i = n - 1 ; i >= 0 ; i--){
        sum += a[i];
        if(sum <= 0) return 0;
    }
    return 1;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--){
        if(solve()) cout << "YES\n";
        else cout << "NO\n";
    }
}

Tutorial is loading...

code

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

ll x;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> x;
    vector <ll> f;
    for(ll i = 2 ; i * i <= x ; i++){
        if(x % i == 0){
            ll cur = 1;
            while(x % i == 0){
                x /= i;
                cur *= i;
            }
            f.push_back(cur);
        }
    }
    if(x > 1) f.push_back(x);
    int n = f.size();
    ll ansa = 1e18, ansb = 1e18;
    for(int i = 0 ; i < (1 << n) ; i++){
        ll a = 1, b = 1;
        for(int j = 0 ; j < n ; j++){
            if((i >> j) & 1) a *= f[j];
            else b *= f[j];
        }
        if(max(a, b) < max(ansa, ansb)){
            ansa = a;
            ansb = b;
        }
    }
    cout << ansa << " " << ansb << endl;
}

easier implementation

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

ll x;

ll lcm(ll a, ll b){
    return a / __gcd(a, b) * b;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> x;
    ll ans;
    for(ll i = 1 ; i * i <= x ; i++){
        if(x % i == 0 && lcm(i, x / i) == x){
            ans = i;
        }
    }
    cout << ans << " " << x / ans << endl;
}

Tutorial is loading...

code

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n;
vector <int> a;

int solve(vector <int> &c, int bit){
    if(bit < 0) return 0;
    vector <int> l, r;
    for(auto &i : c){
        if(((i >> bit) & 1) == 0) l.push_back(i);
        else r.push_back(i);
    }
    if(l.size() == 0) return solve(r, bit - 1);
    if(r.size() == 0) return solve(l, bit - 1);
    return min(solve(l, bit - 1), solve(r, bit - 1)) + (1 << bit);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    a.resize(n);
    for(auto &i : a) cin >> i;
    cout << solve(a, 30) << endl;
}

Tutorial is loading...

Author: MikeMirzayanov

code (pikmike)

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second

using namespace std;

const int INF = 2e9;

typedef pair<int, int> pt;
map<int, int> ls;

int get(vector<pt> a){
	int cnt = 0;
	int l = -INF, r = -INF;
	sort(a.begin(), a.end());
	forn(i, a.size()){
		if (a[i].x > r){
			if (r != -INF)
				ls[l] = 0;
			++cnt;
			l = a[i].x, r = a[i].y;
		}
		else{
			r = max(r, a[i].y);
		}
	}
	ls[l] = 0;
	return cnt;
}

void process(vector<pair<int, pt>> &qr, vector<int> &ans){
	set<int> open;
	forn(i, qr.size()){
		vector<int> op, cl;
		int j = i - 1;
		while (j + 1 < int(qr.size()) && qr[j + 1].x == qr[i].x){
			++j;
			if (qr[j].y.x == 1)
				op.push_back(qr[j].y.y);
			else
				cl.push_back(qr[j].y.y);
		}
		if (open.size() == 1 && !op.empty()){
			++ans[*open.begin()];
		}
		for (auto it : op){
			open.insert(it);
		}
		for (auto it : cl){
			open.erase(it);
		}
		i = j;
	}
}

void solve(){
	int n;
	scanf("%d", &n);
	vector<pt> a(n);
	forn(i, n) scanf("%d%d", &a[i].x, &a[i].y);
	
	vector<pair<int, pt>> qr;
	forn(i, n){
		qr.push_back({a[i].x, {1, i}});
		qr.push_back({a[i].y, {-1, i}});
	}
	sort(qr.begin(), qr.end());
	
	vector<int> ans(n, 0);
	ls.clear();
	int cur = get(a);
	
	process(qr, ans);
	forn(i, n) if (ls.count(a[i].x)) ++ls[a[i].x];
	forn(i, n) if (ls[a[i].x] == 1) --ans[i];
	
	printf("%d\n", *max_element(ans.begin(), ans.end()) + cur);
}

int main(){
	int tc;
	scanf("%d", &tc);
	forn(i, tc)
		solve();
}

Tutorial is loading...

code (mohammedehab2002)

#include <bits/stdc++.h>
using namespace std;
#define MX 100000
int arr[100005],u[MX+5],cnt[MX+5];
vector<int> d[MX+5];
bool b[MX+5];
int coprime(int x)
{
	int ret=0;
	for (int i:d[x])
	ret+=cnt[i]*u[i];
	return ret;
}
void update(int x,int a)
{
	for (int i:d[x])
	cnt[i]+=a;
}
int main()
{
	for (int i=1;i<=MX;i++)
	{
		for (int j=i;j<=MX;j+=i)
		d[j].push_back(i);
		if (i==1)
		u[i]=1;
		else if ((i/d[i][1])%d[i][1]==0)
		u[i]=0;
		else
		u[i]=-u[i/d[i][1]];
	}
	int n;
	scanf("%d",&n);
	long long ans=0;
	for (int i=0;i<n;i++)
	{
		int a;
		scanf("%d",&a);
		ans=max(ans,(long long)a);
		b[a]=1;
	}
	for (int g=1;g<=MX;g++)
	{
		stack<int> s;
		for (int i=MX/g;i>0;i--)
		{
			if (!b[i*g])
			continue;
			int c=coprime(i);
			while (c)
			{
				if (__gcd(i,s.top())==1)
				{
					ans=max(ans,1LL*i*s.top()*g);
					c--;
				}
				update(s.top(),-1);
				s.pop();
			}
			update(i,1);
			s.push(i);
		}
		while (!s.empty())
		{
			update(s.top(),-1);
			s.pop();
		}
	}
	printf("%I64d",ans);
}

Full text and comments »

Tutorial of Codeforces Round 613 (Div. 2)

+132

Osama_Alkhodairy
5 years ago
171

Codeforces Round #613 (Div. 2)

By Osama_Alkhodairy, 5 years ago, In English

Hello Codeforces!

We are glad to invite you to Codeforces Round 613 (Div. 2), which will be held on Jan/10/2020 17:05 (Moscow time). The round is rated for Div. 2 contestants. There will be six problems with a duration of 2:15

The problems were prepared by me, mohammedehab2002, TripleM5da, and MikeMirzayanov.

I'd like to thank awoo for coordinating the round, dorijanlendvaj, aryanc403, Ari, nooinenoojno, defolaut, Pavlova, mahmoudbadawy, zoooma13, Mohammad_Yasser, Rox, and BledDest for the invaluable testing, and MikeMirzayanov for great Codeforces and Polygon systems.

Good luck!

UPD1: We decided to add one more problem and extend the duration to 2:15 to make the contest more balanced.

UPD2: Score distribution: 500-1000-1250-1750-2250-3000

UPD3: Editorial is out.

UPD4: Thanks for participating! Congratulations to the winners:

Div. 1 (unofficial) participants

Div. 2 participants

Full text and comments »

Announcement of Codeforces Round 613 (Div. 2)

+401

Osama_Alkhodairy
5 years ago
179