CareerCup

We basically have to find out the subarray with maximum P's such that the total cost of the subarray is < than X. We can solve this using sliding window and try to maximize the number of P's in the window.

We don't need to count the revisited images.
We have to find the max number of different images.
You can just move to next image.
No Random jump is allowed.

About this problem could you share with us if recruiter gave you hint. Did hi mentioned how many are approximately the images. I see two approaches actully - dynamic programming and brute force soluiton with backtrack. The problem in my dynamic approach is the my state is too big - all possible configurations of pictures (visited, not visited(. Is there a way to decrease state?

As it's mentioned maximum number of images you can see. So considering Landscape and Portrait Image cost, Portrait Image costs least. So we will be able to find maximum number of images only if there are only Portrait images. Now let's consider mathematical equations :-

Cost of Viewing say 3 Portrait images would be = Vp+m+Vp+m+Vp --> Basically 3(Vp)+2(m)

We could consider Vp+m as one combination.
Max Images = IntegerOf(x/(Vp+m)) + y

y is calculated as follows :-
if( (x- IntegerOf(x/(Vp+m)) * (Vp + m) ) = Vp) // Remaining amount is equal to Cost of one Portrait Image
then y = 1
else
y = 0

Is this right solution to calculate. Please comment this is my first answer on CareerCup.

I was able to solve ot in O(n2) , using optimized bruite force. But
a better solution was expected.

The approach is to go through the list mark the starting element with the value of MAX cost. Now at every image specify the reduction in the amount that you have. Once you have attributes all images with the cost.
It's a two pointer problem where you track two pointers where expanding the second pointer till the amount difference > X. Else move the first pointer. You do not need to double iterate. So this is O(n) problem now.

rajnikant12345 - can you please give the relative costs? i.e. m < Vp < Rp. or all these are considered equal?

Can someone explain it with an example.

I tried to make the equation where
n => No of total images which can be viewed which we want to maximize
X = m*(n-1) + (n-a)Vp + a(Rp + Vp)

X => Total cost given in problem
a => No of landscape images that can be viewed
n-a => No of portrait images

But now I am not getting how to proceed further.

int count = 0, i = 0
While(arr[i]!= NULL && x > 0)
{
x -= vp + (arr[i] != P) ? rp : 0;
if (X > 0)
count++;
else
return count;
x -= m;
i++;
}
return count;

public int findMax(int m, int R, int V, int x, char[] arr){
	int count = 0, sum =0;
	for(char c: arr){
		sum+= getCost(c);	
	}
	count += x/sum*arr.length;
	x=x%sum;
	if(count>0)
		x+=m;
	if(x < V)
		return count;
	sum = 0;
	int b =0;
	for(char c: arr){
		if(getCost(c)+sum < x){
			sum+=getCost(c);
			count ++;
		}
		else {
			sum= sum -getCost(arr[b])+getCost(c);
			b++;
		}
	}
	return count;
}

private int getCost(char c, int R, int V, int m){
	int cost = V+m;
	if(c == 'L')
		cost+= R;
	return cost;
}

Could you elaborate on the subejct if we have to find max number of different images we can see or it is possible to cycle through same images?