Poisonous Plants
Problem Statement :
There are a number of plants in a garden. Each of the plants has been treated with some amount of pesticide. After each day, if any plant has more pesticide than the plant on its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each of the plants. Determine the number of days after which no plant dies, i.e. the time after which there is no plant with more pesticide content than the plant to its left. Example p = [ 3, 6, 2, 7, 5 ] // pesticide levels Use a 1-indexed array. On day 1, plants 2 and 4 die leaving p' = [ 3, 2, 5 ] . On day ,2, plant 3 in p' dies leaving p^n = [ 3, 2 ]. There is no plant with a higher concentration of pesticide than the one to its left, so plants stop dying after day 2. Function Description Complete the function poisonousPlants in the editor below. poisonousPlants has the following parameter(s): int p[n]: the pesticide levels in each plant Returns - int: the number of days until plants no longer die from pesticide Input Format The first line contains an integer n, the size of the array p. The next line contains n space-separated integers p[ i ] .
Solution :
Solution in C :
In C++ :
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
in dct=0;
map<in,in> mar;
set<in> td;
void proc(in id){
auto it=mar.find(id);
auto it2=it;
++it2;
mar.erase(it);
if(it2!=mar.end() && it2!=mar.begin()){
it=it2;
--it;
if(it2->second>it->second)
td.insert(it2->first);
else{
if(td.count(it2->first))
td.erase(it2->first);
}
}
}
VI otd;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
in n;
cin>>n;
in ta;
forn(i,n){
cin>>ta;
mar[i]=ta;
if(i>0 && mar[i]>mar[i-1])
td.insert(i);
}
while(!td.empty()){
dct++;
otd.clear();
fors(i,td)
otd.PB(*i);
td.clear();
reverse(all(otd));
forv(i,otd){
proc(otd[i]);
}
}
cout<<dct<<endl;
return 0;
}
In Java :
import java.util.Scanner;
public class Solution {
private Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
new Solution().solve();
}
private void solve() {
int n = sc.nextInt();
int[] p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = sc.nextInt();
}
int min = p[0];
int maxDays = 0;
for (int i = 1; i < n; ++i) {
min = Math.min(min, p[i]);
if (p[i] > p[i - 1]) {
int last = p[i];
int k = i + 1;
int days = 1;
while (k < n && min < p[k]) {
if (p[k] <= last) {
last = p[k];
++days;
}
++k;
}
maxDays = Math.max(maxDays, days);
}
}
System.out.println(maxDays);
}
}
In C :
#include<stdio.h>
int main(){
long int n,i,j,min=0,locmin;
scanf("%ld",&n);
long long int *p=(long long int *)malloc(sizeof(long long int)*n);
for(i=0;i<n;i++)
scanf("%lld",&p[i]);
i=n-2;
j=n-1;
while(i>=0){
if(j<n && p[j]>p[i]){
locmin=0;
while(j<n && (p[j]>p[i] || p[j]<0)){
//if(p[j-1]<0)
if(p[j]>0)
p[j]=locmin-1;
if(locmin>p[j])
locmin = p[j];
//else
//p[j] = -1;
j++;
}
}
j=i;
i--;
}
for(i=0;i<n;i++){
if(p[i]<min)
min=p[i];
}
printf("%ld ",-min);
free(p);
return 0;
}
In Python3 :
class plant:
def __init__(self, pest):
self.pest = pest
self.prevkiller = self.nextkiller = None
__slots__ = 'pest,next,prevkiller,nextkiller'.split(',')
nplants = int(input())
plants = [int(pest) for pest in input().split()]
start = current = plant(plants[0])
curkiller = firstkiller = plant(None)
for pest in plants[1:]:
current.next = newplant = plant(pest)
if current.pest < newplant.pest:
curkiller.nextkiller = current
current.prevkiller = curkiller
curkiller = current
current = newplant
last = current.next = plant(-1)
last.prevkiller = curkiller
curkiller.nextkiller = last
day = 0
while last.prevkiller is not firstkiller:
day += 1
curkiller = last.prevkiller
while curkiller is not firstkiller:
victim = curkiller.next
if not(hasattr(victim, "next")):
print(victim.pest, day)
curkiller.next = victim.next
if victim.prevkiller == curkiller:
curkiller.nextkiller = victim.nextkiller
victim.nextkiller.prevkiller = curkiller
victim.prevkiller = victim.nextkiller = None
curkiller = curkiller.prevkiller
curkiller = last.prevkiller
while curkiller is not firstkiller:
prevkiller = curkiller.prevkiller
if curkiller.pest >= curkiller.next.pest:
curkiller.nextkiller.prevkiller = prevkiller
prevkiller.nextkiller = curkiller.nextkiller
curkiller.prevkiller = curkiller.nextkiller = None
curkiller = prevkiller
print(day)
View More Similar Problems
Square-Ten Tree
The square-ten tree decomposition of an array is defined as follows: The lowest () level of the square-ten tree consists of single array elements in their natural order. The level (starting from ) of the square-ten tree consists of subsequent array subsegments of length in their natural order. Thus, the level contains subsegments of length , the level contains subsegments of length , the
View Solution →Balanced Forest
Greg has a tree of nodes containing integer data. He wants to insert a node with some non-zero integer value somewhere into the tree. His goal is to be able to cut two edges and have the values of each of the three new trees sum to the same amount. This is called a balanced forest. Being frugal, the data value he inserts should be minimal. Determine the minimal amount that a new node can have to a
View Solution →Jenny's Subtrees
Jenny loves experimenting with trees. Her favorite tree has n nodes connected by n - 1 edges, and each edge is ` unit in length. She wants to cut a subtree (i.e., a connected part of the original tree) of radius r from this tree by performing the following two steps: 1. Choose a node, x , from the tree. 2. Cut a subtree consisting of all nodes which are not further than r units from node x .
View Solution →Tree Coordinates
We consider metric space to be a pair, , where is a set and such that the following conditions hold: where is the distance between points and . Let's define the product of two metric spaces, , to be such that: , where , . So, it follows logically that is also a metric space. We then define squared metric space, , to be the product of a metric space multiplied with itself: . For
View Solution →Array Pairs
Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .
View Solution →Self Balancing Tree
An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ
View Solution →