Blog entries - Codeforces

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

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

Codeforcer's blog

Djisktra is just too slick

By Codeforcer, history, 13 days ago, In English

I was going through multiple blogs on Djikstra recently, viz Graph Modelling, K path skip and Eppstein algorithm. I came across many interesting problems which were just not possible for me to solve without prior knowledge of these concepts. I am still struggling to do these problems (at a rate of 1 per day). Came across some ingenious yet elegant problems as well. I would love to know more on the type of patterns that Djikstra can solve and if you guys know any cool tricks or problems like the one above.

Thanks!

Full text and comments »

djikstra, graphs

Codeforcer
13 days ago
2

Looking for a general solution to a retroactive bugaboo.

By Codeforcer, history, 3 years ago, In English

Recently I solved this problem. Upon first reading this and before solving it, I thought of many other possible approaches like which would either TLE/MLE. One of them being to maintain a dp; Until I finally realized the retroactiveness the question demands. If you look at it closely it is the same as this task. Now I have a few "questions" on how to solve a more general version of it if...

1 The A was variable i.e. we are also given an array each having some A[i] with atmost one drink per day.

2 Instead of atmost 1 drink per day, We are allowed to choose any number of drinks per day with given A[i]'s

If you have any thoughts or ideas on this one please make sure to share. As for me, it is the first time I have seen such variations in such a problem with these constraints. Also can we even solve it in some efficient complexity ? I am very eager to know.

P.S I have used bugaboo, task, problem and question so that no one feels hurt!

Thanks for reading !

Full text and comments »

variation, new, problem

Codeforcer
3 years ago
0

Help->O(NlogN) giving TLE(4 s) in TRIE problem.

By Codeforcer, history, 3 years ago, In English

I was attempting this problem :

https://codeforces.net/contest/706/problem/D

I tried using trie and it gives TLE. I saw solutions of other people but most of them have created a TRIE by using struct and pointers. I have done it using a 2d next array following the idea from Errichto topic video of trie. I cant figure out why there is TLE, maybe because of map ? Any help would be appreciated.

Here is my code :

#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int N = 2e5+2;

int id = 0;

int nxt[3*N][2];
map<int,int> m;

int bit(int x,int p){
	return ((x&(1<<p)) > 0 ? 1 : 0);
}
void add(int x){
	int node = 0;
	for(int i=30;i>=0;--i){
		if(nxt[node][bit(x,i)]==0){
			nxt[node][bit(x,i)] = ++id;
		}
		node = nxt[node][bit(x,i)];
	}
}
void remove(int x){
	int node = 0, z = 30, y = 0;
	for(int i=30;i>=0;--i){
		if(nxt[node][0]!=0 and nxt[node][1]!=0){
			y = node;
			z = i;
		}
		node = nxt[node][bit(x,i)];
	}
	for(int i=z;i>=0;--i){
		int temp = y;
		y = nxt[y][bit(x,i)];
		nxt[temp][bit(x,i)] = 0;
	}
}
void get(int x){
	int node = 0,val = 0;
	for(int i=30;i>=0;--i){
		if(bit(x,i)>0 and nxt[node][0]!=0){
			node = nxt[node][0];
			val+=(1<<i);
		}
		else if(bit(x,i)==0 and nxt[node][1]!=0){
			node = nxt[node][1];
			val+=(1<<i);
		}
		else
			node = nxt[node][bit(x,i)];
	}
	cout<<val<<"\n";
}

void run_case(){
	int q,x;
	char op;
	cin >> q;
	add(0);
	while(q--){
		cin >> op >> x;
		if(op=='+'){
			++m[x];
			if(m[x]==1)
				add(x);
		}
		else if(op=='-'){
			--m[x];
			if(m[x]==0)
				remove(x);
		}
		else
			get(x);
	}	
}

int main(){
	fast;
	int t=1;
	while(t--){
		run_case();
	}
}

