POGOSTCK - EDITORIAL

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. :slight_smile:

6 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.

3 Likes

Can somebody please explain why my solution is not working on first subtask and second task of second subtask.
My solution link

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 :slight_smile:
I fixed the code- https://www.codechef.com/viewsolution/23741549 (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 :wink:

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 :stuck_out_tongue:
Then I converted your code to Java and submitted and Codechef gave NZEC RTE. Then I realised :stuck_out_tongue:

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 :frowning: but you can have a look at my code, it is similar to your code. link

Setter’s code looks scary.

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
 // BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
 InputReader in = new InputReader(System.in);
 OutputWriter out = new OutputWriter(System.out);
 //maximim sum subsequence having no adjacent elements seperated by k
 int T = in.readInt(),i,j;
 while(T>0)
 {   int ans = Integer.MIN_VALUE;
	 int temp_max = Integer.MIN_VALUE;
	 int arr[] = IOUtils.readIntArray(in,2);
	 int k = arr[1];
	 int values[] = IOUtils.readIntArray(in,arr[0]);
	 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();
}

}

}

class InputReader
{
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;
}

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

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

public String readString()
{
    int c = read();
    while (isSpaceChar(c))
        c = read();
    StringBuilder res = new StringBuilder();
    do
    {
        res.appendCodePoint(c);
        c = read();
    } while (!isSpaceChar(c));
    return res.toString();
}

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

public long readLong()
{
    int c = read();
    while (isSpaceChar(c))
        c = read();
    int sgn = 1;
    if (c == '-')
	{
        sgn = -1;
        c = read();
    }
    long res = 0;
    do
	{
        if (c < '0' || c > '9')
            throw new InputMismatchException();
        res *= 10;
        res += c - '0';
        c = read();
    } 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()
{
    return readString();
}

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
InputReader in = new InputReader(System.in);
OutputWriter out = new OutputWriter(System.out);

//read int
int i = in.readInt();
//read string
String s = in.readString();
//read int array of size N
int[] x = IOUtils.readIntArray(in,N);
//printline
out.printLine(“X”);

//flush output
out.flush();

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

class IOUtils
{
public static int[] readIntArray(InputReader in, int size)
{
int[] array = new int[size];
for (int i = 0; i < size; i++)
array[i] = in.readInt();
return array;
}

}