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 representslets 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
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.