Chef and Segments CodeChef Solution

Problem -Chef and Segments 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.

Chef and Segments CodeChef Solution in C++14

“ ”

#include <bits/stdc++.h>

using namespace std;

#ifdef PRADEEP
  #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;
    num_matrices answer, tempAnswer;
     
    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]);
     
            answer = 0;
            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;
                tempAnswer = 0;
                REPEAT(j, height) {
                    while (stack[stackLength-1] != -1 && emptyToRight[i][stack[stackLength-1]] >= emptyToRight[i][j]) {
                        tempAnswer -= (stack[stackLength-1]-stack[stackLength-2])*emptyToRight[i][stack[stackLength-1]];
                        stackLength--;
                    }
                    stack[stackLength++] = j;
                    tempAnswer += (stack[stackLength-1]-stack[stackLength-2])*emptyToRight[i][stack[stackLength-1]];
                    answer += tempAnswer;
                }
            }
            //printing answer
            printf("%lli\n", answer/2);
        }
        
        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 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	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)
	{
		ArrayDeque<Pair> ad=new ArrayDeque<>();
		
		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++)
		{
			while(ad.size()>0 && ad.getFirst().val>=a[i])		
			{
				ad.removeFirst();
			}
			
			if(ad.size()>0)
			{
				prev[i]=ad.getFirst().idx+1;
			}
			
			ad.addFirst(new Pair(i,a[i]));
		}
		
		ad.clear();
		
		for(int i=n;i>=1;i--)
		{
			while(ad.size()>0 && ad.getFirst().val>a[i])
			{
				ad.removeFirst();
			}
			
			if(ad.size()>0)
			{
				next[i]=ad.getFirst().idx-1;
			}
			
			ad.addFirst(new Pair(i,a[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
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        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;
using System.Threading;
using System.Threading.Tasks;

class Program
{
    static void solve(StreamReader reader, StreamWriter writer)
    {
        int t = reader.ReadInt();
        while (t-- > 0)
        {
            int n = reader.ReadInt();
            var a = new int[n];
            var x = new int[n];
            for (int i = 0; i < n; ++i)
            {
                a[i] = reader.ReadInt();
            }
            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()))
        {
            using (var reader = new StreamReader(
#if CODECHIEF_LOCAL
    "input.txt"
#else
    Console.OpenStandardInput()
#endif
                ))
            {
                solve(reader, writer);
            }
        }
    }
    #endregion
}

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

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

static class IOExtensions
{
    public static string ReadString(this StreamReader reader)
    {
        return reader.ReadToken();
    }

    public static int ReadInt(this StreamReader reader)
    {
        return int.Parse(reader.ReadToken(), CultureInfo.InvariantCulture);
    }

    public static long ReadLong(this StreamReader reader)
    {
        return long.Parse(reader.ReadToken(), CultureInfo.InvariantCulture);
    }

    public static double ReadDouble(this StreamReader reader)
    {
        return double.Parse(reader.ReadToken(), CultureInfo.InvariantCulture);
    }

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

    static string ReadToken(this StreamReader reader)
    {
        while (buffer.Count == 0)
        {
            reader.ReadLine().Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries).ToList().ForEach((t) =>
            {
                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!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn