CareerCup

Cost=1?

I do get when U say 1 there is only one pair misplaced but how can we be so sure.
Don't we need to scan the array to check whether that the elements are in the right positions.

compare elements in pairs, and decide what to do to sort them.

In 4,3,5,6 --> compare (4,3) --- cost 1 to make 4->3

In 10,3,11,12 --> compare (10,3) --- cost 3 to remove 3

Typical dynamic programming thing

I have the sequence say 3 10 7 9 1
Find the longest non-decreasing sequence, which is 3 7 9

If a number is not included in the longest non-decreasing sequence:
check if it can be included by one of the following methods:
1. 10 can be deleted. cost = 10
2. 10 can be decremented to 3 or 7 to be included in the sequence. of cost (10-3) or (10-7). Minimum cost = 3
So, we select option 2.

for 1, it cannot be decremented. so it can be deleted with minimum cost.

What will it do for
10 2 3

I guess it will change 10->1 when the correct answer I guess is to remove 2 and 3 ?

/*


Add an Interview Question


IBM Interview Question for Software Engineer / Developers
Anonymous on August 26, 2010

You are given an array of positive integers. Convert it to a sorted array with minimum cost. Only valid operation are
1) Decrement -> cost = 1
2) Delete an element completely from the array -> cost = value of element

For example:
4,3,5,6, -> cost 1
10,3,11,12 -> cost 3
*/
#include<vector>
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
using namespace std;
typedef struct nn{
	int cost;
	int minimum;
	int maximum;
}costnode;
#define print(arr) for(int i = 0;i<arr.size();i++) cout<<arr[i]<<" ";cout<<endl;
int ComputeMinimumCostSortedArray(vector<int> &arr)
{
	
	int sz = arr.size();
	print(arr);
	vector<costnode> Cost;
	for(int i=0;i<sz;i++)
	{
		costnode c;
		c.cost = 0;
		c.minimum = arr[i];
		c.maximum = arr[i];
		Cost.push_back(c);
	}
	for(int i=1;i<sz;i++)
	{
		vector<costnode> temp;
		for(int j=0;j<sz-i;j++)
		{
			int mincostleft = Cost[j].cost + ((arr[j+i]>Cost[j].maximum)?0:arr[j+i]);
			int mincostright = Cost[j+1].cost + ((arr[j]<Cost[j+1].minimum)?0:(arr[j]-Cost[j+1].minimum));
//			printf("j: %d %d %d LC: %d RC: %d LCMin:%d LCMAx: %d RCMin: %d RCMax: %d ResLeft:%d ResRight:%d %d\n", j, mincostleft, mincostright, Cost[j].cost, Cost[j+1].cost, Cost[j].minimum, Cost[j].maximum, Cost[j+1].minimum, Cost[j+1].maximum, ((arr[j+i]>Cost[j].maximum)?0:arr[j+i]), (arr[j]<Cost[j+1].minimum)?0:(arr[j]-Cost[j+1].minimum), Cost[j+1].cost + ((arr[j]<Cost[j+1].minimum)?0:(arr[j]-Cost[j+1].minimum)));
			costnode c;
			if(mincostleft<mincostright)
			{
				c.cost = mincostleft;
				c.minimum = Cost[j].minimum;
				c.maximum = (arr[j+i]>arr[j+i-1])?arr[j+i]:Cost[j].maximum;
			}
			else{
				c.cost = mincostright;
				c.minimum = (arr[j]<Cost[j+1].minimum)?arr[j]:Cost[j+1].minimum;
				c.maximum = Cost[j+1].maximum;
			}
			temp.push_back(c);
		}
		Cost = temp;
	}
	printf("%d\n", Cost[0].cost);
}
int main()
{
	int n;
	while(1)
	{
		vector<int> arr;
		while(scanf("%d", &n)!=EOF && n!=-1)
		{
			arr.push_back(n);
		}		
		ComputeMinimumCostSortedArray(arr);
	}
}