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

- Contest URL: https://atcoder.jp/contests/abc229
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20211127T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: leaf1415, physics0523, sugarrr
- Tester: blackyuki, kyopro_friends
- Rated range: ~ 1999

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

We are looking forward to your participation!

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.

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

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 solutionscosts cannot be zero

you can replace 0 with 2 and 1 with 10000 if it makes you happy

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

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.

quite close to this

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/

BSTA?

Binary search the answer

LeetCode's problem 1703 is easier. There is no need to binary search on the answer.

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

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

Plz. anyone tell me how to solve problem E. I did not understood it from the editorial.