---
# System prepended metadata

title: '2023 mock interview Candidate: louis'
tags: [Tag(template)]

---

# 2023 mock interview Candidate: louis
###### tags: `Tag(template)`
---
https://codeforces.com/problemset/problem/1748/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:37

the score of array is means 
sum(a1 + a2 + a3 ...) = 0




5
0 1 2 3  4
2 0 1 -1 0

idx: 1  value: 0 -> -2


2 -2 1 -1 0
2 0  1  0 0

the score = 3


  
       

score is prefix, maximum the zero nubmer
replace 0 to any int

# 作法講解
//time: 21



2 0 1 -1 0
2 2 3 2  2

choose index = 4
2 0 1 -1 -2
2 2 3 2  0

choose index = 1
2 0 1 -1 -2
2 2 3 2  0
  -2 -2 -2 -2
  
observation:
we must choose smallest index to replace 

idea:
greedy, we do from to left to right
when we meet 0, we just calculate the current
add a negative sign
   
   x        v
2  0   1 -1 0 x x x
2  2   3 2 -2 0 0 0 

what if we meet 0, we can either replace to current -value, or skip it
TC: O(n2^n)


   x        v
2  0   1 -1 0 x x x
2  2   3 2 -2 0 0 0 

   change or no change

dp[i][0], maximum score can get, start from index i, and idnex is not changed
dp[i][1], maximum score can get, start from index i, and idnex changed


i -> i+1, value change 2
dfs(i, pre, ischanged)
    
    int score = pre == 0;
    res = dfs(i+1, pre+arr[i], 0)
    if arr[i] == 0
        res = dfs(i+1, 0, 1)
    



val =  2 0 1 -1 1 -1 1 -1 
sum    2 2 3 2  3 2  3  2
 
 
val =  2 -2 1 -1 1 -1 1 -1 
sum    2 0  1 0  3 2  3  2


val =   2 0  2 1 1 -1 1 -1 1 -1 
sum     2 2  4 5 6  5 6  5 6  5

sum     2 0  2 3 4  3 4  3 4  3 

val =   2 -5  2 1 1 -1 1 -1 1 -1 
sum     2 2   4 5 6  5 6  5 6  5
         
       

dp[i][current sum] space is very big

  v      v
2 0 | 1 -1 0 | z z z z 0
2 2   3 2  2
  x    x x x   x x x x x
           y   y y y y y

  v        v
2 0 | 1 -1 0 | z z z z 0
2 2   3 2  2

  x             v
2 0   x x x 0 0 0  z z z z 0
2 -2  a a a 0 0 2
            x x 
            
  x             v
2 0   x x x | 0 0 0  z z z z 0
2 0   a a a | 0 0 2
              x x 
              
              
  x           v
2 2   x x x | -2 0 0  z z z z 0
2 0   a a a | 0 0 2
              x x         

step 1: change first idx value is 0
step 2: change second idx, value is 0,


              
       0   x x x | (0 y y y) | (0 z z z)
pre= 2 2   0 0 0   
       0

either change or no change -> find maximum score before next zero index

       0   x x x | (0 y y y) | (0 z z z)
pre= 2 2   0 0 0   
       0


         v
       2 0 0 0 | 0 0 0 0 0 0| (0 z z z)
pre=   2 2 2 [0   0 0 0 0 0 0] 
         
         v
       2 [-2]  | 0 0 0 0 0 0| (0 z z z)
pre=   2  0   2 [0   0 0 0 0 0 0] 



        0   x x x | (0 y y y) | (0 z z z)
pre= 2 -2   y y y 




    2 0 2 -1 1 -1
    2 2 4 3  4 3
    
    2 -2 2 -1 1 -1
    2 0  2  1 2  1
    
    2 0  3 -3 3 -3
    2 0  3 0  3. 0
      -2 1 -2 1 -2
 
how to find the affect of replace??

seperately do each segment

hashtable record the number, value -> fre

change:
 0
 -2, max of (mp[2], mp[3], mp[4])
 
 0 -> -3
 0 -> -4
 
 0 -> 2
 0 -> 3
 
    3 0   3 -3 3 -3 | 
    3 -3  3 0  3. 0
          0 -3 0 -3
 
   1             
 2 0 |x x x x x x| 0 |        |
                p
                
                   0
                4  -4  | x x x x x x x x |
                5  -5  | x+1 x+1 x+1 x+1 x+1 x+1 x+1 x+1 |
                6  -6  | x+2 x+2 x+2 x+2 x+2 x+2 x+2 x+2 |
 2 -2
   0
 
 no change
 mp[0]

use the value to calculate the next segment


hint: we can think which range is chagned after replace 0 to anther value.


# coding
//time: 

```cpp=



```
# 完成
//time: 



# comment



self:
列舉example greedy觀察失敗
然後想了brute force複雜度很高
然後想了dp但沒想到prefix可以變成其他數值gg, wrong
開始卡 -> how to avoid? ask for a hint