We will hold UNIQUE VISION Programming Contest 2022 Winter(AtCoder Beginner Contest 283).
- Contest URL: https://atcoder.jp/contests/abc283
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20221224T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: cn449, MMNMM, yuto1115, m_99, nok0
- Tester: math957963, nok0
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!
UNIQUE VISION rounds can always surprise me.
Looking forward to the contest in the evening!
Merry Christmas!
How to do problem E?
Try to use dp.
Will iterative dp work for this problem ? If yes, then please share the solution (anyone who solved).
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]fromd[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 buildingd[2][..]you cannot flip line0. Also, when buildingd[n+1][..]you don't want to flip linen+1.It helps to border the matrix.
ans = min(d[n+1][conf] | 0 <= conf < 4).Solution.
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]).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 whenif (abs(i - j) - 1 >= ans[i])and did similarly for $$$j$$$ from $$$i + 1$$$ to $$$n$$$.https://atcoder.jp/contests/abc283/submissions/37510713
Is this intended?
I wasn't expecting this easy solution to this problem.
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
del
why is it passing :?
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
Why is the time complexity becoming O(n*sqrt(n))?
True, good find! What's more: we can prove that
sum(ans[i])<=(3+eps)*n*sqrt(n)=O(n*sqrt(n)), sketch of the proof:
For 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)
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: j<i, and pj<pi, then t=pi-pj+i-j=pi+i-(pj+j), so pi+i is constant and min(t) is equivalent to max(pj+j), which could be solved by a query of maximum value in the interval of [1, pi-1]. Then, we update index of pi, with value of pi+i
case2: j<i, and pj>pi, 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.
Yep, this is what I did. I think this is the intended solution.
Well could u please explain why u have to update the tree SummerSky
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
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.
can anyone please provide some tricky test case for problem E?
Is it rated still?
why not?
problem D had some issues :((
what kind of issues?
I think problem statement was bad, but it's not a reason to make the round unrated
ACed E after contest because I mistyped
=as==, painIs it rated or not?
G is almost the same as problem 4 from this blog.
Please share the testcases of D.
Problem E had weak system tests. For example, my accepted solution gives wrong answer on this test:
My solution to D was a bit simpler than the editorial.
The 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
Editorial where?
The Japanese one.
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.
From clarification:
Sorry for the issue.
so this contest is rated or not?
I think it is rated for most participants except these https://img.atcoder.jp/abc283/list.txt
I saw this just got posted on AtCoder's official twitter account.
Update:
Unrated list: https://img.atcoder.jp/abc283/list.txt
Original tweet: https://twitter.com/atcoder/status/1606681898268655618
Cool contest, thanks!
Is it possible to solve E using 2-SAT?