# 22strb - THTB Sơn Trà 2022

## Mắc đèn

Công thức $8a$.

Các bạn thử lấy vở ô ly và vẽ test VD để hiểu :smile:

## Bài 2

Ngày chia hết cho $18$ là ngày cả 2 máy đều nghỉ

## Bài 3

### Subtask 1 (50%): $O(n^3)$

Đề bảo chọn ra 3 vị trí --> Dùng 3 vòng lặp For

for (i từ 1 tới n-2) {
    for (j từ i+1 tới n-1) {
        for (k từ j+1 tới n) {
            kết quả = max(kết quả, a[i] + a[j] - a[k]);
        }
    }
}


## Subtask 1.5: $O(n^2)$ (thanks hoangtieuho)

kq = 0;

 for(int i = 1; i <= n-2; i++) {
    int min_aj = a[i+1];
    for(int k = i+2; k <= n; k++) {
        kq = max(kq, a[i] - min_aj + a[k]);
        min_aj = min(min_aj, a[k]);
    }

## Subtask 2: $O(n)$

Chỉ chạy một vòng lặp `for` j để cố định $a_j$

Cần tìm (nhanh):
- $i$ là vị trí của phần tử lớn nhất TRƯỚC $j$
- $k$ là vị trí của phần tử lớn nhất SAU $j$

CTDL: Prefix-sum. Chi tiết: https://www.youtube.com/watch?v=gK4sTB4aznA&t=1650s

## Bài 4:

### Subtask 1 $a,n \le 1000$

Đặt L: mực nước

kq = 0;

for (L từ 1 tới max_a) {
    a[0] = -1
    a[n+1] = -1
    đếm_cô_đơn = 0
    for (i từ 1 tới n) {
        if (a[i] >= L) và (a[i-1] < L) và (a[i+1] < L) {
            đếm_cô_đơn += 1
        }
        kq = max(kq, đếm_cô_đơn)
    }
}

$O(n\times a_{\max})$

### Subtask 2

Mỗi tòa nhà sẽ có một khoảng thời gian liên tiếp mà nó bị cô độc.

pigbank - lqdoj
https://wiki.vnoi.info/vi/algo/data-structures/prefix-sum-and-difference-array

### Subtask 3

$[1,300]$ và $[50,400]$

$[1,3]$ và $[2,4]$

Áp dụng kĩ thuật nén số: https://viblo.asia/p/roi-rac-hoa-nen-so-38X4E9QA4N2