wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Blue and red ball distances
        
(Message started by: witee on Jul 29^th, 2010, 9:49am)

Title: Blue and red ball distances
Post by witee on Jul 29^th, 2010, 9:49am

There are n red and n blue balls. Each ball is given a unique number between 1-n. So that
number and color is unique combination. And i’th red balls index in the array is always less than
corresponding i’th blue ball. struct ball {int num, char *color;};
The distance between i’th blue ball and i’th red ball is called some xyz distance. Calculate sum of
all these distances for the array.
for eg. r1 r3 b1 r2 b3 b2
Hence sum of those distances is : 2 + 3 + 2 = 7

Title: Re: Array Problem
Post by towr on Jul 29^th, 2010, 10:42am

sum=0;
for b in array
{
if red(b)
hashtmap[num(b)]=idx(b);
if blue(b)
sum += hashtmap[num(b)] - idx(b);
}

Title: Re: Array Problem
Post by birbal on Jul 29^th, 2010, 11:00am

on 07/29/10 at 10:42:26, towr wrote:

sum=0;
for b in array
{
if red(b)
hashtmap[num(b)]=idx(b);
if blue(b)
sum += hashtmap[num(b)] - idx(b);
}

should it be
sum += idx(b) - hashtmap[num(b)];
as index of red is less than blue.

Title: Re: Array Problem
Post by towr on Jul 29^th, 2010, 11:15am

Yes, you're quite right.
Or do sum=-sum at the end :P

If I were a teacher, I would say I make these mistakes on purpose to see if people are paying attention; unfortunately I really am just that careless.

Title: Re: Array Problem
Post by birbal on Jul 29^th, 2010, 11:19am

Well, that's a nice way to defend yourself :P ;) :D

Title: Re: Array Problem
Post by msaha on Aug 6^th, 2010, 2:05pm

How about this?

Code:

struct ball
{
char color;
int num;
struct ball *next;
};

int sumOfPath(ball *begin)
{
ball *p = begin;
ball *q;
int sum = 0, p_sum = 0;

while (p)
{
p_sum = 0;
q=p;
if (p->color == 'R')
{
do{

p_sum++;
q=q->next;

}while (q->color != 'B' || q->num != p->num);
}

p=p->next;
sum += p_sum;
}

return sum;
}

Title: Re: Array Problem
Post by towr on Aug 6^th, 2010, 2:25pm

At a glance, it should work, but it will take quadratic time, so it's a bit slower than might be desirable.

Title: Re: Array Problem
Post by msaha on Aug 6^th, 2010, 10:53pm

Yes, It will be O(n^2). :(

Towr, Can you please explain your earlier answer using hashmap; correct me if i am wrong but it would increase the space complexity while maintaining the time complexity, right?

Title: Re: Array Problem
Post by spicy on Aug 7^th, 2010, 5:01am

There is one solution with O(1) memory and O(n) time complexity

Title: Re: Array Problem
Post by towr on Aug 7^th, 2010, 11:33am

on 08/06/10 at 22:53:18, msaha wrote:

Towr, Can you please explain your earlier answer using hashmap; correct me if i am wrong but it would increase the space complexity while maintaining the time complexity, right?

The amortized time complexity using a hashmap would be O(n). So it's generally faster. But it does use O(n) extra space, so that is a disadvantage.

If you're allowed to (temporarily) destroy the information in the array, you could try moving all the balls to a position corresponding to their index if they're red or n+index for blue, and change their number to what their original index was. It's probably useful to change the colour as a way of marking which balls have been moved.
Once all that's sorted out, it is very easy to print out all the distances.
And you can undo the damage to the array, by doing the same thing a second time.

That should work for O(1) memory O(n) time.

Title: Re: Array Problem
Post by spicy on Aug 8^th, 2010, 3:04am

sum=0;
for b in array
{
if red(b)
sum -= idx(b);
else
sum +=idx(b);
}
print sum;

Title: Re: Array Problem
Post by towr on Aug 8^th, 2010, 8:19am

Doh. :-[
Yeah, this problem really does only ask that much doesn't it. It's like I was taking driving lessons because someone asked my to get something from their car. :P

Title: Re: Array Problem
Post by msaha on Aug 13^th, 2010, 1:05pm

on 08/08/10 at 03:04:44, spicy wrote:

sum=0;
for b in array
{
if red(b)
sum -= idx(b);
else
sum +=idx(b);
}
print sum;

Great answer I must say... :o :o

Title: Re: Array Problem
Post by birbal on Aug 14^th, 2010, 10:13pm

on 08/08/10 at 03:04:44, spicy wrote:

sum=0;
for b in array
{
if red(b)
sum -= idx(b);
else
sum +=idx(b);
}
print sum;

Better solution indeed...using all the available information.