# TS 2024 Problemset #1 Editorial

[Contest link](https://codeforces.com/contestInvitation/d9acccedf268ea2af5e652276aa73e4fd6b85ae3)

[TOC]

----

## 1 - Problem Pytago

Có thể các bạn đã code cái gì đó trong như này:

int n, ans;

signed main(){
    std::ios_base::sync_with_stdio(0); std::cin.tie(NULL); std::cout.tie(NULL);
    std::cin >> n;
    for(int a = 1; a <= n; ++a){
        for(int b = a; b <= n; ++b){
            long long d = 1ll * a * a + 1ll * b * b;
            int c = sqrt(d);
            if(1ll * c * c == d && c <= n)
                ++ans;
        }
    }
    std::cout << ans;
}

Và AC thì mình chịu.

Trên thực tế `sqrt(d)` sẽ chạy với độ phức tạp $O(logV)$ với $V$ là giá trị của tham số cho vào hàm, dẫn đến thuật toán chạy trong $O(N^2logV)$. Rõ ràng chỉ có thể qua được subtask 1.

Để AC subtask 2 bạn cần làm như sau:

int main()
{
     ios::sync_with_stdio(0);
     cin.tie(0);
     cout.tie(0);
     int n,ans=0;
     cin>>n;
     for(int a=1;a<=n;a++)
     {
         for(int X=1;X<=n;X++)
         {
             if((a+X)%2)continue;
             int Y = (a*a)/X;
             int c = (X+Y)/2;
             int b = Y-c;
             if(a<b && b<c && c<=n && a*a+b*b==c*c){ans++;}
         }
     }
     cout<<ans;
}

Độ phức tạp là $O(N^2)$.

----------------------------------------------

## 2 - Problem Kiaria's Vintage boutique

#### Phương pháp sinh tập con

Có thể các bạn đang sinh tập con của $N$ phần tử bằng cách đệ quy. Chúng ta hãy cùng tìm hiểu một phương pháp thay thế sử dụng bitset.

for(int mask = 0;mask < (1 << n);mask++)
{
    for(int i = 0;i < n;i++) if((1 << i) & mask) dosomething();
    ....
}

Đầu tiên hãy xét một xâu $mask$ chỉ gồm kí tự $0$ và $1$. Nếu $mask_i = 1$ thì ta đang chọn phần tử thứ $i$.

Giả sử $N = 3$, các $mask$ có thể có bao gồm:
$000 = 0$
$001 = 1$
$010 = 2$
$011 = 3$
$100 = 4$
$101 = 5$
$110 = 6$
$111 = 7 = 2^3-1$
Ở bên trái là $mask$, có thể thấy $mask$ còn là một số ở hệ nhị phân mà khi đổi ra hệ thập phân là số bên phải. Từ đó ta có dòng $1$ như trong code.

Với mỗi $mask$ chúng ta cần xác định bit nào đang bật. Ta có thể tạo ra một $submask = (1 << i)$ chỉ có một bit bật ở vị trí $i$ và thực hiện phép $AND$ lên $mask$ đang xét.

Giả sử $mask = 110$:
$i = 0 => 001 \ AND \ 110 = 000$
$i = 1 => 010 \ AND \ 110 = 010$
$i = 2 => 100 \ AND \ 110 = 100$
Và nếu kết quả là $0$ tức là bit thứ $i$ đang không được bật. Từ đó ta có dòng thứ $3$ trong code.

#### SUBTASK 1: $1 \leq N \leq 20$.

Với giới hạn này, bạn có thể thử toàn bộ $2^N$ cách chọn đồ, kiểm tra chúng có thõa điều kiện hay không và lưu kết quả tối ưu nhất lại.

Độ phức tạp $O(2^N * N)$.

#### SUBTASK 2: $K = 13$.

Với $K = 13$ cơ bản là vứt điều kiện về $K$ đi. Bài toán trở thành bài toán knapsack kinh điển.

Độ phức tạp: $O(N * W)$

#### SUBTASK 3: $K = 12$.

Với $K = 12$ đồng nghĩa với việc chọn ra một loại sản phẩm duy nhất mà Gfby sẽ không mua. Bạn có thể thử chọn bỏ từng loại rồi chạy thuật toán như Subtask 2.

Độ phức tạp $O(13 * N * W)$

#### SUBTASK 4: Không có ràng buộc gì thêm.

Tương tự subtask 3, ta sẽ xét từng cách chọn $N - K$ loại sản phẩm mà Gfby sẽ không mua.

Lưu ý ta chỉ cần bỏ đi đúng $N - K$ sản phẩm vì kết quả khi bỏ nhiều hơn sẽ không bao giờ tối ưu hơn.

Độ phức tạp $O(C^K_{13} * N * W)$

:::spoiler **CODE**

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

#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
#define pii pair<int,int>
#define sz(a) a.size()
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define fi first
#define se second
const int MAXN = 1e3 + 10;
const int MAXT = 1e7 + 5e5;
const ll inf = 1e9 + 10;
const ll MOD = 1e9 + 7;
const ll base = 41;
const int offset = 131;
const int mask_s = 1 << 7;

ll a[MAXN],b[MAXN],c[MAXN],dp[MAXN][3 * MAXN];
vector<int> v;
int n,W,k;

ll cal(int x)
{
    v.clear();
    for(int i = 1;i <= n;i++) if(((1 << c[i] - 1) & x))  v.push_back(i);
    for(int i = 1;i <= sz(v);i++)
    {
        int p = v[i-1];
        for(int j = 0;j <= W;j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j - b[p] >= 0) dp[i][j] = max(dp[i][j],dp[i-1][j - b[p]] + a[p]);
        }
    }
    return dp[sz(v)][W];
}

