maroonrk's blog

AtCoder Regular Contest 174 Announcement
By maroonrk, history, 8 months ago, In English

We will hold AtCoder Regular Contest 174.

The point values will be 300-300-500-500-700-900.

We are looking forward to your participation!

  • Vote: I like it
  • -26
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

As a writer, my shittest mistake is got negative color change at ARC173, last week. Anyway, GLHF!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow! 300-300-500-500?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is the difficulty of 500 points problem same in ABC and ARC?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

That math problem is too hard. Solved it too slowly. I'm losing a lot rating.

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

Today i found out that "1e18" is not equal to 1000000000000000000, it cost me a WA penalty.

Submissions — WA AC , can anybody tell why this happens?

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

    1e18 is equal to $$$10^{18}$$$ if you type cast it to long long.

    The problem is that comparing the equality of long long n and 1e18 automatically converts n to double and thus, its value gets rounded.

    For reference, if you run

    #include <iostream>
int main() {
    std::cout << (1000000000000000001 == 1e18) << '\n';
    std::cout << (1000000000000000001 == (long long) 1e18) << '\n';
}

    your output will be

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

    "Today i found out that "1e18" is not equal to 1000000000000000000".

    that's not true, I think the way why you probably get WA is something like this:

    #include <bits/stdc++.h>
int main() {
    std::cout << (999999999999999999 == 1e18); // true
    return 0;
}

    you can read about it here (Precision limitations on integer values)

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    In fact, 1e18 is a float or a double, so there may be a precision problem. You can use const ll inf=1000000000000000000 to avoid typing 18 zeros in the main body of your program.

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

      const ll inf = 1e18 works, as 1e18 is exactly $$$10^{18}$$$. You probably shouldn't use const ll inf = 1e18 + 1 or similar as that may cause rounding errors. ll(1e18) + 1 works, though.

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

        Thanks, though I still don't want to risk using anything like 1e9+7 or 1e18.

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

      This is part of my code of another problem: (the problem is CSP-S 2022 T2; link to Luogu)

      long long ans=flag?ask(l1,r1,l2,r2):1e18;

      Because 1e18 is not a long long, the ask(l1,r1,l2,r2) is firstly transformed into a float or double before storing into ans, so there's a precision problem. I got WA 0pts on this problem :(

      → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thanks to all of you for the clarification.

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

    Usually double is precise up to around $$$9 \times 10^{16}$$$ only

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

First time solving problem D in ARC. Thanks for the contest!

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

