taklo's blog

By taklo, history, 5 years ago, In English

Hi all I am trying this problem using digit dp approach though I have not applied memoization yet but my recursive backtrack is not working appropriately . please help me to figure out where is the problem

Problem
#include<iostream>
#define ll long long 
using namespace std;
ll n;
ll x=0;
ll solve(ll index, ll small, ll last){
	if(index==x)
		return 0;
	ll ans=0;	
	if(small){
		ll ans1=solve(index+1,small,0);
		ll ans2=solve(index+1,small,1);
		if(last==1) ans2++;
		ans=ans1+ans2;
	}
	else{
		if((n&(1<<(x-index-1)))!=0){
			ll ans1=solve(index+1, 1, 0);
			ll ans2=solve(index+1, 0, 1);
			if(last==1) ans2++;
			ans=ans1+ans2;			
		}
		else{
			ans=solve(index+1, 0, 0);
		}		
	}
	return ans;
}
int main(){			
	ll t;
	cin>>t;
	while(t--){
				
		cin>>n;
		ll cpy	= n;
		x=0;
		while(cpy>0){
			x++;
			cpy/=2;
		}		
		cout<<solve(0,0,0)<<"\n";
	}
	return 0;
}

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By taklo, history, 5 years ago, In English

Problem

I am unable to proceed

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By taklo, history, 5 years ago, In English

in the blog written by founder of a2oj it was mentioned that ladders will remain static . Here what does he meant by saying static , if he meant that we will be able to access the ladders but ladders would not be updated with time then what about categories section . I liked a2oj a lot and just want to use it Please Help(Sorry for grammatical errors)

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it

By taklo, history, 5 years ago, In English

Hello Codeforces Community, I am new to java until now I have done all of my competitive programming in C++ 17 and now I want to learn basic JAVA through sports programming . I have searched for it on google but i'm confused with various type of map containers available in java , Please guide me .

#include<iostream>
#include<map>
using namespace std;
int main(){
	map<int ,int > M;
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];		
		M[a[i]]++;
	}
	if(M.find(10)!=M.end()){
		cout<<"10 is present \n ";
	}
	for(auto x: M){
		cout<<x.first<<" "<<x.second<<"\n";
	}
	return 0;
}

Please Tell me the alternative Java Code Thanks in Advanced

Full text and comments »

  • Vote: I like it
  • -7
  • Vote: I do not like it

By taklo, history, 5 years ago, In English

We are given an array 'a' of size N. We have 2 type of query Type 1 :- i , x update a[i] with a[i]+x Type 2:- i Give output S. Where S = a[0]+a[1]+.....+a[i] Constraint:- N<=100000 Q<=100000 Where N = size of array Q=Number of query

Example a={1,2,3,4,5,6} Type 1: 0,5 Type 2: 3 Type 1: 4,3 Type 2: 5

Output: 15 29

Full text and comments »

  • Vote: I like it
  • -16
  • Vote: I do not like it

By taklo, history, 5 years ago, In English

I Have Tried the following problem using Digit DP please tell me how to apply memoization to it

--- Problem Link ---

Your code here...
#include<iostream>
#include<vector>
#define Mod 1000000007
#define ll long long 
using namespace std;
int a,b,n;
bool check_good(int digit_sum){
	bool res=1;
	while(digit_sum>0){
		if(digit_sum%10!=a && digit_sum%10!=b){
			res=0;
			break;
		}
		digit_sum/=10;
	}
	return res;
}
vector<int > num;
ll call(int pos,int digit_sum){
	if(pos==n){
		if(check_good(digit_sum)){
			return 1;
		}
		else{
			return 0;
		}
	}
	ll ans=0;
	ans=(ans+call(pos+1,digit_sum+a))%Mod;
	ans=(ans+call(pos+1,digit_sum+b))%Mod;
	return ans;
}
int main(){
	cin>>a>>b>>n;
	cout<<call(0,0);
	return 0;
}

Full text and comments »

  • Vote: I like it
  • -10
  • Vote: I do not like it

By taklo, history, 5 years ago, In English

I Came to know about Digit DP from this blog https://codeforces.net/blog/entry/53960 and I Tried the following problem on DIGIT DP as given in the blog https://vjudge.net/problem/LightOJ-1068

here is my code I am Getting TLE on it Please Help Me!!!

Your code here...
#include<iostream>
#include<cstring>
#include<vector>
#define ll long long 
using namespace std;
vector<int > num;
void convert(ll n){
	vector<int > g;
	while(n>0){
		g.push_back(n%10);
		n/=10;
	}
	for(int i=g.size()-1;i>=0;i--) num.push_back(g[i]);
}
ll a,b,k;
ll DP[20][200][200][2];
ll call(int pos,int nmodk,int digmodk,int flag){
	if(pos==num.size()){
		if(nmodk%k==0 && digmodk%k==0)
			return 1;
		return 0;			
	}
	if(DP[pos][nmodk][digmodk][flag]!=-1)
		return DP[pos][nmodk][digmodk][flag];
	int lmt=9;
	if(!flag)
		lmt=num[pos];
	int ans=0;	
	for(int dgt=0;dgt<=lmt;dgt++){
		int nflag=flag;
		int nnmodk=(((nmodk%k)*(10%k))%k+dgt%k)%k;
		int ddigmodk=(digmodk%k+dgt%k)%k;
		if(flag==0 && dgt<lmt) nflag=1;
		ans+=call(pos+1,nnmodk,ddigmodk,nflag);
	}		
	DP[pos][nmodk][digmodk][flag]=ans;
	return ans;
}
ll solve(ll b){
	num.clear();
	memset(DP,-1,sizeof(DP));
	convert(b);
	return call(0,0,0,0);
}
int main(){
	ll t;
	cin>>t;
	int p=0;
	while(t--){
		cin>>a>>b>>k;
		cout<<"Case "<<p<<": "<<solve(b)-solve(a-1);
		p++;
	}
	return 0;
}

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

By taklo, history, 5 years ago, In English
  • Vote: I like it
  • 0
  • Vote: I do not like it

By taklo, history, 5 years ago, In English

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

What is the way to figure out the optimal way of playing for a player in a game theory Problem? please help!!

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it

By taklo, history, 5 years ago, In English

https://atcoder.jp/contests/dp/tasks/dp_e

this is knapsack problem with tough constraints so making dp table is not feasible (100*(10^9))

How this can be approcahed ?

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it