UPD Got accepted!

Thanks!

Full text and comments »

trie, tle, help

Codeforcer
3 years ago
0

Need help in pbds (Find by order using pairs)

By Codeforcer, history, 3 years ago, In English

When I try to use find by order using pairs in ordered_set of pbds it shows some error of no matching call as such. So how do I resolve it?

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds; 
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int N = 2e5+2;
const ll mod = 1e9+7;
using namespace __gnu_pbds;

typedef tree<pi, null_type, less_equal<pi>, rb_tree_tag,
                    tree_order_statistics_node_update>
                    ordered_set;

ordered_set ord_set;

int main(){
	int a;
        cin >> a;
	ord_set.insert({a,-1});
	*ord_set.find_by_order(make_pair(a,-1)); //Why does this not work ?
   	ord_set.order_of_key({a,-1});
}

Full text and comments »

pbds, help

Codeforcer
3 years ago
2

Memoization and RE

By Codeforcer, history, 3 years ago, In English

I was solving this : https://leetcode.com/problems/minimum-jumps-to-reach-home/ and wrote essentially 2 same solutions, just the way of calculating transitions is a bit different. I get AC in one and RE in the second. I am not getting the reason for such a difference in results. So please help me understand.

One which gives RE

class Solution {
public:
   
    int dp[7001][2];
    set<int> now; 
    int solve(int pos,int f,int a ,int b,int x){
     //   cout<<pos<<" "<<f<<endl;
        
         if(pos == x)
            return 0;
        
        if( pos < 0 or now.count(pos) or pos>6000 )
            return 1e9;
        
        if(dp[pos][f]!=-1)
            return dp[pos][f];
        
        int &ans = dp[pos][f];
     
        if(f)
            ans = solve(pos+a,0,a,b,x)+1;
        else
            ans = min(solve(pos+a,0,a,b,x),solve(pos-b,1,a,b,x))+1;
        
        return ans;
    }
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        for(int x1 : forbidden)
            now.insert(x1);
        
        memset(dp,-1,sizeof(dp));
        
        int ans = solve(0,0,a,b,x);
        if(ans>1e9)
            return -1;
        return ans;
    }
};

One which gives AC

class Solution {
public:
   
    int dp[7001][2];
    set<int> now; 
    int solve(int pos,int f,int a ,int b,int x){
     //   cout<<pos<<" "<<f<<endl;
        
         if(pos == x)
            return 0;
        
        if( pos < 0 or now.count(pos) or pos>6000 )
            return 1e9;
        
        if(dp[pos][f]!=-1)
            return dp[pos][f];
        
        int &ans = dp[pos][f];
     
        ans = solve(pos+a,0,a,b,x)+1;
        if(!f)
            ans = min(ans,solve(pos-b,1,a,b,x)+1);
        
        return ans;
    }
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        for(int x1 : forbidden)
            now.insert(x1);
        
        memset(dp,-1,sizeof(dp));
        
        int ans = solve(0,0,a,b,x);
        if(ans>1e9)
            return -1;
        return ans;
    }
};

The difference

        //RE if I do this
        int &ans = dp[pos][f];
        if(f)
            ans = solve(pos+a,0,a,b,x)+1;
        else
            ans = min(solve(pos+a,0,a,b,x),solve(pos-b,1,a,b,x))+1;

        //AC if I do this.
        int &ans = dp[pos][f];
        ans = solve(pos+a,0,a,b,x)+1;
        if(!f)
            ans = min(ans,solve(pos-b,1,a,b,x)+1);

As you can see logically both are correct then why the difference ?

Thanks!

Full text and comments »

memoization, dp, help, re

Codeforcer
3 years ago
1

Getting TLE'd with O(nlogn) (2-sec)

By Codeforcer, history, 4 years ago, In English

I cannot figure out why this code is getting TLE'd despite of everything being under order and constraint. I knew those mod operations were costly so I optimized them but still no luck.

