Just solved it.. The approach is same as Don's but starting from the
front... Hence, penning it down..
Let F(i) be defined as the no. of integers that are possible to be
formed using the first 'i' integral differences..
Then F(i+1) = No. of integers from set F(i) where the units place >= 'i
+1' i
@Moheed: 0 is not a three-digit number. By convention, we do not print
leading zeros except in the units position. Thus, there are only 9
three digit numbers with absdiff={0,0}.
Dave
On Dec 13, 12:58 pm, Moheed Moheed Ahmad wrote:
> Thanks Don for pointing it out. It will not work [the second an
Thanks Don for pointing it out. It will not work [the second and
consecutive abs-diffs are not mutually exclusive].
However, here are the 10 possible numbers that will work for n=3 and
absdiff={0,0}:
0 0 0
1 1 1
2 2 2
--
8 8 8
9 9 9
-Moheed
'If a man neglects education, he walks lame to the en
Trying the combinations is not necessary. See my solution above.
Don
On Dec 13, 3:59 pm, Gaurav Kumar wrote:
> Thanks for pointing out the issue with my logic. What I am wondering is
> what is the general solution to finding the number of possible numbers? Is
> the only way is to try these combin
Thanks for pointing out the issue with my logic. What I am wondering is
what is the general solution to finding the number of possible numbers? Is
the only way is to try these combinations? Please share if you know.
Gaurav
On Tue, Dec 13, 2011 at 1:56 PM, Gaurav Kumar wrote:
>
>
> On Tue, Dec 1
On Tue, Dec 13, 2011 at 12:40 PM, Don wrote:
> That gives an answer of 40,320, but the correct answer is 39. You
> can't multiply all of those values together and expect to get the
> right answer. There are not 14 possible values for the first digit,
> and if there were, for any particular value
That gives an answer of 40,320, but the correct answer is 39. You
can't multiply all of those values together and expect to get the
right answer. There are not 14 possible values for the first digit,
and if there were, for any particular value of the first digit there
are not 16 possible values for
I am just trying to understand the number of ways we can form this number,
lets say d is the absolute difference between the numbers and the length of
the numbers is n. Lets say we are considering base 10 numbers, so lets say
radix r = 10.
if you try to see all the comparisons, here is what holds
When the difference is 0, the numbers will be repeated:
000, 111, 222, 333, 444, 555, 666, 777, 888, 999 but only these are
possible.
Gaurav
On Tue, Dec 13, 2011 at 10:47 AM, Don wrote:
> Moheed,
> If n=3 and absdiff = {0,0}, your program says that there are 100
> possible numbers. Can you show
Moheed,
If n=3 and absdiff = {0,0}, your program says that there are 100
possible numbers. Can you show me at least 10 of them?
Don
On Dec 13, 12:24 pm, Moheed Moheed Ahmad wrote:
> To get a abs difference of 0 there are 10 ways
> similarly getting abs difference of 1 there are 9x2 ways(w1)
> for
To get a abs difference of 0 there are 10 ways
similarly getting abs difference of 1 there are 9x2 ways(w1)
for 2 its 8x2 (say w(2)
for 3 its 7x2
.
for 9 its 1x2(w9)
let w(i) represents the number of ways to get abs diff of i.
So total numbers that are possible from the given abs diff i j k l
thanks don , i got it , it was due the condition in if expression .
modified code
i have highlighted the change
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};
for(int num=1;num<=9;num++)
findNumber(digit,4,num,0,num);
}
One other observation: if any of the absolute differences was zero, it
would print the same number more than once.
Your algorithm is fine for n=5, but as n gets larger, the execution
time increases exponentially. The dynamic programming algorithm is
O(n).
Don
On Dec 13, 11:37 am, tech coder wro
There should be 39 combinations with that input. You are missing
numbers which include the digit zero, such as 14610, 30278, and 52056.
Don
On Dec 13, 11:37 am, tech coder wrote:
> I tried the problem and written the code for it . it is in java. it is
> printing all the possible numbers
> I am
I tried the problem and written the code for it . it is in java. it is
printing all the possible numbers
I am treating the differences ans an array of integers.
here is the code
public class Main {
public static void main(String[] args)
{
int digit[]={3,2,5,1};// array of absolu
The following is a dynamic programming solution to this problem.
It builds up an array num[i][j] such that num[i][j] is the number of
combinations of digits starting with digit j at position i.
The answer is the sum of num[1][1]..num[9][1].
#include
int main(int argc, char* argv[])
{
int
The following is a dynamic programming solution to this problem.
It builds up an array num[i][j] such that num[i][j] is the number of
combinations of digits starting with digit j at position i.
The answer is the sum of num[1][1]..num[9][1].
#include
int main(int argc, char* argv[])
{
int
@Amir: Presumably, since these are digits in a number, they are
bounded on the bottom by 0 and on the top by radix-1. So in decimal,
if a digit is 7 and the absolute difference between it and the next
digit is 3, there is only one possibility for the next digit, 7-3 = 4,
since 7+3 is too large. So
If the optimal internal containing a[m] contains oneelement, it is simply a[m]
But here the optimal interval containing a[m] is not a[m] alone.
4 alone gives you 4 * 4 = 16
Including 7, you will get (4 + 7) * 4 = 44
Then include 8 , (4+7+8) * 4 = 76
Now try including 2, (2+4+7+8) * 2 =
Prunthaban Kanthakumar wrote:
> Hi,
>
> The proposed solution does not talk about multiplication. It talks about the
> sum alone.
> The sum is simply a[m].
> Of course you need to muliply later.But that does not affect the correctness
> of the solution!
For this set:
5
1 2 4 7 8
what would the s
Hi,
The proposed solution does not talk about multiplication. It talks about the sum alone.
The sum is simply a[m].
Of course you need to muliply later.But that does not affect the correctness of the solution!
Regards,
Prunthaban
On 9/24/06, GoCooL <[EMAIL PROTECTED]> wrote:
This is the orig
Solved it. It was a initialization bug. I got accepted for that solution.
regards
Arunachalam.
On 6/27/06, Arunachalam <[EMAIL PROTECTED]> wrote:
Sorry,
I did not read the Gene's solution properly. Great work Gene. I doubt the solution given above.
On 6/27/06, Googmeister <[EMAIL P
Arunachalam wrote:
> Had anyone tried coding this solutions. I have got wrong answer for the
> implementation. Might be a coding flaw too.
>
> If anyone is able to successfully crack it , please share your solution.
Another worst-case O(n log n) solution:
1. (O(n)) Set values of sum[] where sum
Had anyone tried coding this solutions. I have got wrong answer for the implementation. Might be a coding flaw too.
If anyone is able to successfully crack it , please share your solution.
regards
Arunachalam.
On 6/28/06, Gene <[EMAIL PROTECTED]> wrote:
Googmeister wrote:> > Hi Gm,> >> > If fi
When you have a nice algorithm from Googmeister in O(n log n) why try something else...?
On 7/5/06, mg <[EMAIL PROTECTED]> wrote:
#includestruct key { int min; double sum; };
int main(int argc,char **argv){int n,i,j,k;int start=0,end=0;double currentValue=0,eVa
#include
struct key {
int min;
double sum;
};
int main(int argc,char **argv)
{
int n,i,j,k;
int start=0,end=0;
double currentValue=0,eValue=0;
struct key opt[10];
int a[10];
while ( scanf("%d",&n) != EOF )
{
start =
Googmeister wrote:
> > Hi Gm,
> >
> > If finding this interval requires linear time, then the run time is
> > proprtional to n^2
>
> No. It's the standard n log n recurrence.
>
> > because there is no bound on the size of the
> > interval you're searching for
>
> Yes there is. At each recursive c
Googmeister is right!
A simple and wonderful solution in O(n log n)
The strange thing I notcied is... we are getting algorithms simiar to sorting algorithms like mergesort and quicksort for this problem
Looks like there is a strange connection between sorting and this problem...
On 6/2
Gene wrote:
> Googmeister wrote:
> > Pradeep Muthukrishnan wrote:
> > > I have been trying this problem for quite some time now...but havent
> > > found anything concrete...can anyone solve this?
> > > http://acm.zju.edu.cn/show_problem.php?pid=2642
> >
> > Here's a O(n log n) mergesort style sol
Googmeister wrote:
> Pradeep Muthukrishnan wrote:
> > I have been trying this problem for quite some time now...but havent
> > found anything concrete...can anyone solve this?
> > http://acm.zju.edu.cn/show_problem.php?pid=2642
>
> Here's a O(n log n) mergesort style solution:
>
> * Divide the e
Arunachalam wrote:
> Sorry,
> I did not read the Gene's solution properly. Great work Gene. I
> doubt the solution given above.
>
>
> On 6/27/06, Googmeister <[EMAIL PROTECTED]> wrote:
> >
> >
> >
> > Pradeep Muthukrishnan wrote:
> > > I have been trying this problem for quite some time
Sorry,
I did not read the Gene's solution properly. Great work Gene. I doubt the solution given above.
On 6/27/06, Googmeister <[EMAIL PROTECTED]> wrote:
Pradeep Muthukrishnan wrote:> I have been trying this problem for quite some time now...but havent
> found anything concrete...can any
CPP program based on Vikram Venkatesan's Algo:#include #include using namespace std;class arr{ int *a; int n; /*No. of elements in an array*/
public: arr() { a=0; n=0; } arr(int num_of_elements) { n = num_of_element
Arunachalam,
Giving a quick thought... i felt duplicates are not going to affect my algorithm... If you have duplicate minimums you can select any one (may be the most central one) as the pivot and proceed...
Am i correct?
On 6/27/06, Googmeister <[EMAIL PROTECTED]> wrote:
Arunachalam wrote:>
Arunachalam wrote:
> Gene's solution also works fine. But this will also be n^2. since we have
> to scan back to get the upper and lower bound. for each element i, we have
> to go through all the elements and get the lower and upper bound. ( Huh...
> same problem again).
Gene uses balanced BST
Pradeep Muthukrishnan wrote:
> I have been trying this problem for quite some time now...but havent
> found anything concrete...can anyone solve this?
> http://acm.zju.edu.cn/show_problem.php?pid=2642
Here's a O(n log n) mergesort style solution:
* Divide the elements in the middle: a[l..m-1]
Prundhaban's solution works fine. But how to handle duplicates and how to bring it down to nLogn.
Gene's solution also works fine. But this will also be n^2. since we have to scan back to get the upper and lower bound. for each element i, we have to go through all the elements and get the lower
Hi, A similar but straightfoward O(n^2) solution ;-) For each element a[i], traverse on either side of the array with a[i] as the pivot until you reach elements a[j]This solution differs from Gene's in that, it doesn't select the minimum element each time as i thought it would take more tim
Hi Pradeep,
I don't think a DP will work... (unless it is single dimensional DP)...
My idea was on the same lines of Gene... But I was thinking about an easy implementation which runs in O(n log n) on average case... (Of course... in worst case it takes... O(n^2)... But... why not give it a try
Pradeep Muthukrishnan wrote:
> I have been trying this problem for quite some time now...but havent
> found anything concrete...can anyone solve this?
> http://acm.zju.edu.cn/show_problem.php?pid=2642
Hello Pradeep. Here is an idea.
I am going to write [a..b] for a potential solution range with
(top of my head) I would keep the minimum and the sum for each interval, and just calculate the max of the sum times the minimum for each interval (the trick is store the minimum of each interval to avoid O(n) searches each time you calculate the max)
sorry for the quick response... must go on w
can u please explain the recurrence? I have been thinking abt DP but
could never find a recurrence
On 6/26/06, Guillermo Garcia <[EMAIL PROTECTED]> wrote:
> Try dynamic programming
>
>
>
> On 6/26/06, Pradeep Muthukrishnan <[EMAIL PROTECTED]> wrote:
> >
> > I have been trying this problem for qui
Try dynamic programming
On 6/26/06, Pradeep Muthukrishnan <[EMAIL PROTECTED]> wrote:
I have been trying this problem for quite some time now...but haventfound anything concrete...can anyone solve this?
http://acm.zju.edu.cn/show_problem.php?pid=2642
--~--~-~--~~~---~--~
43 matches
Mail list logo
