maroonrk's blog

AtCoder Regular Contest 125 Announcement
By maroonrk, history, 3 years ago, In English

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!

  • Vote: I like it
  • +165
  • Vote: I do not like it

Comments Comments (21)
| Write comment?
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Great

→ Reply
»
3 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Congratulations！

→ Reply
»
3 years ago, # |
  Vote: I like it -24 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

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)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    code:My Code

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

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

    .

    → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply