[algogeeks] Spoj problem-pigbank
i am a beginner.pl help me with this code.i submitted a solution.it s
giving op for all given testcases.but the judge is giving me a TLE.
code:
#includeiostream
#includemap
#define inf 9
using namespace std;
mapint,int m2;
int func(mapint,int m1,int w)
{
if(m2[w]inf)
return m2[w];
mapint,int::iterator it;
int min=inf;
for(it=m1.begin();it!=m1.end();it++)
{
if((*it).second=w)
{
int x=func(m1,w-(*it).second);
if(x+(*it).first min)
min=x+(*it).first;
}
}
m2[w]=min;
return min;
}
main()
{
int t;
cint;
while(t--)
{
int w1,w2;
cinw1w2;
int w=w2-w1,no,a,b;
cinno;
mapint,int m1;
for(int i=0;ino;i++)
{
cinab;
m1.insert(pairint,int(a,b));
}
m2[0]=0;
for(int i=1;i=w;i++)
m2[i]=inf;
func(m1,w);
if(m2[w]!=inf)
coutThe minimum amount of money in the piggy-bank is
m2[w].\n;
else
coutThis is impossible.\n;
}
}
pl say hw i can improve.
thanks in advance.
--
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.
Re: [algogeeks] Longest interval with maximum sum
@fenghuang: the last step will take O(n logn ) . Or there is some better way? -- 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.
Re: [algogeeks] Amazon Interview Question
What if we have an array :- index - 1 2 3 4 5 value - 1 2 3 4 5 How will ANY logn solution determine all ALL elements are equal to it's index value ? Maybe I misunderstand. Thank you, Ashim On Sat, Dec 4, 2010 at 5:38 PM, ankit sablok ankit4...@gmail.com wrote: u can then move to other advance data structures On Sat, Dec 4, 2010 at 4:58 PM, mo...@ismu mohan...@gmail.com wrote: in worst case it takes o(n)time if all the elemets match with their indexes -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.
Re: [algogeeks] Re: Amazon Interview Question
If All the elements are unique and sorted in ascending order then we can design an algorithm for O(lgn) and all nos are positive. Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] FIND_EQUAL(A,start,end) 1.Go to the middle element 2.If A[mid]==mid) return mid+1; if(A[mid]mid) then FIND_EQUAL(A,start,mid-1) else FIND_EQUAL(A,mid+1,end) Runs in O(lgn) On Sun, Dec 5, 2010 at 12:20 PM, jai gupta sayhelloto...@gmail.com wrote: Any algorithm must in worst case lead to O(n) if the elements are not unique. Take the case: 1 2 3 4 5 6 as all the elements satisfy the condition of of key==index . we must go someway to each element. Hence O(n). This may be somehow made less if the element are given to be unique by using heap. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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.
Re: [algogeeks] Re: Amazon Interview Question
yaar I can use simple O(n) sweep to find out who all are equal, I think it can't be less than this On Sat, Dec 4, 2010 at 8:05 PM, Abioy Sun abioy@gmail.com wrote: 2010/12/4 ankit sablok ankit4...@gmail.com: as all the elements are sorted in the array make a min heap of the array elements and as min heap is a tree of keys querying a min heap or a binary search tree requires operations with time equal to the height of the tree which is log(n) hence time for querying a min heap I think you might be use a log(n) time to find out a element whose value is equal to some certain index, so the complexity could be n*log(n)? -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.
Re: [algogeeks] Spoj problem-pigbank
#includeiostream
#includeclimits
using namespace std;
int m[1];
struct coin
{
int value;
int weight;
}s1[1000];
main()
{
int t,w0,w1,n,temp,temp1,i,j,w;
cint;
while(t--)
{
cinw0w1;
w=w1-w0;
cinn;
temp1=INT_MAX;
for(i=1;i=n;i++)
{
cins1[i].values1[i].weight;
if(temp1s1[i].weight)
temp1=s1[i].weight;
}
for(i=0;itemp1;i++)
m[i]=0;
for(i=temp1;i=w;i++)
{
temp1=INT_MAX;
for(j=1;j=n;j++)
{
temp=0;
if(i-s1[j].weight=0)
{
if(m[i-s1[j].weight]0 || i==s1[j].weight)
temp=m[i-s1[j].weight]+s1[j].value;
}
if(temptemp1 temp!=0)
temp1=temp;
}
if(temp1==INT_MAX)
m[i]=0;
else
m[i]=temp1;
}
if(!m[w])
coutThis is impossible.endl;
else
{
coutThe minimum amount of money in the piggy-bank is
m[w].endl;
}
}
}
This is my code
On Sun, Dec 5, 2010 at 2:01 PM, Bharath 2009503507 CSE
bharathgo...@gmail.com wrote:
i am a beginner.pl help me with this code.i submitted a solution.it s
giving op for all given testcases.but the judge is giving me a TLE.
code:
#includeiostream
#includemap
#define inf 9
using namespace std;
mapint,int m2;
int func(mapint,int m1,int w)
{
if(m2[w]inf)
return m2[w];
mapint,int::iterator it;
int min=inf;
for(it=m1.begin();it!=m1.end();it++)
{
if((*it).second=w)
{
int x=func(m1,w-(*it).second);
if(x+(*it).first min)
min=x+(*it).first;
}
}
m2[w]=min;
return min;
}
main()
{
int t;
cint;
while(t--)
{
int w1,w2;
cinw1w2;
int w=w2-w1,no,a,b;
cinno;
mapint,int m1;
for(int i=0;ino;i++)
{
cinab;
m1.insert(pairint,int(a,b));
}
m2[0]=0;
for(int i=1;i=w;i++)
m2[i]=inf;
func(m1,w);
if(m2[w]!=inf)
coutThe minimum amount of money in the piggy-bank is
m2[w].\n;
else
coutThis is impossible.\n;
}
}
pl say hw i can improve.
thanks in advance.
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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] Re: k nearest points
use kd-tree -- 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.
Re: [algogeeks] Re: Amazon Interview Question
@Nikhil run you algo .. on test case index - 1 2 3 4 5 value - 1 2 3 4 5 ouput is mid+1= 3+1=4 but it should be 5... correct me if i am wrong... and u have assumed all are positive, hence base index should be 1 On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: If All the elements are unique and sorted in ascending order then we can design an algorithm for O(lgn) and all nos are positive. Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] FIND_EQUAL(A,start,end) 1.Go to the middle element 2.If A[mid]==mid) return mid+1; if(A[mid]mid) then FIND_EQUAL(A,start,mid-1) else FIND_EQUAL(A,mid+1,end) Runs in O(lgn) On Sun, Dec 5, 2010 at 12:20 PM, jai gupta sayhelloto...@gmail.comwrote: Any algorithm must in worst case lead to O(n) if the elements are not unique. Take the case: 1 2 3 4 5 6 as all the elements satisfy the condition of of key==index . we must go someway to each element. Hence O(n). This may be somehow made less if the element are given to be unique by using heap. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile -- 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.
Re: [algogeeks] Re: Amazon Interview Question
@ashim please refer my post.I posted an o(lgn) algo.i.e. I am copying again
below with an update
If All the elements are unique and sorted in ascending order then we can
design an algorithm for O(lgn) and all nos are positive.
Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]
FIND_EQUAL(A,start,end)
1.Go to the middle element
2.If A[mid]==mid||mid==0)
{
if(mid==0A[0]!=0)
return 0;
return mid+1;
}
if(A[mid]mid)
then FIND_EQUAL(A,start,mid-1)
else
FIND_EQUAL(A,mid+1,end)
Runs in O(lgn)
On Sat, Dec 4, 2010 at 8:08 PM, Ashim Kapoor ashimkap...@gmail.com wrote:
yaar I can use simple O(n) sweep to find out who all are equal, I think it
can't be less than this
On Sat, Dec 4, 2010 at 8:05 PM, Abioy Sun abioy@gmail.com wrote:
2010/12/4 ankit sablok ankit4...@gmail.com:
as all the elements are sorted in the array make a min heap of the
array elements and as min heap is a tree of keys querying a min heap
or a binary search tree requires operations with time equal to the
height of the tree which is log(n) hence time for querying a min heap
I think you might be use a log(n) time to find out a element whose
value is equal to some certain index, so the complexity could be
n*log(n)?
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
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.
Re: [algogeeks] Re: k nearest points
@jai gupta how can you find solution in O(n) in O(n) you can just find the distance of all the points form origin.. then find the k smallest numbers(distance) in O(k log n + n ) using heap short.. On Sun, Dec 5, 2010 at 7:28 PM, alexsolo asp...@gmail.com wrote: use kd-tree -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile -- 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.
Re: [algogeeks] Re: k nearest points
@alexsolo what is Kd-tree .. plz explain a little bit you algorithm... On Sun, Dec 5, 2010 at 7:28 PM, alexsolo asp...@gmail.com wrote: use kd-tree -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile -- 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] Re: Dynamic prog.
Could anyone able to provide pseudo code/algorithm for this problem using DP? On Dec 1, 11:42 pm, Harshal hc4...@gmail.com wrote: Someone please explain why do we need dynamic programming approach to solve this? Cant we find the solution as mentioned by 'algose chase' above?? -- 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] FINDSR in spoj
I've did the problem http://www.spoj.pl/problems/FINDSR with brute force approach.. It is showing TLE.. Anyone tell the approach to solve that problem... -- 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.
