chokudai's blog

UNIQUE VISION Programming Contest 2022 Winter(AtCoder Beginner Contest 283) Announcement
By chokudai, history, 16 months ago, In English

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!

  • Vote: I like it
  • +19
  • Vote: I do not like it

Comments Comments (38)
| Write comment?
»
16 months ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

UNIQUE VISION rounds can always surprise me.

Looking forward to the contest in the evening!

Merry Christmas!

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do problem E?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try to use dp.

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Will iterative dp work for this problem ? If yes, then please share the solution (anyone who solved).

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

        Solution.

        → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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]).

        → Reply
»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

Is this intended?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wasn't expecting this easy solution to this problem.

    → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      del

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        why is it passing :?

        → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          16 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why is the time complexity becoming O(n*sqrt(n))?

          → Reply
        • »
          »
          »
          »
          »
          16 months ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          It is not n*n but n*sqrt(n)

          True, good find! What's more: we can prove that

          Spoiler
          → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yep, this is what I did. I think this is the intended solution.

      → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well could u please explain why u have to update the tree SummerSky

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
16 months ago, # |
  Vote: I like it +13 Vote: I do not like it

can anyone please provide some tricky test case for problem E?

→ Reply
»
16 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Is it rated still?

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

ACed E after contest because I mistyped = as ==, pain

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is it rated or not?

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

G is almost the same as problem 4 from this blog.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please share the testcases of D.

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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
→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution to D was a bit simpler than the editorial.

Solution
→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.

    → Reply
»
16 months ago, # |
  Vote: I like it +50 Vote: I do not like it

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

Original tweet: https://twitter.com/atcoder/status/1606681898268655618

→ Reply
»
16 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Cool contest, thanks!

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve E using 2-SAT?

→ Reply