POGOSTCK - EDITORIAL

array
observations
simple
taran_1407
ltime70

#1

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:


#2

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


#3

Writing mistake. Corrected. Thanks.


#4

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


#5

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;
}

}


#6

Problem allows negative values too.


#7

i too have the same doubt


#8

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!


#9

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:


#10

Thanks bro for helping you are right


#11

I missed that small but important detail.


#12

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:


#13

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


#17

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;

}


#18

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


#19

Setter’s code looks scary.