Can someone please help me on how to approach this Problem

Thanking you in anticipation.

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

1 | tourist | 3843 |

2 | jiangly | 3705 |

3 | Benq | 3628 |

4 | orzdevinwang | 3571 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3530 |

8 | ecnerwala | 3499 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

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

1 | maomao90 | 171 |

2 | awoo | 163 |

3 | adamant | 162 |

4 | TheScrasse | 158 |

5 | nor | 153 |

5 | maroonrk | 153 |

7 | -is-this-fft- | 152 |

8 | Petr | 146 |

9 | orz | 145 |

10 | pajenegod | 144 |

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: Jun/17/2024 00:45:00 (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?