maroonrk's blog

AtCoder Regular Contest 179 Announcement
By maroonrk, history, 6 months ago, In English

We will hold AtCoder Regular Contest 179.

The point values will be 300-500-500-700-800-1000.

We are looking forward to your participation!

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does my problem C submission TLEs ? I submitted with and without flush , still it TLEs. link https://atcoder.jp/contests/arc179/submissions/54181883

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

    You don't read index of new number after addition. I had the same problem.

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

Why does my submission on problem C has WA on three cases. https://atcoder.jp/contests/arc179/submissions/54182351

Edit: Found the mistake now.

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

I used set in problem C but got wa in most cases, why can't my set perform correctly?

https://atcoder.jp/contests/arc179/submissions/54182683

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

Could somebody please take a look at my C? It's not even passing sample, but seems fine when I tested it locally:

https://atcoder.jp/contests/arc179/submissions/54180675

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

    You should swap line 67 and line 68 of your code.

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

      It worked, thank you so much! Must be UB that makes it work locally but not on the judge.

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

How to get improve in combination problems, in today's ARC I solved A, C, D(after contest) but unable to solve B :( any suggestions and resources are sooo helpful

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

Initially I was doing this in task C, but it fails in 3 cases out of 83:

While size(A) > 1:
   1) sort A using mergesort (NlogN compares)
   2) combine indices i and N-i for all i < N/2

I got 7 WAs. Changed my approach to this:

Sort A using mergesort
While size(A) > 1:
   1) combine A[1] and A[N]. 
   2) insert the new index at correct position using BS

This gets AC. Why does the first approach fail?

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

    Overflow (intermediate sum > R).

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

    I think first approach fails here

    nums: -10 6 7 8

    R: 11

    according to first method it will combine 6 and 7, which gives 13>R.

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

    Thanks. I also did same mistake :).

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

    May be this test case? N=6 , R=10 -9 -9 7 8 9 9

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

I am getting WA in 1 test case and TLE in 2. Looks like some edge case is not handled. Can someone take a look https://atcoder.jp/contests/arc179/submissions/54181150.

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

$$$B$$$ is a great DP problem , it's a shame that I couldn't solve it during contest by not being quick enough to debug but solved after the contest

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

The problems are quite interesting. I passed A, B and C and got a positive delta! Wish to solve D next time.

→ Reply
»
6 months ago, # |
← Rev. 4   Vote: I like it +6 Vote: I do not like it

Could somebody pls take a look at my C's submission ? It's getting WA on only one test case. Thanks! https://atcoder.jp/contests/arc179/submissions/54176831.

UPD: Found it, my l for binary search should be 0 not 1 :( , I have no idea how did this get accepted on 82 test cases.

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

A simpler solution for problem E that doesn't require graphs:

Let's say we merge using $$$h$$$ if the $$$h$$$ dimension of the two rectangles are the same and we make a new rectangle overlapping these two edges.

Consider places where we "switch" between the two dimensions when we merge (those $$$i$$$ where we merge $$$i-1$$$ and $$$i$$$ using $$$h$$$, but merge $$$i$$$ and $$$i+1$$$ using $$$w$$$, or the other way round). WLOG, suppose that we merge $$$i-1$$$ and $$$i$$$ using $$$h$$$, then it's easy to see that $$$h_{i-1}=h_i$$$ and $$$w_i=w_{i+1}$$$.

We can observe that whatever we do before $$$i$$$, the rectangle that is being merged into $$$i+1$$$ is always $$$(h_i,w_{i+1})$$$. Therefore, we denote $$$g_{i,0/1}$$$ which means the maximum place we can reach if we start with $$$(h_i,w_{i+1})$$$ or $$$(h_{i+1},w_i)$$$ and start merging from rectangle $$$i$$$.

In order to get the value of $$$g$$$, we can simply find the next place where we have to switch, and from the place on, we can use the $$$g$$$ we have already calculated to get the answer. This place can be found easily using binary search.

There is only one exception, where we can use both dimensions to make a move. However, in this case, the rectangle we currently have and the next one must be exactly the same. Therefore we can simply denote $$$f_i$$$ meaning the answer if we start with $$$(h_i,w_i)$$$ and merge from $$$i$$$. The way to find $$$f$$$ is similar to $$$g$$$, and so is the way to find the actual answer.

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

Why does my submission on problem C has WA? https://atcoder.jp/contests/arc179/submissions/54188277

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

    The problem is line 43 in your comparator class.

    Spoiler

    If you know that "a is not less than b" you can not conclude that "b is less than a", because they might be equal. You can fix this by removing line 43 and making S a multiset because it can contain multiple elements with the same key. Also you need to be careful now when erasing elements from S. Now you still have 11 Wrong Answer: https://atcoder.jp/contests/arc179/submissions/54253178. This is because you make too many queries.

    Spoiler

    Apparently the constant factor of set is too high for this problem. I testet it locally and found that the highest number of queries is 28754, so it just barely is not enough.

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

Could anybody tell me how to do problem D?

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

here is the 630b code of problem C with lots of STLs

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

Seems my solution for E is different from the editorial, so I'm just leave it here:

Consider looping $$$j$$$ from $$$1$$$ to $$$n$$$ and for each $$$i \le j$$$, maintain all possible rectangle generated from subarray $$$[i, j]$$$, for convenience, assume each such rectangle $$$(h, w)$$$ is a point on a 2D plane.

Observe after doing $$$j$$$-th operation, all possible result rectangle have either height $$$h_j$$$ or width $$$w_j$$$, so all the points we want to maintain is on $$$x = h_j$$$ or $$$y = w_j$$$, let's consider using two set to maintain points on $$$x = h_j$$$ and $$$y = w_j$$$.

Then when we want to increase $$$j$$$ to $$$j + 1$$$, only rectangle with height $$$h_{j + 1}$$$ or width $$$w_{j + 1}$$$ can be further concatenated, so we eliminate everything doesn't lies on $$$x = h_{j + 1}$$$ or $$$y = w_{j + 1}$$$, which takes $$$O(n)$$$ amortized time.

Then concatenate $$$j$$$-th rectangle with previous result correspond to shift all points on $$$x = h_{j + 1}$$$ to the positive axis of $$$y$$$ by $$$w_{j + 1}$$$ unit, or shift all points on $$$y = w_{j + 1}$$$ to the positive axis of $$$x$$$ by $$$h_{j + 1}$$$ unit, which can be done in $$$O(1)$$$ by adding a tag on the set.

Finally don't forget to add rectangle formed by subarray $$$[j + 1, j + 1]$$$, then add (the number of different $$$i$$$ such that rectangle formed by $$$[i, j + 1]$$$ is in the set) to the answer.

my implementation: https://atcoder.jp/contests/arc179/submissions/54871393

→ Reply