maroonrk's blog

Tokio Marine & Nichido Fire Insurance Programming Contest 2021（AtCoder Regular Contest 122) Announcement
By maroonrk, history, 4 years ago, In English

We will hold Tokio Marine & Nichido Fire Insurance Programming Contest 2021（AtCoder Regular Contest 122).

The point values will be 400-500-600-700-800-1200.

We are looking forward to your participation!

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

Comments Comments (67)
| Write comment?
»
4 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Reminder that contest starts in 5 minutes

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

Reminder that contest starts in 4 minutes

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

Reminder that contest starts in 3 minutes

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

Reminder that contest starts in 1 minute.

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

Reminder that contest starts in 10 seconds

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

it's been 45 min and I have done NOTHING.

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

F*ckin' precision errors >:O

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

I used to treat ARCs as Div. 2 contests.

I was wrong.

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

Can we solve Problem B — Insurance , when the scenarios don't happen with equal probability?

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

    I think the solution will be pretty much the same.

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

    It would be exactly the same, but when you are computing the expected value you multiply by the probability, not by $$$1/n$$$.

    In this code, in function f you can just replace E += p * v; with E += p[i] * v;.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

C had a cancer implementation.

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

    My (unproven) solution is quite easy to implement. Just apply Euclidean algorithm with pairs $$$(n, b)$$$ such that $$$b$$$ is close to $$$n / \varphi$$$, until you find a solution with less than $$$130$$$ operations.

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

      what is n/φ and how did you arrive at this conclusion?

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

        $$$\varphi = (1 + \sqrt 5) / 2$$$. The last operations (of type $$$3$$$ and $$$4$$$) are executed only once (alternately) for each side, so $$$a, b$$$ grow "fast". The only bottleneck is that there may be many initial operations of type $$$1$$$ and $$$2$$$ (because of the error propagation of $$$b - n / \varphi$$$), but the total operations are about $$$200$$$ on average with a very high deviation.

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

      that was my first solution, then I couldn't find a way to get it down below 150 moves.

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

        For which input did your code reach $$$150$$$ moves?

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

          1e18 gave exactly 150 moves (for my initial code)

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

            b = 618033988749894686 works in 106 moves.
            b = 618033988749894689 works in 127 moves.
            b = 618033988749894693 works in 119 moves.

            The density of $$$b$$$ that work seems quite high.

            UPD: actually it's not necessary to choose $$$b \approx n / \varphi$$$, just using a random $$$b$$$ seems to work.

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

Problem D: Try and fail to write the solution by yourself. Remember there's a XOR MST problem in codeforces, google it and copy a solution from there

https://codeforces.net/contest/888/submission/32165432

https://atcoder.jp/contests/arc122/submissions/23373118 ;)

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

    I don't get the relationship between today's problem and MST. Is "the graph with edges $$$\leq x$$$ is connected" equivalent to "Bob can get a score $$$\leq x$$$"? (Why?)

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

      It isn't. We take only the edges that merge components of not both even size. Think about how things work in a trie, if you have both subtrees of even size then you'll solve the subtrees independently otherwise there'll be one number going to the other subtree and that'll dominate everything.

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

How To Lose Rating

  1. search on Google "pair with min xor"
  2. find this solution on gfg: "sort the given array, traverse and check xor for every consecutive pair"
  3. get wa
  4. debug the solution for $$$30$$$ minutes
  5. $$$2$$$ minutes to the end, realize that the solution in 2) can't be generalized if you want to find $$$\min(a_i \oplus b_j)$$$ (i.e. using, for each $$$a_i$$$, lower_bound() and upper_bound() to find the closest elements in $$$b$$$ doesn't work)
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to prove that the function in B is convex? I can't get it?

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

    There should've been a red alert going in your head when you tried the first step and realised you don't have a given array, but 2 given arrays.

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

      My thinking flow

      • ok, wait, we have 2 arrays
      • oh nvm, I can just do upper_bound() and it works
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Same by sorting the two given arrays and get WA. Luckily I came up with a counterexample soon and implement Trie after that.

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

          Can you share that counter-example? I got WA using that too lol

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

            For example if $$$a=[3],b=[4,7]$$$, by only checking consecutive pairs you get the answer $$$7$$$, but the real answer is $$$4$$$.

            I haven't come up with counter-example for upper_bound ones yet :P

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

        That takes an array as argument. Which array and why not the other way around? Hmm.

        It's why I want to at least intuitively understand the algorithms I copy. If I get wrong results, might as well throw it away and start over otherwise.

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

how to solve C?

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

    https://atcoder.jp/contests/arc122/editorial/2071

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

      Its a very nonintuitive way (atleast for me) , if you have solved it , can you tell me your intuition or how u solved it.

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

        I didn't solve it :P

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

        While exploring the possible solutions, I've decided to see what happens in some easy scenarios. One of those scenarios was to start from $$$x=1$$$, $$$y=0$$$ and then do operations $$$x=x+y$$$ and $$$y=x+y$$$ alternatively. I've noticed that in this case $$$x$$$ and $$$y$$$ after some steps are always Fibonacci numbers, so we need just to represent $$$N$$$ as a sum of Fibonacci numbers.

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

I used Fibonacci triangle rows in A

https://oeis.org/A144154

https://atcoder.jp/contests/arc122/submissions/23371678

