Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Cute Chef Gift CodeChef Solution

Problem -Cute Chef Gift 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.
<<Previous CodeChef Problem Next Codechef Problem>>

Cute Chef Gift CodeChef Solution in C++17

#include <iostream>
using namespace std;

const int MAXN{100000 + 4};
int dzielnik[MAXN];
int gdzie_lewo[MAXN];
int gdzie_prawo[MAXN];
int ile_przedzialow[MAXN];

void Sito(){
    for(size_t i = 2; i * i < MAXN; i++){
        if(dzielnik[i] == 0){
            for(size_t j = i * i; j < MAXN; j += i)
                dzielnik[j] = i;
        }
    }
    for(size_t i = 2; i < MAXN; i++){
        if(dzielnik[i] == 0)
            dzielnik[i] = i;
    }
}

void Solve(){
    //Czyszczenie tablic
    for(size_t i = 1; i <= MAXN; ++i){
        gdzie_lewo[i] = MAXN - 1;
        gdzie_prawo[i] = 0;
        ile_przedzialow[i] = 0;
    }
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++ i){
        int a;
        cin >> a;
        while(a > 1){
            int p = dzielnik[a];
            gdzie_lewo[p] = min(gdzie_lewo[p], i);
            gdzie_prawo[p] = max(gdzie_prawo[p], i);
            a /= p;
        }
    }
    for(size_t i = 2; i < MAXN; ++i){
        int l = gdzie_lewo[i];
        int p = gdzie_prawo[i];
        if(l <= p){
            ile_przedzialow[l] +=1;
            ile_przedzialow[p] -=1;
        }
    }
    for(size_t i = 1; i <= n; ++i){
        ile_przedzialow[i] += ile_przedzialow[i-1];
    }
    for(size_t i = 1; i < n; ++i){
        if(ile_przedzialow[i] == 0){
            cout << i << endl;
            return;
        }
    }
}

int main() {
	// your code goes here
	Sito();
	int t;
	cin >> t;
	for(size_t i = 1; i <= t; ++i)
	    Solve();
	    
	return 0;
}

Cute Chef Gift CodeChef Solution in C++14

#include<iostream>
using namespace std;
typedef long long ll;
constexpr ll maxA=1e5+7;
ll D[maxA];
int T,N;
int main(){
    for (int i = 2; i < maxA; i++)
    {
        D[i]=-1;
    }
    for (ll i = 2; i < maxA; i++)
    {
        if(D[i]==-1){
            D[i]=i;
            for (ll j = i*i; j < maxA; j+=i)
            {
                D[j]=i;
            }
        }
    }
    cin>>T;
    for (int t = 0; t < T; t++)
    {
        cin>>N;
        ll nums[N+1];
        ll first[maxA]={0};
        ll last[maxA]={0};
        for (int i = 1; i <=N; i++)
        {
            cin>>nums[i];
            int x=nums[i];
            while(x>1){
                int div=D[x];
                if(first[div]>i||first[div]==0){
                    first[div]=i;
                }
                if(last[div]<i){
                    last[div]=i;
                }
                x=x/div;
            }
        }
        int range[N+1]={0};
        for (int i = 2; i <maxA; i++)
        {
            if(first[i]>0&&last[i]>0){
                range[first[i]]+=1;
                range[last[i]]+=-1;
            }
        }
        for (int i = 1; i < N+1; i++)
        {
            range[i]=range[i-1]+range[i];
        }
        for (int i = 1; i < N+1; i++)
        {
            if(range[i]==0){
                cout<<i<<'\n';
                break;
            }
        }
        
        
    }
    return 0;
}

Cute Chef Gift CodeChef Solution in PYTH 3

# cook your dish here
N=100000
prime=[-1 for i in range(N+1)]
i=2
while(i<=N):
    if prime[i]==-1:
        prime[i]=i
        for j in range(2*i,N+1,i):
            if prime[j]==-1:
                prime[j]=i
          
    i+=1
