# Poisonous Plants

# Poisonous Plants

w00tles + 0 comments it can be done with a list of stacks*

let's say we start with

`6 5 8 7 4 7 3 1 1 10`

we'll represent it as a list of stacks like this:

**monday**`6>5, 8>7>4, 7>3>1>1, 10`

each stack is a maximal non-increasing chain

now, to let one day pass:

- pop the top element from every stack (excluding the unique leftmost stack). these are the plants that die on this day.

**tuesday**`6>5, 7>4, 3>1>1, -`

- now check to see if any adjacent stacks can be merged. here we see that
`7>4`

and`3>1>1`

can be merged to form a longer chain. stacks can be merged in O(1)

**tuesday**`6>5, 7>4>3>1>1`

- one day has now passed. repeat the process.

**wednesday**`6>5, 4>3>1>1`

**wednesday**`6>5>4>3>1>1`

- now that just one stack remains in our list, we know we are done.

*NB these stacks are linked-list-based and maintain a pointer to their base element. This allows for O(1) merge operations, and O(1) checking of the top and bottom values.*

purnawirman + 0 comments I passed all the test cases and am interested to share the general algorithm I used. A very good starting point is to read on "the stock span problem", understanding the solution to this problem gives >80% of the solution I have here.

A lot of discussions mentioned about finding the potential killer of each plant by using stack, scanning from right to left. I am not sure how they do this, because my scan is left to right.

Okay, with the stock span problem understanding, now we can discuss the step in the algorithm. The explanation here is developed from step by step insights that I get while working on the problem.

- read in the data as an array/list (I used java)
- Here is the hardest part, use the stock span problem algorithm to find the "killer" array. For a plant that will survive to the end, mark the killer as -1. Let me give an example, an array plant of [1, 4, 7, 6, 2]. The array that represent the killer would be [-1, 0, 1, 1, 0]. Note the killer[0] = -1, since the first element will always survive, killer[1] = 0, since the second element 4 will be killed by the first element 1, killer[3] = 1, since the fourth element 6 will be killed by second element 1.
- The key here is to use the stack, as shown in stock span problem. The stack keep the indices of latest killers (well, technically, all indices will be pushed to the stack once, but it will be popped soon after it is pushed, again, please read the stock span problem first and understand it well).
- After you obtained the killer array, you will realize that you can infer the days needed for the killer to kill all the victims. For example, a killer array of [-1, 0, 0, 1, 1, 0], where all plants are killed by either the first or second element. Since there are 3 zeros here, it mean plant[0] need at least 3 days to kill them.
- Here comes another tricky part, the kill count in part 4 only tell us the lower bound. But what we need is the exact days, and sometimes some plant has to wait for another plant to die before being killed itself. Any plant that is going to be killed by index i always need to wait until all the plants killed by index j>i done their jobs. For example, a killer array of [-1, 0, 1, 1, 0], plant[1] need 2 days to kill its victim. Only after 2 days, then the last element can be killed by plant 0. Thus you should get 3 days instead 2 in the solution!
- Now what's left is to implement insight in part 5. To do it in O(n) time, we can augment the stack of indices with max day needed. I kind of hack this through, by noticing that I should track the max day whenever I pop an element from a stack, or whenever I add a maxday for every kill happen. This is easier than other parts.

Hope this help!

phillm6 + 0 comments Thanks to all the people who posted. Getting pointed toward the stock span algorithm was very helpful (thanks purnawirman).

I would, though, like to offer my own explination, partly to give help without giving out a solution (so people can have the satisfaction of at least partially solving it themselves).

My first algorithm was brute force working on a linked list. Obviously this took worst case O(n*k) where k was the number of days (it only timed out on 5 cases) because linked list removal is O(1).

The root intuition behind my final (successful) algorithm was that each 'flower' only has to know the number of days it will take the longest lived flower to die between him and his killer.

Take [1, 5, 4]: 1 will never die (call that day 0), so 5 sees that 1 will kill him and knows he'll die on day 1, so 5 says, I die on day one. Then 4 looks at five and says you won't kill me, what day do you die on? 4 learns that 5 dies on day 1 so he knows he'll die on day 2 at the earliest. 5 no longer has useful information for anyone, so he can go enjoy his twilight hours. 4 looks at one and says, ah, you'll kill me, so I die on day 2.If a number doesn't find a killer, he obviously doesn't die. So he jumps on the (now empty) stack with his 0.

Careful though about equal numbers. Also, my final algorithm (just the primary function) was only 13 lines, so if you're doing a lot of fancy stuff it might be confusing you more than helping.

Also, the algorithm has to look at every number at least once, and, though there is a stack and while loop that could remove many elements on any single run (a couple hints there too), each element will be pushed exactly once and popped at most once [each being O(1)]. Therefore, the final algorithm is O(n).

sanket1549 + 0 comments Below code works perfectly

`int main() { int n; cin>>n; int* p = new int[n]; for(int i=0;i<n;i++) cin>>p[i]; int* days = new int[n](); int min = p[0]; int max = 0; stack<int> s; s.push(0); for(int i=1;i<n;i++) { if(p[i] > p[i-1]) days[i] = 1; min = min < p[i]?min:p[i]; while(!s.empty() && p[s.top()] >= p[i]) { if(p[i] > min) days[i] = days[i] > days[s.top()] + 1?days[i]:days[s.top()] + 1; s.pop(); } max = max>days[i]?max:days[i]; s.push(i); } cout<<max<<endl;`

}

muneebaadil + 0 comments My code is giving wrong answer on test cases 12, 20, 21, 23. I don't know what exception I am missing in my logic building, but since the test case is very large, I cannot possibly trace my code on that test case. Can someone please find a bug in my code?

int main(){

`unsigned long int totalplants; cin>>totalplants; unsigned long long int* plants; plants = new unsigned long long int [totalplants]; for (int i = 0; i < totalplants; i += 1) { cin>>plants [i]; } stack <unsigned long long int> plantsdata; unsigned long int maxdays = 0; for (int i = totalplants - 1; i >= 0; i -= 1) { if (plantsdata.empty() or plants[i] >= plantsdata.top()) plantsdata.push(plants[i]); else { unsigned long int currentdays = 0; while (not plantsdata.empty() and plants[i] < plantsdata.top()) { currentdays += 1; plantsdata.pop(); } if (currentdays > maxdays) maxdays = currentdays; plantsdata.push(plants[i]); } } cout<<maxdays; return 0;`

}

Sort 233 Discussions, By:

Please Login in order to post a comment