We will hold AtCoder Regular Contest 174.
- Contest URL: https://atcoder.jp/contests/arc174
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240317T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: physics0523
- Tester: maspy, potato167
- Rated range: — 2799
The point values will be 300-300-500-500-700-900.
We are looking forward to your participation!
As a writer,
my shittest mistake is got negative color change at ARC173, last week. Anyway,GLHF!Color — not permanent, skill — permanent
Wow! 300-300-500-500?
Excited!
is the difficulty of 500 points problem same in ABC and ARC?
That math problem is too hard. Solved it too slowly. I'm losing a lot rating.
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?
1e18is equal to $$$10^{18}$$$ if you type cast it tolong long.The problem is that comparing the equality of
long long nand1e18automatically convertsntodoubleand thus, its value gets rounded.For reference, if you run
your output will be
"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:
you can read about it here (Precision limitations on integer values)
In fact,
1e18is afloator adouble, so there may be a precision problem. You can useconst ll inf=1000000000000000000to avoid typing 18 zeros in the main body of your program.const ll inf = 1e18works, as1e18is exactly $$$10^{18}$$$. You probably shouldn't useconst ll inf = 1e18 + 1or similar as that may cause rounding errors.ll(1e18) + 1works, though.Thanks, though I still don't want to risk using anything like
1e9+7or1e18.This is part of my code of another problem: (the problem is CSP-S 2022 T2; link to Luogu)
Because 1e18 is not a
long long, theask(l1,r1,l2,r2)is firstly transformed into afloatordoublebefore storing intoans, so there's a precision problem. I got WA 0pts on this problem :(Thanks to all of you for the clarification.
Usually
doubleis precise up to around $$$9 \times 10^{16}$$$ onlyFirst time solving problem D in ARC. Thanks for the contest!
I hope people stop proposing problems like C to online programming contests :(
Why, it's just a spinoff on DP-like problems?
Well, math knowledge invloved is too specific.
The only math I did was solving a cyclic recurrence relation in dp[x], for dp[x]. (Similar to https://atcoder.jp/contests/dp/tasks/dp_j ). dp[x] here is a pair which has the minimum cost for the two players, when there are x numbers not chosen.
sorry i have to w8 4 more hours to send one
Why not give a stronger sample for F? It was really a pain debugging the 300-line code with bold eyes :(
C is like the coupon collector's problem but I have no idea :(
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.
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.
in problem C,
the fine paid amount could tend to infinity right, so how can one find the expected fine paid in that case ?
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.
Can someone tell why in problem B greedy is the only solution?
I tried Binary Search but it failed
https://atcoder.jp/contests/arc174/submissions/51397702
I solved using binary search:
https://atcoder.jp/contests/arc174/submissions/51387866
The difficulty of the ARC174 was disappointing, at least for me.
I totally agree as there are $$$201$$$ participants who solved $$$5$$$ problems.
It was very enjoyable to stare at problem C for 1:30 hours and have no idea, what to do with 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.
Yeah, it's too specific-knowledge requiring problem :(
what? gp summation is too specific knowledge now?
Is it something common now?
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)
🤯
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.
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 + ....
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,
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.
Despite I find C very easy, I think is more harder than D
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.
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?
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$$$.
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 :)
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:
I ran kadanes algo to find subarray with max sum and sub array with min sum
Another approach:
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.
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
how was A math
what is "a math" ? Have you learned English ?
I can't understand what you said.
He means problem A.
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.
C is a cute problem, thanks
How to solve B?
Problem A Very close to a problem I solved on CodeForces
1155D - Красивый массив
Is solving 1900 rating problem in atcoder is harder or solving 2200 rating problem in codeforces is harder, can anyone please clarify?
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$$$
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?