atcoder_official's blog

By atcoder_official, history, 7 weeks 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

»
7 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

Lovely score distribution ever

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

A round with prizes,NICE.

»
7 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

HUAWEI Round. Excited.

»
7 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

tourist register and he will get more money

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

omg HUAWEI round

»
7 weeks 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!

»
7 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

yeah!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

HUAWEI's contest!!!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

excited

»
7 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

F<<<E!!!

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I observed that, but what's next?

      • »
        »
        »
        »
        7 weeks 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
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you do for F ?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      imo: Brute force (enuming) with Segment Tree.

  • »
    »
    7 weeks 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?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

G is easier that D :)

  • »
    »
    7 weeks 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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    are you serious??

»
7 weeks 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.

»
7 weeks 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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    We can achieve a square number bigger than 2e5

  • »
    »
    7 weeks 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$$$.

  • »
    »
    7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain F?

  • »
    »
    7 weeks 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

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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}$$$ .

»
7 weeks 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?

»
7 weeks 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

»
7 weeks 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 🤡

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks 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

      • »
        »
        »
        »
        7 weeks 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.

        • »
          »
          »
          »
          »
          7 weeks 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

»
7 weeks 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

  • »
    »
    7 weeks 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?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

HUAWEI Round. Excited.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks 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?

  • »
    »
    7 weeks 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).

»
7 weeks 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?

  • »
    »
    6 weeks 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.

»
7 weeks 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://mirror.codeforces.com/group/7Dn3ObOpau/contest/506759

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

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

difficulty: G < E < F

I solved ABCDG(

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Admin please conduct contests on both Saturday and Sunday

»
7 weeks 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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

when the prize will be awarded :)