111 - History Grading

[junjieliang]

The sequence in sample input 2 is:
3 1 2 4 9 5 10 6 8 7
Note that the number 1 is in the second position, so it has rank 2.
2 has rank 3.
3 has rank 1, etc etc.
So the rank is
2 3 1 4 6 8 10 9 5 7

Hope I didn't get it wrong...been some time since I solved this problem.

[kurnia w]

i've got TLE for this problem...is there any way to make it more faster ?? anyway here is my code... thank's
[c]
#include<stdio.h>
#define max 20
int angka[max+1],temp[max+1],temp2[max+1],length[max+1];
int n;
void table() {
int i;
for(i=0; i<n; i++) scanf("%d",&angka);
}
void main() {
int i, j, k,count;

scanf("%d",&n);
table();
while(1) {
count=1;
for(i=0; i<n; i++) {
scanf("%d",&temp);
temp2[temp]=angka;
}
for(i=1; i<=n; i++) {
if(temp2<temp2[i+1]) count++;
}
printf("%d\n",count);
}
}[/c]

[turuthok]

How did you get out of the while(1) break ?

-turuthok-

[kurnia w]

Yes i see that, but in what condition that i should make it stop ??
i still new in here...last time i'm use this way...i.ve got Output limit exceeded...
[c]for(i=0; i<n; i++) {
if(scanf("%d",&temp)!=1) break;
else temp2[temp]=angka;
}
[/c]

Thank's for the advance...

[minskcity]

According to problem description:
1 point for each event in the longest (not necessarily contiguous) sequence of events which are in the correct order relative to each other.

One of samples:

Code: Select all

Sample Input 2
10
3 1 2 4 9 5 10 6 8 7
2 10 1 3 8 4 9 5 7 6

Sample Output 2
9

Can anybody tell me where these 9 "events" have place??
Where is "longest (not necessarily contiguous) sequence" and how it looks like??

[kurnia w]

see this page :
http://acm.uva.es/board/viewtopic.php?t=2241

Hope can help u understand the problem

[kurnia w]

Hi Hisoka...can you give me more test case for this problem...
i've modify my code & got WA for that...

[deddy one]

hi kurnia,

maybe this web page can help you get AC

http://www-2.cs.cmu.edu/~cburch/pgss99/ ... zsoln.html

read the last part of that page

[kurnia w]

Got it AC, Terima kasih semuanya...

[deddy one]

hehe

smuanya yg disini dari indo ya, baru sadar..

[turuthok]

It's a great feeling to see friends from Indonesia in this forum ... Hisoka, I was also from Binus ... graduated 1997.

By the way, friends, let's follow suit by using English in this public forum ...

Take care and good luck

-turuthok-

[deddy one]

BINUSIAN 2006 too

[xbeanx]

Yes, there is a problem with the search. I've been experiencing it for a while.

[Master]

Hi everybody,
I have tryed to solve the problem 111 but could not be able to understand the problem. so i have searce the board and others help page like Steven Halim's website and i find that this is a LIS problem. But i feel this is a LCS problem and so i solve this like an LCS problem and got AC.

M H Rasel
acmbeginner.tk

[UFP2161]

Since the numbers can't repeat, LCS by treating the list of numbers as characters, or LIS by treating the list of numbers as A<B pairs, amount to the same thing in this particular case.

You can use either method, depending on how you want to interpret that first line.