Can someone please help me on how to approach this Problem
Thanking you in anticipation.
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 151 |
Can someone please help me on how to approach this Problem
Thanking you in anticipation.
Name |
---|
for query you can use sparse table or segment tree
Use a range query data structure such as segment tree/sparse table.
The solution that I found most common after having solved the problem was using a range query data structure to answer queries on range [L, R] efficiently. I used a RQ DS too and so I'll explain a solution that uses segment tree.
For a fixed point L, find the left most right boundary R such that $$$gcd([L, ..., R])$$$ is 1. Once we have such a value R, we can now move the left boundary. For any index i in [L, R], the $$$gcd([i, ..., R])$$$ will either be 1 or something greater. When we encounter a left boundary that makes gcd to something not 1, we start searching for another right boundary keeping the left boundary fixed. Among all such [L, R] endpoints, the one with maximum length is your answer.
The solution using RQ DS is, imo, the most intuitive. The complexity you achieve this way is $$$O(n.log(n))$$$. You can use either segment tree or sparse table or any other logarithmic query associative DS to achieve this complexity. Note that the complexity actually seems like it's $$$O(n.log^2(n))$$$ because of gcd being in there but finding the gcd of an entire array is magically $$$O(n)$$$ approximately and not $$$O(n.({some \space log \space factor}))$$$.
There also is a solution that uses something called a gcdqueue which is similar in structure to this but I do not understand it and will not explain.
I solved it this way: https://github.com/actium/cf/blob/master/edu/09/2g.cpp
I actually am not able to understand with this is
O(n)
. At first glance it seemedO(n^2)
to me.What I thought was, for every
j
, the remove function in the tutorial in worst case removes no elements, which is analoguous here to moving thei
pointer fromj
to the start (j
times).So the no of iterations in the worst case:
1+2+3...n = O(n^2)
Please let me know if I have made any mistake at any point... Would really appreciate the help...
getting tle or accepted ?
In tutorial, we can easily get max/min when adding an element, but it's hard to remove an element.
How does the tutorial solve it?
It uses two stacks to implement the queue, and get the result of max/min from two of the stack to get the result.
Can we just replace it with other merge function?
This was my solution, I suggest that you read through the theory in step 2 segment with small spread. It's sad to see that there is no proper editorial for the problems in edu.
saisumith770 Can you please clarify will these work for problem like, to find the smallest segment with all gcds in it to be 10 , if not then -1.
Suppose
n=6 arr = [15,30,10,20,30,40] and gcd of all in segment should be 10
Here the ans will be 1 with [10] as segment .
Will this code work for anything other than 1 as gcd ?
And also even if it is to find the gcd as 1, it wont work , suppose n=5 arr = [3,6,9,4,6]
here ans should have been 3 but it is giving -1.
Your code is considering only those segments which start from first ele .