### maroonrk's blog

By maroonrk, history, 4 weeks 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!

• +165

 » 4 weeks ago, # |   +12 Great
 » 4 weeks ago, # |   -14 Congratulations！
 » 4 weeks ago, # |   -24 Why it is 300-500-600-700-800-900?
•  » » 4 weeks ago, # ^ |   0 It is scored according to the difficulty
•  » » 4 weeks ago, # ^ |   0 because even if someone all-killed ABC(before 212) before,he still can't get D(which seems exactly like what me did :(
•  » » » 4 weeks ago, # ^ |   0 orz!
 » 4 weeks ago, # |   -29 I look forward to terrible things as I try and recover in time from last night's Kick Start round (and/or the extremely painful handprint from facepalming so hard).
 » 4 weeks ago, # | ← Rev. 3 →   +8 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)
•  » » 2 weeks ago, # ^ |   0 i did the same approach but still got WA , can you send your code or tell me what's the wrong with my code ? https://ideone.com/5VgRxT
 » 4 weeks ago, # |   0 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.
•  » » 4 weeks ago, # ^ |   0 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.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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
 » 4 weeks ago, # |   0 Has anyone tried to solve D, similar to count unique subsequences dp ?
•  » » 4 weeks ago, # ^ |   0 use BIT to get dp[cur] and change dp[lst] easily(which is pretty well explained in the editorialcode:My Code
 » 4 weeks ago, # |   0 how to solve B — Squares,anyone help please..
•  » » 4 weeks ago, # ^ |   0 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)
•  » » » 2 weeks ago, # ^ |   0 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 weeks ago, # ^ | ← Rev. 3 →   0 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
 » 4 weeks ago, # |   0 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?
•  » » 4 weeks ago, # ^ |   +27 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$.
•  » » » 4 weeks ago, # ^ |   0 Thanks!
 » 12 days ago, # |   +5 In problem E, why do we sort array by ci/bi
•  » » 12 days ago, # ^ |   0 sorry guys, I think I get it