Max Sum Codevita 9 Solution
Two friends A and B are playing with an array of integers. They both agree upon the operations to be performed on the array but differ on choice of window size to perform the said operations.
The operations to be performed on the array are explained below:
· One can choose to add at the most X consecutive elements.
· After performing the addition operation, it is mandatory to skip the next element in the array.
· The goal is to achieve maximum sum by choosing appropriate elements in the array.
A wants X to be W, while B wants X to be (W + D). This is the only difference that they have. Your task is to find out who wins. Winner is the person whose sum is higher.
The inputs that will be provided are values of elements of array, value of W and value of D.
Example:
Array: 4 5 6 1 2 7 8 9
Window Size (W): 3
Output: 39
Explanation
- We will choose to add elements 4, 5, 6 since window size is 3.
- Since one addition operation is complete, we have to skip one element which is 1.
- We choose to skip element 2 because the next three values are also higher than 2.
- The max sum thus obtained is 39.
- Now suppose the array was: 4 5 6 1 2 3 7 8 9 We will choose to add elements 4, 5, 6 since window size is 3.
- Since one addition operation is complete, we have to skip one element which is 1.
- Now we choose to pick element 2 because we can skip element 3 and still pick up the next 3 values viz 7, 8, 9.
- The max sum thus obtained is 41.
- Note that we picked up only one element in second selection since constraint is only on maximum number to be chosen, not minimum. Now suppose the array was: 4 5 6 7 Since one can start from any index, we choose element 5, 6, 7.
- The max sum thus obtained is 18. The above examples illustrate the game with a fixed window size of W.
- Since B prefers to play the same game with the size of W+D, the steps will remain the same but the max sum output may be different. Print different output depending on whether A wins, B wins or it’s a tie.
Constraints
- 0 <= N <= 10 ^ 5
- 5 <= W <= 10 ^ 5
- -10^5 <= D <= 10^5
- 0 < (W + D) <= N
- 0 <= elements in array <= 10 ^ 9
Input
First line contains three space separated integers N and W and D respectively, which denote
N – size of array
W – window size
D – difference
Second line contains of N space separated integers denoting the elements of the array
Output
- If B wins, print “Right ”
- If A wins, print “Wrong ”
- If It’s a tie, print “Both are Right”
- Refer Examples section for better understanding
Time Limit
1
Examples
Example 1
Input
8 5 -2
4 5 6 1 2 7 8 9
Output
Wrong 2
Explanation
- Here we have given N = 8, W = 5, D = -2
- A will maximize the sum of elements of the array using window size 5. Whereas B will maximize the sum of elements of the array using window size 3 (5-2).
- Using logic as depicted above A will get the max sum as 41 and B will get the max sum as 39. The absolute difference is 41 – 39 = 2.
- Hence, output will be: Wrong 2
Example 2
Input
9 2 2
4 5 6 1 2 3 7 8 9
Output
Right 10
Explanation
- Here we have given N = 9, W = 2, D = 2
- A will maximize the sum of elements of the array using window size 2. Whereas B will maximize the sum of elements of the array using window size 4 (2+2).
- Using logic as depicted above A will get the max sum as 33 and B will get the max sum as 43. The absolute difference is 43 – 33 = 10.
- Hence, output will be: Right 10
Example 3
Input
10 9 -3
4 5 6 3 2 3 7 8 9 2
Output
Both are right
Explanation
- Here we have given N = 10, W = 9, D = -3
- A will maximize the sum of elements of the array using window size 9.
- Whereas B will maximize the sum of elements of the array using window size 6 (9-3).
- Using logic as depicted above A will get the max sum as 47 and B will get the max sum as 47. The absolute difference is 47 – 47 = 0.
- Hence, output will be: Both are right
SOLUTION
Program: Max Sum Codevita 9 Solution in Python
x,y,n=map(int,input().split())
p=list(map(float,input().split()))
sum_x=0.0
sum_y=0.0
for i in range(x):
sum_x += p[i]
for i in range(y):
sum_y += p[i]
ma_x=20*[0]
ma_y=20*[0]
ma_x[0]=sum_x/x
ma_y[0]=sum_y/y
j=1
for i in range(x,n):
j+=1
sum_x +=(-p[i-x] + p[i])
ma_x[j] = sum_x/x
j=1
for i in range(y,n):
j+=1
sum_y +=(-p[i-y] + p[i])
ma_y[j] = sum_y/y
above=0
count=0
if(ma_x[y-x] > ma_y[0] and above==0):
above = 1
if(ma_x[y-x] < ma_y[0]):
above = -1
for i in range(1,n-y+1):
if(ma_x[y-x+i] < ma_y[i] and above == 1):
count += 1
above = -1
elif(ma_x[y-x+i] > ma_y[i] and above == -1):
count += 1
above = 1
print(count)
Codevita Season 9 All Questions Solution
- Even Odd Codevita 9 Solution
- Largest Gold Ingot Codevita 9 Solution
- Fill the Cube Codevita 9 Solution
- Logic for Single Lane Highway Codevita 9
- Faulty Keyboard Codevita 9 Solution 2020
- Signal Connection Codevita 9 Solution 2020
- Closing Value Codevita 9 Solution
- CodeVita season 9 Zone 2 All Solutions
- Railway Station Codevita 9 Solution
- Count Pairs Codevita 9 Solution
- 7 X 7 Codevita 9 Solution
- Tennis Score codevita 9 Solution
- Unlocker Codevita 9 Solution
- Path through graph Codevita 9 Solution
- Secret Word Codevita 9 Solution
- 3 Palindrome Codevita 9 Solution
- Max Sum Codevita 9 Solution
- Equalize Weights Codevita 9 Solution
- Binary Equivalent Codevita 9 Solution
- String Word Codevita 9 Solution
- 4 Particles Codevita 9 Solution
- String Pair Codevita 9 Solution
- Corona Virus Codevita 9 Solutions
- Factor of 3 Codevita 9 Solutions
- Single Lane Highway Codevita 9 Solution