304 North Cardinal St.
Dorchester Center, MA 02124

# Chef and Segments CodeChef Solution

## Chef and Segments CodeChef Solution in C++14

``````#include <bits/stdc++.h>

using namespace std;

#include "dbg.h"
#else
#define dbg(x...)
#endif

using ll = long long;

const int N = 1005;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);

int T;
cin >> T;
for (int test_case = 1;test_case <= T;test_case++) {
int n;
cin >> n;
vector<int> a(n);
for (int& i : a) {
cin >> i;
}
map<int,vector<int>> p;
for (int i = 0;i < n;i++) {
p[a[i]].push_back(i);
}
auto nc2 = [](int x) {
return (x * (x + 1)) / 2;
};
using T = set<pair<int,int>> ;
auto modify = [&](T& d,int& val,int pos) {
auto lb = d.lower_bound({pos, -1});
if (lb == d.end() or lb->first > pos) lb--;
auto now = *lb;
d.erase(lb);
// split the seg..
val -= nc2(now.second - now.first + 1);
if (now.first == now.second) return ;
if (now.first < pos and now.second > pos) {
d.insert({now.first, pos - 1});
d.insert({pos + 1,now.second});
val += nc2(pos - now.first) + nc2(now.second - pos);
} else if (now.first == pos) {
d.insert({now.first + 1,now.second});
val += nc2(now.second - now.first);
} else {
d.insert({now.first,now.second - 1});
val += nc2(now.second - now.first);
}
};
int ans = 0;
for (int i = n - 2;i >= 0;i--) {
set<pair<int,int>> segs; segs.insert({i + 1,n - 1});
int now = nc2(n - i - 1);
map<int,int> vis;
for (int j = i;j >= 0;j--) {
if (vis[a[j]]) {
ans += now;
continue ;
}
vis[a[j]] = 1;
for (auto it = lower_bound(p[a[j]].begin(), p[a[j]].end(), i + 1);it != p[a[j]].end();it++) {
modify(segs, now, *it);
}
ans += now;
}
}
cout << ans << '\n';
}

return 0;
}``````

## Chef and Segments CodeChef Solution in C

`````` #include <stdio.h>

#include <stdlib.h>

#define REPEAT(token, num) for (token = 0; token < num; token++)

typedef long test_cases;
typedef long num;
typedef long num_cells;
typedef long cell;
typedef long long num_matrices;

num list[1000];
cell matrix[1000][1000];
num_cells width, height, emptyToRight[1000][1000], stack[1000], stackLength;

int main() {
num_cells i, j, prevToRight;
test_cases numTestCases;
//input for number of test cases
scanf("%li", &numTestCases);
//checking with testcases
while (numTestCases--) {
scanf("%li", &width);
height = width;
REPEAT(i, width) scanf("%li", list+i);
REPEAT(i, width) REPEAT(j, height) matrix[i][j] = (list[i] == list[j]);

REPEAT(j, height) {
prevToRight = 0;
REPEAT(i, width) {
if (matrix[i][j]) emptyToRight[i][j] = 0;
else emptyToRight[i][j] = prevToRight+1;
prevToRight = emptyToRight[i][j];
}
}

REPEAT(i, width) {
stack[0] = -1, stackLength = 1;
REPEAT(j, height) {
while (stack[stackLength-1] != -1 && emptyToRight[i][stack[stackLength-1]] >= emptyToRight[i][j]) {
stackLength--;
}
stack[stackLength++] = j;
}
}
}

exit(0);
} ``````

## Chef and Segments CodeChef Solution in JAVA

``````import java.io.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

class chef_and_subs
{
static FastScanner sc=new FastScanner(br);
static PrintWriter out=new PrintWriter(System.out);
static Random rnd=new Random();
static int n;

static long solve(int[] a)
{

int[] prev=new int[n+1],next=new int[n+1];

Arrays.fill(prev,1);Arrays.fill(next,n);

for(int i=1;i<=n;i++)
{
{
}

{
}

}

for(int i=n;i>=1;i--)
{
{
}

{
}

}

//	out.println(Arrays.toString(prev)+" "+Arrays.toString(next));

long ret=0;

for(int i=1;i<=n;i++)
{
long val1=i-prev[i]+1,val2=next[i]-i+1;

ret=ret+(val1*val2*a[i]);
}

return ret;
}

public static void main(String args[]) throws Exception
{
int t=sc.nextInt();

while(t>0)
{

n=sc.nextInt();int[] a=new int[n+1];int[][] arr=new int[n+1][n+1];

for(int i=1;i<=n;i++)
{
a[i]=sc.nextInt();
}

for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
arr[i][j]=(a[i]==a[j]?1:0);
}
}

int[][] val=new int[n+1][n+1];

for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(arr[i][j]==0)
{
val[i][j]=1+val[i][j-1];
}
}
}

