atcoder_official's blog

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342） Announcement
By atcoder_official, history, 10 months ago, In English

We will hold HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）.

We are looking forward to your participation!

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

»
10 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Lovely score distribution ever

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

Excited!

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

A round with prizes,NICE.

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

HUAWEI Round. Excited.

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

tourist register and he will get more money

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

omg HUAWEI round

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

omg this is the first time that I see a video in the contest description!

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

yeah！

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

HUAWEI's contest!!!

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

excited

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

OH,I'm newbie, I can't do C

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

F<<<E!!!

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

    Really? I felt like E was just "yeah this is your standard ABC dijkstra problem, enjoy implementing for 10-15 mins :)" while F actually required some rough thinking.

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

      I observed that, but what's next?

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

        start with n-1 storing val-c in priority queue to next node where val=current node max value.

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

    How did you do for F ?

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

      imo: Brute force (enuming) with Segment Tree.

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

    Any ideas why this solution to E :: Last Train fails just a single test case?

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

I think D was two pointer problem.Am i right?

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

G is easier that D :)

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

    How ? I implemented segTree with sets in G, but D was just dividing and checking a pair of cases

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

    are you serious?？

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

For F: I was able to find out the probability of achieving $$$x = x_0$$$ and the winning probability when $$$x = x_0$$$. Using this info, how do I determine the answer.

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

Can anyone provide me edge case for my solution for Problem D Link

Approach: Precompute all the squares till 2e5 and check by dividing that if good pair exists or not.

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

    We can achieve a square number bigger than 2e5

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

    Why would the squares be bounded by $$$2 \cdot 10^5$$$?.

    Consider $$$A = [5 \cdot 10^4, 2 \cdot 10^5]$$$, here $$$A_1 \cdot A_2 = 10^{10}$$$ which is a perfect square greater than $$$2 \cdot 10^5$$$.

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

    Ai = 2e5, Aj = 2e5, the product is equal to (2e5)^2. So squares till 2e5 are not enough.

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

Can someone explain F?

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

    First compute the probability that dealer gets at least $$$x$$$ points linearly. Then do dynamic programming over $$$dp[x]$$$ = probability that you win if you start with $$$x$$$ points.

    https://atcoder.jp/contests/abc342/submissions/50612581

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

    For the dealer we can simulate the probabilities of them having a particular sum at the end since they have a fixed move for a given sum.

    Pseudocode

    Now for the player, if we stop at a specific score $$$x$$$, we know the probability of winning is $$$\text{player_probability[x]} = 1 - \sum_{i = x}^{n}{\text{dealer_probability[i]}}$$$. However, we can also decide to continue playing, in which case it becomes the average probability among all possible dice rolls, i.e, $$$\frac{\sum_{i = x + 1}^{\text{min(x + d, n)}}{\text{player_probability[i]}}}{d}$$$, so we take the max of these two values. Doing this in decreasing order of $$$x$$$ gives us a way to calculate the probability for all scores.

    Pseudocode

    Then player_probability[0] is the value you want. To speed this up from $$$O(n ^ 2)$$$ to $$$O(n)$$$, use difference arrays and prefix sums to get rid of the inner loops in both of the above parts.

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

      Thank you,this explanation is beautiful.

      I think $$$\sum_{i = x+1}^{min(x+d,n)}\frac{player_pprobability[i]}{n}$$$ should be replaced by $$$\sum_{i = x+1}^{min(x+d,n)}\frac{player_pprobability[i]}{d}$$$ .

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

How are the rating updates for the ABC calculated if there are so many participants whose ratings are outside the rated range? I mean, they are still considered in the ranking list, aren't they? Wouldn't it be unfair to calculate the rating changes based on the rank each time, as sometimes there are stronger competitors?

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

Is it just me who overcomplicated the solution of problem C with small-to-large merging xD? Submission

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

90% of E is figuring out what the statement is trying to say 🤡

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

    I couldn't even understand statement of $$$B$$$

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

      Given sequence $$$a_n$$$ and suppose $$$b_{a_i}=i$$$. In each query given $$$x,y$$$, print $$$x$$$ if $$$b_x>b_y$$$, or $$$y$$$ if not.

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

G much easier than F, although I cannot figure it out.

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

    Tl;dr — Simple range addition, point query segtree except t[v] is a multiset of possible values and you take the max of all of the sets.

    Let each node contain a multiset of possible values for the range. Initially this is $$$a_i$$$ for a leaf node and nothing for all other nodes.

    When we perform a lazy update for the range $$$[l, r]$$$, we will add this to the set of each of the terminal nodes ($$$l = tl$$$ and $$$r = tr$$$) we reach.

    Now every node in the range $$$[l, r]$$$ is covered by at least one of these nodes, so for each query we can just walk over all the nodes which cover the position and take the max of all the values.

    Note that cancellations are now just update operations but with "erase 1 occurrence of x" instead of "insert 1 occurrence of x".

    Code

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

      And what should be the total complexity of your solution, looking from far seems like quite larger than n*(logn)^2, considering the heavy operation of transferring the laziness when required

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

        1. We update at most $$$\log(n)$$$ nodes in a single update. In each node we add at most 1 value into a set. So each update takes at most $$$O(\log^2(n))$$$ time.

        2. We don't need to propagate the "max" update values down down since we just check the $$$\log(n)$$$ containing nodes for the given position during the query. Since we're just checking the first (greatest) element, this takes $$$O(\log(n))$$$ time per query.

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

          Oh Thank you.

          I understood now, it's kind of strange segtree where the root node doesn't necessarily contain the values related to children,

          So we don't need to push because we are not even necessarily getting down to the leaf node because terminal nodes already contain such information

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

https://atcoder.jp/contests/abc342/submissions/50599311

can anyone tell me what is wrong in this code? Any help would be appreciated

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

    Consider this input:

    Input

    Your code gives dtcovvr as output. However, d is supposed to be replaced by v. Why do we still see d in the output?

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

HUAWEI Round. Excited.

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

didn't know that discussion panel in atcoder redirects to codeforces lol

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

btw in D if we factorize all numbers, we will know if the product of two num is squared, if only after adding their factors there is even numbers of factors right? 3 -> 3 and 12 -> 2,2,3 so 2,2,3,3

but how we can find all such pairs?

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

    You can find square-free part of number (make sure to handle zeros separately). In particular, the square-free parts of both numbers must be equal. Or, you can do something similar to what is done in 1225D - Power Products, where you ignore zeros, and check the rest (there are only $$$\mathcal{O}(\log 10^5)$$$ prime factors for each number).

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

Can anyone explain me line no. 35 of jiangly's solution to problem E?

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

    the main idea is: 1. build the graph from end to begin(not from begin to end) 2. using Dijkstra

    the code he used is C++20, a little smooth.

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

To help you build intuition for F and lead you to the solution in a more natural manner, I've created an easy version $$$O(n^3)$$$ and $$$O(n^2)$$$ which focuses on the probability + DP part (instead of optimization). It also asks you to print each intermediate DP values, since debugging probability problems can be tricky. I also added some followup problems to test your understanding.

You can find the contest here: https://codeforces.net/group/7Dn3ObOpau/contest/506759

The problems are untested. If you see any issues, please let me know.

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

difficulty: G < E < F

I solved ABCDG(

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

Admin please conduct contests on both Saturday and Sunday

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

The solution to G https://atcoder.jp/contests/abc342/submissions/50593706 is hacked by:
1
1
4
1 1 1 2
1 1 1 2
2 1
3 1

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

when the prize will be awarded :)

→ Reply