### chokudai's blog

By chokudai, history, 14 months ago,

We will hold UNIQUE VISION Programming Contest 2022 Winter(AtCoder Beginner Contest 283).

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

• +19

| Write comment?
 » 14 months ago, # | ← Rev. 2 →   -10 UNIQUE VISION rounds can always surprise me.Looking forward to the contest in the evening!Merry Christmas!
 » 14 months ago, # |   0 How to do problem E?
•  » » 14 months ago, # ^ |   0 Try to use dp.
•  » » » 14 months ago, # ^ |   0 Will iterative dp work for this problem ? If yes, then please share the solution (anyone who solved).
•  » » » » 14 months ago, # ^ | ← Rev. 4 →   0 Try d[i][conf] = minimum number of steps to consider the first $i$ lines. (i.e. solve the first $i-1$ lines) $conf \in { 0, 1, 2, 3 }$ shows if lines $i-1$, $i$ have been flipped in this particular configuration.When calculating d[i][..], you are "cementing" the state of line $i-1$.Build d[i][conf] from d[i][conn], where $conn$ has the same configuration as $conf$ for line $i-1$, but anything for line $i-2$.Suppose d[1][0] = 0, d[1][1] = 1. Watch out, when building d[2][..] you cannot flip line 0. Also, when building d[n+1][..] you don't want to flip line n+1.It helps to border the matrix.ans = min(d[n+1][conf] | 0 <= conf < 4).
•  » » » » 14 months ago, # ^ |   +1 I solved it using the following state: Let j = 0/1 where 1 means we flip the current row Let k = 0/1 where 1 means we flip the next row dp[i][j][k] = the min cost s.t. the rows i is in state j and the i+1 th row will be in state k (so the cost is not considered for the i+1th row yet). The rationale behind this state is that at the jth row is dependent on whether the i-1th row is flipped and whether the i+1th row must be flip, and depending whether the next row can be both flip/unflip, flip only, unflip only, we update the state.The ans would be min(dp[H-1][0][0], dp[H-1][1][0]).
 » 14 months ago, # |   +8 In F.I just moved $j$ backward from $i - 1$ to $0$ and did ans[i] = min(ans[i], abs(i - j) + abs(a[i] - a[j])); and broke out of inner loop when if (abs(i - j) - 1 >= ans[i]) and did similarly for $j$ from $i + 1$ to $n$.https://atcoder.jp/contests/abc283/submissions/37510713Is this intended?
•  » » 14 months ago, # ^ |   0 I wasn't expecting this easy solution to this problem.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 I have the similar solution, The test cases are so weak.I'm curious if this solution can be hacked?https://atcoder.jp/contests/abc283/submissions/37522936
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 del
•  » » » » 14 months ago, # ^ |   0 why is it passing :?
•  » » » » 14 months ago, # ^ |   0 It is not n*n but n*sqrt(n) which should be ok. The terminating condition in inner loop uses x which is continuously getting minimized and for these type of solutions for this question we can generate tc which will give n*sqrt(n) time complexity. This solution is somewhat like mentioned here
•  » » » » » 14 months ago, # ^ |   0 Why is the time complexity becoming O(n*sqrt(n))?
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   +3 It is not n*n but n*sqrt(n) True, good find! What's more: we can prove that Spoilersum(ans[i])<=(3+eps)*n*sqrt(n)=O(n*sqrt(n)), sketch of the proof: SpoilerFor simplicity consider that n=K*K, split K*K elements into K groups of K elements consider the contribution of the first group[1:K]==ans[Pinv[1]]+ans[Pinv[2]]+...+ans[Pinv[K]] (it's <=3*K*K), similarly for the other groups.Hint: consider the positions Pinv[1], Pinv[2],...,Pinv[K], what happens if we sort these, and how we can construct (something), where 3*K*K>=something>=ans[Pinv[1]]+ans[Pinv[2]]+...+ans[Pinv[K]]For general case we can find K, such that K*K<=N<(K+1)*(K+1), so N<=K*K+2*K, so at most 2 extra groups of size K with contribution<=2*(3*K*K)=o(K*K*K)
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 I read codes from SSRS, and I think the intended solution is based on segment tree. To compute t=abs(pi-pj)+abs(i-j) for some i, there are several cases.case1: jpi, then t=pj-pi+i-j=i-pi-(j-pj), and min(t)=max(j-pj), which could be solved by a query of maximum value in the interval of [pi+1, n]. Then, we update index of pi, with value of i-pi. for j>i, the idea is similar.Well, my first idea is to transform it into a geometry problem, which is related to manhattan distance, but failed getting a solution.
•  » » » 14 months ago, # ^ |   0 Yep, this is what I did. I think this is the intended solution.
•  » » » 14 months ago, # ^ |   0 Well could u please explain why u have to update the tree SummerSky
•  » » » » 14 months ago, # ^ |   0 Well, I think the solution is to compute di from i=1 to i=n. Thus, when we are computing di, we need some intermediate results from 1 to i-1, while computing d_(i+1), we would need results from 1 to i. This is done in a sequential order, and thus we have to repeat the following steps: compute di according to results of [1, i-1], then update i; compute d_(i+1) according to [1, i], and update i+1
•  » » 14 months ago, # ^ |   0 I think the worst-case scenario in your solution will go O(n*sqrt(n)), although a nlogn solution is possible but given the constraint of the problem, your solution should be acceptable.
 » 14 months ago, # |   +13 can anyone please provide some tricky test case for problem E?
 » 14 months ago, # |   +2 Is it rated still?