long res=0;

for(int j=1;j<=n;j++)
{
int[] x=new int[n+1];

for(int i=1;i<=n;i++)
{
x[i]=val[i][j];
}

res+=solve(x);

//	out.println(res);
}

out.println(res/2);t--;
}

out.close();
}
}
class Pair
{
int idx,val;

public Pair(int idx,int val)
{
this.idx=idx;this.val=val;
}

}
class FastScanner
{
StringTokenizer st;

this.in = in;
}

public String nextToken() throws Exception {
while (st == null || !st.hasMoreTokens()) {
}
return st.nextToken();
}

public String next() throws Exception {
return nextToken().toString();
}

public int nextInt() throws Exception {
return Integer.parseInt(nextToken());
}

public long nextLong() throws Exception {
return Long.parseLong(nextToken());
}

public double nextDouble() throws Exception {
return Double.parseDouble(nextToken());
}
}``````

## Chef and Segments CodeChef Solution in PYTH

``````import sys

def solution():
T = int(raw_input().strip())
for _ in xrange(T):
N = int(raw_input().strip())
arr = list(map(int, raw_input().strip().split(' ')))
dp_arr = [[0,0] for i in xrange(N)]
sums = 0
for i in xrange(N):
previous_sum = 0
streak = 0
for j in xrange(i + 1, N):
if arr[i] != arr[j]:
streak += 1
dp_arr[j][0] += 1
dp_arr[j][1] = dp_arr[j][0]
if dp_arr[j][0] >= dp_arr[j - 1][0]:
previous_sum += dp_arr[j][0]
dp_arr[j][1] = dp_arr[j][0]
sums += previous_sum
#print "&&", i, j, sums, previous_sum

else:
mins = dp_arr[j][0]
new_sum = mins
for k in xrange(j-1, j-streak, -1):
if dp_arr[k][0] > mins:
previous_sum -= dp_arr[k][1]
new_sum += mins
dp_arr[k][1] = mins
else:
break
previous_sum += new_sum
sums += previous_sum
#print "&&", i, j, sums, previous_sum
else:
dp_arr[j][0] = 0
dp_arr[j][1] = 0
streak = 0
previous_sum = 0
#print "%%%",i,sums, dp_arr
print "%d" % (sums)

solution()``````

## Chef and Segments CodeChef Solution in C#

``````using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;

class Program
{
{
while (t-- > 0)
{
var a = new int[n];
var x = new int[n];
for (int i = 0; i < n; ++i)
{
}
long res = 0;
for (int i = 0; i < n; ++i)
{
var map = new Dictionary<int, int>();
var e = new long[n];
var r = new int[n];
map[a[i]] = 0;
for (int j = i + 1; j < n; ++j)
{
if (!map.ContainsKey(a[j]))
{
map[a[j]] = j - i;
}
int k = j - 1;
while (k > i && map[a[j]] < map[a[k]])
{
k = r[k];
}
e[j] = map[a[j]] * (j - k) + e[k];
r[j] = k;
res += e[j];
}
}
writer.WriteLine(res);
}
}

#region launch
static void Main(string[] args)
{
using (var writer = new FormattedStreamWriter(Console.OpenStandardOutput()))
{
#if CODECHIEF_LOCAL
"input.txt"
#else
Console.OpenStandardInput()
#endif
))
{
}
}
}
#endregion
}

#region helpers
class FormattedStreamWriter : StreamWriter
{
public FormattedStreamWriter(Stream stream)
: base(stream)
{
}

public override IFormatProvider FormatProvider
{
get
{
return CultureInfo.InvariantCulture;
}
}
}

static class IOExtensions
{
{
}

{
}

{
}

{
}

static Queue<string> buffer = new Queue<string>(100);

{
while (buffer.Count == 0)
{
{
buffer.Enqueue(t);
});
}
return buffer.Dequeue();
}
}
#endregion``````

## Chef and Segments CodeChef Solution in GO

``````package main

import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)

