Блог пользователя chokudai

Автор chokudai, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +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 :/

  • »
    »
    3 года назад, # ^ |
    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, 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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    quite close to this

»
3 года назад, # |
  Проголосовать: нравится 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/

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.