The problem with inheritence is that it is compile time(i.e a class A
inheriting from class B cannot be modified again) whereas composition can
be used to change the objects during runtime(by having a base class pointer
we can change the objects runtime).
Correct me if i'm wrong.
On Sun, Jun
*Hi,*
*
*
*Based on most comments, The popular puzzle of the last week is*
*
*
*
http://dailybrainteaser.blogspot.com/2011/06/find-next-number.html?lavesh=lavesh
*
*
*
**
*
*
*
http://dailybrainteaser.blogspot.com/2011/06/sherlock-puzzle.html?lavesh=lavesh
*
*
*
You Can Also follow us on Facebook
http://www.spoj.pl/problems/STRDIST/
Getting WA repeatedly. Can someone help me with the below code.
#include iostream
#include string
#include stdio.h
#include algorithm
using namespace std;
int main()
{
int k,l;
scanf(%d %d,k,l);
string str1 = ;
string str2
@Divye:
Awesome solution dude with amortized complexity of O(1)!
The examples made things even clearer :)
On Jun 26, 8:13 am, DK divyekap...@gmail.com wrote:
I've solved it for find_min() - the find_max implementations are analogous.
Example:
i = insert
d = delete
i 1 -
q - 1
dq - 1 --
Given a sequence of numbers in the range of 1-N^2, what is the most
efficient way to sort the numbers (better than NlgN)..
Can counting sort be used here? Is an O(N) solution possible..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
Yes ! Count Sort !!
On Sun, Jun 26, 2011 at 1:44 PM, ross jagadish1...@gmail.com wrote:
Given a sequence of numbers in the range of 1-N^2, what is the most
efficient way to sort the numbers (better than NlgN)..
Can counting sort be used here? Is an O(N) solution possible..
--
You received
this is so helpful :P
On Sun, Jun 26, 2011 at 12:30 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote:
*Hi,*
*
*
*Based on most comments, The popular puzzle of the last week is*
*
*
*
http://dailybrainteaser.blogspot.com/2011/06/find-next-number.html?lavesh=lavesh
*
*
*
**
*
*
So finally what will be the solution?
Harshal's solution doesn't print the characters in the order of
appearance in the orignal array as nishant righly pointed out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
anonymous see this http://ideone.com/TuNbS
Can anyone tell me why gcc complier giving this warning
prog.c:8: warning: implicit declaration of function ‘strlen’
On 6/26/11, anonymous procrastination opamp1...@gmail.com wrote:
So finally what will be the solution?
Harshal's solution doesn't print
use
#includestring.h instead of #includestrings.h
--
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
I don't know how far u have been able to conquer the problem .. We tried
this and used epipolar geometry and 7point algo and found the Homography
matrix.. try referring to Hartley and Zeisserman book.!!
On Thu, Jun 23, 2011 at 3:52 PM, DK divyekap...@gmail.com wrote:
Perspective transformations
@radhakrishnan: Counting sort in this case, will be O(n2).. as it
involves traversing the entire array!
On Jun 26, 5:03 pm, L prnk.bhatna...@gmail.com wrote:
Count sort is O(n+k), since k~n^2 here, it will be O(N^2).
Radix sort has complexity O(r.n) which is nearly O(n logn).
Are you sure that
@L: It was asked if we could take advantage of the ranges of the
integers between 1-N^2..
I doubt if its possible.
On Jun 26, 5:33 pm, ross jagadish1...@gmail.com wrote:
@radhakrishnan: Counting sort in this case, will be O(n2).. as it
involves traversing the entire array!
On Jun 26, 5:03 pm,
@ross:
I guess the orignal problem is that there are N numbers which are all in the
range [1, N * N], can you do the sorting in O(N) time complexity?
If this is true, we can firstly do the discretization and then do the
counting sort.
--
You received this message because you are subscribed to
@Rujin Cao: Yea, your formulation of the problem is correct.. my bad,.
missed that there are N numbers.
can u elaborate more on the discretization procedure and how ll u do
counting sort (which might warrant traversing of N^2 elements)
On Jun 26, 5:45 pm, Rujin Cao drizzle...@gmail.com wrote:
hmm for starting this , we need 2 shots of a scene right? I have only a
single image..no stereo vision here
On Sun, Jun 26, 2011 at 2:16 PM, sukhmeet singh sukhmeet2...@gmail.comwrote:
I don't know how far u have been able to conquer the problem .. We tried
this and used epipolar geometry and
@aditya:it is given in the question that u cannot access the entire
element in single operaion..therefore both your above solution do not
hold for this question.
On 6/25/11, sunny agrawal sunny816.i...@gmail.com wrote:
@Dave
yes u r right that integers means it can be big integers too.
@dave:can u please give the divide and conquer solution
On 6/26/11, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@aditya:it is given in the question that u cannot access the entire
element in single operaion..therefore both your above solution do not
hold for this question.
On 6/25/11,
@ross:
It seems that after discretization , the time complexity still would be
O(nlogn).
The discretization idea is:
say there are 4 numbers, each of them is in the range[1, 16].
e.g. 12 3 12 15
You can do one time transverse to map each of them to a global increasing
index (hashing is the
@Kamakshii: In O(n), you can determine whether the low order bit of
the missing number is 0 or 1. You can eliminate the approximately n/2
numbers that do not have this low order bit. Then, in O(n/2), you can
determine the next-to-low order bit. Etc. O(n) + O(n/2) + O(n/4) + ...
= O(n).
Dave
On
Use a radix sort.
Complexity of the radix sort is O(N k) where k is the number of digits used
to represent the number in some base b.
If we use the convenient fiction that both N and N^2 fit into the same 32
bit integer then
k is a constant and we get an O(N) sort. (It's kindof cheating :) ).
YES.. we need to have 2 shots.. !!
u said u had some matching points in the 2 images
On Sun, Jun 26, 2011 at 6:23 PM, Arun Vishwanathan
aaron.nar...@gmail.comwrote:
hmm for starting this , we need 2 shots of a scene right? I have only a
single image..no stereo vision here
On Sun, Jun
Given an array A , of N integers ( In no particular order), fill up an
auxilary array B such that B[i] contains the product of
all elements in A other than A[i].
Constraints:
O(n) Time,
Can this be done with O(1) space?
Division is *not* allowed .
eg: A 1 2 3 4 5
B 120 60 40 30 24
--
You
@Divye: Good theoretical proof and analysis as well.. As you
mentioned, this one works like charm for uniformly distributed
inputs :)
On Jun 26, 8:36 pm, DK divyekap...@gmail.com wrote:
Use a radix sort.
Complexity of the radix sort is O(N k) where k is the number of digits used
to represent
u can use radix sort
On Sun, Jun 26, 2011 at 9:44 PM, ross jagadish1...@gmail.com wrote:
@Divye: Good theoretical proof and analysis as well.. As you
mentioned, this one works like charm for uniformly distributed
inputs :)
On Jun 26, 8:36 pm, DK divyekap...@gmail.com wrote:
Use a radix
@Ross: This satisfies your constraints...
B[0] = 1;
for( i = 1 ; i N ; ++i )
B[i] = B[i-1] * A[i-1];
int x = 1;
for( i = N-1 ; i 0 ; --i )
{
x *= A[i];
B[i-1] *= x;
}
Dave
On Jun 26, 11:08 am, ross jagadish1...@gmail.com wrote:
Given an array A , of N integers ( In no particular
#include iostream
using namespace std;
int main()
{
int input[10];
int n;
coutenter nendl;
cinn;
int output[10];
coutenter input arrayendl;
for(int i=0;in;i++)
cininput[i];
int a[n],b[n];
a[0]=1;
for(int i=1;in;i++)
{
a[i]=a[i-1]*input[i-1];
}
this is goog question
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, Jun 26, 2011 at 10:04 PM, Dave dave_and_da...@juno.com wrote:
@Ross: This satisfies your constraints...
B[0] = 1;
for( i = 1 ; i N ; ++i )
B[i] = B[i-1] * A[i-1];
this will need two passes
first pass creates the hash map of char and count
second pass walk over the the string again, refer hash map to print that
many chars, remove this char from hash once printed and move on untill the
complete string is covered or hashmap size is 0
Best Regards
Ashish
@Dave: Very good solution.. I had thought an idea of using separate
arrays to store next and previous products. And multiplying the
elements of the 2 arrays to give B. The solution given by you
satisfies ALL constraints inplace :)
@sameer: Your solution is not O(1) in space dude..Dave's solution
--
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
.
Find solutions for Mathematics Institute Millennium Prize Problems by
replacing the food particles as prey with the solutions as prey in
HTML5 Javascript Neural Networks example.
Using Neural Networks with or without Genetic Algorithms to find
solutions to Clay Mathematics Institute Millennium
There are 6 beer bottle nd one is poisoned. we have mice who will die
within 14 hrs after drinkin poisned beer. In 24 hrs we have to find
poisoned beer bottle. How many no of mice we require to find out
poisoned bottle.
--
You received this message because you are subscribed to the Google Groups
3
On Mon, Jun 27, 2011 at 2:10 AM, amit the cool amitthecoo...@gmail.comwrote:
There are 6 beer bottle nd one is poisoned. we have mice who will die
within 14 hrs after drinkin poisned beer. In 24 hrs we have to find
poisoned beer bottle. How many no of mice we require to find out
poisoned
Find solutions for Clay Mathematics Institute Millennium Prize
Problems by replacing the food particles as prey with the solutions as
prey in HTML5 Javascript Neural Networks example. .
Find solutions for Clay Mathematics Institute Millennium Prize
Problems by replacing the food particles as prey
@DK - your solution works great but my only concern is that for the
worst case, insert() is not really O(1). For example, if you have 1000
elements being inserted in ascending order and then 1001'st element is
smaller than the first element, the insert() will become O(n).
On Jun 25, 10:13 pm, DK
can u please explain how is it 3?
On Jun 26, 11:18 pm, D.N.Vishwakarma@IITR deok...@gmail.com
wrote:
3 mice .
On Sun, Jun 26, 2011 at 6:13 PM, ArPiT BhAtNaGaR
arpitbhatnagarm...@gmail.com wrote:
3
On Mon, Jun 27, 2011 at 2:10 AM, amit the cool
amitthecoo...@gmail.comwrote:
A small tweak (and possible optimization) to Dave's algorithm mighe be
to use bit based array. That is, have an array of 12500 byte
values where for each byte, the 8 bits represent a flag of whether
that particular number is present in the file or not.
So, a[0] would indicate whether numbers
4
@amit what's the answer ?
On Mon, Jun 27, 2011 at 12:40 AM, shiv narayan narayan.shiv...@gmail.comwrote:
can u please explain how is it 3?
On Jun 26, 11:18 pm, D.N.Vishwakarma@IITR deok...@gmail.com
wrote:
3 mice .
On Sun, Jun 26, 2011 at 6:13 PM, ArPiT BhAtNaGaR
3
think in binary.. :)
On Mon, Jun 27, 2011 at 12:56 AM, Arpit Sood soodfi...@gmail.com wrote:
4
@amit what's the answer ?
On Mon, Jun 27, 2011 at 12:40 AM, shiv narayan
narayan.shiv...@gmail.comwrote:
can u please explain how is it 3?
On Jun 26, 11:18 pm, D.N.Vishwakarma@IITR
first make two group of 3 bottle each
one mice for each group
make mixture of 3 bottle and put for mice .
do same for other group
only one mice will die
. then select group of dead mice .
beak it into three group
one bottle each
now we can use old mice which is not dead and one more for two bottle
3 Mice: Call them mouse #1, mouse #2, and mouse #4 (think binary
code).
Give mouse #1 a mixture of bottles 1, 3, and 5.
Give mouse #2 a mixture of bottles 2, 3, and 6.
Give mouse #4 a mixture of bottles 4, 5, and 6.
Add up the numbers of the mice that die to get the number of the
poisoned beer
you cant use the old mouse again because time he has mentioned is 14
hours... so you will have to wait for another 14 hours which exceeds the
given time limit of 24 hours... so it is 4.
On Mon, Jun 27, 2011 at 1:00 AM, D.N.Vishwakarma@IITR deok...@gmail.comwrote:
first make two group of
thanks dave.
On Mon, Jun 27, 2011 at 1:07 AM, Dave dave_and_da...@juno.com wrote:
3 Mice: Call them mouse #1, mouse #2, and mouse #4 (think binary
code).
Give mouse #1 a mixture of bottles 1, 3, and 5.
Give mouse #2 a mixture of bottles 2, 3, and 6.
Give mouse #4 a mixture of bottles 4, 5,
@D.N.: The problem with your solution is that it can take up to 28
hours, but you must determine the poisoned beer in at most 24 hours.
Dave
On Jun 26, 2:30 pm, D.N.Vishwakarma@IITR deok...@gmail.com wrote:
first make two group of 3 bottle each
one mice for each group
make mixture of 3
@Sankeet: How do you know that you wouldn't do more i/o for swapping
than just reading the data twice? Since the input numbers are not
sorted, it seems that you could be swapping a different block in for
every number.
Dave
On Jun 26, 2:12 pm, Sanket vasa.san...@gmail.com wrote:
A small tweak
1. There are N address lines in the procesor, which is true regarding the
virtual space of the running process and why
a. there is no limit on virtual space
b. 2^N bytes in virtual space
c. it depends upon size of RAM
d. none of the above
--
You received this message because you are subscribed
hw u r gettin 3
i m gettin 4
mine is make 4 grups
1,2,6 no 1
2,3,5 no 2
1,3,4 no 3
4,5,6no 4
nw out of 4 2 mice will die,and in their corresponding groups common bottle
will give you the answer.
correct me if i am wrong
--
You received this message
@Harshit: Check dave's solution... U'll get ur ans :)
--
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
i got it :)
nice @dev!!
--
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,
I found the problem statement on the web page link to be a bit
weak. Nothing in the problem statement says that you must do
anything other than read in two lines of integers and multiply them in
pairs and sum the results ( ie. Dot Product ).
People seem to think that you should sort the data
Your question is good for a classroom style discussion/debate.
However, in the real world, there is no simple answer.
There are lots of sorting algorithms. Each one has it's pros cons
and no single sorting algorithm is best, especially when not much is
known about the data to be sorted. In
thanks dave..
On 6/26/11, Dave dave_and_da...@juno.com wrote:
@Kamakshii: In O(n), you can determine whether the low order bit of
the missing number is 0 or 1. You can eliminate the approximately n/2
numbers that do not have this low order bit. Then, in O(n/2), you can
determine the
@Dan: see, that is not the point. We are just looking for a better
solution not just an algorithm which fetches us 0.00 time given the
SPOJ conditions. Actually we are not worried about the compiler stuff
because its all relative. Some other person on this SPOJ platform has
submitted the code
Dave - Can you elaborate on how you can do this - you can determine
whether the low order bit of the missing number is 0 or 1
On Jun 26, 2:32 pm, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
thanks dave..
On 6/26/11, Dave dave_and_da...@juno.com wrote:
@Kamakshii: In O(n), you can
These type of solutions require to think in binary.
First of all leave the last one because if we don't find a poisoned
bottle in first 5 then it means the last one is poisoned.
So 5 can be expressed using 3 bits.
these 3 bits will correspond to mice... 1 indicates the mice drinks
and 0 indicates
Harshal's solution can be modified to make it worth with just 1 pass
over the input string.
What we need is an additional link pointer for each entry in the
auxillary array.
Additionally, we need current and start pointers which will be
null to start with.
Now, for every character in the input
5 mice:
result time complete
bottle to mice1: 14 hour
after 2.5 hour to mice2 : 16.5 hour
after 2.5 hour to mice3 : 19 hour
after 2.5 hour to mice4 : 21.5 hour
after 2.5 hour to mice5 : 24 hour
one of
Use the view as source code option in your web browser to view the
code at http://www.nixuz.com:8080/html5/fish.html. Modify the code by
replacing the food particle code with the Millennium or other problem
code, save and run from your browser as a local file or upload to a
host server / cloud as
@Sanket: Sure. 0^1^2^...^N is periodic with period 4. Thus, only the
last two bits of N need be considered, i.e., N 3. You could index
into an array A[] = {0,1,1,0}, or note that 0110 in binary is 6, so
the expression can be evaluated with bit operations by (6 (N 3))
1. Also, calculate the xor
Thanks Dave.
Won't Also, calculate the xor of the low order bits of the data
require you to access each value in the array once? Or am I not
understanding what you meant?
On Jun 26, 6:50 pm, Dave dave_and_da...@juno.com wrote:
@Sanket: Sure. 0^1^2^...^N is periodic with period 4. Thus, only the
http://anandtechblog.blogspot.com/2010/09/given-array-of-numbers-replace-each.html
On Sun, Jun 26, 2011 at 10:12 AM, ross jagadish1...@gmail.com wrote:
@Dave: Very good solution.. I had thought an idea of using separate
arrays to store next and previous products. And multiplying the
elements
@HowTechStuffWorks - I haven't heard of a recommendation to use
composition over inheritance. In my opinion, it is simply based on the
problem space. If you have related entities that have commonality that
you wish to abstract, you use inheritance. Composition is preferred
when you have dependent
hey harry.what r u upto?
guys have already shown that answer is three
On Mon, Jun 27, 2011 at 4:45 AM, hary rathor harry.rat...@gmail.com wrote:
5 mice:
result time complete
bottle to mice1: 14 hour
after 2.5
Need a Better Algorithm
here is a trivial question we are given an array of 2n elements in the
form
{a1,a2,a3,..,an,b1,b2,b3b...bn}
we need to output a resultiing array in the form
{a1,b1,a2,b2,an,bn}
but without using another array here is my algorithm which uses nested
loops
You are correct, this question is by no means testing anything non trivial/hard.
It is one of the problems that the beginners in competitive programming solve.
As for the discussion regarding this problem in current thread, some
enthusiastic
guy had got this AC in 0.08 at SPOJ, and everyone was
I am able to get this accepted with 0.00 Seconds http://ideone.com/Eg2wZ
But, I am using 512 KB Buffer. Not sure how I do get 0.00 with a
smaller buffer size say 8KB
On Sun, Jun 26, 2011 at 7:54 AM, Wladimir Tavares wladimir...@gmail.com wrote:
sometimes using global static variables may be
@Sanket: Yes. That is the first O(n) in my previous posting
http://groups.google.com/group/algogeeks/msg/cd32a2276c6a2d22.
Dave
On Jun 26, 6:55 pm, Sanket vasa.san...@gmail.com wrote:
Thanks Dave.
Won't Also, calculate the xor of the low order bits of the data
require you to access each
2^N bytes in virtual space. Because since the processor has N address
lines so the processor can address only 2^N bytes of data, even though
the actual RAM may be less than 2^N bytes of data or the RAM allocated
to a process is less than that.
On Sun, Jun 26, 2011 at 12:49 PM, Akshata Sharma
69 matches
Mail list logo
