chokudai's blog

UNIQUE VISION Programming Contest 2022 Winter(AtCoder Beginner Contest 283) Announcement
By chokudai, history, 3 years 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?
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to do problem E?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Try to use dp.

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
        ← 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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    3 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      3 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      del

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        why is it passing :?

        → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

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

          → Reply
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
          ← 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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Is it rated still?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Is it rated or not?

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Please share the testcases of D.

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

Solution
→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

Cool contest, thanks!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is it possible to solve E using 2-SAT?

→ Reply