Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### maroonrk's blog

By maroonrk, history, 2 years ago, We will hold AtCoder Regular Contest 125.

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

We are looking forward to your participation! Comments (21)
| Write comment?
 » Great
 » Congratulations！
 » Why it is 300-500-600-700-800-900?
•  » » It is scored according to the difficulty
•  » » because even if someone all-killed ABC(before 212) before,he still can't get D(which seems exactly like what me did :(
•  » » » orz!
 » 2 years ago, # | ← Rev. 3 →   I have a slightly different approach to BWe can iterate over values of Z, but do it in a smart waysay N = 10^12We 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 itThen all Z, 250000000000 <= Z < 500000000000, are absolutely the same for us, because Z^2 + y can reach only one square numberNext we consider all Z that can reach two square numbers and so onFor 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.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   Thanks.I finished by just finding the best cost for a character that differ from s. 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 editorialcode: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 ?
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   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$. $dp[i] = sum(j,i-1)$ $modify(last[a[i]],0)$ $modify(i,dp[i])$ $last[a[i]]=i$All these operations can be done using BIT/segment tree. Finally the answer would be $dp[n+1]-1$.
•  » » » Thanks!
 » In problem E, why do we sort array by ci/bi
•  » » sorry guys, I think I get it