Smallest Rotation With Highest Score


  • 0

    Click here to see the full article post


  • 0
    T

    It seems that this is not a "Interval Stabbing" problem
    https://www.cs.cmu.edu/afs/cs/academic/class/15210-f11/www/resources/recis/rec12.pdf
    Please correct me if I am wrong.


  • 0
    A

    Can anyone please explain:-
    "what we will do instead is keep track of the cumulative total: bad[2]--; bad[5]++. For "wrap-around" intervals like [8, 9, 0, 1, 2], we will keep track of this as two separate intervals: bad[8]--, bad[10]++, bad[0]--, bad[3]++. (Actually, because of our implementation, we don't need to remember the bad[10]++ part.)"

    It totally went over my head.


  • 0
    A

    I didn't quite understand how bad[2]-- and bad[5]++ is the same as bad[2]--, bad[3]-- , bad[4]--


  • 0
    B

    @Aakash_Ajay Hi I think i figure this out. It's tricky but brilliant. Let's say you have an array bad with index from 0 to 5. bad[2]--, bad[3]--, bad[4]--, makes the array looks like this:
    0_1520824714550_bad1.png
    So the -1 give an information that there is an interval [2,3,4]. To save time instead of this you will do bad[2]-- and bad[5]++ which result in:
    0_1520826146421_bad2.png
    and then you do a cumulative sum from i = 1 to end of array bad[i] += bad[i-1]:
    0_1520826369315_bad3.png .
    It will be still beter time because the idea is that you put all the bad[left] and bad[right] first and then at the end make cumulative sum once. Small example: two intervals [1,2,3]; [3,4]:
    0_1520827595559_bad4.png


  • 0
    K

    Hi there, I think there is a mistake in the explanation :

    When we shift by 2, we'll get final index 0. ==> ok
    If we shift 5-1 = 4 before this, this element will end up at final index 4. ==> seems wrong, we end up at index 6 !
    

    I think you meant that if we shift by 8, we end up at position 4


  • 0
    K

    Hello again :
    I think the shifting position is always to be positive right ?
    Else there is an issue with the clarity of the problem ?

    In general (modulo N), a shift of abs( i - A[i] + 1 ) to i will be the rotation indexes that will make A[i] not score a point.
    

  • 0
    A

    @bodziozet ya, I got your explanation, the logic is so elegant, it took time to digest in.


  • 0
    B
    public int bestRotation(int[] a) {
    
    	int[] resultArray = new int[a.length];
    	int finalScore = 0;
    
    	for (int m = 0; m <= a.length - 1; m++) {
    		Integer new_index = 0;
    		
    		for (int i = 0; i <= a.length - 1; i++) {
    			if ((i - a[m]) < 0) {
    				new_index = (i - a[m]) + (a.length);
    			} else {
    				new_index = (i - a[m]);
    			}
    			resultArray[new_index] = a[i];
    		}
    
    		int totalscore = 0;
    		for (int j = 0; j <= resultArray.length - 1; j++) {
    			if (resultArray[j] <= j) {
    				totalscore++;
    			}
    		}
    		if (totalscore > finalScore) {
    			finalScore = totalscore;
    		}
    	}
    	return finalScore;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.