---
# System prepended metadata

title: '2023/02/12 mock interview Candidate: louis'
tags: [Tag(mock interview)]

---

# 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
          



