Обсуждение @ 1846. НОД 2010 @ Timus Online Judge

havaliza Solve without Segment Tree [11] // Задача 1846. НОД 2010 18 сен 2011 22:58

Is this problem solvable in any other way not using Segment Tree?
Can this problem solved using Fenwick Tree?

Vit Demidenko Re: Solve without Segment Tree // Задача 1846. НОД 2010 19 сен 2011 08:44

gcd ~ min
but, we can't use fenwick tree, because, when update, new minimum should be no more than previous.

but I could be wrong :)

kleninz Re: Solve without Segment Tree // Задача 1846. НОД 2010 19 сен 2011 09:52

I used gcd tree and set. And I got TL 17. Then I remade my recursive update function to nonrecursive. I got AC. Then I remade my recursive get_gcd function to nonrecursive function. AND GOT TL AGAIN!

Kirill Borozdin Treap [1] // Задача 1846. НОД 2010 19 сен 2011 20:26

Using a treap is another nice way.
AC 0.296 without any optimizations (and 0.234 after some :) )

Edited by author 20.09.2011 21:38

Jumbo Re: Treap // Задача 1846. НОД 2010 18 июл 2012 17:55

I got TL with treap ><, it's strange.
Can someone help me?
Code here: http://www.everfall.com/paste/id.php?bkqpp0lvnsye

Edited by author 18.07.2012 17:56

Edited by author 18.07.2012 17:56

Pavel Kovalenko Re: Solve without Segment Tree [4] // Задача 1846. НОД 2010 20 сен 2011 20:38

I use SQRT-decomposition. Accept 0.468 on Java.

ibra (TNU) Re: Solve without Segment Tree // Задача 1846. НОД 2010 20 сен 2011 21:21

I also solved it by Sqrt-decomposition. Accept 0.292 on C++

Xun Li Re: Solve without Segment Tree // Задача 1846. НОД 2010 23 апр 2012 23:11

Could you explain a little more about "SQRT-decomposition" or where I can find an introduction to it?
I tried google it but it's nowhere.
Thanks!

Xun Li What is SQRT-decomposition? [1] // Задача 1846. НОД 2010 24 апр 2012 10:42

Could you explain a little more about "SQRT-decomposition" or where I can find an introduction to it?
I tried google it but it's nowhere.
Thanks!

Jumbo Re: What is SQRT-decomposition? // Задача 1846. НОД 2010 19 июл 2012 15:35

http://translate.google.ru/translate?hl=ru&sl=ru&tl=en&u=http%3A%2F%2Fe-maxx.ru%2Falgo%2Fsqrt_decomposition

async_prince Augmented BST [1] // Задача 1846. НОД 2010 1 окт 2011 21:07

I used balanced bst (AVL tree), keeping GCD for each subtree. Got 0.39
Thought about segment tree but found it not so elegant. How does your segment tree solution look?

ibra, Pavel Kovalenko, thanks for sqrt-decomposition hint!

Edited by author 01.10.2011 21:08

vlyubin Re: Augmented BST // Задача 1846. НОД 2010 10 фев 2012 07:36

Did you use some modifications to Sqrt-decomposition? I seem to be unable to AC it. I use C++ (on Java it's a bit tougher) and I use multiset for storing integer, not a vector. I get TLE 22 ... I tried to modify sizes, but that doesn't seem to help.Did you use Sqrt-decomp twice?

Обсуждение задачи 1846. НОД 2010