Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Circular Merging CodeChef Solution
Problem -Circular Merging CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Circular Merging CodeChef Solution in C++14
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=1e18;
/* debugger */
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
/* end of debugger */
void circular_merging() {
int n;
cin>>n;
vector<ll> a(n);
ll tot=0;
for(int i=0;i<n;i++) {
cin>>a[i];
tot+=a[i];
}
vector<vector<ll>> dp(n,vector<ll>(n,inf));
/*
dp[i][j]: cost of merging from index i to j
i can be > j : cyclic
*/
for(int i=0;i<n;i++) {
dp[i][i]=0;
}
for(int len=2;len<=n;len++) {
for(int i=0;i<n;i++) {
int j=(i+len-1)%n;
// merging from i to j
ll sum=0;
for(int k=0;k<len;k++)
sum+=a[(i+k)%n];
for(int k=0;k<len-1;k++) {
int mid=(i+k)%n;
// i to mid, mid+1 to j
dp[i][j]=min(dp[i][j],dp[i][mid]+dp[(mid+1)%n][j]+sum);
}
}
}
ll ans=inf;
for(int len=1;len<n;len++) {
for(int i=0;i<n;i++) {
int j=(i+len-1)%n;
ans=min(ans, dp[i][j]+dp[(j+1)%n][(i-1+n)%n]+tot);
}
}
cout<<ans<<"\n";
}
int main() {
int t;
cin>>t;
while(t--) {
circular_merging();
}
}Circular Merging CodeChef Solution in PYTH 3
def toneMerge(tone, n):
if n==2: return sum(tone) # 长度为2时，就是这两堆石头的和
n = n*2
tone = tone + tone
dp = [[float('inf')]*(n+1) for _ in range(n+1)] # 初始化dp
sk = [[None]*(n+1) for _ in range(n+1)] # 初始化sk
for i in range(n+1): dp[i][i], sk[i][i] = 0, i
sm = [tone[0]] # 记录 列表从0 到 n 的累加和
for i in range(1, n): sm.append(sm[i-1]+tone[i]) # 累加求和
for gap in range(1, n//2): # i 到 j 的间隔
for i in range(n-gap):
j = i + gap # 确定本次 i--j
tmp = sm[j] - [0, sm[i-1]][i > 0] # 获取第 i 到第 j 堆石子的总数量
i1, j1 = sk[i][j-1], sk[i+1][j]+1 # 新的区间
for k in range(i1, j1): # 选择i 到 j 的最优解
if dp[i][j] > dp[i][k] + dp[k+1][j] + tmp:
dp[i][j], sk[i][j] = dp[i][k] + dp[k+1][j] + tmp, k # 更新dp， 并记录最有位置k
return min([dp[i][i+n//2-1] for i in range(n//2)])
for _ in range(int(input())):
n = int(input())
lst = list(map(int,input().split()))
print(toneMerge(lst,n))Circular Merging CodeChef Solution in C
#include <stdio.h>
#define MAX 100000000000000000
long long int a[1000];
long long int dp[800][800];
long long int add[800];
long long int min(long long int a, long long int b)
{
return (a>b)?b:a;
}
long long int cirmerge( int i,int j)
{
if(i==j)
return 0;
if(dp[i][j]!= -1)
return dp[i][j];
dp[i][j]= MAX;
for(int k=i;k<=j;k++)
dp[i][j]= min(dp[i][j], cirmerge(i,k)+ cirmerge(k+1,j)+(add[j]-add[i]+a[i]));
return dp[i][j];
}
int main(void) {
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%lld",&n);
long long int ans=MAX;
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
a[n+i]=a[i];
}
add[0]= a[0];
for(int i=1;i<2*n;i++)
add[i]= add[i-1]+a[i];
for(int i=0;i<2*n;i++)
for(int j=0;j<2*n;j++)
dp[i][j]=-1;
for(int k=0;k<n;k++)
{
ans= min(ans, cirmerge(k,n-1+k));
}
printf("%lld\n",ans);
}
return 0;
}Circular Merging CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static long find(int arr[],int n){
long sv[][]=new long[n][n];
long dp[][]=new long[n][n];
for(int i=0;i<n;i++) sv[i][i]=arr[i];
for(int col=1;col<n;col++){
for(int row=col-1;row>=0;row--){
dp[row][col]=9223372036854775807L;
sv[row][col]=sv[row][row]+sv[row+1][col];
for(int k=row;k<col;k++) dp[row][col]=Math.min(dp[row][col],dp[row][k]+dp[k+1][col]+sv[row][col]);
}
}
for(int col=0;col<n-1;col++){
for(int row=n-1;row>col;row--){
dp[row][col]=9223372036854775807L;
if(col+1==row) sv[row][col]=sv[0][n-1];
else sv[row][col]=sv[0][n-1] - sv[col+1][row-1];
for(int k=row;k<col+n;k++) dp[row][col]=Math.min(dp[row][col],dp[row][k%n]+dp[(k+1)%n][col]+sv[row][col]);
}
}
long res=dp[0][n-1];
for(int col=1;col<n;col++) res=Math.min(res,dp[col][col-1]);
return res;
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner s=new Scanner(System.in);
int t=s.nextInt();
for(int i=0;i<t;i++){
int n=s.nextInt();
int arr[]=new int[n];
for(int j=0;j<n;j++) arr[j]=s.nextInt();
System.out.println(find(arr,n));
}
}
}Circular Merging CodeChef Solution in PYPY 3
def merge(A,p,st,fin):
if st==fin:
p[st][fin]=0
return 0
elif p[st][fin]!=-1:
return p[st][fin]
elif st+1==fin:
p[st][fin]=A[st]+A[fin]
return p[st][fin]
sum1=0
for i in range(st,fin+1):
sum1+=A[i]
min1=10000000000000000
for i in range(st,fin):
tmp=sum1+merge(A,p,st,i)+merge(A,p,i+1,fin)
if min1>tmp:
min1=tmp
p[st][fin]=min1
return min1
t=int(input())
for u in range(t):
n=int(input())
A=[int(x) for x in input().split()]
max=-1
for i in range(n):
if A[i]>max:
max=A[i]
idx=i
A=A[idx:]+A[:idx]
p=[[-1]*n for i in range(n)]
print(merge(A,p,0,n-1))Circular Merging CodeChef Solution in C#
using System;
namespace CodeChef19._7
{
// Prepared as a solution to CirMerge
// David Sturge (David_S) 13 July 2019.
// *** use method in editorial, for practice
// https://discuss.codechef.com/t/cirmerge-editorial/29723
class CirMerge
{
static void Main()
{
// Read T
int space_i;
int t = StringToInt(Console.ReadLine(), 0, out space_i);
while (t-- > 0) {
// Read N, A
int n = StringToInt(Console.ReadLine(), 0, out space_i);
long[] a = StringToLongArray(n, Console.ReadLine());
long[,] dp = new long[n, n];
long[,] sums = new long[n, n];
int n1 = n - 1;
for (int jj = 0; jj < n; ++jj) {
for (int i = 0; i < n; ++i) {
int j = i + jj;
if (j > n1)
j -= n;
long s;
switch (jj) {
case 0:
dp[i, i] = 0;
sums[i, i] = a[i];
break;
case 1:
s = sums[i, i] + sums[j, j];
sums[i, j] = s;
dp[i, j] = dp[i, i] + dp[j, j] + s;
break;
default:
int k = (i < n1) ? i + 1 : 0;
s = sums[i, i] + sums[k, j];
sums[i, j] = s;
dp[i, j] = dp[i, i] + dp[k, j];
for (int kk = 1; kk < jj; ++kk) {
int kb = k;
if (++k > n1)
k = 0;
long dpn = dp[i, kb] + dp[k, j];
if (dpn < dp[i, j])
dp[i, j] = dpn;
}
dp[i, j] += s;
break;
}
}
}
long result = dp[0, n1];
for (int i = 1; i < n; ++i) {
if (dp[i, i - 1] < result)
result = dp[i, i - 1];
}
Console.WriteLine(result);
}
Console.ReadKey();
}
private static long[] StringToLongArray(int num, String s)
// Decode num integers from line of input
// Store them as 'long' because it will be useful later.
{
long[] output = new long[num];
int num_read = 0;
int start_i = 0;
int len = s.Length;
while (num_read < num && start_i < len) {
int next_i;
output[num_read++] = StringToInt(s, start_i, out next_i);
start_i = next_i + 1;
}
return output;
}
private static int StringToInt(String s, int index, out int space_i)
// Convert string from index up to next space or end to integer.
// Return space_i = index of next space encountered, or off end of string.
{
const char c_zero = '0';
int n = s[index] - c_zero;
int len = s.Length;
while (++index < len) {
if (s[index] < c_zero)
break;
n = n * 10 + ( s[index] - c_zero );
}
space_i = index;
return n;
}
}
}Circular Merging CodeChef Solution in GO
package main
import (
"bufio"
"fmt"
"os"
)
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] != ' ' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readNum(scanner *bufio.Scanner) (a int) {
scanner.Scan()
readInt(scanner.Bytes(), 0, &a)
return
}
func readTwoNums(scanner *bufio.Scanner) (a int, b int) {
res := readNNums(scanner, 2)
a, b = res[0], res[1]
return
}
func readNNums(scanner *bufio.Scanner, n int) []int {
res := make([]int, n)
x := 0
scanner.Scan()
for i := 0; i < n; i++ {
for x < len(scanner.Bytes()) && scanner.Bytes()[x] == ' ' {
x++
}
x = readInt(scanner.Bytes(), x, &res[i])
}
return res
}
func fillNNums(scanner *bufio.Scanner, n int, res []int) {
x := 0
scanner.Scan()
for i := 0; i < n; i++ {
for x < len(scanner.Bytes()) && scanner.Bytes()[x] == ' ' {
x++
}
x = readInt(scanner.Bytes(), x, &res[i])
}
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] != ' ' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readInt64(bytes []byte, from int, val *int64) int {
i := from
var tmp int64
for i < len(bytes) && bytes[i] != ' ' {
tmp = tmp*10 + int64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readNInt64Nums(scanner *bufio.Scanner, n int) []int64 {
res := make([]int64, n)
x := -1
scanner.Scan()
for i := 0; i < n; i++ {
x = readInt64(scanner.Bytes(), x+1, &res[i])
}
return res
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
tc := readNum(scanner)
for tc > 0 {
tc--
n := readNum(scanner)
A := readNNums(scanner, n)
fmt.Println(solve(n, A))
}
}
const INF = 1 << 50
func solve(n int, A []int) int64 {
if n < 2 {
return 0
}
if n == 2 {
return int64(A[0] + A[1])
}
B := make([]int, 2*n)
copy(B, A)
copy(B[n:], A)
N := 2 * n
dp := make([][]int64, N)
sum := make([][]int64, N)
for i := 0; i < N; i++ {
dp[i] = make([]int64, N)
sum[i] = make([]int64, N)
for j := 0; j < N; j++ {
dp[i][j] = INF
}
dp[i][i] = int64(A[i%n])
sum[i][i] = int64(A[i%n])
}
for j := 1; j < N; j++ {
for i := j - 1; i >= 0 && i > j-n; i-- {
sum[i][j] = int64(A[i%n]) + sum[i+1][j]
for k := i; k < j; k++ {
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])
}
dp[i][j] += sum[i][j]
}
}
var best int64 = INF
for i := 0; i < n; i++ {
for j := i; j < i+n; j++ {
a := dp[i][j]
b := dp[j+1][i-1+n]
best = min(best, a+b)
}
}
return best
}
func min(a, b int64) int64 {
if a <= b {
return a
}
return b
}Circular Merging CodeChef Solution Review:
In our experience, we suggest you solve this Circular Merging CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Circular Merging CodeChef Solution.
Conclusion:
I hope this Circular Merging CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
