We have a maze R X C where 1<=R,C<=500. This maze is filled by numbers from -1 to 100. Now , the game is as follows :

1. Where ever there is -1 in square , assume that is a stone block in that cell and you cannot move throught that cell.
2. You can begin from any cell on 1st column (of course that does not have -1) and exit from any cell from last column .
3. You can move either up , down , right.
4. As you move , u collect the numbers in the cell except -1 which denote a big stone is placed in our maze. Each cell has to be visited once only.

What is the path from left to right where you can select maximum sum of numbers ? EASY !! Dp can do magic But But ... here's the catch — Rule 5 .

1. We can move out of maze if we can reach first or bottom row. But then 2 things happen :

a) We lose all points collected till now. b) we renter the maze in the same column but in the opposite cell.

ex: consider 3X3 maze (1 -indexed) . so if we reach say , (1,2) we can exit from there and lose all points and enter (3,2) , and game continues ....

Now what will the path with maximum points ?

My approach was to first find all possible source points. If we come out of maze form 1st or last row , we begin fresh and where we land next becomes our source point. So , I perform multi source BFS taking cells of leftmost column to get it . And do calculate such optimal path score for each cell by dp . IS there any other optimal method to solve this game ?

Recent I encountered this problem on trees whose solution I found in O(n*q) . I am thinking if there is much better way to deal this with lesser complexity.

The problem is here as follows :

Given an unweighted tree of 'n' nodes ( n>=1 and n can go to 10⁵ ) , Its nodes can be special or non special. Node 1 is always special and rest non special initially. Now ,There are two operations :

1.we can update any non special node to special node by an update operation by "U Node_Number"

OR

2.At any time , we can ask user "Q Node_Number" which should return that special node in tree closest to "Node_Number".

These operations can also go upto 10⁵.

My Solution :

I thought of creating adjacency list. For operation 1, I can keep record of special or Non special by boolean flag. But for operation 2 , my solution comprises of doing BFS whenever "Q Node_Number" is asked taking "Node_Number" as root to begin my BFS.

But complexity is quadratic. Is this the most optimal way of going about this problem ?