chokudai's blog

By chokudai, history, 3 years ago, In English

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!

  • Vote: I like it
  • +60
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it -24 Vote: I do not like it

For the problem F: https://atcoder.jp/contests/abc229/tasks/abc229_f

I 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 <bits/stdc++.h>
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<<ans;
}

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 :/

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For N=5 it might be optimal to delete 4 edges. E.g.

    A = 0, 1, 1, 1, 1 B = 1, 0, 0, 0, 1

    Hence 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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How does everyone have almost the same solution for E? Was there a similar problem to it somewhere?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    quite close to this

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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/

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Surreal number in beginner contest (H), are you kidding?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Recently, H in ABC treats trending topics of competitive programming, which are often very advanced but is a good lesson for even an expert.