### hocky's blog

By hocky, history, 2 months ago,

## 1575A. Another Sorting Problem

Author: hocky
Developer: richiesenlia
Editorialist: hocky

Idea

## 1575B. Building an Amusement Park

Author: Panji
Developer: hocky, rama_pang
Editorialist: hocky, rama_pang

Idea

## 1575C. Cyclic Sum

Author: steven.novaryo
Developer: steven.novaryo
Editorialist: steven.novaryo

Idea

## 1575D. Divisible by Twenty-Five

Author: hocky
Developer: hocky
Editorialist: hocky

Idea
Short Solution

## 1575E. Eye-Pleasing City Park Tour

Author: steven.novaryo
Developer: rama_pang, hocky, steven.novaryo
Editorialist: rama_pang, steven.novaryo

Idea

## 1575F. Finding Expected Value

Author: rama_pang
Developer: rama_pang
Editorialist: rama_pang

Idea

## 1575G. GCD Festival

Author: Zap
Developer: hocky, Zap
Editorialist: rama_pang

Idea

## 1575H. Holiday Wall Ornaments

Author: hocky
Developer: Sakamoto, hocky
Editorialist: hocky, rama_pang

Idea

## 1575I. Illusions of the Desert

Author: JulianFernando
Developer: JulianFernando, hocky
Editorialist: hocky

Idea

## 1575J. Jeopardy of Dropped Balls

Author: richiesenlia
Developer: richiesenlia
Editorialist: hocky

Idea

## 1575K. Knitting Batik

Author: hocky
Developer: hocky
Editorialist: hocky

Fun fact
Idea

## 1575L. Longest Array Deconstruction

Author: Zap
Developer: steven.novaryo
Editorialist: steven.novaryo

Idea

## 1575M. Managing Telephone Poles

Author: Zap
Developer: steven.novaryo
Editorialist: steven.novaryo

Fun fact
Idea

• +102

 » 2 months ago, # |   +48 This contest is highly educational for me
 » 2 months ago, # |   +8 Hi can someone elaborate on the Divide and Conquer solution for problem L ?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 The DnC solution is more known as CDQ DnC. You can read more from the first search result of google. The link also contains a solution to the 3D LIS problem which can be applied in L.
 » 2 months ago, # |   0 Can anyone please tell in the editorial of G, how to conclude $\sum _{y} \phi (y) ( \sum _{i=1} ^{\lfloor \frac n x \rfloor} [a_{ix} mod y = 0])^{2}$ $from$ $\sum _{i=1} ^{\lfloor \frac n x \rfloor} \sum _{j=1} ^{\lfloor \frac n x \rfloor} \sum _{y \in d(a_{ix},a_{jx})} \phi (y)$
•  » » 2 months ago, # ^ |   +32 $\sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lceil \frac{n}{x} \rceil} \sum_{y \in d(a_{ix}, a_{jx})} \phi(y)$ $\sum_{y} \phi(y) \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} [a_{ix} \bmod y = 0 \land a_{jx} \bmod y = 0]$ $\sum_{y} \phi(y) \sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} [a_{ix} \bmod y = 0] \sum_{j = 1}^{\lfloor \frac{n}{x} \rfloor} [a_{jx} \bmod y = 0]$ $\sum_{y} \phi(y) \left(\sum_{i = 1}^{\lfloor \frac{n}{x} \rfloor} [a_{ix} \bmod y = 0]\right)^2$
 » 2 months ago, # | ← Rev. 2 →   +24 I have solution for problem L in Square Root decomposition.We divide the complete array into $SQRT$ blocks. For each block, we maintain, $dp[BLOCK][LEN]$, which shows maximum score we can achieve by using subsequence of size $LEN$ up-to $BLOCK$. How to update? We have 2 updates: $dp[BLOCK+1][LEN]$ can be updated from $max(dp[BLOCK][LEN-k])$ for all $k \leq SZ$ where $SZ$ is size of each $BLOCK$. To solve this, we can use maximum over all segments of size $SZ$, which is a standard problem using deque.There is another transition, when subsequence increases in value inside the $BLOCK$ to be updated. For that we can use $sqrt(n)^{2}$ dp inside the $BLOCK$.Code: 130653046
 » 2 months ago, # | ← Rev. 2 →   0 Can you provide your implementation for problem G? My solution had the same complexity but it got TLE.