Problem : https://codeforces.net/contest/1466/problem/E

Code

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int N = 3e4+10;
const ll mod = 1e9+7;
const int BLOCK_SIZE = 200;


ll mul(ll a,ll b){
	if(a>=mod)
		a%=mod;
	if(b>=mod)
		b%=mod;
	ll xt = a*b;
	if(xt>=mod)
		return (xt)%mod;
	return (xt);
}
ll add(ll a,ll b){
	if((a+b)>=mod)
		return (a+b)%mod;
	return (a+b);
}

void run_case(){
	ll n,i,j,k;

	//<i,j> -> {<j,1>+<j,2>+<j,3>,...............,<j,n>}
	//{<1,1> + <2,1> + .... + <n,1>}-> {1,..|{1,2,...n}}
	cin >> n;
	ll x[n];
	ll C[n][60];
	REP(i,n)
		REP(j,60)
			C[i][j]=0;
	ll col[60];
	memset(col,0,sizeof(col));

	for(i=0;i<n;i++){
		cin >> x[i];
		ll tt = x[i];
		vector<ll> bin;
		while(tt>0){
			bin.pb(tt%2);
			tt/=2;
		}
		for(j=0;j<bin.size();++j){
			C[i][j] = bin[j];
		}

	}
	for(i=0;i<60;i++){
		ll cnt=0;
		for(j=0;j<n;j++)
			cnt+=C[j][i];
		col[i]=cnt;
	}
	ll ans=0;
	for(i=0;i<n;i++){
		ll tt = x[i];
		vector<ll> bin;
		ll O=0,A=0;
		while(tt>0){
			bin.pb(tt%2);
			tt/=2;
		}
		while(bin.size()<60)
			bin.pb(0);
		for(j=0;j<bin.size();++j){
			if(bin[j]==1){
				O = add(O,mul(n,(1LL<<j)));
				A = add(A,mul(col[j],(1LL<<j)));
			}
			else
				O = add(O,mul(col[j],(1LL<<j)));
		}
		ans = add(ans,mul(O,A));
	}
	cout<<ans<<"\n";
}
int main(){
	fast;
	int t;
	cin >> t;
	while(t--){
		run_case();
	}
}

Update-1 : Resolved, It barely passed(1996 ms) after I changed some ll's to ints. Would still like to hear some advice or a good solution though!

Update-2 : The comments are absolute gold thanks guys! Made the necessary changes and made code more concise.

New Code

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int N = 3e4+10;
const ll mod = 1e9+7;
const int BLOCK_SIZE = 200;


ll mul(ll a,ll b){
	if(a>=mod)
		a%=mod;
	if(b>=mod)
		b%=mod;
	if(a*b>=mod)
		return (a*b)%mod;
	return (a*b);
}
ll add(ll a,ll b){
	ll xt = a+b;
	if(xt>=mod)
		return xt-=mod;
	return xt;
}

void run_case(){
	int n,i,j,k;

	//<i,j> -> {<j,1>+<j,2>+<j,3>,...............,<j,n>}
	//{<1,1> + <2,1> + .... + <n,1>}-> {1,..|{1,2,...n}}
	
	cin >> n;
	ll x[n];

	int col[60];
	memset(col,0,sizeof(col));

	for(i=0;i<n;i++){
		cin >> x[i];
		for(j=0;j<60;++j){
			if(x[i]&(1LL<<j))
				++col[j];
		}
	}
	ll ans=0;
	for(i=0;i<n;i++){
		ll O=0,A=0;
		for(j=0;j<60;++j){
			if(x[i]&(1LL<<j)){
				O = add(O,mul(1LL*n,(1LL<<j)));
				A = add(A,mul(1LL*col[j],(1LL<<j)));
			}
			else
				O = add(O,mul(1LL*col[j],(1LL<<j)));
		}
		ans = add(ans,mul(O,A));
	}
	cout<<ans<<"\n";
}
int main(){
	fast;
	int t;
	cin >> t;
	while(t--){
		run_case();
	}
}

