maroonrk's blog

AtCoder Regular Contest 159 Announcement
By maroonrk, history, 20 months ago, In English

We will hold AtCoder Regular Contest 159.

The point values will be 300-400-500-600-900-900.

We are looking forward to your participation!

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

Comments Comments (23)
| Write comment?
»
20 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Scoring distribution looks friendly! I'll surely participate. GLHF!

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

    Nice round! I can get a large positive delta this time.

    Wrote a strange solution of B and it passed quickly. Idk whether it's right or weak data.

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

      Ok. It's $$$\mathcal O(\sqrt N \log N)$$$.

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

C++20 support when

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

Good luck! Scoring distribution DOES look friendly! Wish everyone's rating increases!

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

Great problem D, awesome generalization of the classic LIS (and hence a very natural problem statement).

→ Reply
»
20 months ago, # |
← Rev. 3   Vote: I like it -53 Vote: I do not like it

Got TLE again and again on B problem (36/41). This 2sec time limit sucks :(
Can someone tell me how I can optimize this further..

My Code (B-problem)
→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain how to solve B? The editorial is slightly confusing.

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it -45 Vote: I do not like it

    My code is giving TLE after some test cases, could you please look once and optimize it?

    code
    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      you are manually performing the operations, ofcourse it will give TLE

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

    Let $$$g = \text{gcd}(a, b)$$$. Suppose $$$a < b$$$.

    • $$$(a, b)$$$ is equivalent to $$$(a / g, b / g)$$$. Then, you can assume $$$a, b$$$ coprime.
    • Goal: get a $$$g > 1$$$ (it's enough to find it $$$O(\log b)$$$ times, because you are halving $$$b$$$ every time).
    • Let $$$(a, b) = (a, a+d)$$$. While $$$(a, a+d)$$$ are coprime, you subtract $$$1$$$ from both, so you get $$$(c, c+d)$$$ ($$$c = a, a-1, \dots$$$). Recall that, when $$$c, c+d$$$ are not coprime, $$$g > 1$$$.
    • So, you have to find the maximum $$$c \leq a$$$ such that $$$\text{gcd}(c, c+d) = \text{gcd}(c, d) > 1$$$. So, $$$c$$$ must be multiple of some prime $$$p$$$ that divides $$$d$$$. Find such primes in $$$O(\sqrt{d})$$$. Then, the candidate $$$c$$$ are the $$$p \cdot \lfloor \frac{d}{p} \rfloor$$$.
    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For some reason I still can't understand the idea behind B? I don't get why you can take a, b and perform a//g and b//g, when g != 1 for starters. How can that be the same thing?

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

        Try to simulate operations starting from $$$(a, b)$$$ and from $$$(a/g, b/g)$$$. You will notice that all the partial results in the first case are the same as in the second case, multiplied by $$$g$$$ (and it should be easy to prove). So, you will reach $$$0$$$ at the same moment.

        → Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it +74 Vote: I do not like it

Another round with 3200perf+unr_reg

wtf.png

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

Why my D code always Runtime Error and Wrong Answer? Can anyone help me? Code Link

→ Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Actually, we can find the minimum number of operations required for problem C (code). Though it was much harder to implement than simply constructing one, and I couldn't manage to finish it during contest time :(

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

    Do you mind explaining the idea?

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

      First we iterate through all $$$s$$$, and check whether we can make all elements equal using exactly $$$s$$$ steps. We can easily get rid of the case where the sum doesn't fit and some other trivial cases, so now we try to find a way to make every element $$$V$$$ in $$$s$$$ steps.

      Note that if we construct a $$$n\times n$$$ matrix $$$M$$$ where $$$0\le m_{i,j}\le s$$$ denotes the number of permutations where $$$p_i=j$$$, if the matrix satisfy the constraint that every row and every column sum up to $$$s$$$, we can always find $$$s$$$ permutations that corresponds to this matrix. This can be done using bipartite matching in $$$O(sn\sqrt n)$$$ time, which is obviously enough since $$$s\le 10^4$$$. Thus we try to find this matrix with the additional condition that for all $$$i$$$ , $$$\sum_{j=1}^n j\times m_{i,j}=V-a_i$$$.

      Instead of the original matrix, we try to construct the suffix sum matrix $$$A$$$, such that $$$A_{i,j}=\sum_{k=j}^n m_{i,j}$$$, now we re-write the constraints on $$$A$$$: row sum equals $$$V-a_i$$$, column sum equals $$$(n-i+1)s$$$, $$$A_{i,1}=s$$$, and $$$A_{i,j}\ge A_{i,j+1}$$$.

      Since the constraint on row sum is annoying, we first construct any such matrix without this condition. This can be done easily by greedy or whatever method. Then we try to adjust this matrix so that every row satisfy the constraint without breaking the other ones. Let $$$b_i=V-a_i-\sum_{j=1}^n A_{i,j}$$$, then if all $$$b_i=0$$$, we are finished. Otherwise, WLOG, suppose $$$b_1$$$ is the smallest one, then we need to move some other elements to this row to make this row good. To do this, we simply iterate through all $$$i$$$ such that $$$b_i\ge 0$$$, and for every $$$j$$$, we can calculate the maximum value that can be subtracted from $$$A_{i,j}$$$ and can be added to $$$A_{1,j}$$$ without violating other constraints (we can only care about whether $$$A_{i,j}\ge A_{i,j+1}$$$ here because the other conditions are always ok). We keep doing this until all $$$b_i=0$$$, in which case we have constructed the matrix succesfully, or we can't make the smallest value bigger, which results in a failure.

      Now we analyse the complexity. Let $$$v$$$ be the number of $$$i,j$$$ such that $$$A_{i,j}\ne A_{i,j+1}$$$. Since when we move every time, we make at least one $$$A_{i,j}=A_{i,j+1}$$$ or we make at least one $$$b_i=0$$$. Though it is possible that previously $$$A_{i,j}=A_{i,j+1}$$$, and later we make $$$A_{i,j+1}=A_{i,j+2}$$$, when we iterate through all $$$j$$$, $$$v$$$ decreases by at least $$$1$$$ every time we move from an $$$i$$$, and $$$v$$$ never increases. Since $$$v$$$ is at most $$$O(n^2)$$$, and it takes $$$O(n)$$$ time to move from $$$i$$$, the complexity for checking is $$$O(n^3)$$$. Since the answer is always less than $$$O(n^2)$$$, the total complexity is $$$O(n^5)$$$. However, we can never actually reach this upper bound since 1. the minimum number of operations is far fewer than $$$n^2$$$, and 2. the number of operations needed to adjust the matrix is far fewer than $$$n^3$$$ since it is just a theoretical bound.

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

        Note: if it's possible in $$$s$$$ steps, it's also possible in $$$s+2$$$ steps. So, you can binary search odd and even $$$s$$$, and the complexity becomes $$$O(n^3 \log n)$$$.

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

Can anyone explain the O(n) solution of the F problem (official editorial)? Even though I've gotten AC, I still can't understand the official editorial.

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

For D what should be the solution for this input?

1 1, 2 7, 4 7, 10 15

An Accepted solution return the result = 11. But I think the solution is 13 is it not? Writing this out I get X = 1, 2, 3, 4, 5, 6, 7, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15 It seems plain to me that I would take 1,2,3,4,5,6,7,10,11,12,13,14,15 as the longest strictly increasing subsequence?

Maybe I found a missing testcase actually cause If I try

1 1, 2 7, 4 8, 10 15

The same accepted solution gives 14, which is the answer I would expect for this.

This is the solution that seems to give these, It was written from someone else I was just learning it, and realized it didn't make sense on a test input I came up with. 

class SegmentTree():
    """UnitXは単位元、fは区間で行いたい操作、initは自然数あるいは配列"""
    def __init__(self, init, unitX, f):
        self.f = f # (X, X) -> X
        self.unitX = unitX
        self.f = f
        if type(init) == int:
            self.n = init
            self.n = 1 << (self.n &mdash; 1).bit_length()
            self.X = [unitX] * (self.n * 2)
        else:
            self.n = len(init)
            self.n = 1 << (self.n &mdash; 1).bit_length()
            # len(init)が2の累乗ではない時UnitXで埋める
            self.X = [unitX] * self.n + init + [unitX] * (self.n &mdash; len(init))
            # 配列のindex1まで埋める
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
    
    def update(self, i, x):
        """0-indexedのi番目の値をxで置換"""
        # 最下段に移動
        i += self.n
        self.X[i] = x
        # 上向に更新
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
            i >>= 1
    
    def getvalue(self, i):
        """元の配列のindexの値を見る"""
        return self.X[i + self.n]
    
    def getrange(self, l, r):
        """区間[l, r)でのfを行った値"""
        l += self.n
        r += self.n
        al = self.unitX
        ar = self.unitX
        while l < r:
            # 左端が右子ノードであれば
            if l & 1:
                al = self.f(al, self.X[l])
                l += 1
            # 右端が右子ノードであれば
            if r & 1:
                r -= 1
                ar = self.f(self.X[r], ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)
 
R = []
Q = []
N = 4
arr = [(1, 1), (2, 7), (4, 7), (10, 15)]
for l, r in arr:
    R.append(r)
    R.append(l)
    Q.append([l,r])
dic = {num:i for i, num in enumerate(list(sorted(set(R))))}
st1 = SegmentTree([0]*len(dic),-float('inf'),max)
st2 = SegmentTree([-float('inf')]*len(dic),-float('inf'),max)
res = 0
for l,r in Q:
    nn = r-l+1
    m1 = st1.getrange(0,dic[l])
    m2 = st2.getrange(dic[l],dic[r])
    nn = max(nn,m1+r-l+1,m2+r)
    st1.update(dic[r],nn)
    st2.update(dic[r],nn-r)
    res = max(res,nn)
print(res)
→ Reply