•  » » 2 months ago, # ^ |   0 Here is my solution (same as editorial) 130644884
•  » » » 6 weeks ago, # ^ |   0 Thanks
•  » » 2 months ago, # ^ |   +8 It seems that the many modulo operations are the reason for TLE, as it is a very expensive operation.Here is your code, but with the modulo operations removed. In custom invocation, this speeds up your code by 4-5 times. As a side note, the answer comfortably fits in long long data type (the maximum answer is less than $10^{16}$).
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Somehow I never realized that sum of $gcd(i, j)$ for $1 \le i, j \le n$ is not that large. Thanks for the answer.
 » 2 months ago, # |   0 An easier way to achieve the second complexity in B is to binary search on $log(answer)$.
 » 2 months ago, # | ← Rev. 2 →   0 Can someone explain H a little bit better?
•  » » 7 weeks ago, # ^ |   +5 I'll explain to you the way I did it: (if you don't know kmp you need to learn it first cause it won't make sense otheriwse) dp[posInA][bPrefix][matches] is the minimum amount of characters you need to change in (1...posInA) in order to have 'matches' nr of ocurences of B in (1...posInA) AND the last 'bPrefix' elements of (1...posInA) in our changed A is the same as the first 'bPrefix' elements in B. Now for the transitions: We'll need to precalculate the prefix function for b like in kmp. And now we'll do the transitions forward-style. So we're in a dp[posInA][posInB][matches]. We can either make a[posInA + 1] a 0 or a 1. We try both, and now we need to calculate the new prefix and the new number of matches. If you know kmp the new prefix is gonna be pretty easy to understand, if it isn't clear from my code I can explain it to you. And the matches get increased by 1 whenever the prefix is m Code: https://codeforces.com/contest/1575/submission/132549880
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Thanks a lot for your explanation, I finally understand this dp!But I think your implementation works in $O(n^4)$ (actually it's divided by some big constant, but it's still $O(n^4)$).To see why, imagine a string $1111...111$, to calculate the transition when you change $i$-th symbol to $0$ for each $i$, you need $O(n^2)$ operations in total, because prefix function for this string looks something like $0, 1, 2, 3, \dots , m-1$. You calculating this transitions for each $k$ and for each $i$, so it's $O(n^2*n^2) = O(n^4)$The solution here is for each $pre$ calculate transition first and then for each $k$ update your $dp$, because $pre$ for each $k$ will be the same.
•  » » » » 6 weeks ago, # ^ |   0 Okay, tell me if I'm wrong but I actually think it softens to n^3. Even though one transition might be o(n), that means the newPrefix is gonna be 0. And now the next prefix can only increase by one. It's the same reasoning as to why KMP is o(n), that pre can only increase by 1 every step and every extra operation necessarily decreases it. I think a really important part is that I check if a dp state is valid before I calculate off of it.
•  » » » » » 6 weeks ago, # ^ |   0 It seems that checking if a dp state is valid gives $O(n^3)$. Sorry, I didn't pay much attention to this line of code.
 » 6 weeks ago, # |   0 Does classic LIS really work for L? it's not really clear how to compare pairs (a[i], i-a[i]). if we're using dp[i]-> min pair which the sequence of length i ends in.Also I tried using 2D BIT and I'm getting TLE 3. Would be nice to know what the author had in mind by "standard LIS algorithm"
•  » » 6 weeks ago, # ^ |   0 You just compare pairs the normal way :think:. First priority first element, then second element if first element equal.
•  » » » 6 weeks ago, # ^ |   0 That doesn't work because we need both components of the pair to increase simultaneously
 » 6 weeks ago, # |   0 How to do problem J with DSU as explained in the editorial?
 » 6 weeks ago, # |   0 Can someone share the editorial for it?
 » 3 weeks ago, # |   0 In problem G:What is the process of thinking that will lead to such a solution ? I mean I knew the key idea for the solution but it never occurred to me to use Euler function here