GNU C++17(64 bit) -> 453 ms

GNU C++17 ->1263 ms

Would still like to know more on the difference in time on the above 2 compilers.

Thanks!

Full text and comments »

#goodbye2020, tle, div2e

Codeforcer
4 years ago
6

Need Help in resolving TLE in DP with memo and iterative.

By Codeforcer, history, 4 years ago, In English

Why do some solutions containing dp with memoization result in TLE but the same iterative version always passes? I have had this doubt for quite a while.

For example this problem : https://codeforces.net/contest/628/problem/D

DP+Memo->TLE


#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int N = 2e5+10;
const ll mod = 1e9+7;


int m,d;
string a,b;
int dp[2001][2][2001];

int solve(int pos,int f1,int rem,string x){
	if(pos==(int)a.length()){
		if((rem%m)==0)
			return 1;
		return 0;
	}
	if(dp[pos][f1][rem]!=-1)
		return dp[pos][f1][rem];
	int ulmt;
	if(f1)
		ulmt=9;
	else
		ulmt=(x[pos]-'0');
	int ans=0;
	for(int i=0;i<=ulmt;++i){
		int nf1,nrem,nis;
		if(f1==0 and i==ulmt)
			nf1=0;
		else if(f1==0 and i<ulmt)
			nf1=1;
		else
			nf1=1;

		nrem=(10*rem+i)%m;
		if(pos%2==1 and i==d){
			ans+=solve(pos+1,nf1,nrem,x);
			if(ans>=mod)
				ans-=mod;
			break;
		}
		else if(pos%2==0 and i!=d){
			ans+=solve(pos+1,nf1,nrem,x);
			if(ans>=mod)
				ans-=mod;
		}	
	}
	return dp[pos][f1][rem] = ans;
}

int main(){
	fast;
	cin >> m >> d >> a >> b;
	memset(dp,-1,sizeof(dp));
	int a1 = solve(0,0,0,b);
	memset(dp,-1,sizeof(dp));
	int a2 = solve(0,0,0,a);
	bool ok=true;
	int rem=0;
	for(int i=0;i<(int)a.length();++i){
		if(i%2==1 and (a[i]-'0')!=d){
			ok=false;
		}
		if(i%2==0 and (a[i]-'0')==d){
			ok=false;
		}
		rem=(10*rem+(a[i]-'0'))%m;
	}
	int ans;
	if(ok and rem==0)
		ans=(a1-a2+1+mod)%mod;
	else
		ans=(a1-a2+mod)%mod;
	cout<<ans<<"\n";
	
}

Checking the editorial they have done the same thing just iterative.

So my questions are this :

->What should be a good practice to write dp memoized or iterative?

->Can every memoized dp problem be converted to iterative ?

->What exactly goes wrong with memoized versions getting TLE'd ?

->How to resolve such TLE's ?

Thanks!

Full text and comments »

dp, #memoization, iterative, digit dp

-7

Codeforcer
4 years ago
8

Cant figure out reason for TLE.

By Codeforcer, history, 4 years ago, In English

I cant figure out reason for TLE, code seems to be O(n) with some small constants, any help would be appreciated.

Problem Link : https://codeforces.net/contest/1251/problem/C

Code

#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int INF = 4e5;
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
           
#define time__(d) \
    for ( \
        auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
        blockTime.second; \
        debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
    )


