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

×

ITERATIVE method instead of RECURSIVE one to solve SPOJ GSS1 question

I'm trying to solve the spoj GSS1 using an iterative implementation of segment trees instead of a recursive approach. I have successfully built the segment tree but I'm finding it difficult to code the query() method using an iterative approach! Can anyone help in implementing the code using an iterative approach? Link to my code

asked 18 Nov '17, 17:20

dushyant7917's gravatar image

5★dushyant7917
716
accept rate: 0%

edited 19 Nov '17, 10:42


Check out this tutorial on Codeforces for iterative segment trees. For GSS1, the part titled "Non-commutative combiner functions" will be applicable. Since you have already solved it recursively, it shouldn't be too hard to follow.

link

answered 19 Nov '17, 16:38

meooow's gravatar image

6★meooow ♦
7.1k718
accept rate: 48%

I have read the tutorial but I'm unable to code the combine() function as described in "Non-commutative combiner functions" section for my use-case.

(20 Nov '17, 00:31) dushyant79175★

The combine() function should be the same as in your recursive approach. If you didn't use a separate function to combine nodes, you can just take the procedure of combining two nodes and put that in a separate combine() function.

(20 Nov '17, 03:03) meooow ♦6★

I have implemented it but it gives wrong answer...

https://notepad.pw/query-GSS1

(20 Nov '17, 12:47) dushyant79175★

That's because you are not combining it correctly. Really it's much easier to work when you have a separate combine() function. But if you insist on doing without one, the left part should be replaced by something like

left_mps = max(left_mps, left_sum + tree[left].max_prefix_sum);
left_mss = max(left_mss + tree[left].sum, tree[left].max_suffix_sum);
left_max = max(left_max, max(tree[left].max_sum, left_mss + tree[left].max_prefix_sum));
left_sum += tree[left].sum;
Similarly you can work out for right.

(21 Nov '17, 01:50) meooow ♦6★

I would still recommend using a combine() function like

ST combine(ST lt, ST rt) {
    ST x;
    x.max_sum = max(max(lt.max_sum, rt.max_sum), lt.max_suffix_sum + rt.max_prefix_sum));
    x.max_prefix_sum = max(lt.max_prefix_sum, lt.sum + rt.max_prefix_sum);
    x.max_suffix_sum = max(lt.max_suffix_sum + rt.sum, rt.max_suffix_sum);
    x.sum = lt.sum + rt.sum;
    return x;
}

(21 Nov '17, 01:55) meooow ♦6★

Actually the order of calculating sum, max_prefix_sum, max_suffix_sum, max_sum for left and right nodes is tricky!

Your hints and drawing proper diagram helped...

Working code https://notepad.pw/dushyant7917-GSS1

Thanks for help :)

(21 Nov '17, 15:11) dushyant79175★

Nice work :)

(25 Nov '17, 22:32) meooow ♦6★
showing 5 of 7 show all
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:

×2,718
×1,755
×1,136
×21

question asked: 18 Nov '17, 17:20

question was seen: 589 times

last updated: 25 Nov '17, 22:32