# MK Special Round: Goodbye 2021 & Hello 2022 Editorial
## A. Xâu con
Chuẩn bị bởi: Stickman
### Hướng dẫn
Lần lượt xét các xâu con trong chuỗi kí tự từ trái sang phải cùng với đó là xác định xem xâu con đó có phải là hoán vị của từ ```special``` hay không.
### Cài đặt

#include <bits/stdc++.h>

using namespace std;

string S = "aceilps";
string s;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    int cnt = 0;
    for (int i = 0; i <= s.length() - 7; ++i) {
        string subs = s.substr(i, 7);
        sort(subs.begin(), subs.end());
        if (subs == S) cnt++;
    }
    cout << cnt;
    return 0;
}

## B. I wanna be the guy
Chuẩn bị bởi: iwannabetheguy
### Hướng dẫn
Ta chỉ cần kiểm tra xem trong các ước của $N$ thì có những ước nào là số chính phương.
### Cài đặt

#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
//ifstream fin("template.in");
//ofstream fout("fenceplan.out");
#include<fstream>
#define pb push_back
#define all(c) (c).begin(), (c).end()
//#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
using namespace std;
bool check(ll x){
    return(sqrt(x) == (ll)sqrt(x));
}
int main(){
    ll n;
    cin >> n;
    ll ans =0 ;
    for(int i = 1; i <= (ll)sqrt(n); i++){
        if(n % i == 0){
            if(check(i)){
                ans++;
            }if(check(n / i)){
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

## C. Dãy đầu cuối
Chuẩn bị bởi: iwannabetheguy
### Hướng dẫn
Dãy kết quả $K$ là $F_1, F_3, ..., F_4, F_2$ nên để có được dãy $F$ ban đầu, ta chỉ cần lưu các phần tử trong nửa đầu vào nửa cuối vào hai mảng và in ra lần lượt.
### Cài đặt

#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
//ifstream fin("template.in");
//ofstream fout("fenceplan.out");
#include<fstream>
#define pb push_back
#define all(c) (c).begin(), (c).end()
//#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
using namespace std;
int main(){
    int n;
    cin >> n;

    vt<ll>odd;
    vt<ll>even;

    ll now = ceil((double)n / (double)2);
    for(int i = 0; i < now; i++){
        ll x;
        cin >> x;
        odd.pb(x);
    }
    for(int i = now; i < n; i++){
        ll x;
        cin >> x;
        even.pb(x);
    }
    reverse(even.begin(), even.end());
    for(int i =0 ; i < even.size(); i++){
        cout << odd[i] << " ";
        cout << even[i] << " ";
    }
    if(n % 2 == 1){
        cout << odd[odd.size() - 1] << " ";
    }
    return 0;
}

## D. Cấp số cộng
Chuẩn bị bởi: Hnhat1234
### Hướng dẫn
Nếu nhân một số với $m$ thì chắc chắn hai số còn lại sẽ phải tạo thành cấp số cộng. Ví dụ, nếu ta muốn nhân $m$ với $c$ thì $a = x_1$, $b=x_2=x_1+d$.

Vì $b-a=d$ nên $c=a+2*d$ hay $c=b+d$. Qua đó chỉ cần kiểm tra xem $a+2*d$ có chia hết cho $c$ hay không.

Tương tự với khi ta nhân $a$ hay $b$ với $m$.
### Cài đặt

#include <stdio.h>
long long a,b,c;
int main(){
        scanf("%lld%lld%lld",&a,&b,&c);
        if ((2*b-c)%a==0&&(2*b-c)/a>0){
            printf("YES");
        }else if ((2*b-a)%c==0&&(2*b-a)/c>0){
            printf("YES");
        }else if ((a + c)%2==0&&((a+c)/2)%b==0){
            printf("YES");
        }else{
            printf("NO");
        }
    return 0;
}

## E. Leo núi
Chuẩn bị bởi: Strkss
### Hướng dẫn
Từ đỉnh núi thứ $i$ thì có thể đến được từ đỉnh núi $i-1$ hoặc $i-2$. Thời gian đến được đỉnh núi thứ $i-1$ hoặc $i-2$ luôn phải là tối ưu. Qua đó chắc bạn cũng đoán được đây là một bài quy hoạch động khá cơ bản với công thức là:

$dp[i] = min(|h[i]-h[i-1]|+dp[i-1], |h[i]-h[i-2]|+dp[i-2]).$
### Cài đặt

#include <bits/stdc++.h>
using namespace std;
int main(){
		ios::sync_with_stdio(false);
		cin.tie(0);
		cout.tie(0);
		int n;
		cin>>n;
		vector<int> a(n);
		for (int i=0;i<n;i++){
			cin>>a[i];
		}
		vector<int> f(n);
		for (int i=0;i<n;i++){
			if (i==0){
				f[i]=0;
			}
			else if (i==1){
				f[i]=abs(a[i]-a[0])+f[0];
			}
			else{
				f[i]=min(abs(a[i]-a[i-1])+f[i-1],abs(a[i]-a[i-2])+f[i-2]);
			}
		}
		cout<<f[n-1];
}

## F. Cập nhật truy vấn
Chuẩn bị bởi: Strkss
### Hướng dẫn
Nếu bạn đang định dùng Prefix Sum thì chắc chắn sẽ bị TLE. Thay vì dùng Prefix Sum thì ta sẽ dùng Fenwick Tree (hay còn gọi là Binary Indexed Tree) để giải bài này. Vì hai thao tác tính tổng và cập nhật phần tử đã có khá nhiều trên mạng nên mình sẽ không nói tới nữa.
### Cài đặt

#include <bits/stdc++.h>
using namespace std;
 
long long sum(vector<long long> &bit, int pos){
    long long res=0;
    while (pos>=1){
        res+=bit[pos];
        pos-=(pos&(-pos));
    }
    return res;
}
 
void update(vector<long long> &bit, long long diff, int pos, int n){
    while (pos<=n){
        bit[pos]+=diff;
        pos+=(pos&(-pos));
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    vector<long long> a(n+1);
    vector<long long> s(n+1);
    vector<long long> bit(n+1);
    for (int i=1;i<=n;i++){
        cin>>a[i];
        if (i==1){
            s[i]=a[i];
        }
        else{
            s[i]=s[i-1]+a[i];
        }
    }
    for (int i=1;i<=n;i++){
        bit[i]=s[i]-s[i-(i&(-i))];
    }
    while (q--){
        int t;
        cin>>t;
        if (t==1){
            long long pos, val;
            cin>>pos>>val;
            long long diff=val-a[pos];
            update(bit, diff, pos, n);
        }
        else{
            int l, r;
            cin>>l>>r;
            long long suml=sum(bit, l-1);
            long long sumr=sum(bit, r);
            cout<<sumr-suml<<"\n";
        }
    }
}

## G. COWVID - 19
Chuẩn bị bởi: Ice Cream
### Hướng dẫn
Đầu tiên hãy sắp xếp các khoảng lại theo thứ tự tăng dần và tìm kiếm nhị phân trên $D$ khác nhau. Mỗi một hằng số $D$, ta muốn kiểm tra xem có thể đặt $N$ chú bò hay không.
### Cài đặt

#include <bits/stdc++.h>
using namespace std;
#define LIFESUCKS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
//ifstream fin("template.in");
//ifstream fin("template.in");
#include<fstream>
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
int n, m;
pair<ll, ll>p[100000];
bool check(ll mid){
    ll curr = p[0].fi;
    int can = 1;
    int now = 0;
    while(now < m){
        while(curr + mid > p[now].se && now < m){
            now++;
            
        }
        if(now == m){
            break;
        }
        curr = max(p[now].fi, curr + mid);
        can++;
    }
    return(can >= n);
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> p[i].fi >> p[i].se;
        
    }
    sort(p,  p + m);
    ll l =  1;
    ll ans;
    ll r = 1e18;
    while(l <= r){
        ll mid = l + (r - l)  / 2;
        if(check(mid)){
            ans = mid;
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}

## H. Nhà từ thiện Swyrin
Chuẩn bị bởi: Swyrin
### Hướng dẫn
Nếu mà bạn code bài này mà sử dụng `BFS/Flood Fill` thì đảm bảo các bạn sẽ bị TLE, và nếu các bạn thật sự làm như thế thì các bạn đã bị bắt thóp bởi mình, vì ý định của người ra đề là lừa mấy bạn ham cài thuật toán mà không nhìn vào bản chất vấn đề, hoặc ít nhất là mặt đơn giản hơn của nó.

#### Approach 1
Hmm, nếu mà mấy bạn thật sự làm như thế thì chỉ chạy được các bài có `N`, `Q` nhỏ, với độ phức tạp là <img src="https://render.githubusercontent.com/render/math?math=O(Q * complexity(BFS))"> nếu các bạn chỉ dùng code BFS đơn giản nhất. Cài đặt loại này [đầy trên mạng](https://cp-algorithms.com/graph/breadth-first-search.html) nên là mình sẽ không đưa lại cho các bạn code nữa nhé :D

#### Approach 2
Chúng ta có thể thấy được là nếu 3 ô phía trên (hoặc dưới) vị trí được đóng cọc có 1 cọc khác thì hiển nhiên là nước lũ sẽ không thể chảy qua, mặc kệ ở 1 vị trí xa lắc xa lơ nào đó đã có cọc rồi (hiên nhiên là Swyrin sẽ tiếp tục đói). Lý do mà chúng ta chỉ xét đến 3 ô vì nếu 3 ô đó chưa được đóng cọc thì nếu ta xét thêm 2 ô bên cạnh nó cũng là thừa, nước vẫn có thể chảy qua, nhìn hình dưới để hiểu thêm

x x x
. o .

. o .
x x x

Nếu chúng ta tìm thấy được cọc khác được đóng ở 1 trong 3 vị trí `x` phía trên/dưới nó (`o` là cọc được đóng theo kế hoạch xây dựng hiện tại) thì hiển nhiên là nước lũ sẽ không thể chảy qua được. 2 ô kề cạnh `o` thì sao? Như mình nói rồi đó, vì nếu 3 ô đó chưa được đóng cọc thì nếu ta xét thêm 2 ô bên cạnh nó cũng là thừa, nước vẫn có thể chảy qua.

### Cài đặt

void solve() {
  int N, Q; cin >> N >> Q;
  set<pair<int, int>> s;
  int count_others = 0;
  
  for (int q = 1; q <= Q; ++q) {
    int y, x; cin >> y >> x;
    bool hasPlaced = s.count({y, x});

    // chạy qua 9 ô (3 ô hàng trên, 2 ô cạnh nó, chính nó, 3 ô hàng dưới)
    for (int r = y - 1; r <= y + 1; ++r) {
      for (int c = x - 1; c <= x + 1; ++c) {
        // cùng hàng
        if (r == y) continue;

        // không nằm trong
        if (!(1 <= r && r <= 2 && 1 <= c && c <= N)) continue;
        
        // nếu mà ô lân cận của ô hiện tại đã có cọc rồi
        // mà ô hiện tại cũng đã có cọc, tức là sắp bị dỡ
        // nên count_others sẽ âm (cùng lắm <= 0)
        // nếu ô hiện tại chưa có cọc, tức là sẽ được đóng cọc, thì sẽ tính các ô lân cận
        // nên count_others sẽ dương
        if (s.count({r, c}))
          if (hasPlaced) --count_others;
          else ++count_others;
      }
    }
    
    // chuyển trạng thái
    if (hasPlaced) s.erase({y, x}); else s.insert({y, x});
    
    if (count_others >= 1) cout << "NO" << '\n'; else cout << "YES" << '\n';
  }
}