Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
ChefGame CodeChef Solution
Problem -ChefGame 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.
ChefGame CodeChef Solution in C++14
“#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define ff first
#define ss second
#define inf (1LL<<61)
#define pi acos(-1)
#define ppcll __builtin_popcountll
#define all(x) x.begin(), x.end()
#define intPow(n, p) (ll)(pow(n, p) + 0.5)
#define InTheNameofAllah ios_base::sync_with_stdio(0); cin.tie(NULL);
#define debug(x) cout<<"["<<#x<<": "<<x<<"]\n"
#define debug2(x, y) cout<<"["<<#x<<": "<<x<<"]"<<" ["<<#y<<": "<<y<<"]\n"
#define debug3(x, y, z) cout<<"["<<#x<<": "<<x<<"]"<<" ["<<#y<<": "<<y<<"]"<<" ["<<#z<<": "<<z<<"]\n"
#define debug4(x, y, z, k) cout<<"["<<#x<<": "<<x<<"]"<<" ["<<#y<<": "<<y<<"]"<<" ["<<#z<<": "<<z<<"]"<<" ["<<#k<<": "<<k<<"]\n"
const ll N = 6666+6;
const ll mod = 747474747;
ll dis[N];
struct Point {
vector<ll> cord;
Point(ll n) {
cord.assign(n, 0);
}
void init() {
for(int i=0; i<cord.size(); i++) cin>> cord[i];
}
ll dist(Point& other) {
ll ans = 0;
for(int i=0; i<cord.size(); i++) {
ans += (other.cord[i] - cord[i])*(other.cord[i] - cord[i]);
}
return ans;
}
};
int main()
{
InTheNameofAllah
ll tt;
cin>> tt;
while(tt--){
ll n, d;
cin>> n >> d;
vector<Point> points(n, Point(d));
for(int i=0; i<n; i++) points[i].init();
dis[0] = 1;
vector<int> taken(n);
ll ans = 1;
for(int i=0; i<n; i++) {
int u = -1;
for(int j=0; j<n; j++) {
if(!taken[j] && (u==-1 || dis[j] > dis[u])) u = j;
}
if(dis[u] == 0) break;
taken[u] = 1;
ans = (ans * (dis[u]%mod)) % mod;
for(int v=0; v<n; v++) {
if(!taken[v] && dis[v] < points[u].dist(points[v])) dis[v] = points[u].dist(points[v]);
}
}
cout<< ans << endl;
for(int i=0; i<n; i++) dis[i] = 0;
}
}ChefGame CodeChef Solution in C
“#include<stdio.h>
#include<stdlib.h>
long long int arr[6666][5];
int visited[6666];
long long int MST = 1;
long long int cost[6666];
int N,D;
long long int distance(int i,int j){
long long int dist=0;
for(int k=0;k<D;k++){
dist+=(arr[i][k]-arr[j][k])*(arr[i][k]-arr[j][k]);
}
return dist;
}
long long int findMST(){
for(int i = 0; i<N;i++){
visited[i] = 0;
cost[i] = 0;
}
int index=0;
long long int tempCost = 0;
visited[index] = 1;
int currIndex = 0;
MST = 1;
for(int i = 0; i < N-1;i++){
tempCost = 0;
for(int j=0; j < N; j++){
if(visited[j] == 1)continue;
if(cost[j] < distance(index,j)){
cost[j] = distance(index,j);
}
if(cost[j]>tempCost){
tempCost = cost[j];
currIndex = j;
}
}
visited[currIndex] = 1;
if(tempCost != 0)
{
MST = (MST*(tempCost%747474747))%747474747;
index = currIndex;
}
}
return MST%747474747;
}
int main(){
int T;
scanf("%d",&T);
for(int i = 1; i<=T; i++){
scanf("%d %d",&N,&D);
for(int j = 0;j<N;j++){
for(int k = 0;k<D;k++){
scanf("%lld",&arr[j][k]);
}
}
printf("%lld\n",findMST());
}
return 0;
}ChefGame CodeChef Solution in JAVA
“
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.InputMismatchException;
public class Main {
static boolean[]marked;
static long distTo[];
static IndexPQ pq;
static int N,D;
static int[][]coords;
private static final long MOD = 747474747;
public static void main(String[] args) throws Exception {
final InputReader in = new InputReader(System.in);
final OutputWriter out = new OutputWriter(System.out);
int T = in.readInt();
while (T-- > 0) {
N = in.readInt();
D = in.readInt();
coords = new int[N][D];
for(int i=0;i<N;i++){
for(int j=0;j<D;j++){
coords[i][j]=in.readInt();
}
}
long res = 1;
if(N > 1){
distTo = new long[N];
marked = new boolean[N];
pq = new IndexPQ(N);
prim(0); // minimum spanning forest
for(int v=0;v<N;v++){
if(distTo[v]!=0){
res = (res * (distTo[v]%MOD))%MOD;
}
}
if(res < 0)
res*=-1;
}
out.printLine(res);
}
out.close();
}
// run Prim's algorithm in graph G, starting from vertex s
static void prim(int s) {
distTo[s] = 0;
pq.insert(s, distTo[s]);
while (!pq.isEmpty()) {
int v = pq.delMin();
scan(v);
}
}
// scan vertex v
static void scan(int v) {
marked[v] = true;
for (int w=1;w<N;w++) {
if (marked[w]) continue; // v-w is obsolete edge
long dist = 0;
for(int d=0;d<D;d++){
dist += pow(coords[v][d]-coords[w][d]);
}
dist*=-1;
if (dist < distTo[w]) {
distTo[w] = dist;
if(pq.priority[w]==0)
pq.insert(w, distTo[w]);
else
pq.change(w, distTo[w]);
}
}
}
static long pow(long a)
{
return a*a;
}
static class IndexPQ {
private int N; // number of elements on PQ
private int[] pq; // binary heap
private int[] qp; //
private double[] priority; // priority values
public IndexPQ(int NMAX) {
pq = new int[NMAX + 1];
qp = new int[NMAX + 1];
priority = new double[NMAX + 1];
N = 0;
}
public boolean isEmpty() { return N == 0; }
// insert element k with given priority
public void insert(int k, double value) {
N++;
qp[k] = N;
pq[N] = k;
priority[k] = value;
fixUp(pq, N);
}
// delete and return the minimum element
public int delMin() {
exch(pq[1], pq[N]);
fixDown(pq, 1, --N);
return pq[N+1];
}
// change the priority of element k to specified value
public void change(int k, double value) {
priority[k] = value;
fixUp(pq, qp[k]);
fixDown(pq, qp[k], N);
}
/**************************************************************
* General helper functions
**************************************************************/
private boolean greater(int i, int j) {
return priority[i] > priority[j];
}
private void exch(int i, int j) {
int t = qp[i]; qp[i] = qp[j]; qp[j] = t;
pq[qp[i]] = i; pq[qp[j]] = j;
}
/**************************************************************
* Heap helper functions
**************************************************************/
private void fixUp(int[] a, int k) {
while (k > 1 && greater(a[k/2], a[k])) {
exch(a[k], a[k/2]);
k = k/2;
}
}
private void fixDown(int[] a, int k, int N) {
int j;
while (2*k <= N) {
j = 2*k;
if (j < N && greater(a[j], a[j+1])) j++;
if (!greater(a[k], a[j])) break;
exch(a[k], a[j]);
k = j;
}
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public String readLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public String readString() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public long readLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void printLine(Object... objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
}
}ChefGame CodeChef Solution in PYPY 3
“import sys
import os
try:
sys.stdin = open('./input.txt', 'r')
sys.stdout = open('./output.txt', 'w')
except:
pass
def compute_edge_cost(u,v,node_dimension):
weight = 0
for ai,bi in zip(node_dimension[u],node_dimension[v]):
weight += ((ai-bi)**2)
return weight
for _ in range(int(input())):
nodes,dimensions = map(int,input().split())
node_dimension = []
score = 1
for _ in range(nodes):
dimension = list(map(int,input().split()))
node_dimension.append(dimension)
computed_nodes = [False for _ in range(nodes)]
computed_nodes[0] = True
edge_values = []
for v in range(nodes):
edge_cost = compute_edge_cost(0,v,node_dimension)
edge_values.append(edge_cost)
for _ in range(1,nodes):
max_node = 0
for i in range(nodes):
if not computed_nodes[i] and (edge_values[max_node] < edge_values[i] or max_node==0):
max_node = i
computed_nodes[max_node] = True
if edge_values[max_node] < 2:
break
score = score*(edge_values[max_node] % 747474747)
score %= 747474747
for i in range(nodes):
if not computed_nodes[i]:
edge_values[i] = max(edge_values[i],compute_edge_cost(i,max_node,node_dimension))
print(score)ChefGame 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) {
scanner.Scan()
x := readInt(scanner.Bytes(), 0, &a)
readInt(scanner.Bytes(), x+1, &b)
return
}
func readNNums(scanner *bufio.Scanner, n int) []int {
res := make([]int, n)
x := -1
scanner.Scan()
for i := 0; i < n; i++ {
x = readInt(scanner.Bytes(), x+1, &res[i])
}
return res
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
t := readNum(scanner)
for t > 0 {
N, D := readTwoNums(scanner)
points := make([][]int, N)
for i := 0; i < N; i++ {
points[i] = readNNums(scanner, D)
}
fmt.Println(solve(N, D, points))
t--
}
}
const MOD = 747474747
func solve(N int, D int, points [][]int) int64 {
// sort.Sort(Points(points))
dist := make([]int64, N)
dist[0] = 0
for i := 1; i < N; i++ {
dist[i] = distance(points[0], points[i])
}
var score int64 = 1
seen := make([]bool, N)
seen[0] = true
for {
u := -1
for i := 0; i < N; i++ {
if seen[i] {
continue
}
if u == -1 || dist[u] < dist[i] {
u = i
}
}
if u < 0 || dist[u] == 0 {
break
}
score *= (dist[u]) % MOD
score %= MOD
seen[u] = true
for i := 0; i < N; i++ {
if seen[i] {
continue
}
tmp := distance(points[i], points[u])
if tmp > dist[i] {
dist[i] = tmp
}
}
}
return score
}
func distance(a, b []int) int64 {
var res int64
for i := 0; i < len(a); i++ {
d := int64(a[i]) - int64(b[i])
res += d * d
}
return res
}ChefGame CodeChef Solution Review:
In our experience, we suggest you solve this ChefGame 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 ChefGame CodeChef Solution.
“Conclusion:
I hope this ChefGame 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!