•  » » 14 months ago, # ^ | ← Rev. 6 →   0 why not?
•  » » » 14 months ago, # ^ |   0 problem D had some issues :((
•  » » » » 14 months ago, # ^ |   -10 what kind of issues?I think problem statement was bad, but it's not a reason to make the round unrated
 » 14 months ago, # |   0 ACed E after contest because I mistyped = as ==, pain
 » 14 months ago, # | ← Rev. 2 →   0 Is it rated or not?
 » 14 months ago, # | ← Rev. 2 →   +10 G is almost the same as problem 4 from this blog.
 » 14 months ago, # |   0 Please share the testcases of D.
 » 14 months ago, # | ← Rev. 2 →   +11 Problem E had weak system tests. For example, my accepted solution gives wrong answer on this test: 3 5 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 
 » 14 months ago, # |   0 My solution to D was a bit simpler than the editorial. SolutionThe only letters that will be in the box when you encounter a closing parentheses are ones between it and the previous closing parentheses, because any others will have been removed by the time Takahashi reaches that point in the string. So you can just have a boolean array of letters in the box, check if a duplicate ever enters it, and clear it when you see a closing parentheses. Opening parentheses can be ignored entirely. Submission
•  » » 14 months ago, # ^ |   -8 Editorial where?
 » 14 months ago, # | ← Rev. 2 →   0 Maybe this contest is not rated anymore ? I noticed that there has been no rating update. Typically AtCoder does this shortly after a contest is over.
•  » » 14 months ago, # ^ |   +21 From clarification: There was a constraint violation in the test case for the problem D. The number of ‘)’ is less than the number of ‘(’ in some test cases. We are currently discussing whether this contest will be rated. Sorry for the issue.
•  » » » 14 months ago, # ^ |   0 so this contest is rated or not?
•  » » » » 14 months ago, # ^ |   0 I think it is rated for most participants except these https://img.atcoder.jp/abc283/list.txtI saw this just got posted on AtCoder's official twitter account.
 » 14 months ago, # |   +50 Update: For the following 246 participants, ABC283 is Unrated. We are sorry. (This includes those who were originally Unrated.)The others will be Rated. Please wait a little longer for the update.Please contact us if you find anything wrong. Unrated list: https://img.atcoder.jp/abc283/list.txtOriginal tweet: https://twitter.com/atcoder/status/1606681898268655618
 » 14 months ago, # |   -8 Cool contest, thanks!
 » 14 months ago, # |   0 Is it possible to solve E using 2-SAT?