PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan Jaddouh
Tester: Aleksa Plasvic
Editorialist: Taranpreet Singh
DIFFICULTY:
Simple
PREREQUISITES:
Arrays, observation.
PROBLEM:
Given N squares in a straight line, each square having a value written on it which is given by the array A of length N. You are also given an integer K. You are allowed to choose any start point in the array and then making jumps of size K to the right till chef goes beyond the last square. The value of a square is the sum of values of squares which Chef have to visit if Chef starts at that square. We need to find the maximum value.
QUICK EXPLANATION
- The squares visited when starting from square x is just the square x and the squares visited when starting from position x+K.
- So, we can calculate from the last square to the first square, the sum of squares when starting from the xth square as just A[x] plus the sum of squares visited when starting from the x+K match which we calculated just now.
EXPLANATION
The simple solution is to calculate the sum value when starting from each position. It is just, for each position, add all the squares visited by the chef using a nested loop and take the maximum sum.
This solution is O(N^2) and won’t work for the last subtask.
We need to notice that we are doing some work again and again. Suppose we start at square x. The squares visited are x, x+K, x+2*K and so on till x+c*K \leq N
Now, If we consider squares visited when starting from square x+K, these are x+K, x+2*K and so on till x+c*K \leq N. Hence, we can conclude that when starting from x, the sum of squares visited is A[x] plus the sum of squares visited when started from x+K.
So, we can calculate from reverse and store them in an array. Now, for calculating the value of square x, we can easily take the sum of squares from x+K and value of current square. Then we can just take the maximum and print the answer.
Also, It can be done without even making an additional array.
Time Complexity
Time complexity is O(N) per test case.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n;
int arr[100100];
int dp[100100];
int k;
int sm_n=0;
int main(){
//freopen("01.txt","r",stdin);
//freopen("01o.txt","w",stdout);
T=readIntLn(1,1000);
while(T--){
n=readIntSp(1,100000);
k=readIntLn(1,100000);
sm_n += n;
assert(sm_n<=1000000);
for(int i=0;i<n;i++){
if(i==n-1){
arr[i]=readIntLn(-10000,10000);
} else {
arr[i]=readIntSp(-10000,10000);
}
}
int mx=-1<<30;
for(int i=n-1;i>=0;i--){
dp[i]=arr[i];
if(i+k < n){
dp[i]+=dp[i+k];
}
mx=max(dp[i],mx);
}
cout<<mx<<endl;
}
assert(getchar()==-1);
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
const int maxN=1e6+10;
long long d[maxN], f[maxN];
int a[maxN];
int sum = 0;
void solve()
{
int n, k;
scanf("%d%d",&n,&k);
assert(n>0 && n<=1e5);
assert(k>0 && k<=1e5);
sum += n;
for (int i=0;i<max(n,k);i++){
d[i]=0;
f[i]=-(1e10);
}
for (int i=0;i<n;i++)
{
scanf("%d",&a[i]);
assert(-10000<=a[i] && a[i]<=10000);
if (i-k>=0) d[i]=d[i-k]+a[i]; else
d[i]=a[i];
f[i%k]=d[i];
}
long long ans = -1e10;
for (int i=0;i<min(n,k);i++)
ans = max(ans, f[i]);
for (int i=0;i<n-k;i++)
ans = max(ans, f[i%k]-d[i]);
printf("%lld\n",ans);
}
int main()
{
int t;
cin>>t;
assert(t>0 && t<=1000);
while(t--)
solve();
assert(sum<=1e6);
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
class POGOSTCK{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), k = ni();
long[] a = new long[n];
for(int i = 0; i< n; i++)a[i] = nl();
long ans = a[n-1];
for(int i = n-1; i>= 0; i--){
if(i+k<n)a[i]+=a[i+k];
ans = Math.max(ans, a[i]);
}
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long mod = (long)1e9+7, IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)3e5+2;
DecimalFormat df = new DecimalFormat("0.00000000000");
double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = true, memory = false;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
int T = (multipleTC)?ni():1;
//Solution Credits: Taranpreet Singh
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new POGOSTCK().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new POGOSTCK().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
but you can have a look at my code, it is similar to your code. 