from math import gcd
for _ in range(int(input())):
    n=int(input())
    arr=list(map(int,input().split()))
    range_p=[[-1,-1] for i in range(N+1)]
    for i in range(n):
        a=arr[i]
        while(a>1):
            x=prime[a]
            
            if range_p[x][0]==-1:
                range_p[x][0]=i
                range_p[x][1]=i
            else:
                range_p[x][1]=i
            a=a//x
        
    #print(range_p[:10])
    mark=[0 for i in range(n)]
    for i in range(2,N+1):
        if range_p[i][0]!=-1:
            l=range_p[i][0]
            r=range_p[i][1]
            mark[l]+=1
            mark[r]-=1
    for i in range(1,n):
        mark[i]+=mark[i-1]
    #print(mark)
    for i in range(n):
        if mark[i]==0:
            print(i+1)
            break
        

Cute Chef Gift CodeChef Solution in C

#include<stdio.h>
int main(){long int t,i,j,k,a[100005],b[100005],c[100005],g[100005],left,n;
 scanf("%ld",&t);
 for(i=0;i<t;i++)
 {
  scanf("%ld",&n);
  for(j=0;j<n;j++)
  {
   scanf("%ld",&a[j]);
   b[j]=a[j];
   c[j]=j;
  }
  for(j=0;j<=100000;j++)
  {
   g[j]=-1;
  }
  for(j=n-1;j>=0;j--)
  {
   if(b[j]%2==0)
   {
    while(b[j]%2==0)
    {
     b[j]=b[j]/2;
    }
    if(g[2]==-1)
    {
     g[2]=j;
    }
   }
   for(k=3;k*k<=b[j];k=k+2)
   {
    if(b[j]%k==0)
    {
     while(b[j]%k==0)
     {
      b[j]=b[j]/k;
     }
     if(g[k]==-1)
     {
      g[k]=j;
     }
    }
   }
   if(b[j]>2)
   {
    if(g[b[j]]==-1)
    g[b[j]]=j;
   }
  }
  for(j=0;j<n;j++)
  {
   if(a[j]%2==0)
   {
    while(a[j]%2==0)
    {
     a[j]=a[j]/2;
    }
    if(c[j]<=g[2])
    {
     c[j]=g[2];
    }
   }
   for(k=3;k*k<=a[j];k=k+2)
   {
    if(a[j]%k==0)
    {
     while(a[j]%k==0)
     {
      a[j]=a[j]/k;
     }
     if(g[k]>=c[j])
     {
      c[j]=g[k];
     }
    }
   }
   if(a[j]>2)
   {
    if(g[a[j]]>=c[j])
    c[j]=g[a[j]];
   }
  }
  left=0;
  for(j=0;j<n;j++)
  {
   if(left<c[j])
   left=c[j];
   if(left==j)
   break;
  }
  printf("\n");
  printf("%ld\n",j+1);
 }
 return 0;
}