func convertToInt(array []string) []int {
var intarray []int
for _, i := range array {
j, _ := strconv.ParseInt(i, 10, 32)
j32 := int(j)
intarray = append(intarray, j32)
}
return intarray
}

type BitVector struct {
vector []uint64
nBits  int
}

func createBitVector(nBits int) *BitVector {
return &BitVector{vector: make([]uint64, (nBits-1)/64+1), nBits: nBits}
}

func (b *BitVector) set(bitNum uint) {
word := bitNum / 64
bit := bitNum % 64
b.vector[word] |= 1 << bit
}

func (b *BitVector) unset(bitNum uint) {
word := bitNum / 64
bit := bitNum % 64
b.vector[word] &= ^(1 << bit)
}

func (b *BitVector) or(a *BitVector) bool {
changed := false
for i, word := range a.vector {
old := b.vector[i]
b.vector[i] |= word
if old != b.vector[i] {
changed = true
}
}
return changed
}

func (b *BitVector) print() {
for _, word := range b.vector {
fmt.Printf("%064b ", word)
}
fmt.Println()
}

type StartAtIndexI struct {
b        *BitVector
numPairs uint
}

func (s *StartAtIndexI) calculate() {
numPairs := uint(0)
lastOverLapLocation := -1
location := 0
// fmt.Printf("vector: ")
for i := 0; i < len(s.b.vector); i++ {
// fmt.Printf("%064b\n", s.b.vector[i])
}
for i := 0; i < len(s.b.vector); i++ {
word := s.b.vector[i]
if word != 0 {
for j := uint(0); j < 64; j++ {
bit := uint64(1) << j
if bit&word != 0 {
nums_since_last_overlap := location - (lastOverLapLocation + 1)
numPairs += uint((nums_since_last_overlap * (nums_since_last_overlap + 1)) / 2)
// fmt.Println("location:", location, "lastOverLapLocation:", lastOverLapLocation, "nums_since_last_overlap:", nums_since_last_overlap)
lastOverLapLocation = location
}
location += 1
}
} else {
location += 64
}
}
s.numPairs = numPairs
}

func solve(scanner *bufio.Scanner) {
scanner.Scan()
input := scanner.Text()
// _, _ := strconv.ParseInt(input, 10, 32)
scanner.Scan()
input = scanner.Text()
prob_str := strings.Split(input, " ")
prob := convertToInt(prob_str)

new_prob := make([]int, len(prob))
origNumToNewNumMap := map[int]int{}

for i, num := range prob {
if new_num, ok := origNumToNewNumMap[num]; ok {
new_prob[i] = new_num
} else {
origNumToNewNumMap[num] = len(origNumToNewNumMap)
new_prob[i] = origNumToNewNumMap[num]
}
}

bitVectors := make([]*BitVector, len(origNumToNewNumMap))

for i := 0; i < len(bitVectors); i++ {
bitVectors[i] = createBitVector(len(new_prob))
}

startAtIndexIArray := make([]StartAtIndexI, len(new_prob))
for i := 0; i < len(startAtIndexIArray); i++ {
startAtIndexIArray[i].b = createBitVector(len(new_prob))
}

numPairs := uint(0)
for i, num := range new_prob {
// fmt.Println("i:", i)
bitVectors[num].set(uint(i))
startAtIndexIArray[i].b.set(uint(i))
startAtIndexIArray[i].b.or(bitVectors[num])
startAtIndexIArray[i].calculate()
numPairs += startAtIndexIArray[i].numPairs
// fmt.Println("numPairs:", numPairs)
for j := i - 1; j >= 0; j-- {
// fmt.Println("j:", j)
startAtIndexIArray[j].b.set(uint(i))
change := startAtIndexIArray[j].b.or(bitVectors[num])
if change {
startAtIndexIArray[j].calculate()
}
numPairs += startAtIndexIArray[j].numPairs
}
// fmt.Println("numPairs:", numPairs)
}
fmt.Println(numPairs)
}

func main() {
scanner := bufio.NewScanner(os.Stdin)

scanner.Scan()
input := scanner.Text()
ntests, _ := strconv.ParseInt(input, 10, 32)

for i := int64(0); i < ntests; i++ {
solve(scanner)
}
}``````
##### Chef and Segments CodeChef Solution Review:

In our experience, we suggest you solve this Chef and Segments 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 Chef and Segments CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Chef and Segments 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!