Problem Link:
Setter: rjcode_1
Tester: rjcode_1
Editorialist: rjcode_1
DIFFICULTY:
Easy
PREREQUISITES:
Suffix Array, Greedy Approach, Sorting
Problem:
All submissions for this problem are available.Guruji says that gotchi is the answer to all of life’s problems. However, Sartaj knows how potent it really is . Given the array of measures of different potencies in a gotchi solution a1, a2…, an. Divide the array into p cups having non- empty consecutive subarrays such that every element of array is included in exactly one cup.
Let g(i) be the index of cup to which ith element belongs to (cups are numbered from 1 to p from left to right). The gotchi potency value of each cup is determined by following formula ∑(ai g(i)).
Given a= [-3, 4, 5, 4,−7, 8, -2 ] and we can divide it into 4 cups in the following way: [−3 , 4] , [5 , 4] , [−7 , 8] and [-2 ] then the overall potency value is equal to -3⋅1 + 4⋅1 + 5⋅2 + 4⋅2 - 7⋅3 + 8⋅3 – 2⋅4 = 14
Calculate the minimum potency value that Sartaj has to drink .
# EXPLANATION:
Let Suffix(k) be the suffix sum of array. Let the minimum sum (potency that Sartaj has to drink) be minsum.
We observe that at least once every array element is added in minsum. Now in order to find the exact value of minsum we need Suffix(1) and p-1 different suffix sums, for this we first sort the values of suffix sum and then take p-1 minimum values of suffix sum.
By this way we get minimum potency value.
Time Complexity:
O(n) to find suffix sum and O(nlogn) to sort values of suffix sum.
SOLUTIONS:
[details=“Setter’s Solution”]
import java.io.;
import java.util.;
public class Main
{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
int a[]=new int[n];
int j=0;
while (sc.hasNext())
{
a[j++]=sc.nextInt();
if(j==n)
break;
}
ArrayList<Long> suffix_sum=new ArrayList<Long>();
long sum=0;
for(int i=n-1;i>=0;i--)
{
sum+=a[i];
if(i>0)
suffix_sum.add(sum);
}
long res=sum;
Collections.sort(suffix_sum);
for(int i=0;i<k-1;i++)
res+=suffix_sum.get(i);
System.out.println(res);
}
}
[/details]