maroonrk's blog

AtCoder Regular Contest 126 Announcement
By maroonrk, history, 3 years ago, In English

We will hold AtCoder Regular Contest 126. Please note the unusual start time (1 hour later than usual)

The point values will be 300-400-600-600-800-1100.

We are looking forward to your participation!

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

Comments Comments (36)
| Write comment?
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The start time of ARC is the same as the end time of Opencup. Can it be delayed by 15 mins or so.

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

    I tried to avoid the clash with Opencups but I didn't want ARCs to be too late in Japan, so that's the reason for the tight schedule. Though I can't change the contest time now, perhaps I'll have a margin of 5 mins next time, if not 15mins.

    → Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

LimitCoder

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Problem C is the same as this, but with harder limits.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -52 Vote: I do not like it

Nice problems in this contest.

I didn't solve any problems during the contest, but I solved C using Binary Search just a minute after the contest ended.

My submission is here.

Here's my stream that was private/unlisted during the contest.

→ Reply
»
3 years ago, # |
  Vote: I like it -68 Vote: I do not like it

This is really irritating. I think that problem A was a generic ILP problem, but normally there are big math applications or libraries, which take care of it without any need to bother about what is happening under the hood. During the whole contest time I tried to find any usable code snippet or small library suitable for competitive programming environment, but failed.

Here's my broken submission, which tried to use using Simplex Algorithm.cpp code from YouKn0wWho's (The Ultimate) Code Library. But it's LP and I couldn't figure out how to modify it to get an integer solution. Or made some other embarrassing mistake. Was I on a wrong track all along?

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

    This is Atcoder and problem A so the solution would most likely be greedy.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -24 Vote: I do not like it

      This is Atcoder and problem A so the solution would most likely be greedy.

      Many problems can be solved in different ways. And I don't see what's wrong with overkilling a simple problem with a more advanced algorithm. Considering the total absence of any useful responses and all the downvotes, my conclusion is that there's no appreciation for Linear Programming in the competitive programming community. And this is a bit sad, because LP is reasonably useful in the real world.

      LP is effective at solving problems of this kind even if the number of variables and constraints is large. It also does the job when greedy algorithms fail. This is similar to how the classic "minimum coin change" problem can be sometimes solved by a greedy algorithm, but sometimes something more advanced (such as DP) is required.

      May I ask you something? How would you approach the same problem A — Make 10 if it was required to create sticks whose lengths were exactly 13 instead of 10? Also if a provable exact solution was too difficult, then being off by up to something like +-5 was also acceptable (we are dealing with up to $$$10^{15}$$$ sticks and a super accurate precision is rarely needed at this scale).

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

    May you provide which line contains your objective function? (or something related to that)

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

      The objective function is configured by these two lines in my code:

      Spoiler

      The used Simplex Algorithm code template contains the following comment:

      Maximize or minimize f0*x0 + f1*x1 + f2*x2 + ... + fn-1*xn-1 subject to some constraints.

      In this particular case, the objective function is just $$$f(x) = x_0 + x_1 + x_2 + x_3 + x_4$$$ and all the $$$f_i$$$ constants are equal to 1. The variables are:

      • $$$x_0$$$ is the number of 2+2+2+4 sticks
      • $$$x_1$$$ is the number of 3+3+4 sticks
      • $$$x_2$$$ is the number of 2+2+2+2+2 sticks
      • $$$x_3$$$ is the number of 2+2+3+3 sticks
      • $$$x_4$$$ is the number of 2+4+4 sticks

      GNU MathProg model can be used to test or prototype the solution and various online sites can process it:

      Spoiler

      I have pushed a corrected summission to AtCoder and now it got an AC verdict. I have also added a lot of comments there, hopefully explaining everything. But feel free to ask more questions if anything is not clear.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Prob B couldn't be solved by using binary search LIS?

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

    here is my solution of Prob B, it is different like my old binary search before $$$O(n\log n)$$$.

    In code,my thoughts are finding the non-decreasing subsequence,but in fact I am looking for strictly ascending subsequence. and then is pass.

    This maybe help you

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

      I aleady found how to solve using binary search. But thank you for your reply :)

      → Reply
»
3 years ago, # |
  Vote: I like it +99 Vote: I do not like it

Can I already say that rainboy will win next IOI?

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

    I am wondering what would be his real rating if he do all the problems that he can in each contest!

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Got a solution like $$$O(N2^KKlog2(K))$$$ for D but too bad I couldn't squeeze it into the limit :(

→ Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Task A can also be solved using brute force

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

    Nice idea.

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

    Can't A be solved in $$$\mathcal O(1)$$$?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it +33 Vote: I do not like it

      Yes, but i was not sure of some particular way better than the other. So i just brute forced over different possible configurations. I observed that there are only 5 possible ways to get 10 from given set of sticks . So i created a vector containing these ways , and permuted over different possible orders where each order corresponds to priority of getting 10 using a particular way from left to right. So it takes 5.5! operations for each case

      Here is my submission : https://atcoder.jp/contests/arc126/submissions/26014537

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

        That's pretty cool. I had a hard time deciding which of (4, 4, 2) and (3, 3, 2, 2) should be picked first and it eventually costed me more time than B or C did.

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

        Can you please explain more how your solution works

        → Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

B was really nice. My solution is a bit different to the editorial.