Cute Chef Gift 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
{
    static ArrayList<Integer> al;
    static int start[];
    static int end[];
    static int size;
    static int max=(int)1e5+1;
    static Pair array[];
    static class Pair{
        int a,b,c;
        Pair(int a,int b,int c){
            this.a=a;
            this.b=b;
            this.c=c;
        }
    }
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc=new Scanner(System.in);
        boolean val[]=new boolean[1000];
        al=new ArrayList<>();
        for(int i=2;i<val.length;i++)
        {
            if(!val[i]){
                al.add(i);
                for(int j=i*2;j<val.length;j+=i){
                    val[j]=true;
                }
            }
        }
        //System.out.println(al);
        int t=sc.nextInt();
        while(t-->0){
            int n=sc.nextInt();
            int arr[]=new int[n];
            start=new int[max];
            end=new int[max];
            size=0;
            Arrays.fill(start,-1);
            Arrays.fill(end,-1);
            int max_element=0;
            for(int i=0;i<n;i++) {
                arr[i]=sc.nextInt();
                max_element=Math.max(max_element,arr[i]);
            }
            help(arr);
            /*for (int ele : al) {
                System.out.println("val= " + ele + " start= " + start[ele] + " end= " + end[ele]);
                if (ele > max_element)
                    break;
            }*/
            array=new Pair[size];
            int k=0;
            for(int i=0;i< start.length;i++){
                if(start[i]!=-1){
                    array[k]=new Pair(i,start[i],end[i]);
                    k++;
                }
            }
            Arrays.sort(array, new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    return o1.b- o2.b;
                }
            });
            int en=array[0].c;
            for(int i=1;i<array.length;i++){
                if(en<array[i].b){
                    System.out.println(en+1);
                    break;
                }
                en=Math.max(en,array[i].c);
            }
        }
	}
	private static void help(int[] arr) {
        int k;
        for(int i=0;i<arr.length;i++){
            k=0;
            while (arr[i]>1 && k<al.size()){
                int curr=al.get(k);
                while(arr[i]%curr==0){
                    if(start[curr]==-1)
                    {
                        size++;
                        start[curr]=i;
                    }
                    end[curr]=i;
                    arr[i]/=curr;
                }
                k++;
            }
            if(arr[i]>1){
                if(start[arr[i]]==-1)
                {
                    size++;
                    start[arr[i]]=i;
                }
                end[arr[i]]=i;
            }
        }
    }
}

Cute Chef Gift CodeChef Solution in PYPY 3

MAXN = 100000 + 7

# dzielnik[i] = dowolny dzielnik pierwszy liczby i
dzielnik = [0]*MAXN

def sito():
	i = 2
	while (i*i < MAXN):
		if (dzielnik[i] == 0):
			for j in range(i*i, MAXN, i):
				dzielnik[j] = i
		i = i + 1

	for i in range(2, MAXN):
		if (dzielnik[i] == 0):
			dzielnik[i] = i

def solve():
	# gdzieLewo[p] = pierwszy indeks,
	# na ktorym liczba jest podzielna przez p (pierwsze)
	gdzieLewo = [MAXN]*MAXN
	# gdziePrawo[p] = ostatni indeks,
	# na ktorym liczba jest podzielna przez p (pierwsze)
	gdziePrawo = [0]*MAXN

	n = int(input())
	liczby = list(map(int, input().split()))
	for i in range(n):
		a = liczby[i]
		# rozklad liczby a na czynniki pierwsze
		while (a > 1):
			p = dzielnik[a]
			gdzieLewo[p] = min(gdzieLewo[p], i+1)
			gdziePrawo[p] = max(gdziePrawo[p], i+1)
			a //= p

	ilePrzedzialow = [0]*(n + 1)
	for i in range(MAXN):
		l = gdzieLewo[i]
		r = gdziePrawo[i]
		if (l <= r):
			ilePrzedzialow[l] += 1
			ilePrzedzialow[r] -= 1

	for i in range(1, n):
		ilePrzedzialow[i] += ilePrzedzialow[i - 1]

	for i in range(1, n):
		if (ilePrzedzialow[i] == 0):
			print(i)
			return

sito()

T = int(input())
for i in range(T):
	solve()

Cute Chef Gift CodeChef Solution in PYTH


l=[[] for i in range(10**5+1)]
for i in range(2,10**5+1):
    if l[i]==[]:
        for j in range(i,10**5+1,i):
            l[j].append(i)
for _ in range(input()):
    n=input()
    a=map(int,raw_input().split())
    d={}
    for i in range(n):
        for j in l[a[i]]:
            if j in d:
                d[j]+=1
            else:
                d[j]=1
    touched=0
    zer=0
    rech={}
    for i in range(n):
        for j in l[a[i]]:
            if j not in rech:
                touched+=1
                rech[j]=1
            d[j]-=1
            if d[j]==0:
                zer+=1
        if zer==touched:
            ans=i+1
            break
    print ans