With so many solves probably not the intended solution, but I was happy to have found the relation

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

    can you please explain the theory?is it pascal triangle?

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

      I drew some small examples of how many + and — we can have at each position. For example with 4 signs we have:

      • 5 6 6 5
      • 3 2 2 3

      for 5 signs:

      • 8 10 9 10 8
      • 5 3 4 3 5

      Assuming the 1st and last columns always contain fibonacci pairs, how to generate the ones in between? Well at each step each of the — factors will turn into + on the next turn since we cannot have two consecutive -, and also we can notice from drawing smaller examples that the number of + factors also break into fibonacci pairs — 8+ breaks into 5+ 3-, 5+ breaks into 3+ and 2- and so on.

      Then we can see in the above example 8/5, the second column is generated as

      8+ breaking into 5+ and 3-, and 5- turning into 5+

      therefore second column contains 2*5 + and 1*3 -

      similar transition happens for the next column, 2*5+ breaks into 2*3+ and 2*2-

      and 1*3- turns into 1*3+, combined that is 3*3+ and 2*2-

      and we can generalize to

      1*8 2*5 3*3 5*2 8*1

      1*5 1*3 2*2 3*1 5*1

      which are also fibonacci numbers!

      So in my solution I generate these two rows, compute each index's coefficient and add it to my result.

      This "linearity" type solution is used in the video https://codeforces.net/blog/entry/91672?#comment-803151

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

I wish I had more clarity of mind while implementing problems like C :D

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

Can someone please explain me the the implementation of dp in problem A?

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

Managed to solve C only after the contest :(

Here's my Randomised solution:

https://atcoder.jp/contests/arc122/submissions/23376359

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

When you realize, for E, that arbitrarily choosing the last element satisfying the condition works, and you spent last half hour thinking how to select last element if multiple element satisfies condition.

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

I implemented a different solution for B than the one in the official editorial. Hopefully it will prove interesting for some:

We should find minimum after x and y for: (n * x + PS[n] - PS[y] - 2 * x * (n - y)) / n, where PS[i] is the sum of the first i elements of the sorted input array. Basically, y is an index such that all elements 1 <= i <= y will provide min(A[i], 2x) = A[i] and all elements y < i <= n will provide min(A[i], 2x) = 2x. This also suggests a constraint for a fixed y: V[y] / 2 <= x <= V[y + 1] / 2.

Minimizing the formula above is the same as minimizing: n * x - PS[y] - 2 * x * (n - y) = x * (2 * y - n) - PS[y]. In order to minimize this, we can iterate 1 <= y <= n and find a suitable x. In fact, if 2 * y - n is negative, x should be as large as possible, so x = V[y + 1] / 2. Otherwise (2 * y - n is positive), than x should be as small as possible, so x = V[y] / 2.

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

    can you give a link to your submitted solution?

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

Screencast with commentary

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

How much can we rate A in terms of CF ratings ?

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

In B, I first wrote a binary search, but the ans was increasing with decreasing precision. I think, the side it was going was not correct when precision was small and numbers were large. But, ternary search was consistent on this. Can someone clarify more on this?

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

    I did it using binary search on the x Solution. The loss vs x function is initially non-increasing and then non-decreasing, so we'll have to find x corresponding to the trough in the loss function [Start with low = 0 and high = max(Ai), then check the losses for mid, mid-1, mid+1 to half the search space]

    Later checked the editorial, turns out this is just equivalent to finding the median.

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

      I was checking on mid and mid + e(the error term), I think that caused the issue

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

For problem B my solution tries to perform binary search to find when the derivative flips from negative to positive.

$$$f(x) = \sum\limits_{i=1}^N (x + A_{i} - min(A_{i}, 2x)) = \sum\limits_{i=1}^N (x + A_{i} - \frac{Ai + 2x - abs(A_i - 2x)}{2})$$$

$$$f'(x) = \sum\limits_{i=1}^N \frac{2x - A_i}{abs(2x - Ai)}$$$

Points where we get NaNs because of division by zero are skipped.

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

    Thanks.
    This just proves that median observation in editorial since that function is sum of signum functions derivate will change sign at median only.

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

    Nice observation! That way to write $$$min(a,b)$$$ is very clever.

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

ARC E -
If one didnt realises second observation in E. Then $$$LCM_{j \neq i}(A_j)$$$ can be computed in $$$O(n \log max(A_i))$$$ using prefix and suffix LCMs with bigints.
Python Submission
Time complexity $$$O(n^3 \log max(A_i))$$$ remains same.

More specifically how did I come up with this particular solution was -
Since there exists one last no from index $$$i$$$ such that $$$LCM_{j \neq i}(A_j) \neq LCM_{j}(A_j)$$$. This python solution just brute forces to find one such index which can be last. Then recursively solves for the rest of $$$n-1$$$ numbers.

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

In D I thought it was ok to remove all pairs of equal elements initially, so that all the elements are distinct but it was failing on one test case and on removing this it passes all test cases, can someone point out a case where it fails(the test cases are not available on the dropbox yet)

WA AC

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

    $$${1,19,19,20}$$$
    Answer is 18 (1 xor 19 = 18, 19 xor 20 = 7) but removing 19 makes it (1 xor 20=21).

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

C:

spend hour to write solution which uses up to 250 operations, delete it, write proper solution in 15 minutes

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -17 Vote: I do not like it

.

→ Reply