# 2023/02/12 mock interview Candidate: louis
###### tags: `Tag(mock interview)`
---
題目: https://codeforces.com/problemset/problem/1779/C

<font size= 4><center> **倒數計時** </center></font>
<iframe id="oak-embed" width="700" height="400" style="display: block; margin: 0px auto; border: 0px;" src="http://zbryikt.github.io/quick-timer"></iframe>

# 題目講解
//time: 21: 17

int n, m
array,

n is length of array

array = a1 + a2 + a3 .... am is the smallest prefix sum

k = 1 ~ n
a1 + a2 + a3 ... ak >= a1 + a2 + a3 .... am

we can swap any idex in array.
we can change the value by multiple value of index
multi value ai with -1

find the minmum count of swap.

example:
4 2

[0 1 2 3]
-1 -2 -3 -4

-1 -2 -3 = -6 is the smalles prefix sum.

=> -1 -2 -3 4
sum [-1, -3, -6 -2]
sum[2] is the smallest prefix sum

return count is 1

5 1.
-2 3 -5 -5 -20
[-2 1 -4 -9 -29]
^

v v v
array: -2 -3 5 -5 20
prefix: [-2 -5 0 -5 15]

return 3

// time: 21 : 26

# 作法講解
// time: 21 : 28

// goal: minimum the operations, and make pre[m] smallest than other pre[i] in 0~n

// m is fixed
//.
// -2 3 -5 -5 -20
// [-2 1 -4 -9 -29]
//.

// V
// -2 3 -5 -5 -20
// [2 5 -4 -9 -29]

array: -2 -3 5 -5 20
prefix: [-2 -5 0 -5 15]

// m
// v
// -2 3 2
// -2 1 3
//

// max heap (value, index)
// -2 -3 2
// -2 -5 3
//

// v
// -2 -3 -2
// -2 -5 -7
//

// observation
// for i in range(0:m)
// pre[m] > smallest pre
// change the previous value to make prefix greater
//

// v
// -2 (3) -5 -5 -20
// -2. 1
// [-2 -5 -4 -9 -29]
// ^
// 3 -> -3 value change will decrease - 2 * 3

// v
// -2 (3) -5 -5 -20
// -2. 1
// [-2 -5 -10 -9-6 -29-6]

// v v v
// -2 (3) (-5) -5 20
// -2. 1
// [-2 -5 -10+10 -9-6+10 -29-6+10]
// -5 -25+40 = 15

// -5 -> 5 value change will increase 2 * 5

ans array
array: -2 -3 5 -5 20
prefix: [-2 -5 0 -5 15]

4 2

// m
[0 1 2 3]
1. 5. 6 4
-1 -5 -6 -4
pre = 1 6 12. 16

// pick the largest value before -> need to handle how // update the prefix
//
//

// pre = 16 -> minimum (smaller)
// 1. never change the neg to pos (pre greater)
// 2. pos to neg
// choose largest value to negative
//
c

[0 1 2 3]
1. 5. -6 4
pre = 1 6 0. 4

[0 1 2 3]
1. -5. -6 4
pre = 1 -4 -10. -6

[0 1 2 3]
1. -5. -6 -4
pre = 1 -4 -10. -14

// m
[0 1 2 3]
[1. 5. 6] 4
pre = 1 6 12. 8

// m
[0 1 2 3]
1. 5. 6 4
pre = 1 6 12. 16
// <
// m
[0 1 2 3]
1. 5. 6 -4
pre = 1 6 12. 8
>
<
// m
[0 1 2 3]
1. 5. -6 -4
pre = 1 6 0. -4
//

m
[0 1 2 3]
array {x x x} 3

m-1 m
[0 1 2 3]
array {x x 2 -1(less than 0)

m-1 m
[0 1 2 3]
array -5 5 2 -2
pre -5 0 2 0 , [2]
// ^ -10
-5
-5 -10 -8 -10

// 1. calculate the index after m
...
// 2. calculate the index before m
// max heap

p1 p2 m
{x x x x x} { y } {x postive x }
-y +z
-5 2 -1

|p1| is smaller than |p2|

# coding
//time:

# 完成
//time:

# comment

21:46 找到方法解決 index > m 的部分

觀察
prefix
string

You are given two strings s and t.

You are allowed to remove any number of characters from the string t.

The score string is 0 if no characters are removed from the string t, otherwise:

Let left be the minimum index among all removed characters.
Let right be the maximum index among all removed characters.
Then the score of the string is right - left + 1.

Return the minimum possible score to make t a subsequence of s.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

s = yyyyyyyyyyyy
t = xxxx{x}xx{x}xx

// how to find the left, right index

// index array

l. r
t = xxxx{x}xx{x}xx
ans = r - l + 1

s = |yyyyyy| y |yyy|yy
t = xxxx {x}xx{x} xx

s = |yyyyyy| yyyyyyy
t = xxxxxxx{xxxxx}

s = adbc zzzz
t = abc {xxxx} =>

s = adbcxxxxxx t = |abc|

0 -> j
s = {abc}yyyyyyyjjj
t = abc {xxxxx} jjj

sub problem
定義 t : abc, 從 s range: 0 ~ j 滿足 subseq is abc
使得 j 是越小越好

定義 任意長度 len: 1 ~ n: is s's subseq

case 1: t = x x x {x x x x x x x}
left_idx = s[j,j j]

s[0 -> j] 滿足 t[i]

t = abc {xxxxx} j
case 2: t = {x x x x} x x x x x x
right_idx = s[j,j j]
s[j -> sn-1] 滿足 t[i]

i j
case 3: t = x x x {x x x x} x x x
t[i]=>s[0~j] t[j] => s[j~n] j-i-1