babak's blog

number of ways
By babak, 12 years ago, In English

How many ways I can put r1 (same) balls with color 1 , r2 balls with color 2 , ..., rp balls with color p in q different boxes with sizes s1,**s2**,..,**sq** ?

note : r1+r2...+rp=s1+s2+...+sq=N

note 2: N<=1000

I don't have a good algorithm to solve this problem .

Full text and comments »

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

number of permutation
By babak, 13 years ago, In English

There is 1 card with color c1 numbered 1 , 2 cards with color c2 numbered 1 and 2, ... and n cards with color cn numbered from 1 to n. find the number of permutation of these cards with a this restriction :

             any two cards with the same color and consecutive numbers cannot be adjacent.

I think it's an interesting problem :)

Full text and comments »

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

Girth of Graph
By babak, 13 years ago, In English

Let G be a graph with n vertices and Δ(G)≤10 . find an algorithm with O(n) compolexity to determine this graph has girth less than 20 or not ?

thanks for any hint :)

Full text and comments »

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

dp bitmask or greedy
By babak, 13 years ago, In English

I solved this problem with dp bitmask but when I saw this I knew that it may has a better solution , maybe greedy.


but I cannot find any greedy approach for this problem.

tnx for any hints about it. :-)

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

sgu 537
By babak, 13 years ago, In English

I give wrong answer on test 48 and I don't what is the problem with my code.


#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
#define REP(i,n) for((i)=0;(i)<(n);(i)++)


ll gcd(ll a, ll b){
if(b==0)
return a;
return gcd(b,a%b);
}

void solve(vector<ll> &v , ll n){
ll i;
for(i=1;i*i<=n;i++){
if(n%i==0){
v.push_back(i);
if(i*i!=n)
v.push_back(n/i);
}
}
sort(v.begin(),v.end());
}

int main(){
int tsc,tcc,i,n;
ll t,ans;
string s;
cin>>tsc;
REP(tcc,tsc){
map<char,ll> mp;
map<char,ll>::iterator it;
cin>>s;
ans = 0;
n = s.size();
t=1;
for(i=n-1;i>=0;i--){
mp[s[i]]+=t;
t*=10;
}
for(it=mp.begin();it!=mp.end();it++)
ans = gcd(ans,it->second);
cout<<"Case "<<tcc+1<<":";
if(mp.size()==10){
if(n==10){
cout<<" 1 3 9"<<endl;
continue;
}
if(n==13 && s[0]==s[1] && s[0]==s[2] && s[0]==s[3]){
cout<<" 1 3"<<endl;
continue;
}
cout<<" 1"<<endl;
continue;
}
vector<ll> v;
solve(v,ans);
REP(i,v.size())
cout<<" "<<v[i];
cout<<endl;
}
return 0;
}

Full text and comments »

Tags sgu
  • Vote: I like it
  • -15
  • Vote: I do not like it

hide and seek
By babak, 13 years ago, In English
I have no idea for this problem
Can anyone give me some hints for solve it

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

Number Of Circular Permutation
By babak, 13 years ago, In English

a)I have n zeros and m ones and I want to counting the number of circular permutation of this m+n numbers .

m<=50 and n<=50

b) I want to count the number of circular permutation of n zero and ones .
(number of zeros + number of ones = n)
n<=100

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it