10131 - Is Bigger Smarter?

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10131 - Is Bigger Smarter?

Post by brianfry713 » Fri Jan 16, 2015 12:14 am

You are right, your code is correct on the sample input.

Sort by increasing weight.
A O(n * n) LDS by IQ is fast enough for this problem.
Initialize each element of count to 1, and each element of previous to -1.

Code: Select all

  int mx = 1, best_index;
  for(int j = 1; j < n; j++) 
    for(int i = 0; i < j; i++)
      if(e[i].weight < e[j].weight && e[i].iq > e[j].iq)
	if(1 + count[i] > count[j]) {
	  count[j] = 1 + count[i];
	  previous[j] = i;
	  if ( count[j] > mx ) {
	    mx = count[j];
	    best_index = j;
	  }
	}
Then print mx. Then print the path in reverse using the previous array starting at best_index, using the original id's that you kept track of during the sort.
Check input and AC output for thousands of problems on uDebug!

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Re: 10131 - Is Bigger Smarter?

Post by richatibrewal » Fri Jan 16, 2015 8:36 pm

Thanx ... got accepted

But will u plz explain what was the probelm with my logic?

krecik1334
New poster
Posts: 1
Joined: Thu Sep 17, 2015 6:40 pm

Re: 10131 - Is Bigger Smarter?

Post by krecik1334 » Thu Sep 17, 2015 6:43 pm

What's wrong with my code? The first output (lenght) is good but I don't know if the following elements are correct.

http://pastebin.com/hSykeDYE

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest