maroonrk's blog

AtCoder Regular Contest 170 Announcement
By maroonrk, history, 11 months ago, In English

We will hold AtCoder Regular Contest 170.

The point values will be 400-500-600-700-800-1000.

We are looking forward to your participation!

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

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

gl! btw 400-500-600 seems challenging!

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is $$$C$$$ prefix-sum dp?

→ Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it
    Solution
    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Feeling stupid for messing 7 times on B :)

→ Reply
»
11 months ago, # |
  Vote: I like it -19 Vote: I do not like it

D was very nice.

→ Reply
»
11 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone explain why this doesn't work for b

My Code
→ Reply
»
11 months ago, # |
  Vote: I like it +14 Vote: I do not like it

How to do D?

My idea
→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Same idea same wa

    → Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Consider this case:

    4
1 1 7 9
1 1 3 3

    For every value that Bob can choose, Alice can choose two of her numbers to make a triangle. 

    If Bob chooses 1, Alice can choose 1 and 1 to make a triangle
If Bob chooses 3, Alice can choose 7 and 9 to make a triangle

    So you would assume that Alice wins. But Alice has to choose one of her numbers first, which gives Bob a winning strategy:

    If Alice chooses 1, Bob can choose 3 and no triangle is possible
If Alice chooses 7, Bob can choose 1 and no triangle is possible
If Alice chooses 9, Bob can choose 1 and no triangle is possible
    → Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have a different idea for B:

Lets precompute for every index i the value j, where j is the smallest index more than i such that you can form an arithmetic subsequence of length 3 from values i...j. Call this value as nearest_end[i].

To do this we can brute force the difference of the AP from -9 to 9 and greedily choose the smallest next index.

Once this precomputation is done, consider f[i]=number of pairs ending at i. The naive idea to compute this would be to iterate j from i to 1 and find the rightmost j such that nearest_end[j]<=i, then f[i]=j. To optimise this we can use binary search and range minimum queries to find rightmost such j. The ans is just sum of all f[i] from i=1 to n

I know this is an overkill compared to editorials solution but I felt like sharing

link to submission :https://atcoder.jp/contests/arc170/submissions/49553096

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it -32 Vote: I do not like it

B can be reduced to Rectangle Union Area

49545573

→ Reply
»
11 months ago, # |
  Vote: I like it +66 Vote: I do not like it

There's a simpler and faster solution for problem E (the complexity is the same, but without matrix operations).

The solution is the same as the official editorial until the last step. Here we need to calculate the sum for every pair of positions, the probability of them being equal in the LR sequence.

Let's say we fix the two positions $$$x<y$$$. Now, what we choose before $$$x$$$ and what we choose after $$$y$$$ doesn't matter. For the part from $$$x$$$ to $$$y$$$, there is a probability of $$$p$$$ that a character stays the same as the previous one, and $$$1-p$$$ otherwise.

If we want $$$x$$$ to be equal to $$$y$$$, then there should be an even number of positions where the character differs from the previous one, so it boils down to the following problem:

There is a $$$01$$$ sequence of length $$$m$$$, where each position is $$$0$$$ with probability $$$p$$$ and $$$1$$$ with probability $$$1-p$$$. Calculate the probability that this sequence has an even number of $$$1$$$. The answer to the original problem when we fix $$$x,y$$$ is the answer to this problem when $$$m=y-x$$$.

Let $$$q=1-p$$$ and a polynomial $$$f(x)=(p+qx)^m$$$, then we need to calculate $$$\sum_{i=0}^m[i\bmod 2=1][x^i]f(x)$$$. Using the well-known trick to split the even and odd coefficient, this number equals to $$$\frac{f(1)+f(-1)}2$$$, as the odd coefficients will be eliminated while the even ones are counted twice. So the answer to this problem is $$$\frac{1+(2p-1)^m}2$$$.

