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

- Contest URL: https://atcoder.jp/contests/abc342
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240224T2100&p1=248
- Duration: 100 minutes
- Writer: MMNMM, nok0, Nyaan, kyopro_friends, m_99
- Tester: physics0523, kyopro_friends
- Rated range: ~ 1999
- The point values: 150-200-350-400-450-550-625

We are looking forward to your participation!

Lovely score distribution ever

Excited!

A round with prizes,NICE.

HUAWEI Round. Excited.

tourist register and he will get more money

No jiangly will win

Upd: oh he really won! orz

orz jiangly

good contest!

omg HUAWEI round

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

yeah！

HUAWEI's contest!!!

excited

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

I cannot do it either mate

C was tricky,but i do

Apply the operations in reverse order.

what's your country?

think of O( Q * 26 ) complexity

Yep

i tried, but i can't, (sad)

F<<<E!!!

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.

I observed that, but what's next?

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

code...

How did you do for F ?

imo: Brute force (enuming) with Segment Tree.

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

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

it's prime factorization i think

count-of-pairs-in-an-array-whose-product-is-a-perfect-square

G is easier that D :)

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

are you serious?？

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

We can achieve a square number bigger than 2e5

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

sorry, I'm dumb.

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

Can someone explain F?

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

Thanks.

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.

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

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

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

Oops, yeah that should be $$$d$$$, not $$$n$$$. Fixed it now.

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?

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

Notice that there are at most 26 distinct characters in the string xD (Initially, I was on the verge of doing small in large)

what do you mean by small to large merging??

can you please explain

https://usaco.guide/plat/merging

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

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

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.

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

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

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

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.

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.

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

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

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

Consider this input:

InputYour code gives

`dtcovvr`

as output. However,`d`

is supposed to be replaced by`v`

. Why do we still see`d`

in the output?HUAWEI Round. Excited.

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

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?

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

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

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.

To help you build intuition for

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

difficulty: G < E < F

I solved ABCDG(

Admin please conduct contests on both Saturday and Sunday

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

when the prize will be awarded :)