wu :: forums - Blue and red ball distances

wu :: forums « wu :: forums - Blue and red ball distances » Welcome, Guest. Please Login or Register. Apr 17^th, 2025, 4:55pm
RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

   wu :: forums
   riddles
   cs (Moderators: SMQ, william wu, Grimbal, Icarus, ThudnBlunder, Eigenray, towr)
   Blue and red ball distances

« Previous topic | Next topic »

Pages: 1

Notify of replies

Send Topic

Author

Topic: Blue and red ball distances (Read 1323 times)

witee
Newbie

Posts: 48

Blue and red ball distances
« on: Jul 29^th, 2010, 9:49am »

Quote

Modify

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

« Last Edit: Aug 8^th, 2010, 2:18pm by Grimbal »

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Array Problem
« Reply #1 on: Jul 29^th, 2010, 10:42am »

Quote

Modify

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

« Last Edit: Jul 29^th, 2010, 10:42am by towr »

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

birbal
Full Member

Gender:

Posts: 250

Re: Array Problem
« Reply #2 on: Jul 29^th, 2010, 11:00am »

Quote

Modify

on Jul 29^th, 2010, 10:42am, 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.

IP Logged

The only thing we have to fear is fear itself!

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Array Problem
« Reply #3 on: Jul 29^th, 2010, 11:15am »

Quote

Modify

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

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.

« Last Edit: Jul 29^th, 2010, 11:16am by towr »

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

birbal
Full Member

Gender:

Posts: 250

Re: Array Problem
« Reply #4 on: Jul 29^th, 2010, 11:19am »

Quote

Modify

Well, that's a nice way to defend yourself Tongue

IP Logged

The only thing we have to fear is fear itself!

msaha
Newbie

Gender:

Posts: 4

Re: Array Problem
« Reply #5 on: Aug 6^th, 2010, 2:05pm »

Quote

Modify

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;
}

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Array Problem
« Reply #6 on: Aug 6^th, 2010, 2:25pm »

Quote

Modify

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

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

msaha
Newbie

Gender:

Posts: 4

Re: Array Problem
« Reply #7 on: Aug 6^th, 2010, 10:53pm »

Quote

Modify

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

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?

IP Logged

spicy
Newbie

Gender:

Posts: 8

Re: Array Problem
« Reply #8 on: Aug 7^th, 2010, 5:01am »

Quote

Modify

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

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Array Problem
« Reply #9 on: Aug 7^th, 2010, 11:33am »

Quote

Modify

on Aug 6^th, 2010, 10:53pm, 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.

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

spicy
Newbie

Gender:

Posts: 8

Re: Array Problem
« Reply #10 on: Aug 8^th, 2010, 3:04am »

Quote

Modify

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

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Array Problem
« Reply #11 on: Aug 8^th, 2010, 8:19am »

Quote

Modify

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. Tongue

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB