[algogeeks] spoj coin tossing
http://www.spoj.pl/problems/MAIN8_D/ i tried solving this problem any ideas...?? for second test case 'htht' the states i considered are 1 T - (1/2) * x+1 2 HH - (1/4) * x+2 3 HTT - (1/8) * x+3 4 HTHH - (1/16) * x+4 5 HTHT - (1/16)(final state) x is the expected no of coins. x= 1 + 2+3+4+5 gives 16x=15x+26 x=26. answer given is 20... can any one explain this, -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] spoj -cornet disjoint sets suggestions!!
http://spoj.pl/problems/CHAIN can any one suggest how to go about... animals can have only 3 different roots... how do u maintain it.. like u just came across a new animal.. how do u put it in a group.. this cant be done just by parent[i]==i stuff rite?? how to make sure that there is only 3 roots.. normal merge and initialization we do for this disjoint sets cant be done rite?? hlp me out ppl :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] spoj TRAFICN- graph shortest path
i'm trying to solve this problem.. https://www.spoj.pl/problems/TRAFFICN/ https://www.spoj.pl/problems/TRAFFICN/ here there are m edges.. in addition you are given k bi directional edges out of which u can choose only one bi directional or u choose none of the additional edges... aim is to reduce the cost to go from source to destination ans=min(ans,dijkstras(one new added edge)) gives me tle can anyone throw some insight into this problem -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] spoj-lites
this is my code
--
#includeiostream
#includevector
#includestring.h
using namespace std;
vectorint tbf(100,0),array(100,0);
//vector 'tbf' denotes tobeflipped
void make(int ptr,int b,int e)
{
if(b==e)
{
array[ptr]=0;
return;
}
int mid=(b+e)/2;
make(ptr*2,b,mid);
make(ptr*2+1,mid+1,e);
array[ptr]=array[2*ptr]+array[2*ptr+1];
//combine
}
int query(int ptr,int b,int e,int i,int j)
{
if(jb || ie)
return 0;
if(tbf[ptr]1)
{
array[ptr]=(e-b+1)-array[ptr];
tbf[2*ptr]+=tbf[ptr];
tbf[2*ptr+1]+=tbf[ptr];
tbf[ptr]=0;
}
if(b=i e=j)
return array[ptr];
int mid=(b+e)/2;
int x=query(2*ptr,b,mid,i,j)+query(2*ptr+1,mid+1,e,i,j);
return x;
}
void update(int ptr,int b,int e,int i,int j)
{
if(jb || ie)
return;
if(tbf[ptr]1)
{
array[ptr]=(e-b+1)-array[ptr];
tbf[2*ptr]+=tbf[ptr];
tbf[2*ptr+1]+=tbf[ptr];
tbf[ptr]=0;
}
if(b=i e=j)
{
array[ptr]=(e-b+1)-array[ptr];
tbf[2*ptr]+=1;
tbf[2*ptr+1]+=1;
tbf[ptr]=0;
return;
}
int mid=(b+e)/2;
update(2*ptr,b,mid,i,j);
update(2*ptr+1,mid+1,e,i,j);
if(!tbf[2*ptr] !tbf[2*ptr+1])
array[ptr]=array[2*ptr]+array[2*ptr+1];
else if(tbf[ptr*2] tbf[2*ptr+1])
array[ptr]=(mid-b+1-array[2*ptr])+(e-mid-array[2*ptr+1]);
else if(!tbf[2*ptr])
array[ptr]=array[2*ptr]+(e-mid-array[2*ptr+1]);
else
array[ptr]=(mid-b+1-array[2*ptr])+array[2*ptr+1];
}
int main()
{
int n,q,st,en,opt;
cinnq;
make(1,1,n);
for(int i=0;iq;i++)
{
cinoptsten;
//st++;
//en++;
if(opt==0)
update(1,1,n,st,en);
else
coutquery(1,1,n,st,en)\n;
/* coutstate of the array[]\n\n;
for(int i=1;i=7;i++)
coutarray[i]\t;
cout\n;
cout\nstate of the tbf[]\n\n;
for(int i=1;i=7;i++)
couttbf[i]\t;
cout\n--\n;*/
}
}
getting WA..
help me debugging
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] spoj-RENT problem
https://www.spoj.pl/problems/RENT/ tried dp for this problem.. getting tle.. classifier says this is binary search. not able to get how to binary search this problem.. help me out... thanks.. karthikeyan.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] spoj problem PIE
i get correct answer for test cases i tried.. still WA
spoj.pl/problems/PIE
here is my code
#includeiostream
#includevector
#includestdio.h
#includealgorithm
#includemath.h
using namespace std;
vectorunsigned long long int v;
double bin(unsigned long long int n,unsigned long long int req)
{
unsigned long long int hi,lo,x,tmp,count=0,i;
lo=v.front();
hi=v.back();
if(n==1)
return((double)v[0]/(double)req);
while(lohi)
{
count=0;
x=lo+(hi-lo)/2;
for(i=n-1;i=0 v[i]=x;i--)
{
tmp=v[i]/x;
count+=tmp;
}
if(count=req)
lo=x+1;
else
hi=x-1;
}
return lo-1;
}
int main()
{
unsigned long long int pi,tmp,tot,i,t;
scanf(%lld,t);
while(t--){
scanf(%lld %lld,pi,tot);
tot++;
for(i=0;ipi;i++)
{
scanf(%lld,tmp);
v.push_back(tmp*tmp);
}
sort(v.begin(),v.end());
printf(%0.4lf\n,((M_PI*bin(pi,tot;
v.clear();
}
}
help me out... :-)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] spoj-party problem
hey guys.., i tried solving this problem http://www.spoj.pl/problems/PARTY/
i get answer for the test cases that i try.. getting WA in the judge..
can anyone help me out here.. my code is as follows..
#includeiostream
#includestdio.h
using namespace std;
int m[150][150],v[150],wt[150],ans[150][150];
void dp(int weight,int n)
{
int i,j,x,y,anscount=0;
for(i=0;i=weight;i++)
m[0][i]=0;
for(i=1;i=n;i++)
ans[0][i]=0;
for(i=1;i=n;i++)
{
for(j=0;j=weight;j++)
{
if(wt[i]=j)
{
x=(v[i]+m[i-1][j-wt[i]]);
y=(m[i-1][j]);
if(x=y)
{
m[i][j]=x;
//cost=wt[i];
ans[i][j]=wt[i]+ans[i-1][j-wt[i]];
}
else
{
m[i][j]=y;
ans[i][j]=ans[i-1][j];
}
}
else
{
m[i][j]=m[i-1][j];
ans[i][j]=ans[i-1][j];
}
}
}
printf(%d %d,ans[n][weight],m[n][weight]);
}
int main()
{
int weight,no,i,j;
while(1)
{
scanf(%d %d,weight,no);
if(!weight !no)
break;
for(i=1;i=no;i++)
scanf(%d %d,wt[i],v[i]);
dp(weight,no);
}
}
thanks,
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] catalan numbers
can anyone suggest how to implement Catalan numbers.. upper limit 1000, consider modulo 1 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
