2014-06-12

UVa 11031 - Looking for a Subset

1. Problem
2. Input
3. Output
4. Sample Input
5. Output for Sample Input
6. Solution

Problem

Given a set S = { a1, a2, a3, … , an }, you have to find a subset of S, P = { ax1, ax2, ax3, … , axm } such that ( x1 < x2 < … < xm ) and ( ax1< ax2< … < axm ). If there are several subsets possible then you should find the subset where x1 is minimum. If there is still a tie then check for the lowest x2 and so on.

Input

The input file contains several sets of inputs. The total number of test cases will be less than 25. The description of each set is given below:

Each case starts with two integers n (1 ≤ n ≤ 10000) and q (1 ≤ q ≤ 100), q is the number of queries. The next line contains n integers (seperated by a space) denoting a1, a2, a3, … , an respectively. And the next q lines, each contains an integer denoting m (1 ≤ m ≤ n). There is no number in the input file that contains more than 8 digits.

The input will be terminated by the case where n = q = 0. And this case should not be processed.

Output

For each case in the input, you should first print the case number starting from 1.
Then for each query first print the query number starting from 1. And for each m you have to find the result.
If there exists a subset as described above you should print the elements of the subset in a single line. The numbers should be seperated by a space.
Otherwise print ``Impossible’’ without the quotes.

See the sample input-output for more details. Output should be formatted like the sample output.

Sample Input

6 3
3 4 1 2 3 6
6
4
5
6 2
2 4 6 1 3 5
3
4
0 0

Output for Sample Input

Set 1:
  Subset 1:
    Impossible
  Subset 2:
    1 2 3 6
  Subset 3:
    Impossible
Set 2:
  Subset 1:
    2 4 6
  Subset 2:
    Impossible

Solution

題目描述：

對於每次詢問 m，找到一個嚴格遞增的子序列，並且子序列長度等於 m 且字典順序最小。

題目解法：

基於每次字典順序最小，只能採用 greedy 的掃描方式，因此對於每次詢問必須到達 O(n)，無法在 O(m) 的時間完成。

關於貪心的操作，建造反向的遞減序列，狀態為從這個位置為子序列的頭最長的遞減序列長度為何。

為了在 O(n log n) 得到 LDS 表格，這裡使用一個 binary indexed tree 來完成操作。

#include <stdio.h> 
#include <algorithm>
#include <map>
using namespace std;
#define maxN 10005
int A[maxN], LDS[maxN];
int BIT[maxN];
void modify(int i, int val, int L) {
    while(i <= L) {
        BIT[i] = max(BIT[i], val);
        i += i&(-i);
    }
}
int query(int i) {
    int ret = 0;
    while(i) {
        ret = max(ret, BIT[i]);
        i -= i&(-i);
    }
    return ret;
}
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int N, Q, M, u;
    int cases = 0;
    while(ReadInt(&N) && ReadInt(&Q) && N+Q) {
        map<int, int> R;
        for(int i = 0; i < N; i++) {
            ReadInt(A+i);
            R[A[i]] = 0;
        }
        for(int i = 1; i <= N; i++)
            BIT[i] = 0;
            
        int size = R.size();
        for(map<int, int>::iterator it = R.begin();
            it != R.end(); it++) {
            it->second = size--;
        }
        /* reverse LDS with ending at i-th element */
        int maxLDS = 0;
        for(int i = N-1; i >= 0; i--) {
            LDS[i] = query((u = R[A[i]]) - 1) + 1;
            modify(u, LDS[i], R.size());
            maxLDS = max(maxLDS, LDS[i]);
        }
        printf("Set %d:\n", ++cases);
        for(int i = 1; i <= Q; i++) {
            ReadInt(&M);
            printf("  Subset %d:\n", i);
            if(M > maxLDS) {
                printf("    Impossible\n");
                continue;
            }
            printf("   ");
            int prevA = -0x3f3f3f3f;
            for(int j = 0; j < N && M; j++) {
                if(LDS[j] >= M && prevA < A[j]) {
                    printf(" %d", A[j]);
                    M--, prevA = A[j];
                }
            }
            puts("");
        }
    }
    return 0;
}

Morris' Blog