We will hold AtCoder Regular Contest 125.

- Contest URL: https://atcoder.jp/contests/arc125
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210822T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: maroonrk
- Tester: maspy, yamunaku
- Rated range: — 2799

The point values will be 300-500-600-700-800-900.

We are looking forward to your participation!

Great

Congratulations！

Why it is 300-500-600-700-800-900?

because even if someone all-killed ABC(before 212) before,he still can't get D(which seems exactly like what me did :(

orz!

I have a slightly different approach to B

We can iterate over values of Z, but do it in a smart way

say N = 10^12

We can notice no matter how large Y we use all Z >= 5e11 are useless, Z^2 + Y will not reach any square no matter what, so we just skip it

Then all Z, 250000000000 <= Z < 500000000000, are absolutely the same for us, because Z^2 + y can reach only one square number

Next we consider all Z that can reach two square numbers and so on

For N = 1e12 the borders for Z change as follows: 1000000000000 -> 500000000000 -> 250000000000 -> 166666666666 -> 124999999999...

To determine the next border of the interval I use binary search, so the overall complexity is O(sqrtN * logN)

My idea for problem A was to bring '01' or '10' in the beggining of S and if i encounter i digit in T which is different from my starting digit in S in just pay a cost of 2. And if it's the same i pay i cost of 1. I would like to know why my solution is not working. https://atcoder.jp/contests/arc125/submissions/25281998 Thanks.

Your implementtion is very complecated. I think simplest implementation is a simulation. Just try to find the min steps foreach single char. This works in O(n+m) since except the first char it allways works in 0 or 1 step. The only case we have to take care of is if there is no solution at all.

Thanks.I finished by just finding the best cost for a character that differ from s[0]. And iterate through t, if i find a digit different from it i add 2 otherwise i add one to the answer. https://atcoder.jp/contests/arc125/submissions/25283558

Has anyone tried to solve D, similar to count unique subsequences dp ?

use BIT to get dp[cur] and change dp[lst] easily(which is pretty well explained in the editorial

code:My Code

how to solve B — Squares,anyone help please..

We know that $$$y=(x-z)(x+z)$$$

Because $$$x-z\leq x+z$$$ , so we can just count the answer for every $$$x-z\leq 10^6$$$(Note that $$$x-z$$$ and $$$x+z$$$ have the same partity)

i didn't understand how it is the same to count answers for (x-z) not (x-z)*(x+z)

i saw many solution using this formula int binary search but didn't understand it

can you explain more ?

count the number of valid $$$x+z$$$ for every $$$x-z\leq 10^6$$$

pure math is enough so I don't think binary search is a must

In solution of D it is stated that " We can implement it with Binary Indexed Tree to achieve the time complexity of $$$O(n\log(n))$$$." Can anyone explain this part?

Lets consider $$$dp[i]$$$ to be the number of subsequences satisfying the conditions stated in the editorial and ending at index $$$i$$$. Now to calculate $$$dp[i]$$$, lets see where are all the possible second last elements could be ? It's easy to see that the second last element must be after or equal to the prev occurence of $$$A_i$$$. Let $$$j$$$ be the previous occurence of $$$A_i$$$. So essentially $$$dp[i] = \sum_{k=j}^{k=i-1}dp[k]$$$. However, notice that there might be multiple occurences of some element in the range $$$[j,i-1]$$$. In that case, we only need to add the dp value of the last occurence of that element. To take care of this we make sure that only the dp value of last occurence is active in the BIT while iterating through $$$i$$$ in increasing order.

In Conclusion you do the following at each $$$i$$$.

All these operations can be done using BIT/segment tree. Finally the answer would be

.

Thanks!

In problem E, why do we sort array by ci/bi <cj/bj to get minimum value. How can we prove it

sorry guys, I think I get it