We will hold AtCoder Regular Contest 179.

- Contest URL: https://atcoder.jp/contests/arc179
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240602T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: noya2
- Tester: maspy, potato167
- Rated range: — 2799

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

We are looking forward to your participation!

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

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

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

maybe query an already deleted element is illegal.

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

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

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

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

B is a dp more than a combination.

Cap. There's no one in the ranklist who solved exactly A, C and D.

I checked the same. How can someone solve D but not B

sounded sus from the start!!

maybe he solved after contest idk , but still solving A C D suggests high skill

I got D after contest

you solved A C D? You should be atleast master then , why are you blue?

Think why?

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

I got 7 WAs. Changed my approach to this:

This gets AC. Why does the first approach fail?

Overflow (intermediate sum > R).

How? Combining symmetrically about the center ensures no overflow.

It is not true :)

You shall pick first and last elements to guarantee no overflow

Consider $$$A=-4,2,3,3$$$, and $$$R=4$$$.

Ugh got it 😓 thanks

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.

Thanks. I also did same mistake :).

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

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

Can you explain how you solved it?

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

The problem is line 43 in your comparator class.

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

SpoilerIf you count the queries and assert that you make at most 25000, you will get 11 Runtime Error instead of 11 Wrong answer: https://atcoder.jp/contests/arc179/submissions/54253354.

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.

Understood, thanks for the answer

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