UVA 481: What goes up

Process
I originally tried to solve this problem using the O(N^2) DP algorithm, but I exceeded the time limit. I went back and read up on an O(Nlog(N)) solution and applied that instead. It was a bit tricky to understand, but my implementation is below. It becomes clearer if you work it through with pen and paper. The important points to realize are that the M array stores the last value in the subsequence of length i. The M_id array stores the indexes of those values, and the P array stores the index in A of the element prior to it in the subsequence. The collective of these points is a pretty beautiful solution to the problem. If we save the index of the value first stored in the last column of M, we’re given the last value in the longest increasing subsequence. From there, we recurse on the P array to find all values previous.

/*
 * Sai Cheemalapati
 * UVA 481: What goes up
 *
 */

#include<algorithm>
#include<cstdio>

using namespace std;

int A[1000000], M[1000000], M_id[1000000], P[1000000];

void print(int end) {
	if(end < 0) return;
	print(P[end]);
	printf("%d\n", A[end]);
}

int main() {
	int L = 0, L_end = 0;
	for(int i = 0;; i++) {
		if(scanf("%d", &A[i]) != 1) break;

		int pos = lower_bound(M, M + L, A[i]) - M;
		M[pos] = A[i];
		M_id[pos] = i;
		P[i] = pos > 0? M_id[pos - 1] : -1;
		if(pos == L) {
			L++;
			L_end = i;
		}
	}
	printf("%d\n-\n", L);
	print(L_end);
}

-3
-4
-2
0
8
5
1
-1
11
15
8
4
-1
2
7
2
7
456
3568
234
5
234
234523
6

9
-
-4
-2
0
1
2
7
456
3568
234523

4 thoughts on “UVA 481: What goes up”

  1. This is not a correct approach but you got AC because UVA test cases are bad. It fails when there are multiple LIS with the same length.

    For example:
    Try this input in uDebug and compare the output with yours.
    1825198813
    703574781
    1357013548
    882614101
    91123810
    693635462
    509962994
    13091984
    476503935
    692987701
    845877457
    484660669
    2118992354
    1583536068
    1830890927
    125909470
    389054618
    61633602
    1167630334
    1245222478
    1653407157
    1539092241
    1260848996
    1092105640
    1343321214
    1337792438
    743752911
    895144236
    644021011
    306984050
    206209071
    1968038758
    694647582
    627044827
    1228453736
    923849393
    994690063
    1935458528
    351391203
    1747161030
    1759120300
    1040627854
    1076069512
    1110842238
    2104791827
    326007565
    159295061
    522217290
    1564248899
    459709341
    368308305
    510183713
    1141726537
    2069288597
    94198657
    557718943
    1355469954
    1075065596
    1830809408
    660014489
    1515539776
    750393546
    518211796
    692879112
    1918631132
    533634230
    1974805736
    1999632389
    616397282
    1170189545
    315109278
    834252002
    1161967889
    103216749
    1534876392
    998665307
    1795057301
    1251226459
    900157290
    1509113371
    1092226810
    1988172767
    2128641328
    1107418067
    48984604
    1391219046
    1763691983
    435334167
    1137289136
    78170531
    1100176263
    795618180
    2087635596
    893474920
    1313562613
    1238129761
    314970551
    566882611
    2043820790
    1354652240

    The correct one should prepare for the tie breaker case.

    Reply

Leave a comment