Now back to the original problem, after iterating through all pairs of $$$(x,y)$$$, the answer is $$$\sum_{x=1}^{n-1}\sum_{y=x}^{n-1}\frac{1+(2p-1)^{y-x}}2$$$. Now we fix $$$y-x$$$ first, then we need to calculate $$$\frac12\sum_{i=0}^{n-2}(n-i-1)(1+(2p-1)^i)$$$. This can be calculated in $$$O(\log n)$$$ time after some deduction to the geometric series sum.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain the approach of A please?

→ Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    There are only 2 kind of disparities possible :

    ..B...A..
..A...B..

    To clear disparity of type BA where s[i]='B' and t[i]='A', there are two options to either have sequence AB or BB after the occurrence of BA. Since, we need to minimize our operations we will prefer AB over BB because by doing so we will eliminate two disparities with 1 operation while latter will remove only one disparity.

    To remove BA you can maintain a stack for it whenever you encounter AB pop it and do ans++.

    Now we would still be remaining with some ABs but insufficient number of BA so now we will search for type BB after the last occurrence of BA. Since the BB after the last BA will able to convert all the BAs to BB and do ans++.

    Similarly, do it for AB but now iterate and maintain a stack form the end.

    Here's a link to my submission : (https://atcoder.jp/contests/arc170/submissions/49550689)

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give counter test for B https://atcoder.jp/contests/arc170/submissions/49553730

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

How is this solution accepted for B? Isn't the time complexity O(n^2) at the least?

#49543170

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

    Let W the biggest number of different values allowed for A (here 10).

    By pigeon principe each subarray of length >=2W+1 must contain 3 indices of equal value (which is a particular case of arithmetic progression).

    The solution you mention is in O(n M²) where M is the biggest possible size of a window without any arithmetic progression and M<= 2W=20 by the precedent argument.

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain which corner case I missed as I got 2 WAs.

https://atcoder.jp/contests/arc170/submissions/49543465

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

AtCoder, please provide test cases after contest, its very difficult to check all corner cases after contests also

→ Reply
»
11 months ago, # |
  Vote: I like it +13 Vote: I do not like it

When I was thinking of the problem D, I came up with using random.

Distinctly, the N^2 log N algorithm is common.

And after that, I considered using random. In more detail, I ramdomly chose 100 num (I called it as x) and checked if there is j satisfies (a[i],a[j],b[x]) is possible to form a triangle.

My program (https://atcoder.jp/contests/arc170/submissions/49557854) was accepted, but I wonder if anyone could hack it.

My English is not good, please forgive me for some naive syntax errors.

Thanks for your reading!

→ Reply
»
11 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

In the editorial of C , it is mentioned that when M >= N — 1 and N >= 2 , the answer is M^c , c -> number of zeroes. I don't think it is quite right. for eg. take S = 00100 , and M >= 5. As per above answer shall be M^4 , but it is actually (M-1)^4. I guess you meant (M — 1)^c ?

→ Reply
»
11 months ago, # |
  Vote: I like it +21 Vote: I do not like it

I finally upsolved A. Damn was it hard !!

I'm disappointed the official editorial don't provide "counter exemple" testcase to understand parentheses trick.

Example:

S:BAAAABBBBA
T:ABBBBAAAAB

I'm also disappointed no code solution is provided. Since ABC335, the editorial are often incomplete, i.e. with textual explanation and solution code.

x: textual explanation.
X: textual explanation + solution code.

--------A-B-C-D-E-F-G
ARC170:-x-x-x-x-x-x-x
ABC337:--------------
ABC336:-------X-x-x--
ABC335:---------X-x-X
ABC334:-X-X-X-X-X-X-X

Complete editorial is essential to upsolve and keep motivation.

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I realized that in E you can just use Berlekamp directly on the answer and the recurrence even has size at most $$$4$$$...

You can probably pass by calculating the first $$$8$$$ terms in $$$2^n$$$ or even by precalculating this recurrence offline. Now I find it more interesting that so little people ACed this problem

My code: https://atcoder.jp/contests/arc170/submissions/49586277 I was really about to bash the genfunc when I realized that this will just give me $$$O(1)$$$ linear reccurence

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody explain which testcase I am missing in problem A

https://atcoder.jp/contests/arc170/submissions/50050697

→ Reply