You are not logged in. Please login at www.codechef.com to post your questions!

×

Square root Decomposition

What is Square root Decomposition? I was reading editorial of a problem on hackerrank and came acroos this term.

I tried searching on google, read various forums but couldn't understand how this could optimise a code.

Can anyone please provide a simple explanation of this problem and give a clear, easy and intuitive code for the same?

Thanks in advance :)

asked 03 May '17, 14:34

shraeyas's gravatar image

3★shraeyas
1.3k2618
accept rate: 10%


Square root decomposition is a great way to deal with range queries. This geeksforgeeks article explains it very well:

http://www.geeksforgeeks.org/mos-algorithm-query-square-root-decomposition-set-1-introduction/

This video by @gkcs is very easy to understand:

https://www.youtube.com/watch?v=hqaRYgsLpUI

link

answered 03 May '17, 14:38

abdullah768's gravatar image

6★abdullah768
2.4k420
accept rate: 17%

edited 03 May '17, 14:41

how to write on a new line? Pressing enter doesn't seem to work :/

(03 May '17, 14:39) abdullah7686★
3

Press enter two times :)

(03 May '17, 14:40) shraeyas3★
1

Welcome to codechef @abdullah768 . It took me 15 days to figure that thing out XD

(03 May '17, 14:41) vijju123 ♦♦5★

That worked, Thanks.

(03 May '17, 14:41) abdullah7686★

Square root decomposition is a concept explained by Sergey kulik as well.
I saw it once after last years Snackdown....
Video link:https://m.youtube.com/watch?v=VGq6w9TlJBY

link

answered 03 May '17, 14:44

adhish_kapoor's gravatar image

3★adhish_kapoor
90410
accept rate: 9%

edited 03 May '17, 14:46

Here is the link which explain Sqrt Root Decompostion nicely.

http://www.infoarena.ro/blog/square-root-trick

Just read the "Range Sum" part.

Next go through the blog post of (@anudeep2011) https://blog.anudeep2011.com/mos-algorithm/ which explain query square root decomposition.

Thanks

link

answered 03 May '17, 14:48

vidyut_1's gravatar image

5★vidyut_1
1444
accept rate: 20%

edited 03 May '17, 14:48

can someone please figure out why am i getting wrong answer for my submission in this test case or may be , suggest some new logic for this question ,

Question link - https://www.codechef.com/problems/GIFTCHEF

Solution link - https://www.codechef.com/viewsolution/13428580

link

answered 03 May '17, 21:32

ho_dor's gravatar image

2★ho_dor
311
accept rate: 0%

This is by far the best after watching gkcs video . Here's you can see how to implement this and its very proof as well.

https://www.hackerearth.com/practice/notes/mos-algorithm/

good luck

link

answered 03 May '17, 15:36

ankush23's gravatar image

3★ankush23
314
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×78
×9
×1

question asked: 03 May '17, 14:34

question was seen: 2,045 times

last updated: 03 May '17, 21:32