Cute Chef Gift 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;

// (づ°ω°)づミe★゜・。。・゜゜・。。・゜☆゜・。。・゜゜・。。・゜
public class Solution
{
    private const int SIEVE_SIZE = 100000;
    private readonly bool[] isComposite = new bool[SIEVE_SIZE + 1];
    private readonly List<int> primes = new List<int>();
    void Sieve()
    {
        for (int i = 2; i * i <= SIEVE_SIZE; i++)
            if (!isComposite[i])
                for (int j = i * i; j <= SIEVE_SIZE; j += i)
                    isComposite[j] = true;
        for (int i = 2; i <= SIEVE_SIZE; i++)
            if (!isComposite[i])
                primes.Add(i);
    }

    public void Solve()
    {
        Sieve();

        for (int tt = ReadInt(); tt > 0; tt--)
        {
            int n = ReadInt();
            var a = ReadIntArray();

            var b = Init<List<Tuple<int, int>>>(n);
            int m = primes.Count;
            var rcnt = new int[m];
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; primes[j] * primes[j] <= a[i]; j++)
                    if (a[i] % primes[j] == 0)
                    {
                        int c = 0;
                        while (a[i] % primes[j] == 0)
                        {
                            a[i] /= primes[j];
                            c++;
                        }
                        b[i].Add(Tuple.Create(j, c));
                        rcnt[j] += c;
                    }
                if (a[i] > 1)
                {
                    int x = primes.BinarySearch(a[i]);
                    b[i].Add(Tuple.Create(x, 1));
                    rcnt[x]++;
                }
            }

            int o = 0;
            var lcnt = new int[m];
            for (int i = 0; i + 1 < n; i++)
            {
                foreach (var t in b[i])
                {
                    if (lcnt[t.Item1] == 0 && rcnt[t.Item1] > 0)
                        o++;
                    lcnt[t.Item1]++;

                    rcnt[t.Item1] -= t.Item2;
                    if (rcnt[t.Item1] == 0)
                        o--;
                }
                if (o == 0)
                {
                    Write(i + 1);
                    break;
                }
            }
        }
    }

    #region Main

    protected static TextReader reader;
    protected static TextWriter writer;
    static void Main()
    {
#if DEBUGLOCAL
        reader = new StreamReader("..\\..\\input.txt");
        //reader = new StreamReader(Console.OpenStandardInput());
        writer = Console.Out;
        //writer = new StreamWriter("..\\..\\output.txt");
#else
        reader = new StreamReader(Console.OpenStandardInput());
        writer = new StreamWriter(Console.OpenStandardOutput());
        //reader = new StreamReader("input.txt");
        //writer = new StreamWriter("output.txt");
#endif
        try
        {
            new Solution().Solve();
            //var thread = new Thread(new Solver().Solve, 1024 * 1024 * 128);
            //thread.Start();
            //thread.Join();
        }
        catch (Exception ex)
        {
#if DEBUG
            Console.WriteLine(ex);
#else
            throw;
#endif
        }
        reader.Close();
        writer.Close();
    }

    #endregion

    #region Read / Write
    private static Queue<string> currentLineTokens = new Queue<string>();
    private static string[] ReadAndSplitLine() { return reader.ReadLine().Split(new[] { ' ', '\t', }, StringSplitOptions.RemoveEmptyEntries); }
    public static string ReadToken() { while (currentLineTokens.Count == 0) currentLineTokens = new Queue<string>(ReadAndSplitLine()); return currentLineTokens.Dequeue(); }
    public static int ReadInt() { return int.Parse(ReadToken()); }
    public static long ReadLong() { return long.Parse(ReadToken()); }
    public static double ReadDouble() { return double.Parse(ReadToken(), CultureInfo.InvariantCulture); }
    public static int[] ReadIntArray() { return ReadAndSplitLine().Select(int.Parse).ToArray(); }
    public static long[] ReadLongArray() { return ReadAndSplitLine().Select(long.Parse).ToArray(); }
    public static double[] ReadDoubleArray() { return ReadAndSplitLine().Select(s => double.Parse(s, CultureInfo.InvariantCulture)).ToArray(); }
    public static int[][] ReadIntMatrix(int numberOfRows) { int[][] matrix = new int[numberOfRows][]; for (int i = 0; i < numberOfRows; i++) matrix[i] = ReadIntArray(); return matrix; }
    public static int[][] ReadAndTransposeIntMatrix(int numberOfRows)
    {
        int[][] matrix = ReadIntMatrix(numberOfRows); int[][] ret = new int[matrix[0].Length][];
        for (int i = 0; i < ret.Length; i++) { ret[i] = new int[numberOfRows]; for (int j = 0; j < numberOfRows; j++) ret[i][j] = matrix[j][i]; }
        return ret;
    }
    public static string[] ReadLines(int quantity) { string[] lines = new string[quantity]; for (int i = 0; i < quantity; i++) lines[i] = reader.ReadLine().Trim(); return lines; }
    public static void WriteArray<T>(IEnumerable<T> array) { writer.WriteLine(string.Join(" ", array)); }
    public static void Write(params object[] array) { WriteArray(array); }
    public static void WriteLines<T>(IEnumerable<T> array) { foreach (var a in array) writer.WriteLine(a); }
    private class SDictionary<TKey, TValue> : Dictionary<TKey, TValue>
    {
        public new TValue this[TKey key]
        {
            get { return ContainsKey(key) ? base[key] : default(TValue); }
            set { base[key] = value; }
        }
    }
    private static T[] Init<T>(int size) where T : new() { var ret = new T[size]; for (int i = 0; i < size; i++) ret[i] = new T(); return ret; }
    #endregion
}

