### chokudai's blog

By chokudai, history, 2 months ago,

We will hold NEC Programming Contest 2021(AtCoder Beginner Contest 229).

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

• +60

 » 2 months ago, # |   -24 For the problem F: https://atcoder.jp/contests/abc229/tasks/abc229_fI made the use of the observation that for each of the N triangles forming, for each triangle one edge must be deleted.I had dp(i, j) = lets say we have processed till triangle i, and we have deleted exactly one edge from each triangle from 1 to i, where the edge deleted from current triangle i is jth edge. For each triangle edges are numbered as 0, 1, 2. for a triangle been formed by vertices 0, x and x + 1. 0th edge = between 0 and x, 1st edge = between x and x + 1 and 2nd edge is between 0 and x + 1. But not sure why the answer gets incorrect. #include using namespace std; #define ll long long #define si(X) scanf("%d", &(X)) #define sll(X) scanf("%lld",&(X)) const int M = 200011; ll arr[M], brr[M]; ll dp[M][3]; const ll MAXX = 1e13; ll get_min(ll a, ll b){ if(a == -1) a = MAXX; if(b == -1) b = MAXX; return min(a, b); } int main(){ int n; si(n); for(int i = 1 ; i <= n ; i++){ sll(arr[i]); } for(int i = 1 ; i <= n ; i++){ sll(brr[i]); } ll ans = MAXX; for(int xx = 0 ; xx < 3 ; xx++){ memset(dp, -1, sizeof(dp)); if(xx == 0){ dp[1][0] = arr[1]; } else if(xx == 1){ dp[1][1] = brr[1]; } else{ dp[1][2] = arr[2]; } for(int i = 2 ; i < n ; i++){ // pick anything from this triangle for(int j = 0 ; j < 3 ; j++){ if(j == 0){ // means 2 of previous dp[i][j] = get_min(-1, dp[i - 1][2]); } if(j == 1){ // means 1 or 0 of previous dp[i][j] = brr[i] + get_min(dp[i - 1][0], dp[i - 1][1]); } if(j == 2){ // means 1 or 0 of previous dp[i][j] = arr[i + 1] + get_min(dp[i - 1][0], dp[i - 1][1]); } } } // last triangle remaining; if(xx == 0){ // then this triangle is taken care of ans = get_min(ans, get_min(dp[n - 1][0], dp[n - 1][1])); } else if(xx == 1){ // this triangle needs to cut some edge, and has to be 0 or 1 // for 0 ans = get_min(ans, dp[n - 1][2]); // for 1 ans = get_min(ans, get_min(dp[n - 1][0], dp[n - 1][1]) + brr[n]); } else{ // for 0 ans = get_min(ans, dp[n - 1][2]); // for 1 ans = get_min(ans, get_min(dp[n - 1][0], dp[n - 1][1]) + brr[n]); } } cout<
•  » » 2 months ago, # ^ |   +3 I think the b[] edges form another odd sized circle if n is odd. In that case at least one of the b[] edges must be removed.I tried to implement such dp, but failed :/
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 For N=5 it might be optimal to delete 4 edges. E.g.A = 0, 1, 1, 1, 1 B = 1, 0, 0, 0, 1Hence although for each triangle one edge must be deleted is true, if your dp state represents lets say we have processed till triangle i, and we have deleted exactly one edge from each triangle from 1 to i, you dp states do not capture all solutions
•  » » » 2 months ago, # ^ |   0 costs cannot be zero
•  » » » » 2 months ago, # ^ |   +1 you can replace 0 with 2 and 1 with 10000 if it makes you happy
 » 2 months ago, # |   0 How does everyone have almost the same solution for E? Was there a similar problem to it somewhere?
•  » » 2 months ago, # ^ |   +3 Popular variant is where you delete all edges one by one and have to tell the components on every step. It even appeared in some ABC once.Didn't need much thought to modify the solution for vertex removal variant.
•  » » 2 months ago, # ^ |   +8 quite close to this
 » 2 months ago, # |   0 G previously appeared in a leetcode contest before (well, the version of G after applying BSTA): https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/
•  » » 2 months ago, # ^ |   0 BSTA?
•  » » » 2 months ago, # ^ |   +4 Binary search the answer
•  » » 2 months ago, # ^ |   0 LeetCode's problem 1703 is easier. There is no need to binary search on the answer.
 » 2 months ago, # |   +12 Surreal number in beginner contest (H), are you kidding?
•  » » 2 months ago, # ^ |   +34 Recently, H in ABC treats trending topics of competitive programming, which are often very advanced but is a good lesson for even an expert.
 » 2 months ago, # |   0 Plz. anyone tell me how to solve problem E. I did not understood it from the editorial.