### maroonrk's blog

By maroonrk, history, 2 months ago, 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! Comments (27)
 » Scoring distribution looks friendly! I'll surely participate. GLHF!
•  » » 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.
•  » » » Ok. It's $\mathcal O(\sqrt N \log N)$.
 » I'd like to ask, why the contests' time aren't same all the time? Maybe you should make ABCs all on Saturday, and ARCs all on Sunday. I'd really like to see the changes! And as I am only available on Saturday, I will participate ARC, rather than ABC.
•  » » +1
 » C++20 support when
•  » » 2032
 » Good luck! Scoring distribution DOES look friendly! Wish everyone's rating increases!
•  » » 我要掉大粪的
•  » » » 《落坨翔子》
 » Great problem D, awesome generalization of the classic LIS (and hence a very natural problem statement).
 » 2 months ago, # | ← Rev. 3 →   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)std::ios::sync_with_stdio(false); std::cin.tie(nullptr); long long A, B; scanf("%lld %lld", &A, &B); long long g = std::__gcd(A, B); long long n = 0; while (A >= 1 && B >= 1) { A -= g; B -= g; std::swap(A, B); g = std::__gcd(A, B); ++n; } if (A == 0 || B == 0) printf("%lld", n) ; else printf("%lld", n-1) ;
•  » » Brute force only have no idea to pass this problem.
 » can anyone explain how to solve B? The editorial is slightly confusing.
•  » » My code is giving TLE after some test cases, could you please look once and optimize it? codestd::ios::sync_with_stdio(false); std::cin.tie(nullptr); long long A, B; scanf("%lld %lld", &A, &B); long long g = std::__gcd(A, B); long long n = 0; while (A >= 1 && B >= 1) { A -= g; B -= g; std::swap(A, B); g = std::__gcd(A, B); ++n; } if (A == 0 || B == 0) printf("%lld", n) ; else printf("%lld", n-1) ;
•  » » » you are manually performing the operations, ofcourse it will give TLE
•  » » 2 months ago, # ^ | ← Rev. 3 →   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$.
•  » » » 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?
•  » » » » 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.
 » 2 months ago, # | ← Rev. 2 →   Another round with 3200perf+unr_reg » Why my D code always Runtime Error and Wrong Answer? Can anyone help me? Code Link
 » 2 months ago, # | ← Rev. 2 →   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 :(
•  » » Do you mind explaining the idea?
•  » » » 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.
•  » » » » 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)$.
 » 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.
 » 7 weeks ago, # | ← Rev. 3 →   For D what should be the solution for this input?1 1, 2 7, 4 7, 10 15An 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 try1 1, 2 7, 4 8, 10 15The 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 — 1).bit_length() self.X = [unitX] * (self.n * 2) else: self.n = len(init) self.n = 1 << (self.n — 1).bit_length() # len(init)が2の累乗ではない時UnitXで埋める self.X = [unitX] * self.n + init + [unitX] * (self.n — 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(*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)