int get_num(int l[10],int y){
	int i;
	pi lp[10];
	for(i=0;i<=9;i++){
		lp[i]={l[i],i};
	}
	sort(lp,lp+10);
	for(auto [pos,el] : lp){
		if(pos!=INF && el>y){
			return el;
		}
	}
	return -1;
}
string run_filter(string x,int par){

	int n = x.length(),i,j;
	int leftmost_min[10];
	for(i=0;i<10;i++)
		leftmost_min[i]=INF;
	for(i=0;i<n;i++){
		leftmost_min[(x[i]-'0')]=min(leftmost_min[(x[i]-'0')],i);
		if(i>0 && ((x[i]-'0')%2==par) && ((x[i-1]-'0')%2!=par)){
			//cout<<x<<" "<<i<<" "<<x[i]<<endl;
			int cur=i,go;
		    go = get_num(leftmost_min,(x[i]-'0'));
			if(go!=-1){
				while(i>leftmost_min[go] && (x[i-1]%2)!=par){
					swap(x[i],x[i-1]);
					--i;
				}
				for(j=0;j<10;j++)
					leftmost_min[j]=INF;
				++i;
				while(i<=cur){
					leftmost_min[(x[i]-'0')]=min(leftmost_min[(x[i]-'0')],i);
					++i;
				}
				--i;
			}
		}
	}
	return x;
}

void run_case(){
	string s;
	cin >> s;
	//cout<<run_filter(s,1)<<endl;
	string ans1,ans2;
	time__("MAIN"){
		ans1 = run_filter(run_filter(s,1),0);
		//cout<<ans1<<endl;
		ans2 = run_filter(run_filter(s,0),1);
	}
	//cout<<ans2<<endl;
	if(ans1<ans2)
		cout << ans1;
	cout << ans2;
	cout<<"\n";
}
int main(){
	fast;	
	#ifndef ONLINE_JUDGE 
  
    // For getting input from input.txt file 
    freopen("example.txt", "r", stdin); 
  
    // Printing the Output to output.txt file 
    freopen("output.txt", "w", stdout); 
  
#endif 
	int t;
	cin >> t;
	while(t--){
		run_case();
	}	
}

Thanks!

Full text and comments »

tle, debug, c++

-1

Codeforcer
4 years ago
3

An interesting geometry problem

By Codeforcer, history, 4 years ago, In English

So I was thinking of making some div2B/C level CP problems for my school contest and thought of this....

Here it goes....

Find the maximum number of squares of side length 'a' that can completely be inscribed in a circle of radius 'r' such that exactly one of the vertices of the square touches the circle and no 2 squares overlap each other. Note that all the squares have to be completely inside the circle.

I cant figure this out..ended up taking too many variables which I cant eliminate...any thoughts or hints ?

The figure will look something like this :

No way am using geogebra for this

Apologize for the sketchy figure though.

Full text and comments »

coordinate geometry, help, practice

Codeforcer
4 years ago
7

ARC-105

By Codeforcer, history, 4 years ago, In English

I wanted to do a runtime analysis of B. It got AC even though I doubted it as it looked worst case O(n^2). Basically I just simulated what was asked. It is also mentioned in the editorial that simulation would take too much time. I am now really interested in the runtime of my code.

ARC-105_B

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
const ll maxn=100005;
const ll mod=1e9+7;


int main(){
    fast;
	ll n,i,j,k;
	cin >> n;
	vector<ll> a(n);
	set<ll> hsh;
	for(i=0;i<n;i++){
		cin >> a[i];
		hsh.insert(a[i]);
	}
	sort(all(a));

	ll mx = a[n-1];
	ll mn = a[0];
	ll t;
	while(hsh.size()>1){
		hsh.erase(mx);
		hsh.insert(mx-mn);
		t = min(mx-mn,mn);
		auto it = hsh.end();
		--it;
		mx = *it;
		mn=t;
	}
	cout<<*hsh.begin();
}

Also any ideas on D?

Full text and comments »

arc, 105, help, post

Codeforcer
4 years ago
4

Why was CF down for a day ?

By Codeforcer, history, 4 years ago, In English

Why was CF down for a day? Is there some new feature that has been implemented or just maintanance?

Full text and comments »

codeforces

+158

Codeforcer
4 years ago
43