maroonrk's blog

AtCoder Regular Contest 179 Announcement
By maroonrk, history, 3 weeks 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

»
3 weeks 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
  • »
    »
    3 weeks 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
»
3 weeks 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
»
3 weeks 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
»
3 weeks 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
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

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

    Overflow (intermediate sum > R).

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

    Thanks. I also did same mistake :).

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

Could anybody tell me how to do problem D?

→ Reply
»
2 weeks 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