# POGOSTCK - EDITORIAL

Tester: Aleksa Plasvic
Editorialist: Taranpreet Singh

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 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){
}
long long readIntLn(long long l,long long 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);
while(T--){
sm_n += n;
assert(sm_n<=1000000);
for(int i=0;i<n;i++){
if(i==n-1){
} else {
}
}
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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to Share your approach, If it differs. Suggestions are always welcomed.

7 Likes

Why get the minimum sum? It is stated in the problem that we have to find maximum possible number of points chef can get

Writing mistake. Corrected. Thanks.

4 Likes

1 Like

I did the same thing but I am unable to identify my mistake. Useful help is much appreciated.

#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (tâ€“)
{
int n, k;
int maxSum = 0;
cin >> n >> k;
int arr[n];
long long int sum[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
if(arr[i]>maxSum)
maxSum=arr[i];
}

    for(int i=n-1;i>=0;i--)
{
sum[i]=arr[i];
if(i+k<n)
sum[i]+=sum[i+k];
if(maxSum<sum[i])
maxSum=sum[i];
}

cout << maxSum << endl;
}


}

Problem allows negative values too.

i too have the same doubt

you initialized maxsum at 0 , while the actual max sum may be negative and your answer will continue to print 0 instead of the answer , instead try initializing with maxSum=INT_MIN; and should work fine.
Cheers!

Hi @utkrisht_tech and @giriraj07
I fixed the code- CodeChef: Practical coding for everyone (AC)

Compare line 16 of your old and the new code. Remember that 1 \leq K \leq 10^5 . It doesnâ€™t say anywhere that K \leq N. So when you write max=val[n-k], it resulted in undefined behaviour for inputs where K>N.

Hope this helped

Thanks bro for helping you are right

1 Like

I missed that small but important detail.

1 Like

It took me some time too to find out your mistake
Then I converted your code to Java and submitted and Codechef gave NZEC RTE. Then I realised

2 Likes

I appreciate your work that you gave time to find the error this what I like about codechef and codeforces forum.

1 Like

Can someone please find the error in my code?

#include <bits/stdc++.h>
#include
using namespace std;
#define int int64_t

signed main() {

int t;
cin >> t;
while(t--){
int n,k;
cin >> n >> k;
int *arr = new int[n];
for(int i = 0;i < n;i++)
cin >> arr[i];
int *sum = new int[n];
for(int i = 0;i < n;i++)
sum[i] = 0;
int maximum = INT_MIN;
for(int i = n-1;i >= 0;i--){
if(n-k <= i)
sum[i] = arr[i];
else
sum[i] = max(arr[i],arr[i]+sum[i+k]);
maximum = max(maximum,sum[i]);
}
cout << maximum << endl;
}
return 0;


}

I couldnâ€™t find error in your code but you can have a look at my code, it is similar to your code. link

Setterâ€™s code looks scary.

1 Like

can anybody check whats wrong in my ans***
import java.util.;
import java.io.
;
import java.lang.*;

class cd163
{
public static void main(String args[])throws IOException
{

 try{
//takign input through IO
OutputWriter out = new OutputWriter(System.out);
//maximim sum subsequence having no adjacent elements seperated by k
while(T>0)
{   int ans = Integer.MIN_VALUE;
int temp_max = Integer.MIN_VALUE;
int k = arr[1];
int dp[] = new int[values.length];

for(i=0;i<dp.length;i++)
{
dp[i] = values[i];
if(temp_max<values[i])
{
temp_max = values[i];
}
}

if(k<values.length)
{
for(i=0;i<values.length;i++)
{
j = i+k;
if(j<values.length)
{
dp[j]+=dp[i];
ans = Math.max(ans,Math.max(dp[j],dp[i]));
}else
{
ans = Math.max(ans,values[i]);
}

}

out.printLine(ans);
out.flush();

}else
{
out.printLine(temp_max);
out.flush();
}

T--;
}
out.close();
}catch(Exception e){
e.printStackTrace();
}

}


}

{
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;

public InputReader(InputStream stream)
{
this.stream = stream;
}

{
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars)
{
curChar = 0;
try
{
}
catch (IOException e)
{
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}

{
while (isSpaceChar(c))
int sgn = 1;
if (c == '-')
{
sgn = -1;
}
int res = 0;
do
{
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

{
while (isSpaceChar(c))
StringBuilder res = new StringBuilder();
do
{
res.appendCodePoint(c);
} while (!isSpaceChar(c));
return res.toString();
}

while (isSpaceChar(c))
int sgn = 1;
if (c == '-')
{
sgn = -1;
}
double res = 0;
while (!isSpaceChar(c) && c != '.')
{
if (c == 'e' || c == 'E')
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
}
if (c == '.')
{
double m = 1;
while (!isSpaceChar(c))
{
if (c == 'e' || c == 'E')
if (c < '0' || c > '9')
throw new InputMismatchException();
m /= 10;
res += (c - '0') * m;
}
}
return res * sgn;
}

{
while (isSpaceChar(c))
int sgn = 1;
if (c == '-')
{
sgn = -1;
}
long res = 0;
do
{
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

public boolean isSpaceChar(int c)
{
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public String next()
{
}

public interface SpaceCharFilter
{
public boolean isSpaceChar(int ch);
}


}

class OutputWriter
{
private final PrintWriter writer;

public OutputWriter(OutputStream outputStream)
{
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}

public OutputWriter(Writer writer)
{
this.writer = new PrintWriter(writer);
}

public void print(Object... objects)
{
for (int i = 0; i < objects.length; i++)
{
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}

public void printLine(Object... objects)
{
print(objects);
writer.println();
}

public void close()
{
writer.close();
}

public void flush()
{
writer.flush();
}


}

/*

USAGE

//initialize
OutputWriter out = new OutputWriter(System.out);

//read int array of size N
//printline
out.printLine(â€śXâ€ť);

//flush output
out.flush();

//remember to close the
//outputstream, at the end
out.close();
*/

class IOUtils
{
{
int[] array = new int[size];
for (int i = 0; i < size; i++)
return array;
}

}


can anyone please tell me whatâ€™s wrong with my code

#include
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll a[1000000];
ll b[1000000];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
cin>>t;

while(t--)
{
cin.tie(NULL);
ll n,k;
cin>>n>>k;
ll sum=0,sum1=0;
ll maximum=-1 * INT_MAX;
for(ll i=0;i<n;i++)cin>>a[i];

for(ll i=0;i<k;i++)
{
for(ll j=i;j<n;j+=k)
{
if(sum<sum1)
{
sum=0;
}
sum1=sum;
sum+=a[j];

}
if(sum>maximum)
maximum=sum;
sum=0;

}
cout<<maximum<<"\n";

}


}

PYTHON CODE SOLUTION

for _ in range(int(input())):
a,b = map(int,input().split(â€™ '))
c = list(map(int,input().split()))
for i in range(a,-1,-1):
if(i+b<a):
c[i]+=c[i+b]