Blog entries - Codeforces

Codeforcer's blog

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.com/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, 3 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.com/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
3 years ago
6

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

By Codeforcer, history, 3 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.com/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
3 years ago
8

Cant figure out reason for TLE.

By Codeforcer, history, 3 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.com/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
3 years ago
3

An interesting geometry problem

By Codeforcer, history, 3 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
3 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

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

#	User	Contrib.
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145