Problems with UVa 103?

Revision en1, by descrip, 2016-12-24 02:31:46

Hello, I was trying to solve UVa 103 using O(N2) Longest Increasing Subsequence. Here is my code:

#include <bits/stdc++.h>
using namespace std;

int K, N, dp[31];
pair<vector<int>, int> A[31];
string hist[31];

bool canFit(int i, int j) {
    for (int k = 0; k < N; ++k)
        if (A[i].first[k] >= A[j].first[k])
            return false;
    return true;
}

int main() {
    while (cin >> K >> N) {
        for (int i = 0; i < K; ++i) {
            A[i].first.resize(N, 0);
            for (int j = 0; j < N; ++j)
                cin >> A[i].first[j];
            A[i].second = i;
            sort(A[i].first.begin(), A[i].first.end());
        }
        sort(A, A+K);
        fill_n(dp, 31, 1);
        for (int i = 0; i < K; ++i)
            hist[i] = to_string(A[i].second+1);
        int ans = 1;
        string best = "1";
        for (int i = 1; i < K; ++i)
            for (int j = 0; j < i; ++j)
                if (canFit(j, i) && dp[j]+1 > dp[i]) {
                    dp[i] = dp[j]+1;
                    hist[i] = hist[j] + ' ' + to_string(A[i].second+1);
                    if (dp[i] > ans) {
                        ans = dp[i];
                        best = hist[i];
                    }
                }
        cout << ans << '\n' << best << '\n';
    }
	return 0;
}

I got WA with this submission. However, if I change one small detail, the code gets AC:

                    hist[i] = hist[j] + ' ' + to_string(A[i].second+1);
                    // Make this >= instead of >
                    // i.e. I save a maximum length path even if I already have one
                    if (dp[i] >= ans) {
                        ans = dp[i];
                        best = hist[i];
                    }

Why is this? I thought that using the strict > was okay, since the problem says that "If there is more than one longest nesting string then any one of them can be output." Is there something I'm missing? Thanks.

Tags uva, uva 103, help, c++, lis

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English descrip 2016-12-24 02:31:46 2147 Initial revision (published)