BNGAME - Editorial

Problem link : contest practice

Difficulty : Easy

Pre-requisites : Two pointers

Problem : Calculate the minimum possible penalty for the game described.

Explanation :

The heart of the solution is the following idea:

Let’s say that all the cells with the value of Ai greater than some K are prohibited ones and we can’t use them. Then, we need to find a such way from 0 to N+1 that minimizes the maximal value of By where y is the index of some visited cell. Let’s call this minimal value FK

Let’s check all the possible values of K, namely from 0 to 32000. It is clear that while increasing the value of K some cells stop being prohibited, and therefore the value of FK will only decrease. This gives rise to the two-pointers solution:

Initially, all the cells are prohibited. We iterate our K from 0 to 32000. When K gets increased, some new cells with the value of A equal to K stop being prohibited. But then, we might be able to make some cells prohibited again, and this time, forever. More precisely, when there exists a path from 0 to N+1, we just pick some non-prohibited cell with currently the maximal value of B and if there will still be a path from 0 to N+1, then we delete it. Otherwise, we just stop the deletion, try to improve the answer and proceed the cycle. To check, whether there is a path, it is necessary to find the largest distance between any two adjacent currently non-prohibited cells and to compare it to K.

But how to make the cells prohibited/non-prohibited and to find all the distances? STL does well here. We can store the indexes of currently non-prohibited cells in the set, as well as pairwise differences between adjacent non-prohibited cells. In order to pick a non-prohibited cell with the maximal value of B, we can use the priority queue.

This gives us O(N log N) solution.

Solutions : Setter Tester

4 Likes

Wouldn’t a dynamic programming solution work for this problem?

Let the ith cell be represented as Ai , Bi .

Consider dpA [i] and dpB [i], which store the maximum value of A[i] and B[i] respectively uptil i, such that max(Ax)*max(By) is minimized.

Our solution would be dpA[n+1]*dpB[n+1] .

Solution link - http://www.codechef.com/viewsolution/3942108

I know that my code would TLE for the last set of testcases, but I dont know what is wrong with my approach for smaller testcases. Please help.

I was getting WA for the 2nd testcase in the smallest set of input.

2 Likes

Can anybody help to find what is wrong with my code

My code is at following link

http://code.hackerearth.com/818994d

plzz help me

@xcwgf666 - Shouldnt the overall complexity be O(NlogK) because we are searching in the range of K for a value that allows max a-b difference ?
Correct me if I am wrong.

Me too having the same problem with DP !

1 Like

Same question from my side …

1 Like

Can you please elaborate the following:

" More precisely, when there exists a path from 0 to N+1, we just pick some non-prohibited cell with currently the maximal value of B and if there will still be a path from 0 to N+1, then we delete it."

You can try this test case: N=6, K=2, A=[1,3,1,1,3,3], B=[5,3,3,3,3,3]. The answer should be 9.

1 Like

Thanks, i’m getting wrong answer for your testcase.

mine is giving 9, but why this approach(in python) is wrong My logic was explained in the programme itself please help
http://www.codechef.com/viewsolution/3943799

same question from me, i m getting 9 for the above test case , here the link CodeChef: Practical coding for everyone

please use any other variable than K for iteration, as it might be confusing to ascertain which K you are referring to, the one from the input or the one used for the iteration

1 Like

not getting anything …plz someone explain it

should be explained better

1 Like

@xcwgf666 we are making the Ai constants for a particular value of the k and deleting the maximal Bi, if there still exists a path from 0 to n+1(correct me If I am wrong).
suppose we take the input:-
5 2
5 4
12 8
13 1
14 10
1000 1
then we will iterate k from 0 to 1000,there will be no path from 0 to n+1 until k =14,after that we will start deleting the maximal Bi, so Bi removed in this case will be 8 and after that k will be incremented to 1000 and we will again try to delete the maximal value which is 10.
5 4
//12 8 deleted
13 1
//14 10 deleted
1000 1
which gives 4000,but ans=140

Where are we using two pointer here?