### Agnimandur's blog

By Agnimandur, 3 years 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
• +73

| Write comment?
 » 3 years ago, # | ← Rev. 2 →   +65 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.
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   +1 Sorry, it's already been deleted.Ask the questions again and I will respond! .
 » 3 years ago, # | ← Rev. 2 →   0 Can anyone please point out what's wrong with my code for 2D? 125022309 Getting Runtime error on test 3
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   +6 Thanks for pointing that out. It worked
•  » » » » 3 years ago, # ^ |   +6 You're welcome.
 » 3 years ago, # | ← Rev. 3 →   0 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
•  » » 3 years ago, # ^ |   0 Can you explain your check function?
•  » » » 3 years ago, # ^ |   0 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)
•  » » » » 3 years ago, # ^ |   0 I think something is wrong with your binary search implementation.
 » 3 years ago, # |   +3 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.
•  » » 9 months ago, # ^ |   0 I think the main idea of the solution is the fact that p(k) is the generating function of the answer, so calculate the coefficients of p(k) is like calculate the answers themselves. To calculate p(k), we rewrite p(k) as a geometric series and then use polynomial division to calculate the coefficients
 » 3 years ago, # |   0 thanks for the editorial
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ |   +5 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.
 » 3 years ago, # | ← Rev. 3 →   0 Here is a solution without the segment tree, just using prefix and suffix array for problem D solution
 » 3 years ago, # |   0 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?
•  » » 3 years ago, # ^ |   0 can you explain your sol thoroughly? because i think two pointer will not work in this i guess.
 » 3 years ago, # |   0 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.
 » 20 months ago, # |   0 Hello in english
 » 9 months ago, # |   0 Regarding problem D. If i use binary search submission 218897364 it gives TLE. if i use two pointers submission 218907845 it gets Accepted.Can anyone please figure out why ?.
 » 2 months ago, # |   0 There exists a somewhat different solution (albeit with the same time complexity) for D1E if we consider rows as "representatives" instead of cells. It can be implemented in a somewhat simpler manner using dsu and sets: 252411144