Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Chef and Minimum Colouring CodeChef Solution
Problem -Chef and Minimum Colouring 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 Minimum Colouring CodeChef Solution in C++14
#include<bits/stdc++.h>
using namespace std;
#define fast_cin() \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define int long long int
#define rep(i, a, b) for (ll i = a; i < b; i++)
const int N=1e5+10;
#define PI 3.141592653589793238462
#define mod 1000000007
#define modadd(a, b, c) ((a % c) + (b % c)) % c
#define modmul(a, b, c) ((a % c) * (b % c)) % c
#define modsub(a, b, c) ((a % c) - (b % c)) % c
void solve()
{
int m,n ;
cin>>n>>m;
vector<pair<int,int>>v(n);
for(int i=0;i<n;i++){
cin>>v[i].first;
v[i].second=i%m;
}
int count=m;
int right=0;
int ans=INT_MAX;
sort(v.begin(),v.end());
vector<int>cnt(m,0);
for(int left=0;left<n;left++){
while(right<n and count>0){
count-=cnt[v[right].second]==0;
cnt[v[right].second]++;
right++;
}
if(count==0){
ans=min(ans,v[right-1].first-v[left].first);
}
if(cnt[v[left].second]>0){
cnt[v[left].second]--;
}
// cout<<count<<"a";
count+= cnt[v[left].second]==0;
// cout<<count<<endl;
}
cout<<ans<<endl;
}
signed main(){
fast_cin();
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}Chef and Minimum Colouring CodeChef Solution in PYTH 3
# cook your dish here
for q in range(int(input())):
n,m = map(int,input().split())
l1,l,c,f,r,result =[int(x) for x in input().split()],[],[0]*m,0,0,10**10
for i in range (0,n):
l2 = []
l2.append(l1[i]),l2.append(i%m)
l.append(l2)
l.sort()
for i in range(n):
while(r<n and f<m):
if(c[l[r][1]]==0):f+=1
c[l[r][1]]+=1
r+=1
if(f==m):result = min(result,l[r-1][0]-l[i][0])
c[l[i][1]]-=1
if(c[l[i][1]]==0):f-=1
print(result) Chef and Minimum Colouring CodeChef Solution in C
#include<stdio.h>
#include<stdlib.h>
void merge(long long int arr[],long long int l,long long int m,long long int r)
{
long long int i, j, k;
long long int n1 = m - l + 1;
long long int n2 = r - m;
/* create temp arrays */
long long int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(long long int arr[],long long int l,long long int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
long long int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void sort(long long int ua,long long int m,long long int a[ua][m],long long int i,long long int mav)
{
long long int b[mav];
long long int j,k,l,u;
for(j=0;j<mav;j++)
{
b[j]=a[j][i];
}
mergeSort(b,0,mav-1);
for(j=0;j<mav;j++)
{
a[j][i]=b[j];
}
}
int main()
{
int t;
scanf("%d",&t);
while(t>0)
{
long long int i,j,k,n,m,u,p,min,d1,d2,d3,in,im,min1,max1,ua;
scanf("%lld%lld",&n,&m);
u=n/m;
ua=u;
if(n%m!=0)
{
u++;
}
//printf("%d")
ua=u;
p=0;
long long int a[u][m];
for(i=0;i<u;i++)
{
for(j=0;j<m;j++)
{
scanf("%lld",&a[i][j]);
p++;
if(p==n)
{
break;
}
}
if(p==n)
{
break;
}
}
//printf("Hello\n");
long long int ind[m],max[m];
for(i=0;i<m;i++)
{
ind[i]=0;
max[i]=n/m;
}
u=n%m;
for(i=0;i<u;i++)
{
max[i]++;
}
for(i=0;i<m;i++)
{
sort(ua,m,a,i,max[i]);
}
/*for(i=0;i<ua;i++)
{
for(j=0;j<m;j++)
{
printf("%lld\t",a[i][j]);
}
printf("\n");
}*/
min1=-1;
max1=-1;
min=-1;
while(1)
{
min1=-1;
max1=-1;
for(i=0;i<m;i++)
{
if(min1==-1)
{
min1=a[ind[i]][i];
in=i;
}
else if(min1>a[ind[i]][i])
{
min1=a[ind[i]][i];
in=i;
}
if(max1<a[ind[i]][i])
{
max1=a[ind[i]][i];
im=i;
}
}
//printf("%lld\t%lld\n",max1,min1);
d1=max1-min1;
if(min==-1)
{
min=d1;
}
else if(min>d1)
{
min=d1;
}
ind[in]++;
if(ind[in]==max[in])
{
break;
}
}
printf("%lld\n",min);
t--;
}
}
Chef and Minimum Colouring CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
class Main
{
/* static class pair{
long area;int idx;
pair(){}
pair(long a,int b)
{
area=a;
idx=b;
}
}
private static class Book {
int exercises;
String name;
int index;
public Book(){
this.index=0;
}
}*/
static class box implements Comparable<box>
{
int balls;
int color;
public box(int balls, int color)
{
this.balls = balls;
this.color = color;
}
@Override
public int compareTo (box ob)
{
return(Integer.compare(this.balls, ob.balls));
}
}
static class Color implements Comparable {
Integer color;
Integer value;
public Color(Integer color, Integer value) {
this.color = color;
this.value = value;
}
@Override
public int compareTo(Object o) {
return Integer.compare(this.value, ((Color)o).value);
}
}
/* static class Pair
{
int a,b;
Pair(int a,int b)
{this.a = a;this.b=b;}
}*/
static class Triplet
{
int x[]=new int[3];
Triplet(int a,int b,int c)
{
this.x[0]=a;
this.x[1] =b;
this.x[2] = c;
}
}
static class Rec
{
String s;
int pri;
}static class Point
{
int x;
int y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
};
public static long mod = 1000000007;
public static long [][] tempMatrix;
public static long max = (long) Math.pow(10, 9) + 7;
static StringBuilder sb = new StringBuilder();
public static int rootColor=0;
static boolean primes[]=new boolean[10000001];
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
FastReader in = new FastReader(System.in);
Scanner sc = new Scanner(System.in);
PrintWriter out=new PrintWriter(System.out);
HashMap<Integer, Integer> h = new HashMap<Integer, Integer>();
HashSet<Integer> s = new HashSet<Integer>();
HashSet<Character> h2 = new HashSet<Character>();
//long t= in.nextLong();
// long t = in.nextLong();
//DecimalFormat df = new DecimalFormat("#,###,##0.000000");
long mod = 1000000007;
int prime[]=new int[10000006];
for(int i=2;i<prime.length;i++){
if(prime[i]==0){
for(int j=i;j<prime.length;j+=i){
prime[j]+=i;
}
}
}
int t=in.nextInt();
// while(t-->0)
while(t-->0)
{
Integer N = in.nextInt();
Integer M = in.nextInt();
List<Color> colors = new ArrayList<>();
for (int j = 0; j < N; j++) {
Color color = new Color(j % M, in.nextInt());
colors.add(color);
}
Collections.sort(colors);
Integer minRange = Integer.MAX_VALUE;
int k =0;
Map<Integer, Integer> colourToCount = new HashMap<>();
for (int j = 0; j < N; j++) {
for (; colourToCount.size() != M && k<N ; k++) {
colourToCount.put(colors.get(k).color, colourToCount.getOrDefault(colors.get(k).color, 0) + 1);
}
if (colourToCount.size() == M) {
minRange = Math.min(minRange, colors.get(k-1).value - colors.get(j).value);
}
colourToCount.put(colors.get(j).color, colourToCount.get(colors.get(j).color) - 1);
if (colourToCount.get(colors.get(j).color) == 0) {
colourToCount.remove(colors.get(j).color);
}
}
System.out.println(minRange);
}
}
static long power(long x, long y, long p)
{
long res = 1;
x = x % p;
if (x == 0) return 0;
while (y > 0)
{
if((y & 1)==1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
} return res;
}
static int gcd(int n, int m) {
if(m == 0) return n;
return gcd(m, n % m);
}
static class FastReader {
byte[] buf = new byte[2048];
int index, total;
InputStream in;FastReader(InputStream is) {
in = is;
} int scan() throws IOException {
if (index >= total) {
index = 0;
total = in.read(buf);
if (total <= 0) { return -1;
}
}
return buf[index++];
}
String next() throws IOException {
int c;
for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder();
for (; c > 32; c = scan()) {
sb.append((char) c);
}
return sb.toString();
}String nextLine() throws IOException {
int c;for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder();
for (; c != 10 && c != 13; c = scan()) {
sb.append((char) c);
}
return sb.toString();
}char nextChar() throws IOException {
int c;
for (c = scan(); c <= 32; c = scan()) ;
return (char) c;
} int nextInt() throws IOException {
int c, val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan(); }
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}long nextLong() throws IOException {
int c;
long val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan();
}
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}
}
}
Chef and Minimum Colouring CodeChef Solution in PYPY 3
“for _ in range(int(input())):
n,m = list(map(int,input().split()))
arr = list(map(int,input().split()))
color = []
for i in range(n):
color.append([arr[i],i%m])
color.sort()
final = [0 for i in range(m)]
ans = 10**10
cnt = m
for i in range(n):
if final[color[i][1]]==0:
cnt-=1
final[color[i][1]] = color[i][0]
if cnt==0:
t = max(final)-min(final)
if t<ans:
ans = t
print(ans)Chef and Minimum Colouring CodeChef Solution in PYTH
t = input()
for _ in range(t):
n, m = map(int, raw_input().split())
a = map(int, raw_input().split())
cs = []
for i in range(n):
cs.append((a[i], i % m))
cs.sort()
cnt = [0] * m
ok = 0
l = 0
r = 0
resp = max(a) - min(a)
while r < n:
while ok < m and r < n:
_, c = cs[r]
if cnt[c] == 0:
ok += 1
cnt[c] += 1
r += 1
while ok == m:
resp = min(resp, cs[r - 1][0] - cs[l][0])
_, c = cs[l]
if cnt[c] == 1:
ok -= 1
cnt[c] -= 1
l += 1
print(resp)Chef and Minimum Colouring CodeChef Solution in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Xml.XPath;
namespace CodeChef._2019_11.CAMC
{
#region ConsoleHelper
public interface IConsoleHelper
{
string ReadLine();
T ReadLineAs<T>();
string[] ReadLineAndSplit(char delimiter = ' ');
List<T> ReadLineAndSplitAsListOf<T>(char delimiter = ' ');
void WriteLine(object obj);
void Debug(object obj);
}
public class ConsoleHelper : IConsoleHelper
{
public virtual string ReadLine()
{
return Console.ReadLine();
}
public T ReadLineAs<T>()
{
var line = ReadLine();
return ConvertTo<T>(line);
}
public string[] ReadLineAndSplit(char delimiter = ' ')
{
var splittedLine = ReadLine().Split(delimiter);
return splittedLine;
}
public List<T> ReadLineAndSplitAsListOf<T>(char delimiter = ' ')
{
var splittedLine = ReadLineAndSplit();
return splittedLine.Select(ConvertTo<T>).ToList();
}
public virtual void WriteLine(object obj)
{
Console.WriteLine(obj);
}
public void Debug(object obj)
{
Console.Error.WriteLine(obj);
}
private static T ConvertTo<T>(string value)
{
return (T) Convert.ChangeType(value, typeof(T));
}
}
#endregion
public static class Program
{
public static IConsoleHelper ConsoleHelper;
static Program()
{
ConsoleHelper = new ConsoleHelper();
}
public static void Main(string[] args)
{
SolveMultiple();
}
public static void SolveMultiple()
{
var t = ConsoleHelper.ReadLineAs<int>();
for (var k = 0; k < t; k++)
{
Solve();
}
}
public static void Solve()
{
var input = ConsoleHelper.ReadLineAndSplitAsListOf<int>();
var n = input[0];
var m = input[1];
var items = ConsoleHelper.ReadLineAndSplitAsListOf<int>().ToArray();
var sortedItems = items.Select((x, i) => new {value = x, key = i % m}).OrderBy(x => x.value).ToList();
var queues = sortedItems.GroupBy(x => x.key)
.OrderBy(x => x.Key)
.Select(x => new Queue<int>(x.Select(y => y.value).OrderBy(y => y).ToList()))
.ToArray();
var min = sortedItems[0].value;
var max = queues.Select(g => g.Dequeue()).Max();
var diff = max - min;
for (var i = 0; i < n - 1; i++)
{
var key = sortedItems[i].key;
if (queues[key].Count == 0)
break;
var value = queues[key].Dequeue();
if (value > max)
max = value;
min = sortedItems[i + 1].value;
if (diff > max - min)
diff = max - min;
}
ConsoleHelper.WriteLine(diff);
}
public static void SolveConsecutive()
{
var input = ConsoleHelper.ReadLineAndSplitAsListOf<int>();
var n = input[0];
var m = input[1];
var array = ConsoleHelper.ReadLineAndSplitAsListOf<int>().ToArray();
var max = new int[n];
var min = new int[n];
var diff = new int[n];
var maxIndexes = new List<int>();
var minIndexes = new List<int>();
for (var i = 0; i < n + m; i++)
{
var idx = i % n;
// dequeue
maxIndexes.Remove(i - m);
minIndexes.Remove(i - m);
// enqueue
Add(idx, array, maxIndexes, (current, localMax) => current >= localMax);
Add(idx, array, minIndexes, (current, localMin) => current <= localMin);
// set
max[idx] = array[maxIndexes[0]];
min[idx] = array[minIndexes[0]];
diff[idx] = max[idx] - min[idx];
}
ConsoleHelper.WriteLine(diff.Min());
}
private static void Add(int i, int[] array, List<int> indexes, Func<int, int, bool> comparator)
{
var idx = indexes.Count;
for (var k = 0; k < indexes.Count; k++)
{
if (comparator(array[i], array[indexes[k]]))
{
idx = k;
break;
}
}
indexes.Insert(idx++, i);
indexes.RemoveRange(idx, indexes.Count - idx);
}
}
}Chef and Minimum Colouring CodeChef Solution in GO
package main
import (
"fmt"
"bufio"
"strconv"
"os"
"strings"
"sort"
"container/heap"
)
type element struct {
v, x, y int
}
type minHeap []element
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].v < h[j].v }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) {
*h = append(*h, x.(element))
}
func (h *minHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n - 1]
*h = old[0: n - 1]
return x
}
func max(x, y int) int {
if x > y { return x }
return y
}
func min(x, y int) int {
if x < y { return x }
return y
}
func main() {
reader := bufio.NewReader(os.Stdin)
t, _ := strconv.ParseInt(readLine(reader), 10, 64)
for ; t > 0; t-- {
tmpNM := strings.Split(readLine(reader), " ")
tmpN, _ := strconv.ParseInt(tmpNM[0], 10, 64)
tmpM, _ := strconv.ParseInt(tmpNM[1], 10, 64)
n, m := int(tmpN), int(tmpM)
_ = n
tmpArr := strings.Split(readLine(reader), " ")
box := make([][]int, m)
for i := range(tmpArr) {
tmpNum, _ := strconv.ParseInt(tmpArr[i], 10, 64)
box[i % m] = append(box[i % m], int(tmpNum))
}
h := new(minHeap)
mx := 0
for i := range(box) {
sort.Ints(box[i])
heap.Push(h, element{box[i][0], i, 1})
mx = max(mx, box[i][0])
}
var flag bool = true
var ans int = 1000000000
for flag {
mn := heap.Pop(h).(element)
ans = min(ans, mx - mn.v)
if mn.y < len(box[mn.x]) {
heap.Push(h, element{box[mn.x][mn.y], mn.x, mn.y + 1})
mx = max(mx, box[mn.x][mn.y])
} else {
flag = false
}
}
fmt.Println(ans)
}
return
}
func readLine(reader *bufio.Reader) string {
str, _ := reader.ReadString('\n')
return strings.TrimRight(string(str), "\r\n ")
}Chef and Minimum Colouring CodeChef Solution Review:
In our experience, we suggest you solve this Chef and Minimum Colouring 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 Minimum Colouring CodeChef Solution.
Conclusion:
I hope this Chef and Minimum Colouring 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!
