Can someone please help me on how to approach this Problem

Thanking you in anticipation.

# | User | Rating |
---|---|---|

1 | tourist | 4009 |

2 | jiangly | 3821 |

3 | Benq | 3736 |

4 | Radewoosh | 3631 |

5 | jqdai0815 | 3620 |

6 | orzdevinwang | 3529 |

7 | ecnerwala | 3446 |

8 | Um_nik | 3396 |

9 | ksun48 | 3388 |

10 | gamegame | 3386 |

# | User | Contrib. |
---|---|---|

1 | cry | 164 |

1 | maomao90 | 164 |

3 | Um_nik | 163 |

4 | atcoder_official | 161 |

5 | -is-this-fft- | 158 |

6 | awoo | 157 |

7 | adamant | 156 |

8 | TheScrasse | 154 |

8 | nor | 154 |

10 | djm03178 | 153 |

Can someone please help me on how to approach this Problem

Thanking you in anticipation.

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/11/2024 14:36:18 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

for query you can use sparse table or segment tree

HintUse a range query data structure such as segment tree/sparse table.

SolutionThe 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 seemed`O(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 the`i`

pointer from`j`

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 .