atcoder_official's blog

AtCoder Beginner Contest 314 Announcement
By atcoder_official, history, 16 months ago, In English

We will hold AtCoder Beginner Contest 314.

The point values will be 100-200-300-400-475-475-575-625.

We are looking forward to your participation!

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

Comments Comments (30)
| Write comment?
»
16 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Can anyone tell me what is "Clar" in "About the New Judge"? I hardly found posts about it in Bing.

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

AtCoder Beginner Contest Pi!

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

Wow! New judge!

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

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

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

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

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

    Nobody has mentioned that before(?) This round is just an ordinary one because I can exactly solve problem G as usual.

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

too funny :) I submitted 4 wrong codes on D, such a easy problem.

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

Whyyyyyyyyy both E and F are expected value based question. Guess its time to practice expected value :(

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

    Yeah same, I tend to quit if the problem is about expected value of something

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

    How delighted I was when I solved D, how frustrated I was when I saw E

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

    $$$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.

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

      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

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

Pretty shocked to see that people are discussing ongoing contest in the comment box , some even telling solutions

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

how to solve E?

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

orz chromate00 for the first solve of Ex...

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

How to Solve D?

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

    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.

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

    among the operations of type 2 and 3 only the last operation matters

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

Using simulated annealing and passed task Ex, maybe the data is too weak?

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

    no lol the problem is simply convex, that is why

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

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

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

Can anyone talk more about problem E? I can hardly understand the editorial. Thank you so much.

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

    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

    $$$\displaystyle E_M = C_k + \sum_{j=1}^{P_k} \frac{1}{P_k} E_{M - S_{k_j}}\quad (1)$$$

    (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\}$$$)

    $$$ $$$
    What about zero elements?
    $$$ $$$
    How replacing the costs makes for an easier solution.
    $$$ $$$
    But how can we know k?

    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.

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

      (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.

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

      It is much easier to understand than Editorial.

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

New judge seems much faster?

→ Reply