Page 7 of 7

Re: 10131 - Is Bigger Smarter?

Posted: 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.

Re: 10131 - Is Bigger Smarter?

Posted: Fri Jan 16, 2015 8:36 pm
Thanx ... got accepted

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

Re: 10131 - Is Bigger Smarter?

Posted: 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

Re: 10131 - Is Bigger Smarter?

Posted: Mon Jul 15, 2019 7:29 am

Code: Select all

deleted, Got AC