Need help , Please! [ CF Round #736(Div. 2)

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
20:56:50
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя Muhammad_mhs

Need help , Please! [ CF Round #736(Div. 2) — D ]

Автор Muhammad_mhs, история, 3 года назад, По-английски

My approach to solving this problem was the segment tree with O(n(logn)^2) complexity. but It gives me TLE.

My Submission: 124635301

Please, anyone, help me why this solution gives me TLE

Thanks in advance.

Muhammad_mhs
3 года назад
26

Комментарии (26)

Написать комментарий?

Spartan20859

3 года назад, # |

In my opnion $$$O(nlog^2n)$$$ is too slow for this problem. And the constant time complexity is naturally bigger for Segment Tree.

Why not try using the Spharse Table? And binary searching the solution of each start i is unnecessary. You can simply use a two-pointer method to get the maximum right segment point of each start i.

If you insist your method, then I recommend you use a quicker input method, instead of cin.

This is my code.

→ Ответить

Spartan20859

3 года назад, # ^ |

← Rev. 2 →

Total time complexity is $$$O(nlognlog(max {{a_i}} ))$$$ for initializing the Spharse Table, and $$$O(nlog(max {{a_i}} ))$$$ for getting the answer.

→ Ответить

gupta_samarth

3 года назад, # ^ |

You need to note that, for both Sparse Table and Segment Tree, the complexity will have additional factor of $$$log(MAX)$$$ because combining function is $$$gcd(x, y)$$$.

→ Ответить

Spartan20859

3 года назад, # ^ |

Ahh,yes. I forgot that.

→ Ответить

Muhammad_mhs

3 года назад, # ^ |

I have used ios::sync_with_stdio(0);cin.tie(0); for quicker input method. I have got my mistake. Now, I will try that with the sparse table.

Thanks a lot.

→ Ответить

Piccolo

3 года назад, # ^ |

Can you explain the O(NlogN) method? I think the gcd operator will add an additional logN into the total time complexity.

→ Ответить

caan_do

3 года назад, # |

Since gcd is built into the segment tree, each range query actually has a complexity of O(logn log1e18), which when combined with the binary search, results in a total time complexity of O(n (log n)^2 log1e18). This ends up being too slow. If you still wish to use a segment tree approach, consider changing the binary search to a 2-pointers approach that reduces it to O(n logn log 1e18), which passes under the time limit.

→ Ответить

Muhammad_mhs

3 года назад, # ^ |

Thanks a lot, dear.

→ Ответить

harpreet1237

3 года назад, # ^ |

Thanks for the explanation.

→ Ответить

Tet

3 года назад, # ^ |

← Rev. 2 →

No, you are wrong. GCD is in fact $$$O(log(min(a, b) / ans))$$$, thus the answering each query with segtree is $$$O(log(n) + log(max_A))$$$ which turns out to be good enough for doing binary search. Here's my in contest submission which passed the system tests. $$$O(n \cdot log(n) \cdot (log(n) + log(max_A)))$$$: 124574566.

→ Ответить

gagannagpal68

3 года назад, # ^ |

It's a very nice observation.

→ Ответить

caan_do

3 года назад, # ^ |

That is a very careful observation. Nevertheless, given the large constant factor of a segment tree, it might be best to avoid using binary search, which fails when not using 64-bit.

→ Ответить

epsilon_573

3 года назад, # ^ |

← Rev. 2 →

Can you please elaborate on the GCD complexity?

→ Ответить

Tet

3 года назад, # ^ |

This should help.

→ Ответить

epsilon_573

3 года назад, # ^ |

That was really helpful, thanks :)

→ Ответить

shubham84

3 года назад, # |

Can anyone tell how to get rid of Memory Limit Exceeded. I have implemented a segment tree with two pointer approach.

My Submission:124646523

→ Ответить

Muhammad_mhs

3 года назад, # ^ |

Your query function return int type data. but range gcd can be cross int limit.

→ Ответить

shubham84

3 года назад, # ^ |

Actually in my code i have defined int as long long, although it is not a good practice.

→ Ответить

Muhammad_mhs

3 года назад, # ^ |

And also there is a corner case that is n = 1. You have to fix this case.

→ Ответить

shubham84

3 года назад, # ^ |

Could you share your segment tree accepted solution, it will help a lot.

→ Ответить

Muhammad_mhs

3 года назад, # ^ |

your code doesn't work for n = 1.

My Solution: 124641397

→ Ответить

shubham84

3 года назад, # ^ |

Thanks for the help, it got accepted. The problem was that i was creating new array for every testcase, just fixed it and also the n==1 corner case.

→ Ответить