Circular merging question

#1

Why getting wrong Answer???

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
public static void main(String args[])throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;//=new StringTokenizer(br.readLine());
//int t=Integer.parseInt(st.nextToken());
for(int f=0;f<1;f++){
st=new StringTokenizer(br.readLine());
int n=Integer.parseInt(st.nextToken());
int a[]=new int[n];
st=new StringTokenizer(br.readLine());
for(int i=0;i<n;i++){
a[i]=Integer.parseInt(st.nextToken());
}
long sum=0;
ArrayList lst=new ArrayList<>();
int b[]=new int[2n];
for(int i=0;i<2n;i++){
b[i]=a[i%n];
}
long max=Integer.MAX_VALUE;
long dp[][]=new long[2n][2n];
for(int i=0;i<n;i++){
long l=fun(b,i,n-1+i,dp);
max=Math.min(max,l);
}
System.out.println(max);
}
}
public static long fun(int b[],int i,int j,long dp[][]){
if(i>=j)
return 0;
if(dp[i][j]!=0)
return dp[i][j];
long min=Long.MAX_VALUE;
for(int k=i;k<j;k++){
min=Math.min(min,fun(b,i,k,dp)+fun(b,k+1,j,dp)+summ(b,i,k)+summ(b,k+1,j));
}
return dp[i][j]=min;
}
public static long summ(int b[],int s,int e){
long ss=0;
for(int i=s;i<=e && i<b.length;i++){
ss+=b[i];
}
return ss;
}
}

#2

Please paste the code at ide.codingblocks.com and share the link.

Important details are lost due to the markdown language, so never paste the code like this.

#3
1 Like
#4

Actually, you are taking extra O(n) time to calculate the sum, which makes your approach O(n^4).

Your approach is perfect, regarding the circular array. Just, make some kind of presums or something, so that you get the sum in O(1), so your overall time complexity is O(n^3).

Tell me if you get the idea, or I’ll help you with it.

#5

This is how your summ function should work,

long long int summ(int presum[], int s, int e) {
	if (s == 0) { return presum[e]; }
	return presum[e] - presum[s - 1];
}

and this is how you precalculate presum[],

presum[0] = b[0];
for (int i = 1; i < 2 * n; ++i) {
	presum[i] = presum[i - 1] + b[i];
}