I hope people stop proposing problems like C to online programming contests :(

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

    Why, it's just a spinoff on DP-like problems?

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it -61 Vote: I do not like it

      Well, math knowledge invloved is too specific.

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

Why not give a stronger sample for F? It was really a pain debugging the 300-line code with bold eyes :(

→ Reply
»
8 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

C is like the coupon collector's problem but I have no idea :(

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

    I didn't solve like the editorial, instead I used dp. Let $$$dp_{i,j,k}$$$, be the expected number of coins player $$$k$$$ will pay if it is player $$$j$$$'s turn and $$$i$$$ values have already appeared. Notice that dp is symmetric, so it is enough to calculate $$$dp_{i,1,1}$$$ and $$$dp_{i,0,1}$$$ and we can derive the other two values from these.

    Trivial case is that all $$$n$$$ values have already appeared, so dp value in those cases is $$$0$$$. Now for the transitions there's really two key steps:

    $$$dp_{x,1,1}=\frac{x}{n}(1+dp_{x,0,1})+\frac{n-x}{n}dp_{x+1,0,1}$$$

    $$$dp_{x,0,1}=\frac{x}{n}dp_{x,1,1}+\frac{n-x}{n}dp_{x+1,1,1}$$$

    If you insert the second formula in the first one you will get dp transition for $$$x$$$ which is dependent on $$$x+1$$$.

    Upd: Great that I am getting downvoted for correct solution.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Interesting, thanks for sharing your solution! I didn't think of DP but tried to solve C in a pure math way during the contest.

      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem C,

the fine paid amount could tend to infinity right, so how can one find the expected fine paid in that case ?

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

    Look up geometric distribution and infinite geometric series. The binary tree representation of geometric distribution really helped me, I'll include the image.

    If you've seen n out of N integers, there is p = n / N probability of seeing repeat, and 1 — p probability to see new integer. In the binary tree, if you continue to see repeats you have to follow down the left side of the tree. and by x spin, you have p^x probability to not see a new integer. And since 0 < p < 1, it gets really really small.

    In fact you have p + p^2 + p^3, because you could not see another integer in 1 spin or 2 spins or 3 spins and so on following OR rule of probability. It becomes related to infinite geometric series, this series in fact, which does converge to a value.

    Basically the probability of continually not getting another distinct integer gets smaller and smaller, it approaches 0 is how I think of it. So if you have 4 distinct integers, there is almost 0 probability that you don't get to 5 distinct integer within some number of spins, each spin you don't get it becomes less and less probable.

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell why in problem B greedy is the only solution?

I tried Binary Search but it failed

Code
→ Reply
»
8 months ago, # |
  Vote: I like it +41 Vote: I do not like it

The difficulty of the ARC174 was disappointing, at least for me.

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

    I totally agree as there are $$$201$$$ participants who solved $$$5$$$ problems.

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

It was very enjoyable to stare at problem C for 1:30 hours and have no idea, what to do with it.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Btw, I am surprized by number of solutions of problem C. It looks for me much harder, than problem C from previous round. I guess, it is because it requires some special knowledge, not much related to CP.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it -37 Vote: I do not like it

      Yeah, it's too specific-knowledge requiring problem :(

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        what? gp summation is too specific knowledge now?

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          Is it something common now?

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

            It is taught in our schools atleast yes, and it is quite common in programming contests too....im surprised this is the first time you came across it.

            Further, it is not hard to come up with. It is very reasonable sirs

            Suppose we had to find S = 1 + p + p^2 + .....
            pS = p + p^2 + .....
            (1 — p)S = 1.
            S = 1 / (1 — p)

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

    Question about editorial of problem C.

    "The expected value of the fine increase for the player who is playing is expressed as $$$p + p^3 + p^5 + \dots$$$."

    It is not mentioned, how to get it. I could get it, but in several not trivial steps. How to get it more easily?

    There is a formula $$$p + 2 \cdot p^2 + 3 \cdot p^3 + \dots$$$ = $$$\frac{p}{(1-p)^2}$$$. How I got it: I knew that for geometric distribution the expected value is $$$\frac{1}{p}$$$, but at the same time it is $$$1 + 0 \cdot P(0) + 1 \cdot P(1) + 2 \cdot P(2) + 3 \cdot P(3) + \dots = 1 + 0 \cdot p + 1 \cdot (1 - p)p + 2 \cdot (1 - p)^2p + 3 \cdot (1 - p)^3p + \dots = 1 + p((1 - p) + 2 \cdot (1 - p)^2 + 3 \cdot (1 - p)^3 + \dots) = \frac{1}{p}$$$. Then substitute $$$p := 1 - p$$$ and get $$$1 + (1 - p)(p + 2 \cdot p^2 + 3 \cdot p^3 \dots) = \frac{1}{1 - p}$$$. From it we get the formula.

    Now, the probability, that fine increase is $$$0$$$ is equal to $$$(1 - p)$$$ — the first player immediately gets new number. The probability, that fine increase is $$$1$$$ is equal to $$$p(1 - p) + p^2(1 - p)$$$ — either the first player pays, and the second player gets new number, or the first player pays, the second player pays, and the first player gets new number.

    Add these expessions and simplify: $$$(1 - p)(1 \cdot (p - p^2) + 2 \cdot (p^3 - p^4) + 3 \cdot (p^5 - p^6) \dots) = (1 - p)((p^2 + 2p^4 + 3p^6 + \dots) + \frac{1}{p} \cdot (p^2 + 2p^4 + 3p^6 + \dots)) = (1 - p)(\frac{p^2}{(1 - p^2)^2} + \frac{p}{(1 - p^2)^2}) = \frac{p}{1 - p^2}$$$ as in editorial, but not magically.

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

      The probability that the game goes on for another x turns without getting a new element is p^x.

      The first player pays the fine on odd turns, so p + p^3 + ....

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Google "Tail sum formula for expectation" — $$$E(X) = \sum_{i=0}^\infty P(X > i)$$$.

      You can also find the expectation via a recurrence. Say that the last person to get the distinct number was the first player. $$$X$$$ is the amount of fines paid by the first player. Then,

      $$$ E(X) = p^2 (1 + E(X)) $$$

      Basically, the second player pays a fine, then the first player pays the fine, and you're back to the "starting position". For any other possibility, the contribution to the number of fines would be zero. You can do the same thing for other cases similiarly.

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

Despite I find C very easy, I think is more harder than D

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

I was a bit disappointed today. Of course I didn't perform well. But usually when doing ARC you always get to do some cool observations or some out-of-the-box thinking. Today I found most problems to be quite "inside-the-box". Pretty standard, but not trivial to implement. Also the difficulty was not up to par, as now there's a giant tie with $$$5$$$ problems solved.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Couldn't solve A :(

Solved B and D though

For C: Can someone give suggestions on how to solve questions on probabilities like C one? Are these purely mathematical questions or are there some other (cooler) ways to approach these problems?

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

    Actually you can also solve C in DP instead of pure math. Here is my code, and the only mathematical part is calculating something like $$$x+x^2+x^3+\dots$$$.

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

      Hmmm I see... a similar question involving probabilities and DP had come in my previous year's ICPC preliminary contest too... ig I need to practise these more often because they just seem so out of my capability rn.

      Thank you for the hint and code :)

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

    For problem A. There are two cases:

    Case 1. $$$C > 0$$$. We need to find the segment with maximum sum and apply the operation on it. If sum on segment is less than $$$0$$$, we don't need to do operation.

    Case 2. $$$C \le 0$$$. We need to find the segment with minimum sum and apply the operation on it. If sum on segment is greater than $$$0$$$, we don't need to do operation.

    How to find segment with maximum sum (with minimum the same way). Calculate prefix sums $$$p[i] = a[0] + a[1] + \dots + a[i - 1]$$$. The sum on segment is $$$p[r + 1] - p[l]$$$. Then we need to find maximum $$$p[r + 1] - p[l]$$$ for $$$r \ge l$$$. We can do this:

    left = p[0]
sum = -inf
for i = 1 .. n:
    res = max(res, p[i] - left)
    left = min(left, p[i])
    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I ran kadanes algo to find subarray with max sum and sub array with min sum

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

      Another approach:

      def solve(a, c):
  s0, s1, s2 = 0, 0, 0
  for x in a:
    s0, s1, s2 = s0 + x, max(s0, s1) + x * c, max(s1, s2) + x

  return max(s0, s1, s2)
      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yupp I realised the correct approach immediately once i started fresh after the contest, and it is same as your approach. Kinda scary how I fumble easy questions.

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

A — Math

B — Math

C — Math

D — Math

WTF, mathCoder.

UPD This round is downvoted, it seems that everyone has the same idea with me

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

    how was A math

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it -132 Vote: I do not like it

      what is "a math" ? Have you learned English ?

      I can't understand what you said.

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

        He means problem A.

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it -54 Vote: I do not like it

          Ok, now tell me how was problem A not math ?

          Don't you think problems with $$$\times$$$ is math ?

          You need to get the conclusion with math.

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

C is a cute problem, thanks

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A Very close to a problem I solved on CodeForces

1155D - Beautiful Array

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is solving 1900 rating problem in atcoder is harder or solving 2200 rating problem in codeforces is harder, can anyone please clarify?

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

Binary Search solution to problem B: Submission $$$\newline$$$ Let the original mean be $$$\frac{num}{den}$$$ and the price of $$$4\star$$$ and $$$5\star$$$ review be $$$a$$$ and $$$b$$$ respectively. $$$\newline$$$ $$$\mathbf C\mathbf a\mathbf s\mathbf e1:$$$ If the $$$mean$$$ $$$\ge 3$$$ or $$$a=0$$$ or $$$b=0$$$ then answer is $$$0$$$. $$$\newline$$$ Using a $$$4\star$$$ or a $$$5\star$$$ review is always better to increase the mean. Suppose we use $$$k$$$ reviews out of which $$$x$$$ are $$$4\star$$$ and $$$k - x$$$ are $$$5\star$$$. If the minimum price is $$$m$$$ then we have the following inequalities. $$$\newline$$$ $$$\mathbf I\mathbf n\mathbf e\mathbf q\mathbf u\mathbf a\mathbf l\mathbf i\mathbf t\mathbf y0:$$$ $$$k \geq 1$$$ $$$\newline$$$ $$$\mathbf I\mathbf n\mathbf e\mathbf q\mathbf u\mathbf a\mathbf l\mathbf i\mathbf t\mathbf y1:$$$ $$$0 \leq x \leq k$$$ $$$\newline$$$ $$$\frac{num+4x+5(k - x)}{den + k}\ge 3$$$ $$$\newline$$$ Let $$$c= 3den - num$$$ $$$\newline$$$ $$$\mathbf I\mathbf n\mathbf e\mathbf q\mathbf u\mathbf a\mathbf l\mathbf i\mathbf t\mathbf y2:$$$ $$$x\le 2k - c$$$ $$$\newline$$$ $$$ax + b(k - x) \leq m$$$ $$$\newline$$$ $$$\mathbf C\mathbf a\mathbf s\mathbf e2:$$$ If $$${\mathrm{b}} \leq {\mathrm{a}}$$$ then its always better to use a $$$5\star$$$ review so we get $$$\frac{{\mathrm{c}}}{2}{\mathrm{b}} \leq {\mathrm{m}}$$$ $$$\newline$$$ $$$\mathbf C\mathbf a\mathbf s\mathbf e3:$$$ If $$${\mathrm{b}} \gt {\mathrm{a}}$$$ $$$\newline$$$ $$$\mathbf I\mathbf n\mathbf e\mathbf q\mathbf u\mathbf a\mathbf l\mathbf i\mathbf t\mathbf y3:$$$ $$$x \geq \frac{m - bk}{a - b}$$$ $$$\newline$$$ On solving $$${\mathrm{Inequality}}2$$$ with $$${\mathrm{Inequality}}1$$$ we get $$$\newline$$$ $$${\mathrm{k}} \geq \frac{{\mathrm{c}}}{2}$$$ $$$\newline$$$ On solving $$${\mathrm{Inequality}}3$$$ with $$${\mathrm{Inequality}}1$$$ we get $$$\newline$$$ $$${\mathrm{k}} \leq \frac{{\mathrm{m}}}{{\mathrm{a}}}$$$ $$$\newline$$$ On solving $$${\mathrm{Inequality}}2$$$ with $$${\mathrm{Inequality}}3$$$, we get $$$\newline$$$ $$${\mathrm{m}} + {\mathrm{c}}({\mathrm{a}} - {\mathrm{b}}) \geq (2{\mathrm{a}} - {\mathrm{b}}){\mathrm{k}}$$$ $$$\newline$$$ $$$\mathbf C\mathbf a\mathbf s\mathbf e3.1:2{\mathrm{a}} - {\mathrm{b}} \gt 0$$$ $$$\newline$$$ $$${\mathrm{k}} \leq \frac{{\mathrm{m}} + {\mathrm{c}}({\mathrm{a}} - {\mathrm{b}})}{2{\mathrm{a}} - {\mathrm{b}}}$$$ $$$\newline$$$ Combining all the inequalities we get $$${\mathrm{\max }}(\frac{{\mathrm{c}}}{2},1) \leq {\mathrm{k}} \leq {\mathrm{\min }}(\frac{{\mathrm{m}} + {\mathrm{c}}({\mathrm{a}} - {\mathrm{b}})}{2{\mathrm{a}} - {\mathrm{b}}},\frac{{\mathrm{m}}}{{\mathrm{a}}})$$$ $$$\newline$$$ $$$\mathbf C\mathbf a\mathbf s\mathbf e3.2:2{\mathrm{a}} - {\mathrm{b}} \lt 0$$$ $$$\newline$$$ $$${\mathrm{k}} \geq \frac{{\mathrm{m}} + {\mathrm{c}}({\mathrm{a}} - {\mathrm{b}})}{2{\mathrm{a}} - {\mathrm{b}}}$$$ $$$\newline$$$ Combining all the inequalities we get $$${\mathrm{\max }}(\frac{{\mathrm{m}} + {\mathrm{c}}({\mathrm{a}} - {\mathrm{b}})}{2{\mathrm{a}} - {\mathrm{b}}},\frac{{\mathrm{c}}}{2},1) \leq {\mathrm{k}} \leq \frac{{\mathrm{m}}}{{\mathrm{a}}}$$$ $$$\newline$$$ $$$\mathbf C\mathbf a\mathbf s\mathbf e3.3:2{\mathrm{a}} - {\mathrm{b}} = 0$$$ $$$\newline$$$ Combining all the inequalities we get $$${\mathrm{\max }}(\frac{{\mathrm{c}}}{2},1) \leq {\mathrm{k}} \leq \frac{{\mathrm{m}}}{{\mathrm{a}}}$$$ and $$${\mathrm{m}} \geq - {\mathrm{c}}({\mathrm{a}} - {\mathrm{b}})$$$ $$$\newline$$$

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very enjoyable problems.

For problem E I am wondering what is the way to understand why you take (c — 1) * nPk * k / n term. In specific, why is k / n factor needed. I think it is because you have k / n probability of picking the element out of k available slots and n elements. So I generalized this to this principle. The count of permutations in which element i appears within when you are choosing k from n is nPk * (k / n). But what is reasoning for this?

→ Reply