Solution
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

...

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

I don't see any change in my rating for this contest. When will be the rating change available?

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

please explain anyone, problem D — Pure Straight

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +16 Vote: I do not like it

    I can explain a different solution that works in $$$O(2^KNK)$$$. Let us call the sequence $$$1,2,\cdots, K$$$ a "good sequence". If I choose $$$K$$$ different numbers at indices $$$x_1 < x_2 < \cdots < x_K$$$, I want to create a good sequence starting at $$$i$$$. Then, the optimal way of doing this can be thought of as performing two steps:

    1. "Compressing" the indices $$$x_1, x_2, \cdots, x_K$$$ into the indices $$$i,i+1,\cdots, i+K-1$$$ by the means of adjacent swaps, while preserving the order. So if I start with $$$2,*,*,1,*$$$ and I want to make the good sequence start at $$$i=2$$$, I would make the sequence $$$*,2,1,*,*$$$. The cost of doing this is clearly $$$\sum_{k=1}^K |x_k - (i+k-1)|$$$.
    2. Once I do this, I need to sort the sequence. The minimum number of adjacent swaps to do this is the inversion count, i.e. $$$inv(a_{x_1},a_{x_2}, \cdots, a_{x_k})$$$.

    This gives us the same cost from the editorial. My goal is to find the minimum cost of having a good sequence starting at any $$$i \in [1,n]$$$. To do this, I want to use DP, but the roadblock here is that I'd need to consider numbers coming from both the left and the right of $$$i$$$. Instead, I'll split this into two parts — the prefix and the suffix. Let $$$dp_{pr}[i][S]$$$ be the cost of getting a contiguous sorted sequence of numbers in $$$S$$$, such that all the numbers are from indices $$$\leq i$$$, ending at $$$i$$$. Similiarly, let $$$dp_{su}[i][S]$$$ be the cost of getting a contiguous sorted sequence of numbers in the set $$$S$$$, such that all the numbers are from indices $$$\geq i$$$, starting at $$$i$$$. Then, we can get the cost of a good sequence starting at $$$i-|S|$$$ from the formula:

    $$$ f(i,S) = dp_{pr}[i][S] + dp_{su}[i+1][[k] \setminus S] + inv(S,[k] \setminus S) $$$

    where $$$[k]$$$ is the set of the first $$$k$$$ natural numbers. $$$dp_{pr}[i][S]$$$ will cover the cost of "compressing" the prefix as well the inversion count within the prefix, $$$dp_{su}[i][[k] \setminus S]$$$ will cover the cost of doing this for the suffix, and $$$inv(S,[k] \setminus S)$$$ will cover the inversion count across the prefix and suffix. Hence, the minimal cost would be the minimum of $$$f(i,S)$$$ over all $$$i$$$ and $$$S \subseteq [k]$$$.

    We can find the DPs in $$$O(2^KNK)$$$ and $$$inv$$$ in $$$O(1)$$$ after $$$O(K2^K)$$$ precalculation. The transitions are fairly trivial, you can see them in my submission.

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

F is very interesting. Thanks for the contest

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

Is $$$O(Max(a)log^2(Max(a)))$$$ intended to give TLE. Or Am I doing something strange in C?

Spoiler

I am using the fact that $$$j mod i = j - (j // i) * i$$$

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem B , why Do we sort like this ?

 sort(segs.begin(), segs.end(), [&](auto x, auto y) {
    return x.first < y.first || (x.first == y.first && x.second < y.second);
  });
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If the first element of two pairs are equal, we can choose at most one of them. So we have to sort them somehow that doesnt conflict with the LIS part. Now the best way is to let the one with larger second element, come first

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B is similar to https://leetcode.com/problems/russian-doll-envelopes/ (with larger constraints)

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

Here is my solution to problem C, which is $$$O(N\sqrt {A_i})$$$.

Let $$$g(m)=\sum\limits_{i=1}^N \lceil \frac{A_i}{m} \rceil$$$

We wish to find the largest $$$m$$$ such that $$$mg(m) \le K+\sum\limits_{i=1}^N A_i$$$

We know for all $$$m>\max A_i, g(m)=N$$$

The idea is that we can compute $$$g(m-1)-g(m)$$$ for all $$$m\ge \sqrt{\max A_i}$$$ in $$$O(N \sqrt{A_i})$$$ time and $$$O(N)$$$ space. Note $$$\lceil \frac{A_i}{m} \rceil - \lceil \frac{A_i}{m+1} \rceil $$$ is either 0 or 1

To find $$$m$$$ st $$$\lceil \frac{A_i}{m} \rceil = t, \lceil \frac{A_i}{m+1} \rceil = t-1$$$ in O(1) is left as an exercise to the reader.

We can find all $$$m$$$ such that above holds in $$$O(\sqrt{A_i})$$$. Doing this $$$N$$$ times, we check $$$O(N\sqrt{A_i})$$$. We store results using a sparse/occurrence array. This actually stores $$$g(m)-g(m+1)$$$ for all $$$m>\sqrt{A_i}$$$ so we can compute $$$g(m)$$$ for $$$m<\sqrt{A_i}$$$ and $$$m>\sqrt{A_i}$$$ in $$$O(\sqrt{A_i}N)$$$, which works. My implementation

→ Reply