I just ran the code with your example and it produced 22.
Here is the C table:
m = 11 13 20 22
n = 1 : 9 7 0 0
n = 2 : 20 16 2 0
n = 3 : 22 16 15 13
n = 4 : 22 22 22 22
On Sep 3, 2:18 pm, Discover maniksinghal.n...@gmail.com wrote:
@gene: nice solution..
but it's not
I just figured out you are running the first (incorrect) greedy
algorithm I tried. Please try the DP. It works fine.
On Sep 3, 2:18 pm, Discover maniksinghal.n...@gmail.com wrote:
@gene: nice solution..
but it's not working for a[]={20,22,13,11};
ur code will give soln : 24
but ans should
@gene: nice solution..
but it's not working for a[]={20,22,13,11};
ur code will give soln : 24
but ans should be: 22 {11,11,11,11}
pls correct me if i m wrong
On Aug 28, 8:26 am, jagadish jagadish1...@gmail.com wrote:
@Gene: Thanks alot! :-) your solution works like charm!
On Aug 28, 7:09
nice explanation gene :)
On Sep 2, 8:35 am, Gene gene.ress...@gmail.com wrote:
Okay. First, you can make the DP more efficient than the one I gave
earlier. You don't need to scan the whole previous column when
calculating costs of decrementing. Rather there are only two
possibilities.
I
Okay. First, you can make the DP more efficient than the one I gave
earlier. You don't need to scan the whole previous column when
calculating costs of decrementing. Rather there are only two
possibilities.
I will add that rahul patil's solution looks correct, but it's
exponential time. DP is
I think your code is just the dynamic program for solving this.
Let V be the set of values in the sequence A[1..N].
Then define C(n, m) to be the minimum possible cost of making A[1..n]
into a new non-decreasing sequence B by decrementing and deleting
elements from A with the constraint that all
On Aug 29, 10:43 am, rahul patil rahul.deshmukhpa...@gmail.com
wrote:
Just read the comments. You will get logic.
1 read global variables
2 start with main
3 read rec (a recursive fn)
The main logic is that whether to keep the no in the final no (by
decrementing it)
or to completely
@gene ..if u just give an example herethat will make things more
clear...
--
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
check out this solution.I think this works correct
will explain logic if u find it correct.
#include stdio.h
#define SIZE 4
int result[SIZE];
int final_cost = 10;
int curr_ans[SIZE];
void save_arr(int *result)
{
int i;
for (i=0 ;iSIZE ;i++) {
curr_ans[i] = result[i];
}
}
void
@Rahul Patil:
I ran your code on some basic test cases and i found it to be
correct!
Can you please explain the logic you used to arrive at the solution?
Thanks :-)
On Aug 29, 12:25 pm, rahul patil rahul.deshmukhpa...@gmail.com
wrote:
check out this solution.I think this works correct
will
@ Gene:
Sorry I misunderstood the problem.
I thought the other operation is of increment rather than decrement... My
bad
--
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
Just read the comments. You will get logic.
1 read global variables
2 start with main
3 read rec (a recursive fn)
The main logic is that whether to keep the no in the final no (by
decrementing it)
or to completely remove it.
#include stdio.h
#define SIZE 4
int result[SIZE];/*Array for
@ Gene :
Output for
int a[] = { 14, 15, 16, 13, 11, 18 };
is coming out to be 14
whereas minimum cost will be : 8
--
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
I think this problem is a DP problem too.
Google Code Jam Round 1A has a similar problem in this year.
http://code.google.com/codejam/contest/dashboard?c=544101#s=p1
In the contest analysis page. It also explains the detail.
http://code.google.com/codejam/contest/dashboard?c=544101#s=aa=1
--
Yes. My solution isn't right. It's not a matroid, so greedy doesn't
work. You need a dynamic program.
On Aug 28, 5:41 am, gaurav singhal singhal08gau...@gmail.com wrote:
@ Gene :
Output for
int a[] = { 14, 15, 16, 13, 11, 18 };
is coming out to be 14
whereas minimum cost will be : 8
My proposed solution was not correct. You need a DP because the
problem is not matroid as I thought.
But for this problem 14 seems correct to me. I can't see how you can
get 8. You need to decrement 14, 15, 16 and 13 to 11. This is a
total of 14 decrements. What am I missing?
On Aug 28,
Ouch. I think I was right to begin with and it is a matroid. I should
have been greedy right-to-left rather than left-to-right. This is
because you can only decrement. If we were incrementing instead, then
left-to-right would work fine.
So work right to left and for each item either
a)
My algorithm proposal wasn't correct, but I can't see how to get 8.
You need to decrement 14, 15, 16, 13 to 11. This costs 14.
On Aug 28, 5:41 am, gaurav singhal singhal08gau...@gmail.com wrote:
@ Gene :
Output for
int a[] = { 14, 15, 16, 13, 11, 18 };
is coming out to be 14
whereas
On Sun, Aug 29, 2010 at 1:35 AM, Gene gene.ress...@gmail.com wrote:
My algorithm proposal wasn't correct, but I can't see how to get 8.
You need to decrement 14, 15, 16, 13 to 11. This costs 14.
So do I.
May be he has not noticed that incrementing a number is not an option. ;)
On Aug 28,
@Rahul:
Yea that is admissible.. Each decrement will add one to the cost!
On Aug 27, 9:36 pm, Rahul Singal rahulsinga...@gmail.com wrote:
can u decrement d same element more then once ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
This code is giving incorrect answer in some inputs.If possible someone
correct it.
#includestdio.h
#includeconio.h
static int SIZE=5;
void print(int *array);
int del(int *array,int i);
int decrement(int *array,int i);
void print(int *array)
{
printf(\n);
int i=0;
Explain the logic also
--
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,
greedy won't work on 8,2,2,2,2,2,2...
On Sat, Aug 28, 2010 at 7:39 AM, Gene gene.ress...@gmail.com wrote:
This is a nice problem. It looks like a trivial matroid, so a greedy
algorithm will work fine. The obvious greedy algorithm is to work
left-to-right and incorporate elements into the
@Gene: Thanks alot! :-) your solution works like charm!
On Aug 28, 7:09 am, Gene gene.ress...@gmail.com wrote:
This is a nice problem. It looks like a trivial matroid, so a greedy
algorithm will work fine. The obvious greedy algorithm is to work
left-to-right and incorporate elements into
@Aravind: I think the solution given by Gene works!.
The answer for 8 2 2 2 2 2.. is six..
On Aug 28, 8:26 am, jagadish jagadish1...@gmail.com wrote:
@Gene: Thanks alot! :-) your solution works like charm!
On Aug 28, 7:09 am, Gene gene.ress...@gmail.com wrote:
This is a nice problem. It
Ya it fails.. Should it then be Dynamic Programming then??
On Aug 28, 8:32 am, jagadish jagadish1...@gmail.com wrote:
@Aravind: I think the solution given by Gene works!.
The answer for 8 2 2 2 2 2.. is six..
On Aug 28, 8:26 am, jagadish jagadish1...@gmail.com wrote:
@Gene: Thanks alot!
Should it be done using dynamic programming then?
On Aug 28, 8:32 am, jagadish jagadish1...@gmail.com wrote:
@Aravind: I think the solution given by Gene works!.
The answer for 8 2 2 2 2 2.. is six..
On Aug 28, 8:26 am, jagadish jagadish1...@gmail.com wrote:
@Gene: Thanks alot! :-) your
Yes. Exactly. DP will get it.
On Aug 27, 11:34 pm, jagadish jagadish1...@gmail.com wrote:
Ya it fails.. Should it then be Dynamic Programming then??
On Aug 28, 8:32 am, jagadish jagadish1...@gmail.com wrote:
@Aravind: I think the solution given by Gene works!.
The answer for 8 2 2 2 2
@Gene:
It would be helpful if you could throw some light on the sub structure
of the problem!
And how to formulate it..
Thanks for your time :)
On Aug 28, 8:36 am, Gene gene.ress...@gmail.com wrote:
Yes. Exactly. DP will get it.
On Aug 27, 11:34 pm, jagadish jagadish1...@gmail.com wrote:
@harit..
logic plz.. not the code..
On Wed, Jul 14, 2010 at 9:50 PM, harit agarwal agarwalha...@gmail.comwrote:
this is O(n) solution and using O(n) space...
#includeiostream
#includevector
#includestack
using namespace std;
void leader_count(vectorint v,int *ar)
{
stackint s;
int
One approach will be while creating a BST and also store position of the
element in the original array. While constructing ar_low check for two
condition 1. element should be less than the given element and also position
of element should greater than the given element.
On Tue, Jul 13, 2010 at
I guess it is a dynamic programming problem.
On Wed, Jul 14, 2010 at 11:34 AM, Anand anandut2...@gmail.com wrote:
One approach will be while creating a BST and also store position of the
element in the original array. While constructing ar_low check for two
condition 1. element should be less
It is counting the inversion counts
use merge sort and count the inversions for each element
O(nlogn) time and O(n) space
--
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
this is O(n) solution and using O(n) space...
#includeiostream
#includevector
#includestack
using namespace std;
void leader_count(vectorint v,int *ar)
{
stackint s;
int n=v.size();
int i=n-1;
while(i=0)
{
if(s.empty())
{
ar[--n]=0;
s.push(i);
i--;
}
else
{
if(v[i] = v[s.top()])
{
Initialise all elements of ar_low with 0
for (int i=0; in-1; i++) {
for (int j=i+1; jn-1; j++) {
if (ar[j] = ar[i])
ar_low[i]++ ;
}
}
O(n^2)
For O(nlogn), create a BST - O(nlogn)
Traverse the tree, counting children on the left side of each node and
putting it
actually the problem is to make BST construction in O(nlogn)...
we need rotations which changes the structure so you wont be able to
distinguish between elements right to a particular elements, elements left
to it . ( in original array )..
On Tue, Jul 13, 2010 at 12:52 AM, Tech Id
make a balanced bst which also has the size of subtree at each node
start from ar[n-1] and insert each element and see what is it's rank in BST
for finding the rank when inserting each time you pick the right subtree add
size of left subtree to rank
O(nlogn)
--
You received this message because
// sort ar[]
and store in temp[] -- o(nlogn)
for(i=0 to n-1)
{
//search position of ar[i] in temp[] binary search --o(logn)
ar_low[i] = pos-1;
delete temp[pos];
}
in binary search increase pos until next element is same .
On Tue, Jul 13, 2010 at 4:09 PM, Amir
101 - 138 of 138 matches
Mail list logo
