BNGAME - Editorial

general
, , ,
1

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

3 Likes
2

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
3

Me too having the same problem with DP !

1 Like
4

Same question from my side …

1 Like
5

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."

6

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
7

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

8

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

9

same question from me, i m getting 9 for the above test case , here the link http://www.codechef.com/viewsolution/3942843

10

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
11

not getting anything …plz someone explain it

12

should be explained better

1 Like
13

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

14

@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.

15

@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

16

Where are we using two pointer here?