We will hold AtCoder Beginner Contest 314.
- Contest URL: https://atcoder.jp/contests/abc314
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230812T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: leaf1415, MMNMM, evima
- Tester: kyopro_friends, Nyaan
- Rated range: ~ 1999
The point values will be 100-200-300-400-475-475-575-625.
We are looking forward to your participation!
Can anyone tell me what is "Clar" in "About the New Judge"? I hardly found posts about it in Bing.
Clarifications
AtCoder Beginner Contest Pi!
Wow! New judge!
omg , my java codes are working in 40ms , but why did you removed java 8 , it's the best version of the best language on this earth
No! C++ is the best!
Good contest I was pretty scared that they mentioned it will be harder than usual but I didn't felt this contest is way too different compared to typical atcoder rounds
Nobody has mentioned that before(?) This round is just an ordinary one because I can exactly solve problem G as usual.
too funny :) I submitted 4 wrong codes on D, such a easy problem.
Whyyyyyyyyy both E and F are expected value based question. Guess its time to practice expected value :(
Yeah same, I tend to quit if the problem is about expected value of something
How delighted I was when I solved D, how frustrated I was when I saw E
$$$F$$$'s expected value was just sum of probabilities for each node. But the main work (in my solution) was how to create a DSU variant to build a tree which can be used the propagate (add) the final answer for each node.
That part was easy just small to large merging was needed to be done. I couldn't debug my code again on time :pain:
My code
Pretty shocked to see that people are discussing ongoing contest in the comment box , some even telling solutions
Yes, they should be banned from AtCoder
how to solve E?
orz chromate00 for the first solve of Ex...
How to Solve D?
The problem is solved by considering global operations separately and checking the last update when modifying individual characters.
Regarding global operations, it is sufficient to record the time and type of the last operation.
Finally, if the individual update is made after the global update, it is printed directly; otherwise, the last global update is applied to the individual update before printing.
Similar to https://codeforces.me/problemset/problem/1679/B
among the operations of type 2 and 3 only the last operation matters
Using simulated annealing and passed task Ex, maybe the data is too weak?
no lol the problem is simply convex, that is why
Weak tests in D.
https://atcoder.jp/contests/abc314/submissions/44532834 should fail on
7 Atcoder 3 2 0 a 1 3 a 1 3 BCan anyone talk more about problem E? I can hardly understand the editorial. Thank you so much.
I'm not sure if it would help but I'm writing my way of thought anyways. Keep in mind that it is not really formal, I suggest your refer to the editorial for more formality.
Let $$$E_i$$$ be the expected number of money needed to get $$$i$$$ points when Takahashi adopts the optimal strategy.
At first Takahashi has $$$0$$$ points. So there are $$$M$$$ points he needs (at least), so the expected number of money needed is $$$E_M$$$. What's left is to compute $$$E$$$.
Say Takahashi has $$$0$$$ points (i.e needs $$$M$$$ points). At that point and based on his strategy he will choose some $$$k\in\{1, \dots , N\}$$$ and spin the $$$k$$$-th wheel. Doing that, he will pay $$$C_k$$$ (for sure) and will gain $$$S_{k_j}$$$ points ($$$1\leq j\leq P_k$$$) with probability $$$\frac{1}{P_k}$$$. Then he would have $$$S_{k_j}$$$ points, so he will need $$$M - S_{k_j}$$$ more points. That implies that he will then need an average of $$$E_{M - S_{k_j}}$$$ money. So the expected number of money when having $$$0$$$ points ($$$M$$$ points remaining) is
(keep in mind that $$$E_i = 0$$$ for $$$i \leq 0$$$, but you can just have $$$E_0=0$$$ and always take the index $$$i$$$ as $$$\max\{0, i\}$$$)
Now $$$(1)$$$ is correct, however sometimes $$$S_{k_j} = 0 \implies E_{M - S_{k_j}} = E_M$$$, which means we won't be able to use $$$(1)$$$ as is for the computation of $$$E_M$$$. Let $$$J$$$ be the set of all $$$j$$$ such that $$$S_{k_j} = 0$$$. Then
now with proper algebra
So now we can compute $E_M$ using $$$(2)$$$.
Now we can algebraically see how replacing the costs makes the solution simplier, since $$$(2)$$$ can be written as
which is basically $$$(2)$$$ if we remove the zero elements $$$J$$$ and replace the cost $$$C_k$$$ appropriately.
We know that Takahashi will choose the $$$k$$$ that minimizes the value $$$E_M$$$, so we can iterate over all the choices.
Similarly to $$$E_M$$$ we can compute all of $$$E$$$. This yields a $$$O(MNP)$$$ solution ($$$P=\max_i P_i$$$), which is basically the editorial's solution looking at it slightly differently. I think understanding one solution will make one easily understand the other.
(The problem is resolved, so kindly ignore this message.)
Hello judgme_nt,
I used the exact approach suggested by you. But my code is giving WA on just 1 test case. I can't find the error in my code. I coded a recursive solution and can't find anyone with a similar code. Can you please point out the mistake in my code?
Submission
Here, I have used a "cnt" array to store the number of zero elements in i-th wheel. (The code is written clearly enough, so understanding it would not be tough).
Thank You
UPD: It got accepted when I changed double to long double.
It is much easier to understand than Editorial.
New judge seems much faster?