### Agnimandur's blog

By Agnimandur, 9 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

• +73

 » 9 months 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.
•  » » 9 months 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.
•  » » » 9 months ago, # ^ |   +1 Sorry, it's already been deleted.Ask the questions again and I will respond! .
 » 9 months ago, # | ← Rev. 2 →   0 Can anyone please point out what's wrong with my code for 2D? 125022309 Getting Runtime error on test 3
•  » » 9 months ago, # ^ |   0 I prefer a segment tree to a sparse table :v
•  » » 9 months 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.
•  » » » 9 months ago, # ^ |   +6 Thanks for pointing that out. It worked
•  » » » » 9 months ago, # ^ |   +6 You're welcome.
 » 9 months 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
•  » » 9 months ago, # ^ |   0 Can you explain your check function?
•  » » » 9 months 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)
•  » » » » 9 months ago, # ^ |   0 I think something is wrong with your binary search implementation.
 » 9 months 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 thanks for the editorial
 » 9 months 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
•  » » 9 months 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.
 » 9 months ago, # |   0 in problem E，could give the code by way in the solution 2？ please，i really want to know，it's so exciting.
 » 9 months ago, # | ← Rev. 3 →   0 Here is a solution without the segment tree, just using prefix and suffix array for problem D solution
 » 9 months 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?
•  » » 6 months ago, # ^ |   0 can you explain your sol thoroughly? because i think two pointer will not work in this i guess.
 » 8 months 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.
 » 8 months ago, # |   0 Agnimandur proof for B please
 » 4 months ago, # |   0 int div2 D I used segment tree then used binary search for each index to find the farthest point where gcd is not 1. according to me it should be under the given time limit. 143473490this is my submission which gave tle but using 2 pointer was under the limit