# LQDOJ CUP 2022 - Round 6 - SOLDIER - Editorial

**Author:** Nguyen Huu Nhat Quang - Le Quy Don High School for Gifted Students - Da Nang

**Tóm tắt đề:** Cho một dãy các phần tử $a_1, a_2, ..., a_n$ và một số nguyên dương $k$ ($n, k \leq 5000$). Một phần tử $a_i$ được xem là quan trọng khi và chỉ khi tồn tại một tập các phần tử thuộc dãy $a$ có chứa $a_i$, tạm gọi các phần tử này là $b_1, b_2, ..., b_j$, sao cho $b_1+b_2+...+b_j \ge k$, và $b_1+b_2+...+b_j - a_i<k$. Hỏi từng phần tử trong dãy $a$ có quan trọng hay không.

## Nhận xét 1:
Những phần tử $a_i\ge k$ luôn quan trọng. Bởi vì xét tập hợp $\{a_i\}$, ta có $a_i \ge k$, nhưng $a_i - a_i = 0 < k$.

## Nhận xét 2:
$(b_1+b_2+...+b_j \ge k)\ \&\&\ (b_1+b_2+...+b_j - a_i<k) \Leftrightarrow k - a_i \le b_1+b_2+...+b_j - a_i < k$.

## Ý tưởng đầu tiên:
Với mỗi phần tử của dãy $a$ mà $\le k$, kiểm tra xem phần tử đó có quan trọng hay không bằng cách quy hoạch động. Ký hiệu $dp[s] = true/false$ thể hiện việc có thể tạo được một tập hợp có giá trị $s$ hay không.
- $dp[0] = true$.
- với mỗi $j$ tăng dần từ $1$ đến $n$, $s$ giảm dần từ $n$ về $0$, $j \neq i$, $dp[s] = true$ $\Rightarrow$ $dp[s+a_j] = true$.
- Kiểm tra các giá trị $dp[j]$ với $k-a_i\le j < k$.

Độ phức tạp: $O(n^3)$, có thể tối ưu thành $O(\frac{n^3}{32})$ khi sử dụng bitset.

### Code: $(O(\frac{n^3}{32}),\ 91/100)$:

#pragma GCC Optimize ("Ofast")
#include<iostream>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;

vector<int>A, B, ind, ans;

int n, k;

bool check(long long d)
{
    if(d == A.size()) return true;
    if(d == -1) return false;
    bitset<10000> dp;
    dp.set(0);
    for(int i = 0; i < A.size(); i ++)
        if(i != d) dp |= (dp << (A[i]));
    for(int i = k - A[d]; i < k; i ++)
        if(dp.test(i)) return true;
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("SOLDIER.inp", "r", stdin);
    freopen("SOLDIER.out", "w", stdout);
    cin >> n >> k;
    int t;
    for(int i = 1; i <= n; i ++)
    {
        cin >> t;
        B.push_back(t);
        if(t >= k) ans.push_back(1);
        else
        {
            ans.push_back(0);
            A.push_back(t);
            ind.push_back(i);
        }
    }
    for(int i = 0; i < A.size(); i ++) if(check(i)) ans[ind[i] - 1] = 1;
    for(int i = 0; i < n; i ++) cout << ans[i];
}

## Nhận xét 3:
Nếu $a_i$ quan trọng mà $a_j \ge a_i$, chắc chắn $a_j$ quan trọng.

*Chứng minh:* Do $a_i$ quan trọng nên hiển nhiên tồn tại một tập $S$ sao cho tổng các phần tử trong tập $S$, ký hiệu là $d$, không nhỏ hơn $k$, đồng thời $d-a_i<k$. Xét các trường hợp sau:
- Trường hợp 1: $S$ không chứa $a_j$: lúc này ta thay $a_i$ trong $S$ thành $a_j$, được một tập $S'$ mới có tổng băng $d-a_i+a_j\ge d\ge k$. Sau khi loại bỏ $a_j$ khỏi tập $S'$, tập mới thu được có tổng bằng $d-a_i<k$. Vậy $a_j$ quan trọng.
- Trường hợp 2: $S$ chứa $a_j$: ta loại bỏ $a_j$ khỏi tập $S$ và thu được một tập mới có tổng bằng $d-a_j\le d-a_i <k$. Vậy $a_j$ cũng quan trọng.

Sau khi có nhận xét này, ta thấy rằng thay vì phải xét tất cả các số như ý tưởng đầu tiên, ta có thể chặt nhị phân.

Độ phức tạp: $O(n^2\times log_2(n))$, có thể tối ưu thành $O(\frac{n^2\times log_2(n)}{32})$ khi sử dụng bitset.

### Code $(O(\frac{n^2\times log_2(n)}{32}), \ 100/100)$:
(best submission tại thời điểm 10 giờ 48 phút sáng ngày 6/12/2022)

#pragma GCC Optimize ("Ofast")
#include<iostream>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;

vector<int>A, B, ind, ans;

int n, k;

bool cmp(int a, int b)
{
    return B[a - 1] < B[b - 1];
}

bool check(long long d)
{
    if(d == A.size()) return true;
    if(d == -1) return false;
    bitset<10000> dp;
    dp.set(0);
    for(int i = 0; i < A.size(); i ++)
        if(i != d) dp |= (dp << (A[i]));
    for(int i = k - A[d]; i < k; i ++)
        if(dp.test(i)) return true;
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("SOLDIER.inp", "r", stdin);
    freopen("SOLDIER.out", "w", stdout);
    cin >> n >> k;
    int t;
    for(int i = 1; i <= n; i ++)
    {
        cin >> t;
        B.push_back(t);
        if(t >= k) ans.push_back(1);
        else
        {
            ans.push_back(0);
            A.push_back(t);
            ind.push_back(i);
        }
    }
    sort(A.begin(), A.end());
    sort(ind.begin(), ind.end(), cmp);
    int l = 0, r = A.size(), m;
    while(l < r)
    {
        m = (l + r) / 2 + 1;
        if(check(m - 1) == false) l = m;
        else r = m - 1;
    }
    l --;
    for(int i = l + 1; i < A.size(); i ++) ans[ind[i] - 1] = 1;
    for(int i = 0; i < n; i ++) cout << ans[i];
}