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!
I don't know if I can do D this time ):
Wow! New judge!
...........................
just v* the st*i*g and rea* to pr*n* the ns*e
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!
sheet java lose, c++ 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.
I'm sorry my bad I've saw the old blog it got updated just before 15 hours I saw it before that. If I would've known that before contest I would've made it rated ;_;
It is the previous contest (ABC313) that is harder than normal ABC-class contests.
yes
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.com/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 B
This is a tragedy! link
Can 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.
Hi, could someone please take a look at my solution for problem E and point out problems with the approach? I have added comments on the DP state and transition. Would really appreciate your help. The code snippet is not long.
Can you give me a data that makes my code in question D wrong? Thanks!
New judge seems much faster?
/* It can be proved that the sought expected value is always rational. Also, the constraints of this problem guarantee that if the sought expected value is expressed as an irreducible fraction x y , then x is not divisible by 998244353.
Now, there is a unique integer z between 0 and 998244352, inclusive, such that xz≡y(mod998244353). Report this z. */
can anyone show me the code to achieve that within timelimit?