@vikas
I believe that if we generalize the question saying that there are N
students and K schools, such that each school can accommodate at max
(N/K) students (which means each school needs to accommodate exactly
(N/K) students. Given this we need to find the minimum distance.
By O(n^3), in this
@ above
small correction..
/*
By O(n^3), in this case it means O((N/K ^ K)) .
*/
Therefore, N = 9, K=3.. hence (9/3)^3 = 27
On Aug 4, 4:24 am, Lucifer sourabhd2...@gmail.com wrote:
@vikas
I believe that if we generalize the question saying that there are N
students and K schools, such that
What is N? This is a fixed-size problem so by definition, every
solution will be constant time.
Don
On Aug 1, 2:48 am, vikas rai vikasloves...@gmail.com wrote:
There is a set of 9 students and 3 schools Every school can be alloted
atmax 3 students .Every school and student has its coordinates
Atul,
I think that your approach will work, although it may take a huge
amount of time.
One way to potentially make it faster is to select the invoices with
the smallest number of combinations first.
If you first select all of the invoices with exactly one possible
combination, this will prevent
@Dave : is it a working code??
i have executed your code but getting wrong output...and value of s is
becoming -ve inside loops.
--
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.
0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h
- 1, i+1) )
i am not clear why the parents of a cup in upper row are consecutive?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 10:43 AM, Gene
Well the OP is not clear. You could be right. I solved this problem
once before, and there the glasses were arranged in a pyramid like
they do at weddings in my country (this will only look right if you
set the fixed-width font in Groups:
U
U U
U U U
U U U U
U U U U U
---
The previous proposed solutions all seem far too complicated. It is
not necessary to use a graph data structure. We can simply use an
array to store the quantities of the cups in a row, and update the
array to move to the next row. It would look something like this:
double cupQuan(double L,
Dave, why the assumption that nothing is coming from left side.
Every cup gets something from cup left above and right above itself when
they have something extra?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Mon, Feb 27, 2012 at 8:17 PM, Dave
@Ashish: I didn't make any assumption that nothing comes from the
left. Does my code give the wrong answer?
Dave
On Feb 27, 10:36 am, Ashish Goel ashg...@gmail.com wrote:
Dave, why the assumption that nothing is coming from left side.
Every cup gets something from cup left above and right
Dave's code is good. Here is a more abstract way of thinking about
it. Maybe helpful?
Number the rows starting at the top with h=0, and the left i=0. Then
the parents of cup(h,i) are always cup(h-1,i-1) and cup(h-1,i). When
h0, i0 or i h, the parent does not exist.
Let F(h, i) be the amount
Gene, your DP is what i was thinking of but in code i could not coreleate
G(h - 1, i - 1) + G(h - 1, i) part (:
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote:
G(h - 1, i - 1) +
@Dave : my code is not that complicated ...if you ignore the helper
function and check fillCup();
it just similar to preorder travesal and pour half to left and right child.
here is the explanation :-
node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
@Atul: I don't have an n in my algorithm, so I'm not sure what your
assessment that my algorithm is O(n^2) means. My algorithm is O(h^2),
where h is the height of the triangle of cups, but the number of cups
is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is
yours.
You'll have to
G is just a helper function. You can in line this function and
eliminate it.
When you do this, you'll end up with
F(h, i) = 0.5 * (l + r)
where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else
0
and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0
Here l is the left
@Dave : yeah sorry its O(n) where n is number of nodes.
yeah as i said before its a nice approach...
On Tue, Feb 28, 2012 at 10:15 AM, Dave dave_and_da...@juno.com wrote:
@Atul: I don't have an n in my algorithm, so I'm not sure what your
assessment that my algorithm is O(n^2) means. My
@Gene , @dave : +1 +1
On Tue, Feb 28, 2012 at 10:49 AM, atul anand atul.87fri...@gmail.comwrote:
@Dave : yeah sorry its O(n) where n is number of nodes.
yeah as i said before its a nice approach...
On Tue, Feb 28, 2012 at 10:15 AM, Dave dave_and_da...@juno.com wrote:
@Atul: I don't have
You are assuming is to be a binary tree, its not. Some nodes will
share a common pour.
On Feb 25, 9:24 pm, atul anand atul.87fri...@gmail.com wrote:
i guess this would work...
n=number of nodes
h=height;
pour=quantity poured;
capacity = capacity of each cup
n=pow(2,h+1) -1;
@all
same doubt qstn appears to be of binary tree DS
but the diagram given in between qstn is not like Binary tree so
sharing is there
so how sharing is done plz explain??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
@Ravi: checkout this code...i have created tree where there is sharing of
nodes..
here is my code :-
please let me know is case you find any bug.
#includestdio.h
typedef struct tree{
int idx;
float data;
struct tree *left;
struct tree *right;
}node;
node *createNode(int index)
{
node *temp;
@Sourabh - whats the running time?
On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote:
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
O(N*K)
On Nov 28, 1:04 pm, Nitin Garg nitin.garg.i...@gmail.com wrote:
@Sourabh - whats the running time?
On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote:
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks
Hi
I may not have understood your solution properly. But i think that
your solution is an implementation of brute force where you are
dealing with all cases valid in the range n/2k and 3n/2k without any
optimization with regard to DP. Am i right?
On Nov 28, 2:17 am, sourabh
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking N/K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time would be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm,
Yes nithin its O(n^2)..
The reasoning being say,
We store all the values in a 2-d array of size N * K.
Now to compute each element of the above array , we are looking at N/
K
(3n/2k - n/2k) sub problems..
Hence, the running time will be,
O( N * K * N / K ) i.e O( N^2)...
On Nov 28, 6:42 pm, Nitin
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM,
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to
since its a phone number storing problem, you can sort the numbers and store
the differences. That way you can generate the required number on the go
On Thu, Jun 30, 2011 at 4:39 AM, juver++ avpostni...@gmail.com wrote:
@Navneet
Please read problem again - it is about memory efficient storing.
In TRIE , we can store nodes by characters. So it is very easy to search by
names and hence their corresponding numbers :) .
TRIE saves a lot memory coz it stares a character only once.
LIKE :-
if i want to save sagar with phone no. 123456789 then we store it in TRIE
as :
s-NULL
|
a-NULL
|
Sorry for the previous post it got a mistake here take a look again :-
In TRIE , we can store nodes by characters. So it is very easy to search by
names and hence their corresponding numbers :) .
TRIE saves a lot memory coz it stares a character only once.
LIKE :-
if i want to save sagar
I wonder why people have discarded the idea of Hash map here.
Searching is obviously the most important task here and if we are to
assume that names can be uniformly hashed over a table of 1000 rows
with each row containing 1000 names each.
Further optimization can be achieved by having names
@samby
You are wrong anyway. Main problem is to reduce memory while storing phone
numbers.
We have 1 million of phones, they have many common prefixes which can be
addressed by trie.
For storing names, you may use any data structure which is best for the
particular problem.
Key is name, and
@Navneet
Please read problem again - it is about memory efficient storing.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/-hsmsOgm2YUJ.
To post to this
if u have known the answer u would have probably answered rather than
writing this thing..:|
On Jun 29, 5:40 pm, shady sinv...@gmail.com wrote:
go through the archives you will definitely find the answer :)
On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.com wrote:
What is
u r right buddy but problem is to save memory
On Jun 29, 7:33 pm, ankit sambyal ankitsamb...@gmail.com wrote:
Hey guys, phone usually has comparatively very less memory. So, we
can't afford to have pointers for each phone no. So, the idea of
having a tree is rooted out. The best way can be
trie uses more space
On Jun 29, 5:52 pm, sudheer kumar chigullapallysudh...@gmail.com
wrote:
USE TRIE
On Wed, Jun 29, 2011 at 6:10 PM, shady sinv...@gmail.com wrote:
go through the archives you will definitely find the answer :)
On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR
Please explain why you think TRIE use more space?
To my knowledge TRIE says lot of memory as the common numbers are saved only
once.. If you have any good reason then please explain and don't make any
single line statements.
On Wed, Jun 29, 2011 at 9:21 PM, MONSIEUR monsieur@gmail.com wrote:
@Swathi :We can't use trie data structure to store the phone numbers.
The most sound reason is that the users require phone numbers to be
sorted by name, but by using the trie data structure we can't get the
phone numbers which are sorted by name. Again we can't use trie whose
nodes are numbers,
1,2,43,41,5 , 6
Start at a[3] and a[5] Swap them up .
Reversing it , we get
1,2,43,5,6,41
This does not work
.
On Jun 23, 9:05 pm, Swathi chukka.swa...@gmail.com wrote:
We just need to find the start and end of the decreasing sequence then we
have to reverse the elements in that decreasing
http://anandtechblog.blogspot.com/2011/06/bitonic-merge.html
On Fri, Jun 24, 2011 at 2:17 AM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
1,2,43,41,5 , 6
Start at a[3] and a[5] Swap them up .
Reversing it , we get
1,2,43,5,6,41
This does not work
.
On Jun 23, 9:05 pm, Swathi
@Anand : Plz explain ur algo ???
On Fri, Jun 24, 2011 at 10:55 AM, Anand anandut2...@gmail.com wrote:
http://anandtechblog.blogspot.com/2011/06/bitonic-merge.html
On Fri, Jun 24, 2011 at 2:17 AM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
1,2,43,41,5 , 6
Start at a[3] and
@piyush Sinha
How can you do it in O(1) space and O(n) time dude .The inplace
merging of d sorted arrays take space O(log d) space at least i
think .Plus even at every step , we have to do O(log n) comparisions
to find the next larger or smaller element .How can this be O(n) ???
WAiting eagerly
We just need to find the start and end of the decreasing sequence then we
have to reverse the elements in that decreasing sequence by swapping the
elements at both the edges...
On Thu, Jun 23, 2011 at 2:13 PM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
@piyush Sinha
How can you do
@Piyush: could u plz post the link to the same?
On Jun 22, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote:
This question has been discussed over here once...It was concluded
that this can be solved in O(n) if we know there is a fixed range up
to which the elements keep on increasing and
I heard somewhere in some online video lecture that sites like tinyurl
change the address using more than base three {base 6 } and then apply
hash
On 6/4/11, bittu shashank7andr...@gmail.com wrote:
well i can speak much on these question.as these algorithms are part
of web crawler ..but do u
@Nate...Both TinyUrl Bit.ly Fails in case of our web address is less
then length of their(tinyurl/bit.ly) names..
example if u will try http://www.a.com/a (num of chars 18) in
tinyurl.com it will convert http://tinyurl.com/cl3nc4 which 25 chars
long surly greater then original url length so
well i can speak much on these question.as these algorithms are part
of web crawler ..but do u mean we have to detect the duplicate files,
by file having same size are duplicates..??
also same question raised by me few days back Detecting Duplicate
Documents but no one seems to interested u can
i also thought its relative to database but ultimately it also
depends on the data structure Algorithms used by database to
implement the particularly query.
The simpler implementation of this service is to store, in a database
table, a data pair (id, url) where your id has the autoincrement
Suppose I press As only throughout .
We will have the number of As as A*(number of keystrokes) .This is the
least we can get provided we play stupidly enough .
On Jan 29, 9:16 pm, Saikat Debnath saikat@gmail.com wrote:
@ Sankalp : plz explain this line of yours : No. of As=A*(total number
We can do it Using a binary search approach (The cost function is
monotonic over here , so we can use binary search)
No. of As=A*(total number of keystrokes) , gives us a bound . We
should have a lower bound as this , we can always get this much As
Take the initial value as high and low as
@ Sankalp : plz explain this line of yours : No. of As=A*(total number
of keystrokes) , gives us a bound . We
should have a lower bound as this , we can always get this much As
On Jan 29, 5:32 pm, sankalp srivastava richi.sankalp1...@gmail.com
wrote:
We can do it Using a binary search approach
Nishant's soln is incorrect because he assumes, ctrlA and ctrlC are pressed
each time ctrlV is pressed.
As saikat has pointed out, this is incorrect.
According to me:
*buff = 0; //keeps track of last ctrlC*
*for each i*
*{*
* dp(i)=max(dp(i-1)+1, 2*dp(i-3), dp(i-1) + buff)*
*
@ Nikhil sir : I have coded the same solution, but was waiting for its
correctness to be proved... thanx.. :)
On Fri, Jan 28, 2011 at 1:01 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote:
Nishant's soln is incorrect because he assumes, ctrlA and ctrlC are pressed
each time ctrlV is pressed.
As
Following is the algorithm to ger max number of A's
set n[0] = 0
int get_max(int n)
{
--
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
Following is the algorithm to get max number of A's .
it gives number = 20 for n=10
set buff = 0
call get_max(n)
int get_max(int i)
{
if (i=1 i=3)
{
n[i] = i
m[i] = 'A'
return n[i]
}
else
{
num_A = getmax(i-3);
max= MAX(num_A+3,2*num_A, num_A+3*buff)
Following is the algorithm to get max number of A's .
it gives number = 20 for n=10
set buff = 0
call get_max(n)
int get_max(int i)
{
if (i=1 i=3)
{
n[i] = i
m[i] = 'A'
return n[i]
}
else
{
num_A = getmax(i-3);
max= MAX(num_A+3,2*num_A,
it will give m=15 for n=10,but actually m=16
On Jan 21, 10:58 am, Preetam Purbia preetam.pur...@gmail.com wrote:
Hi,
I think this method will work:
Possible Number of A's = N/2(1+R)
where R=N-(N/2+3)
assuming 11/2 = 5
Thanks
Preetam
On Fri, Jan 21, 2011 at 2:29 AM, Anand
//get n;
if(n%3==0)
{
v=6;
pw=(n-3)/3;
}
else if(n%3==1)
{
v=4;
pw=(n-1)/3;
]
else
{
v=5;
pw=(n-2)/3;
}
maxtimes=(v)*pow(2,pw);
sequence is pressing 'A' v times followed by (select+copy+paste=3
operations) pw times which means 3*pw;
total 3*pw+v=n times
On Jan 19, 8:28 pm, bittu
hope this works :
#includestdio.h
#define MAX(A,B) AB?A:B
#defineMIN(A,B) AB?A:B
int FindMaxA(int n)
{
int i,k,factor,max = 0,cur,prev;
int* arr = new int[n+1];
int p = MIN(n,4);
for( int j = 1;j = p;j++)
arr[j] = j;
for(i=5;i=n;i++)
{
k = i-4;
I think its correct.
On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote:
How about the following dynamic programming solution.
Let dp[i] be the max no of As with i keystrokes.
dp[i]=max(dp[i-1]+1,2*dp[i-3])
dp[N] is the required solution.
Correct me if i am wrong.
On Wed, Jan
According to me Nishaanth's solution is incorrect, as let for n =10, your
output : m=16
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20.
On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20.
Try this on a notepad. you will only 15A's
On Thu, Jan 20, 2011 at 12:46 PM, Saikat Debnath saikat@gmail.comwrote:
According to me Nishaanth's
Hi,
I think this method will work:
Possible Number of A's = N/2(1+R)
where R=N-(N/2+3)
assuming 11/2 = 5
Thanks
Preetam
On Fri, Jan 21, 2011 at 2:29 AM, Anand anandut2...@gmail.com wrote:
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
resulting in 7 keystrokes. then
Keys 23 may be combined, cause there is no sense to use them separately.
It's cost of pressing is 2, however.
For all other keys the cost is 1 though.
DP[i][n] - maximum number of A's we can produce with cost of pressings = i
and we have string of A's with size n in a clipboard.
DP[N][any] -
http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html
On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote:
Given
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
If you can only press the keyboard for N times (with the above four
keys), please write a program to produce maximum numbers of
How about the following dynamic programming solution.
Let dp[i] be the max no of As with i keystrokes.
dp[i]=max(dp[i-1]+1,2*dp[i-3])
dp[N] is the required solution.
Correct me if i am wrong.
On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote:
this will not work out
a[0]b[0] doesn't mean that a[0]+b[i] is ith largest sum
try
int a[]={10,8,6,4,1};
int b[]={9,6,3,2,1};
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Oct 6, 2010 at 11:36 PM, ligerdave david.c...@gmail.com wrote:
http://coders-stop.blogspot.com/2010/12/most-used-data.html
On Jan 7, 5:24 pm, bittu shashank7andr...@gmail.com wrote:
You have a stream of infinite queries (ie: real time Google search
queries that people are entering). Describe how you would go about
finding a good estimate of 1000 samples
@sourav
I think the best way to explain my logic is to draw a 2D matrix
5 4 2 1
6
5
4
2
then you would find the patten. i have something draw on the paper. if
you need, i guess i can scan and send it out
On Oct 7, 10:05 am, sourav souravs...@gmail.com wrote:
@lingerdave
If you get
@ Ercan,
yes, you were right. i forgot about that.
anyway, that's the idea. you would need to move pointers on both,
depends on which is bigger. for loop w/ i=k, when the loop stops, you
have the pointers pointing at the numbers you wanted
On Oct 6, 7:16 pm, Gönenç Ercan gon...@gmail.com wrote:
A - 5, 4, 2, 1
B - 6, 5, 4, 2,
M - 6,b,5,a,5,b,4,a,4,a,2,a,2,a,1,a
x=6b, find the index of B[1]=5 in A, which is 0. so 1 big number. k=1
x=5a, find the index of A[1]=4 in B, which is 3. so there are 2 more,
k=3
.
.
.
In the case if k=2 is asked, we know that k=2 can be found when a=5,
then
use pointers and lengths of two arrays. depends on what K is, if K
m*n/2, you reverse the pointers. therefore, the worst case is either
O(m) when length of m is shorter or O(n) when length of n is
shorter,
make the pointers pointing to the first elements in both arrays.
A)
4,3,2,2,1
^
B)
A - 5, 4, 2, 1
B - 6, 5, 4, 2, 1
k = 3,
ignoring duplicates, the answer is 9 (a=5, b=4) but doesn't the
algorithm below give 8 (a=2, b=6)?
On Oct 6, 9:06 pm, ligerdave david.c...@gmail.com wrote:
use pointers and lengths of two arrays. depends on what K is, if K
m*n/2, you reverse the
77 matches
Mail list logo
