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

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

Edit: Found the mistake now.

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

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

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

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?

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.

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

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

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.

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.

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

Could anybody tell me how to do problem D?

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

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