Editorialist: Tanmay Agrawal
Prerequisites:
Basic Maths Concepts
Problem Link:
Problem Description:
You need to find the maximum sum possible for at most K distinct remainders when divided by 5.
Explanation:
When you divide any number by 5 the remainder can only be one of the following: {0,1,2,3,4}. So, observation here is that at max only 5 elements can be selected, as the possible
Preformatted textdistinct remainders are {0,1,2,3,4}. Hence, for K greater than 5 we can select only 5 elements, not more.
Now, what we can do is make a note of which element is maxed at a given index. To do so, we keep a note of the maximum element at the remainder of an index when divided by 5, since, there are 5 distinct remainders we can keep a note of all 5 of them easily and update them whenever there is an element greater than the one already present at the given remainder of the index when divided by 5.
So, we go through every given element and every time the value is greater than the one before at that remainder of the index when divided by 5 we update its value.
To calculate the answer we work on the set obtained of from maximizing element at the remainder of the index when divided by 5.
If K is greater than 4 we select all 5 elements from the set we obtained, as the number of distinct remainders can’t be greater than 5 and sum them, the resultant value is the answer.
But if K is less than 5 we need to maximize our answer so we take the sum of maximum K elements as the sum of maximum K values will only yield the maximum answer, and the resultant value is the answer.
Consider the first test-case: N = 21 and K = 6
Let Max[i] denote the current maximum element at the ith remainder of the index when divided by 5.
After going through the first 5 given elements of the array, Max pointers are:
Max[1] = 3
Max[2] = 8
Max[3] = 21
Max[4] = 13
Max[5] = 15
After going through the first 10 elements, Max pointers are:
Max[1] = 4
Max[2] = 10
Max[3] = 21
Max[4] = 13
Max[5] = 15
After going through the first 15 elements, Max pointers are:
Max[1] = 4
Max[2] = 11
Max[3] = 21
Max[4] = 14
Max[5] = 16
After going through the first 20 elements, Max pointers are:
Max[1] = 5
Max[2] = 18
Max[3] = 21
Max[4] = 14
Max[5] = 16
After going through all given elements, Max pointers are:
Max[1] = 5
Max[2] = 18
Max[3] = 21
Max[4] = 14
Max[5] = 16
So, the answer is Max[1] + Max[2] + Max[3] + Max[4] + Max[5], i.e, 74.
C++ Code for Experienced Programmers:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
int arr[n+1];
for(int i = 1;i<=n;i++)cin>>arr[i];
int maxValueAtIndex[5];
memset(maxValueAtIndex,0,sizeof maxValueAtIndex);
for(int i = 1;i<=n;i++){
int x = i%5;
if(arr[i] > maxValueAtIndex[x])
maxValueAtIndex[x] = arr[i];
}
sort(maxValueAtIndex,maxValueAtIndex+5,greater<int>());
int x = min(k,5);
int ans = 0;
for(int i = 0;i<x;i++)
ans+= maxValueAtIndex[i];
cout<<ans;
return 0;
}