APCS 06/16/24 Practical Problem Analysis 實作題解析
===

P1. [特技表演 Stunts](https://zerojudge.tw/ShowProblem?problemid=o076)
---

:::success
- 題目: 在給定的長度為N的數列H中找到最長嚴格遞減的子數列。
- Problem: Find the maximum length of strictly decreasing subarray in the given integer sequence H of length N.
:::
---

:::warning
- 實作細節:
- 用變數ans來維護最大值答案。
- 把每個0 ≤ i < N當作起始點，用while迴圈來讓i加一直到h[i+1] < h[i]不成立(須保證判斷過程中i < N-1)
- 過程中以cnt(初始值為一)來紀錄 i 共加了幾次。
- 最後再用cnt和ans取最大值即可。

- Solution Details:
- Use variable "ans" to keep track of the maximum value among all operations.
- Let every 0 ≤ i < N be the inital position, use while loop to increase i by 1 until the condition h[i+1] < h[i] is not satisfied (ensure i < N-1 in conditional statement).
- Use cnt (initially equals 1) to store how many times i is added.
- ans = max(ans, all possible cnt)

- 時間複雜度/Time Complexity: O(N)
:::
---

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

int main(){
int n, ans=0;
cin>>n;
vector<int> h(n);
for (int i=0; i<n; i++) cin>>h[i];

for (int i=0; i<n; i++){
int cnt=1;
while(i<n-1 && h[i+1]<h[i]){
cnt++;
i++;
}
ans=max(ans, cnt);
}
cout<<ans<<'\n';
}
~~~

---
:::info
相似題/Similar Problem: [LeetCode - Longest Strictly Increasing or Strictly Decreasing Subarray](https://leetcode.com/problems/longest-strictly-increasing-or-strictly-decreasing-subarray/description/)
:::

---

P2. [電子畫布 Electronic Canvas](https://zerojudge.tw/ShowProblem?problemid=o077)
---

:::success
- 題目: 給定N次操作，每次操作給r, c, t, x代表所有曼哈頓距離和(r, c)的格子小時等於t都染上顏色x，若已被染則顏色數值累加。輸出最後格子的樣子。
- Problem: Given N updates, each includes r c t x, meaning cells that have Manhanttan Distance less than or equal to t from cell (r, c) will be render to color x, if the cell is already rendered, then sum up the colors. Output the final grid.

曼哈頓距離/Manhanttan Distance = |x1 - x2| + |y1 - y2|
:::

---

:::warning
- 實作細節:
- 對於每次操作，枚舉所有格子，若格子(i, j)和中心點(r, c)距離≤t，則把給定顏色數值x加到此格的答案裡。最後輸出每隔的答案即可。

- Solution Details:
- For each update, enumerate over all cells on the grid, if the distance between the current cell (i, j) and the center cell (r, c) is less than or equal to t, then add given x to the answer of (i, j). Lastly, output the answer for each cell on the grid.

- 時間複雜度/Time Complexity: O(N * H * W)
:::

---

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

int main(){
int h, w, n;
cin>>h>>w>>n;
vector<vector<int>> ans(h, vector<int>(w, 0));

while(n--){
int r, c, t, x;
cin>>r>>c>>t>>x;
for (int i=0; i<h; i++){
for (int j=0; j<w; j++){
if (abs(i-r) + abs(j-c) <= t) ans[i][j]+=x;
}
}
}

for (int i=0; i<h; i++){
for (int j=0; j<w; j++) cout<<ans[i][j]<<' ';
cout<<'\n';
}
}
~~~

---
:::info
延伸題/Extension Problem:
- <font color="#f00">**1 ≤ N ≤ 10^6^**</font>
- 1 ≤ H, W ≤ 20
- 0 ≤ r < H
- 0 ≤ c < W
- 0 ≤ t ≤ 20
- 1 ≤ x ≤ 10
:::

:::info
:::spoiler 解答
若是按照原來的寫法，會得到TLE。思考一下，會發先其實只有N的數值會變，其餘不變。也就是說其實不管N多大，最多能染的也就是20x20格。可以觀察到t的值本來就不大，所以也可以用到這個條件。因此我們可以思考成先把N次操作先記錄到格子上 --> 對於格子(i, j)， 記錄以這個格子為中心距離d的其他格子需要加上的顏色數值總和。所以可以開一個三維陣列存，像以下這樣:

~~~cpp=
const int H = 21;
const int W = 21;
const int T = 21;

int add[H][W][T];

// 對於所有(i, j, d)， 保證i<H && j<W && d<T。
add[i][j][d] = 以格子(i, j)為中心距離d的其他格子要加上的顏色數值總和;
~~~

這樣一來就可枚舉所有點，再以這些點去枚舉所有其他點來得到答案。具體來說，另兩點為(r, c) & (r1, c1)，距離為|r - r1| + |c - c1| = d。如果d≤20，我們就可以知道(r1, c1)的答案要加上add[r][c][d~20]的顏色數值總和。由於直接暴力一個一個加的話可能導致程式碼TLE(因為5重回圈，20^5^)，所以這點可以用前綴和或後綴和來優化(注意overflow)，這樣一來這個題目就結束了!
時間複雜度: O(H^2^W^2^ + N)

:::spoiler 程式碼
~~~cpp=
#include<bits/stdc++.h>
using namespace std;

const int H=21;
const int W=21;
const int T=20;

long long add[H][W][T+1]={};
int ans[H][W]={};

int main(){
int h, w, n;
cin>>h>>w>>n;

while(n--){
int r, c, t, x;
cin>>r>>c>>t>>x;
add[r][c][t]+=x;
}

for (int r=0; r<h; r++){
for (int c=0; c<w; c++){
for (int t=0; t<T; t++){
add[r][c][t+1] += add[r][c][t];
}
}
}

for (int r=0; r<h; r++){
for (int c=0; c<w; c++){
for (int r1=0; r1<h; r1++){
for (int c1=0; c1<w; c1++){
int d=abs(r-r1) + abs(c-c1);
if (d > 20) continue;
ans[r1][c1] += add[r][c][T] - (d > 0? add[r][c][d-1]: 0);
}
}
}
}

for (int r=0; r<h; r++){
for (int c=0; c<w; c++) cout<<ans[r][c]<<' ';
cout<<'\n';
}
}
~~~
:::

:::info
:::spoiler Solution
If we use the exact same code from before, it will result in TLE verdict. However, thinking about this closely, we notice that only the constraint of N changed while others remain exactly same. This also conveys that no matter how large N is, the updates can only performed on maximum of 20x20 cells on the grid. We can also see that the value of t is very small, therefore we can also apply this fact to our algorithm. In conclusion, we can first store N updates on the grid --> for cell (i, j), store the color value in which all cells that have distance d from (i, j) need to be added. Thus, we could declare a three dimensional array to do this, like the code shown below:

~~~cpp=
const int H = 21;
const int W = 21;
const int T = 21;

int add[H][W][T];

// For every (i, j, d), where i<H && j<W && d<T.
add[i][j][d] = the value need to be added to all cells that have distance d from (i, j);
~~~

In this way, we could enumerate over all cells, and enumerate all other cells from this cell to get the answers in the entire grid. More precisely, let two cells be (r, c) & (r1, c1), and distance |r - r1| + |c - c1| = d. If d≤20, we know that the answer for cell (r1, c1) need to increase by the sum of add[r][c][d~20]. However, if we sum it up one by one, it might result in TLE verdict due to 5 nested loops (20^5^). In order to avoid TLE verdict, we could use prefix sum or suffix sum (be aware of overflow) to optimize this step. This problem is solved!
Time Complexity: O(H^2^W^2^ + N)

:::spoiler Code
~~~cpp=
#include<bits/stdc++.h>
using namespace std;

const int H=21;
const int W=21;
const int T=20;

long long add[H][W][T+1]={};
int ans[H][W]={};

int main(){
int h, w, n;
cin>>h>>w>>n;

while(n--){
int r, c, t, x;
cin>>r>>c>>t>>x;
add[r][c][t]+=x;
}

for (int r=0; r<h; r++){
for (int c=0; c<w; c++){
for (int t=0; t<T; t++){
add[r][c][t+1] += add[r][c][t];
}
}
}

for (int r=0; r<h; r++){
for (int c=0; c<w; c++){
for (int r1=0; r1<h; r1++){
for (int c1=0; c1<w; c1++){
int d=abs(r-r1) + abs(c-c1);
if (d > 20) continue;
ans[r1][c1] += add[r][c][T] - (d > 0? add[r][c][d-1]: 0);
}
}
}
}

for (int r=0; r<h; r++){
for (int c=0; c<w; c++) cout<<ans[r][c]<<' ';
cout<<'\n';
}
}
~~~
:::

---

P3. [缺字問題 Missing Characters Problem](https://zerojudge.tw/ShowProblem?problemid=o078)
---

:::success
- 題目: 給定一個大小為K個字母的集合和字串S，求出在使用該集合所組出長度為L字串中，不為字串S子字串的最小字典序字串為何。
- Problem: Given a collection of K alphabets and a string S. Find the lexicographically smallest string of length L, formed by the concatenation of given alphabets (repetitions allowed), that is not a substring of S.
:::

---

:::warning
- 實作細節:
- 使用滑動視窗來紀錄S所有長度為L的子字串，再將記錄的子字串由小到大按字典順序排序。
- 由小到大按字典順序排序K
- 用字母集合K來暴力枚舉所有可能形成長度為L得字串，每次形成便可以用二分搜來查訊是否在S裡出現過。
- 若任何時刻發現所形成字串沒有在S裡，輸出此字串即可。

- Solution Details:
- Make use of sliding window to store all substrings in S with length L, sort them in ascending order afterwards.
- Sort K in ascending order.
- Enumerate all possible strings of length L using K.
- Each time a new string of length L formed, use binary search to check if it appears in S. If it doesn't, output it right away.

- 時間複雜度/Time Complexity: O(K^L^ log|S|)
:::

---

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

set<string> c;
string k, s;
int l;

void dfs(int i, string now){
if (i==l){
auto u=c.find(now);
if (u==c.end()){
cout<<now<<' ';
exit(0);
}
}
else{
for (char ch : k) dfs(i+1, now+ch);
}
}

int main(){
cin>>k>>l>>s;
sort(k.begin(), k.end());

string ss="";
for (int i=0; i<l; i++) ss+=s[i];
c.insert(ss);

for (int i=l; i<s.size(); i++){
ss.erase(0, 1);
ss+=s[i];
c.insert(ss);
}
dfs(0, "");
}
~~~

---

P4. [最佳選擇 Optimal Selections](https://zerojudge.tw/ShowProblem?problemid=o079)
---

:::success
- 題目: 給一個長度為N的正整數序列A，你可以執行多次操作(包含 0 次)。每次操作只能選擇這個序列的第一個或最後一個數字，再將這個數字從序列中刪除並自己搜集起來。求滿足總和不超過K且搜集的數字奇數和偶數個數相同的條件下，所能搜集的數字總和最大為多少。
- Problem: Given an integer sequence A, perform the following operation any number of times, including 0. Remove either front or last element from the sequence, then add it to your collection. Find the maximum sum of removed integers no greater than K, where the number of odd integers and the number of even integers in your collection are equal.
:::

---

:::warning
- 解題想法 & 實作細節:
- 題目保證所有數列A裡的數字為正整數 --> 前綴和 --> 單調性 --> 二分搜。任何時刻基偶數的差值 ≤ 10^3^。
- 因此，這題要用到前綴和搭配二分搜並且從頭到尾紀錄基偶數的差值。
- 測資答案<font color="#f00"> **1 5 2** </font> 2 9 3 5 <font color="#f00"> **8** </font> 可以看成 1 5 2 2 9 3 5 <font color="#f00"> **8** </font> | <font color="#f00"> **1 5 2** </font> 2 9 3 5 8。
- 用變數diff來記錄從0到目前位子基數和偶數的差值。
- 範例測資一解析：
- A[2 * N]: 1 5 2 2 9 3 5 8 1 5 2 2 9 3 5 8
- i = 0 | A[0] = 1 | diff = 1
- i = 1 | A[1] = 5 | diff = 2
- i = 2 | A[2] = 2 | diff = 1
- i = 3 | A[3] = 2 | diff = 0
- i = 4 | A[4] = 9 | diff = 1
- i = 5 | A[5] = 3 | diff = 2
- i = 6 | A[6] = 5 | diff = 3
- i = 7 | A[7] = 8 | diff = 2
- 以此類推. . .
- 以上述測資來講，當i = 7 & diff = 2，我們會發現之前走過i = 1時，diff也是2。仔細想想，其實這代表A[2 ~ 7]的基偶數量相同。但要小心，這是因為i ≥ N - 1，這才可以被考慮進答案，像是A[2 ~ 5]就不行，因為題目有說到每次只能拿最前面或最後面的數字。因此當i < N - 1，其實只有diff = 0時可以被考慮進答案(從頭拿到目前位子i)，但也要確保它的總和 ≤ K。
- 可以用一個map<long, multiset<long>>來紀錄出現過的diff的所有前綴和的值。
- mp[ diff ] = {prefix[i], prefix[j], ...};
- 例如當i = 2更新完時:
- mp[ 1 ] = {1, 8};
- mp[ 2 ] = {6};
- 這樣一來便可以直接對mp[ diff ]做lower_bound找到第一個大於等於目前前綴和減掉K的值。目前前綴和的值和找到的值兩者相差便是答案候選人(它一定 ≤ K)。
- 注意以下幾點:
- 只有i ≥ N - 1才能看跟自己目前一樣的diff。
- 當i < N - 1時，只有diff = 0時可以考慮進答案(更新時確保值 ≤ K)。
- i ≥ N時就可以不要更新mp了，避免取到像A[9 ~ 12] (沒包含到頭尾)。
- 在對mp[ diff ]裡坐二分搜時避免搜尋到位置和自己相差 ≥ N，代表範圍重複了。細節請參考程式碼。
- 二分搜要小心會找不到。要確保搜尋到的iterator != mp[ diff ].end()。

- Solution Ideas & Details:
- This problem ensures that all elements of A are integer --> Prefix Sum --> Monotonicity --> Binary Search. Furthermore, the difference between the number of odd and even integers at any time is ≤ 10^3^.
- As a result, this problem can be solved using prefix sum and binary search, while keeping track of the difference between the number of odd and even integers.
- Let's take a look at the output for sample 1, where <font color="#f00"> **1 5 2** </font> 2 9 3 5 <font color="#f00"> **8** </font> can be seen as 1 5 2 2 9 3 5 <font color="#f00"> **8** </font> | <font color="#f00"> **1 5 2** </font> 2 9 3 5 8.
- Define variable diff to keep track of the difference between the number of odd and even integers from index 0 to the current index i.
- Sample 1 Analysis:
- A[2 * N]: 1 5 2 2 9 3 5 8 1 5 2 2 9 3 5 8
- i = 0 | A[0] = 1 | diff = 1
- i = 1 | A[1] = 5 | diff = 2
- i = 2 | A[2] = 2 | diff = 1
- i = 3 | A[3] = 2 | diff = 0
- i = 4 | A[4] = 9 | diff = 1
- i = 5 | A[5] = 3 | diff = 2
- i = 6 | A[6] = 5 | diff = 3
- i = 7 | A[7] = 8 | diff = 2
- And so on. . .
- According to sample 1 above, when i = 7 & diff = 2, we notice that diff is also 2 when i = 1. Taking a closer observation, this shows that A[2 ~ 7] has the same number of odd and even integers. However, the sum of the observed range can be considered as the answer if and only if i ≥ N - 1. A[2 ~ 5], for instance, cannot be considered as the answer because the problem mentioned that only either front or back elements of A can be taken away in each operation. In fact, for each i < N - 1, the only way to make any changes to the answer is when diff = 0 (sum up elements from index 0 ~ i), and the sum is ≤ K.
- Declare a map<long, multiset<long>> to store the prefix sums for each appeared diff.
- mp[ diff ] = {prefix[i], prefix[j], ...};
- After updating i = 2:
- mp[ 1 ] = {1, 8};
- mp[ 2 ] = {6};
- This way we could directly perform lower_bound on mp[ diff ] to find current prefix sum minus k. The difference between current prefix sum and founded value is the candidate of the final answer.
- Be mindful of the following few points:
- Check the same, appeared diff if and only if i ≥ N - 1.
- For i < N - 1, only if diff = 0, the current prefix sum can be considered as the answer (ensure the value is ≤ K).
- For i ≥ N, no need to update mp, in order to prevent from getting some ranges in between the front and back elements of A.
- When performing binary search
- Avoid searching for the value that has the distance ≥ N from the current index. Refer to the code below for details.
- Ensure founded iterator != mp[ diff ].end().

- 時間複雜度/Time Complexity: O(N logN)
:::
---

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

#define ll long long

int main(){
ll n, k, diff=0, ans=0;
cin>>n>>k;
vector<ll> a(2*n), prefix(2*n+1, 0);
for (int i=0; i<n; i++){
cin>>a[i];
a[i+n]=a[i];
}
for (int i=0; i<2*n; i++) prefix[i+1]=prefix[i]+a[i];

map<ll, multiset<pair<ll, ll>>> mp;
map<ll, multiset<ll>> val;
for (int i=0; i<2*n; i++){
(a[i]&1)? diff++: diff--;
if (i<n && !diff && prefix[i+1]<=k) ans=max(ans, prefix[i+1]);

if (i>=n-1 && mp.find(diff) != mp.end()){
while(mp[diff].size() && i - mp[diff].begin()->first >= n){
val[diff].erase(val[diff].find(mp[diff].begin()->second));
mp[diff].erase(mp[diff].begin());
}

auto it=val[diff].lower_bound(prefix[i+1] - k);
if (it != val[diff].end()) ans=max(ans, prefix[i+1] - *it);
}

if (i>=n) continue;
mp[diff].insert({i, prefix[i+1]});
val[diff].insert(prefix[i+1]);
}
cout<<ans<<'\n';
}
~~~

---

:::info
:::spoiler 其他解法/Alternative Solution:

- 想法: 先從頭到尾紀錄所有diff的所有前綴和值，再從尾走到頭找出現過的-diff (-diff + diff = 0，代表基偶數相同)的所有前綴和值，再做二分搜(利用後綴和和K來搜尋最佳值)。請參考以下程式碼。
- Ideas: Iterate from the beginning to the end, store the prefix sums for each appeared diff. Then, iterate from the end to the beginning, performed binary search on all prefix sums previously stored as -diff (-diff + diff = 0, meaning that the number of odd and even integers are equal) by using current suffix sum and K to find the optimal solution. Refer to the code below:

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

#define ll long long

int main(){
ll n, k, diff=0, sum=0, ans=0;
cin>>n>>k;
vector<ll> a(n);
for (auto &c : a) cin>>c;
map<ll, multiset<pair<ll, ll>>> mp;
map<ll, multiset<ll>> val;

for (int i=0; i<n; i++){
(a[i]&1)? diff++: diff--;
sum+=a[i];

mp[diff].insert({i, sum});
val[diff].insert(sum);
}
if (val.find(0) != val.end()){
auto it = val[0].upper_bound(k);
if (it != val[0].begin()) ans=max(ans, *(--it));
}

diff=sum=0;
for (int i=n-1; i>=0; i--){
(a[i]&1)? diff++: diff--;
sum+=a[i];

if (!diff && sum<=k) ans=max(ans, sum);
if (mp.find(-diff)==mp.end() || sum > k) continue;

while(mp[-diff].size() && mp[-diff].rbegin()->first >= i){
val[-diff].erase(val[-diff].find(mp[-diff].rbegin()->second));
mp[-diff].erase(--(mp[-diff].end()));
}

auto it = val[-diff].upper_bound(k - sum);
if (it == val[-diff].begin()) continue;
ans=max(ans, sum + *(--it));
}
cout<<ans<<'\n';
}
~~~
:::
---