### Agnimandur's blog

By Agnimandur, 18 months ago, All the division 2 problems were created by Agnimandur. 1548E - Gregor and the Two Painters was created by Benq. I hope that this hint-based editorial helps you, no matter what your rating is! Solution code is provided in both C++, Java, and Kotlin when available.

Hint 1
Solution

Hint 1
Hint 2
Solution

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Hint 1
Hint 2
Solution

Hint 1
Hint 2
Hint 3
Solution

Hint 1
Hint 2
Hint 3
Solution

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

## 1548E - Gregor and the Two Painters

Hint 1
Hint 2
Solution Tutorial of Codeforces Round #736 (Div. 1) Tutorial of Codeforces Round #736 (Div. 2) 736, div1, Comments (20)
| Write comment?
 » 18 months ago, # | ← Rev. 2 →   Sorry about having to create a new editorial!The old one passed some character limit built into Codeforces. Whenever I attempted to edit the old one, I was re-directed to the bug page, and the edit was not saved!Thus, the editorial went offline for a while. Ultimately, a new and shorter editorial, was the only viable solution.
•  » » Could you post the old editorial page without the edits? There were several helpful (at least for me) discussions about GCD and solution of 1549D - Integers Have Friends without segment tree and sparse table.
•  » » » Sorry, it's already been deleted.Ask the questions again and I will respond! .
 » 18 months ago, # | ← Rev. 2 →   Can anyone please point out what's wrong with my code for 2D? 125022309 Getting Runtime error on test 3
•  » » The iterator j should iterate in log(n). You're iterating it till n, this is trying to access out of bound memory. Thus the error.
•  » » » Thanks for pointing that out. It worked
•  » » » » You're welcome.
 » 18 months ago, # | ← Rev. 3 →   Can anyone please help me debug my solution for div 2 problem D. I am getting WA on test case 5. Basically what I am doing is implementing binary search on the answer and if I find that lets say answer k is possible then I am searching for answer > k, and if answer k is not possible then I am searching for < k.WA SolutionIf my logic is wrong you are most welcome to correct it :)UPDATE: Got it friends, there was a little problem in binary search implementation. AC Solution
•  » » Can you explain your check function?
•  » » » So the param that I am passing to the function is the answer that I want to check whether it is possible or not. For this I am forming 2 arrays where array pre will store GCD of all the elements from index i to index j and suf will store GCD of all the elements from index j to i+m-1. And if you analyze it you can see that if(__gcd(suf[i], pre[i+m-1])!=1)return true; this piece of code will return true if GCD of m elements starting from i is > 1. If it is true then we can say that our array b has at least one subarray of size m who's GCD>1.(The main motive behind forming pre and suf arrays is to find GCD of any subarray of length m in O(1) time)
•  » » » » I think something is wrong with your binary search implementation.
 » I can't understand how getting the value of p(k) can help in 1549E? How to expand it? What is polynomial long division? How to get the sum of coefficients of k^x? Also, a implementation with sufficient comment for this type of editorial would be good for Pupil like me.
 » thanks for the editorial
 » Solution for D div2 (B div1) without segment trees, sparse table:After building the difference array $D$, for each $r$ we will maintain a list of uniques gcds that we can get if we start at position $r$ going backwards, i.e. all the possible values of $gcd_{l \dots r}=gcd(D_l, D_{l+1}, \dots, D_r)$ for all $1 \leq l \leq r$. Also for each value $g$ of this list we will also keep the maximum $length$ such that $gcd_{r-lenght+1 \dots r}=g$ so that we can update the answer for the problem. We can simulate all this process with a map.Key observation: The size of the list at each iteration (that is, the number of unique gcds) is $O(\log MX)$, where $MX$ is the maximum value of $D_i$. That's because $gcd_{i \dots r}$ is a divisor of $gcd_{i + 1 \dots r}$ for each $1 \leq i < r$. So if $gcd_{i \dots r}$ is different from $gcd_{i + 1 \dots r}$, then $gcd_{i \dots r} \leq gcd_{i + 1 \dots r} / 2$.Based on that, total complexity will be $O(n \cdot \log^2 MX)$ (the second $log$ is for the $gcd$ complexity). But maybe using the analysis of this blog (also cited in the editorial) the complexity can go down to $O(n \cdot \log MX + \log^2 MX)$ or $O(n \cdot \log MX \cdot \log \log MX + \log^2 MX)$ if you take into account the map complexity.Link to my submission
•  » » I have another approach to get around the log factor from segtree / sparse table.I used a two pointer approach to find the subarray and represented the elements with a queue that always knows the gcd of contained elements. The technique is better known as a min-queue but same applies for gcd. It can be implemented with linked lists or like I did with two stacks. Here is my submission.
 » 17 months ago, # | ← Rev. 3 →   Here is a solution without the segment tree, just using prefix and suffix array for problem D solution
 » Has anyone solved Div2D with Segment tree?. I am getting TLE with two pointers{ increase right pointer till gcd >1 in the difference array} and take the maximum size of all valid subarrays.Here is my submission : 126619908Is there any scope for improvement here?
•  » » can you explain your sol thoroughly? because i think two pointer will not work in this i guess.
 » F2:After I got struggled for hours with why "B is always even", I found "the area of the fence is an integer" in the problem statement.QwQ.
 » Hello in english