void solve()
{
    cin >> n >> W >> k;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++) cin >> b[i];
    for(int i = 1;i <= n;i++) cin >> c[i];

    ll res = 0,state = 0;
    for(int i = 1;i < (1 << 13);i++)
    {
        if(__builtin_popcount(i) != k) continue;
        ll best = cal(i);
        if(best > res)
        {
            res = best;
            state = i;
        }
    }
    cal(state);
    vector<int> ans;
    int i = sz(v),j = W;
    while(i != 0)
    {
        if(dp[i][j] != dp[i-1][j])
        {
            ans.push_back(v[i-1]);
            j -= b[v[i-1]];
        }
        i--;
    }
    cout << res << " " << ans.size() << "\n";
    for(int i = 0;i < sz(ans);i++) cout << ans[i] << " ";
}

int main()
{
   // freopen("kvbshopping.inp","r",stdin);
   // freopen("kvbshopping.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

:::

### Nhận xét
Mục đính của bài này là giúp các bạn ôn lại knapsack cơ bản, đồng thời hướng dẫn các bạn một cách sinh tập con $N$ phần tử bằng bitset vừa ngắn vừa hiệu quả hơn so với cách đệ quy.

------------------------------------------------

## 3 - Problem Gacha II

#### SUBTASK 1: Ở mọi thời điểm không có quá $1000$ phần tử trong tập $A$.

Vì luôn chỉ có tối đa $1000$ phần tử, ta có thể tính trước số cặp $GCD$ ngay từ ban đầu và cập nhật chúng sau mỗi truy vấn lên một mảng $cnt$.

Độ phức tạp $O(K^2)$ với $K$ là tổng số phần tử tối đa.

Vì chỉ có $10^5$ giá trị $GCD$ tồn tại và cũng chỉ có tối đa $1000$ truy vấn in số may mắn, ta hoàn toàn có thể chạy vòng lặp cộng tổng trên mảng $cnt$ để tìm kết quả.

Độ phức tạp $O(P * MV)$ với $MV$ là giá trị $GCD$ tối đa có thể xuất hiện.

Tổng quát $O(K^2 + P * MV)$.

#### SUBTASK 2: $1 \leq N \leq 2000$.

Ở subtask này ta có thể tính trước các $GCD$ ban đầu trong mảng $A$ trong $O(N^2)$. Vấn đề ở subtask này là giải quyết các truy vấn.

Xét giá trị $X$ giá trị $Y$ được thêm. Cần lưu ý các điều sau:
- $Y$ là số nguyên tố. Chỉ có $9592$ (google it) số nguyên tố nhỏ hơn $10^5$.
- $GCD(Z,Y) = Y$ nếu $X$ là bội của $Y$, nếu không $GCD(Z,Y) = 1$.

Từ nhận xét trên, ta chia ra làm 2 trường hợp:
#### Trường hợp $GCD(Z,Y) = Y$
Ta cần xác định có bao nhiêu phần tử trong $A$ hiện tại là bội của $Y$, gọi là $B_Y$.

Số lượng $GCD(Z,Y) = Y$ tăng lên sẽ bằng $X * B_Y$ + $X * (X - 1) \over 2$ và $B_Y$ sẽ tăng lên $X$ sau truy vấn cập nhật hiện tại.

#### Trường hợp $GCD(Z,Y) = 1$
Ta chỉ cần tính số lượng số không phải bội của $Y$ hiện tại, gọi là $R$.

Số cặp $GCD(Z,Y) = 1$ sẽ tăng lên bằng $R * X$.

#### Giải quyết truy vấn in đáp án

Nhận thấy chỉ có các cặp có giá trị $GCD$ bằng số nguyên tố hoặc số $1$ là tăng lên.

Ta sẽ tạo một mảng prefixsum $Pf$ của mảng $GCD$ đã tính trước ban đầu.

Sau đó tìm cách lưu số lượng cặp $GCD$ được thêm vào có giá trị bằng các số nguyên tố và $1$, gọi là $ADD$.

Từ nhận xét 1, ta hoàn toàn có thể đi qua từng số nguyên tố trong $[l,r]$ và cộng các thay đổi vào đáp án.

Đáp án sẽ là $Pf_r$ - $Pf_{l-1}$ + $\sum_{p=l}^{r}{ADD_p}$ với $p$ là số nguyên tố cho một truy vấn $[l,r]$.

Nếu $l = 1$ hãy nhớ cộng thêm $ADD_1$.

Độ phức tạp $O(10^4 * Q)$.

Tổng quát $O(N^2 + 10^4 * Q)$.

#### SUBTASK 3: không có ràng buộc gì thêm.
Bây giờ chỉ cần tìm cách tính mảng $GCD$ ban đầu trước với giới hạn hiện tại.

Dùng phương pháp bao hàm loại trừ. Hãy đọc code và ngẫm vì mình lười giải thích <(").

for(int i = 1;i <= n;i++)
{
    int x;
    cin >> x;
    B[x]++;
}

for(int i = 1;i < MAXV;i++)
    for(int j = i*2;j < MAXV;j += i) B[i] += B[j];
        
for(int i = MAXV-1;i > 0;i--)
{
    G[i] = ((B[i] - 1) * B[i]) / (ll) 2;
    for(int j = i+i;j < MAXV;j += i) G[i] -= G[j];
}

Độ phức tạp $O(MV\log MV + 10^4 * Q)$.

:::spoiler **CODE**

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

#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
#define pii pair<int,int>
#define sz(a) a.size()
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define fi first
#define se second
const int MAXN = 1e6 + 10;
const int MAXV = 1e5 + 10;
const ll inf = 1e18 + 10;
const ll MOD = 1e9 + 7;
const ll base = 41;
const int offset = 131;
const int mask_s = 1 << 7;
const int block_s = sqrt(MAXN) + 10;

ll B[MAXN],G[MAXN],cnt[MAXN];
int p[MAXN],nxt[MAXN];
ll n,q;

void sieve()
{
    int last = 0;
    for(ll i = 2;i < MAXV;i++)
    {
        nxt[i] = last;
        if(p[i] == 0)
        {
            for(ll j = i * i;j < MAXV;j += i) p[j] = 1;
            last = i;
        }
    }
}

void solve()
{
    memset(B,0,sizeof(B));
    memset(G,0,sizeof(G));
    memset(cnt,0,sizeof(cnt));
    memset(p,0,sizeof(p));
    memset(nxt,0,sizeof(nxt));
    sieve();

    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        int x;
        cin >> x;
        B[x]++;
    }

    for(int i = 1;i < MAXV;i++)
        for(int j = i*2;j < MAXV;j += i) B[i] += B[j];
        
    for(int i = MAXV-1;i > 0;i--)
    {
        G[i] = ((B[i] - 1) * B[i]) / (ll) 2;
        for(int j = i+i;j < MAXV;j += i) G[i] -= G[j];
    }
    
    for(int i = 2;i < MAXV;i++) G[i] += G[i-1];

    ll tmp = 0;
    cin >> q;
    for(int i = 1;i <= q;i++)
    {
        ll t,x,y;
        cin >> t >> x >> y;
        if(t == 1)
        {
            n += x;
            cnt[y] += x;
            tmp += x * (n - cnt[y] - B[y]);
        }
        else
        {
            ll res = G[y] - G[x-1];
            for(int i = nxt[y + 1];i >= x;i = nxt[i]) if(x <= i && i <= y) res += cnt[i] * B[i] + (cnt[i] - 1) * cnt[i] / (ll) 2;
            if(x == 1) res += tmp;
            cout << res << "\n";
        }
    }

}



int main()
{
//    freopen("kvbshopping.inp","r",stdin);
//    freopen("kvbshopping.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

:::

### Nhận xét
Nhận xét 1 khá hữu dụng các bạn nên lưu ý các nhận xét như vậy.

Ngoài ra mình muốn giới thiệu các bạn phương pháp bao hàm loại trừ ở subtask 3. Nếu bạn đã biết qua cái này thì bài toán trở nên tương đối dễ, mò tí là ra.