DRGNDEN - Editorial

editorial
, , , , , , , ,
22

To put it simply, use stack to find next optimum jump point, construct segment tree for range query to get sum of tastes that accommodate only optimum jump points between two indexes is that it? damn

2 Likes
23

I think fenwick tree implementation for this problem is much more simpler to understand and write code.
Here is my implementation CodeChef: Practical coding for everyone

2 Likes
24

I got a little frustrated, since i knew it has to be done with segment trees for 5-6 days but wasn’t able to clearly grasp it anyhow, segment trees since understanding the complexities of O(n(log(n)) as only possible case, I was thinking on lines of finding longest increasing subsequence, and maintaining a secondary segment tree for taste, I also saw a DAG based approach, can anyone help with this regarding which one fits where(and was my approach even viable)

  1. DAG
  2. segment tree
  3. other variations of BIT, Fenwick tree etc.
    Thanks already
1 Like
25

Can it be solved through mo’s algorithm. Can you please clear it??

26

Try to make automated testcases and solve your answer.

27

i think you can’t do that, since if you touch first 4 then the line joining this index with 2, will be below the “mountain peak”, and won’t be able to glide.
line segment from (2,4) to (4,3); point (3,4) lies above that line segment;
On the contrary i was thinking, if you always go from lower to higher height, you won’t face these issues of clashing with a secondary point.

1 Like
28

The third condition says that the line segment connecting two points should not intersect with the solid part of the mountain.

1 Like
29

Thanks for clarifying, I didn’t notice that the route had to be a line segment

1 Like
30

This is a plain segment tree problem with little tweaks

31

Nicely Done , Plain and Simple

1 Like
32

How do you do that? Can you ellaborate ? Sorry I am kinda beginner, this feels like something that will be helpful a lot in future.

33

This post was flagged by the community and is temporarily hidden.

34

Okay ,I am a beginner so I didn’t did much but can anyone tell me where am I getting wrong,
Here’s my code. Forgive me if this approach is too lame/silly.
https://www.codechef.com/viewsolution/35475695
Thanks in advanced

35
2 Likes
36
1 Like
37

can someone please help with my code,I used monotonocity of function concept.
https://www.codechef.com/viewsolution/35492257

38

My logic was same as you suggested that if you want to go from point a to b then traverse from b to a for pints >b and <a and all that you mentioned above in quick explanation . But it didn;t get submitted for 10 marks also . This is not done . I am recieving WA everytime and my all test cases are running properly with minimum time for 10 marks approach.
you can check Mysubmission on my account for verifying this …Please find mistake on my 10 marks approach if you can @codechef.

39

What does these lines of code means? I can’t understand…

auto iterate = [](int i, stack<int>& traveled, vector<int>& p, vector<int>& h)
                        {
                            while(!traveled.empty() && !(h[traveled.top()] > h[i]))
                                traveled.pop();
                            if(traveled.empty())
                                p[i] = 0;
                            else
                                p[i] = traveled.top();
                            traveled.push(i);
                        };
    for(int i = 1; i <= n; i++)
        iterate(i,travelToRight,pRight,h);
    for(int i = n; i >= 1; i--)
        iterate(i,travelToLeft,pLeft,h);
40

I did it using different approach

I divided the whole polyline of n points in blocks of 300 points and precalculated the path in each block

  1. In query of type 2 I calculated starting block and ending block
    if(startingblock==endingblock) then it is simple bruteforce as operations are no more than 300
    otherwise I applied bruteforce in starting block and did binary search in all other blocks of a height upper than my current height till i reach ending block. So complexity in this case was O(300+(n/300)*log(300))
  2. In query of type 1 i just have to update a single block of 300 points (2 blocks for two directions)

Ofcourse I used different array of blocks for both the directions

So overall complexity was O(q*(600 or 300+(n/300)*log(300)))

I was worried at first that it would give tle but i used lower_bound instead of my own binary search which probably gave some advantage (I don’t know)

3 Likes
41

A very simple solution using segment tree + tree flattening:
https://www.codechef.com/viewsolution/35569458

I constructed two trees for forward gliding and backward gliding and calculated the root → node path prefix sums for the two trees. Then when we want to change the taste of a node, I can change the prefix sums of the whole subtree by newtaste - oldtaste.

Quite a small solution really.

3 Likes