Cute Chef Gift CodeChef Solution in GO

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)

	tc := readNum(reader)
	var buf bytes.Buffer
	for tc > 0 {
		tc--
		n := readNum(reader)
		A := readNNums(reader, n)
		res := solve(n, A)
		buf.WriteString(fmt.Sprintf("%d\n", res))
	}
	fmt.Print(buf.String())
}

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] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

func readUint64(bytes []byte, from int, val *uint64) int {
	i := from

	var tmp uint64
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + uint64(bytes[i]-'0')
		i++
	}
	*val = tmp

	return i
}

const MAX_A = 100010

var spf [MAX_A]int

func init() {
	set := make([]bool, MAX_A)
	for x := 2; x < MAX_A; x++ {
		if !set[x] {
			for y := x; y < MAX_A; y += x {
				if spf[y] == 0 {
					spf[y] = x
				}
				set[y] = true
			}
		}
	}
}

func solve(n int, A []int) int {
	left := make(map[int]int)
	right := make(map[int]int)

	update := func(mem map[int]int, k int, v int, fn func(int, int) int) {
		if w, ok := mem[k]; !ok {
			mem[k] = v
		} else {
			mem[k] = fn(w, v)
		}
	}

	for i := 0; i < n; i++ {
		cur := A[i]

		for spf[cur] != cur {
			x := spf[cur]
			update(left, x, i, min)
			update(right, x, i, max)
			cur /= x
		}
		update(left, cur, i, min)
		update(right, cur, i, max)
	}

	cnt := make([]int, n+1)

	for k, i := range left {
		j := right[k]
		cnt[i]++
		cnt[j]--
	}

	for i := 1; i <= n; i++ {
		cnt[i] += cnt[i-1]
	}
	for i := 1; i <= n; i++ {
		if cnt[i-1] == 0 {
			return i
		}
	}
	return -1
}

func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}
Cute Chef Gift CodeChef Solution Review:

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

Find on CodeChef

Conclusion:

I hope this Cute Chef Gift 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

Leave a Reply

Your email address will not be published. Required fields are marked *