Блог пользователя maroonrk

Автор maroonrk, история, 5 месяцев назад, По-английски

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!

  • Проголосовать: нравится
  • +86
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
5 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

Edit: Found the mistake now.

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
5 месяцев назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

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.

»
5 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

$$$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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

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.

»
5 месяцев назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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.

»
5 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could anybody tell me how to do problem D?

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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