304 North Cardinal St.
Dorchester Center, MA 02124

# Chef and Ants CodeChef Solution

## Chef and Ants CodeChef Solution in C++17

``````#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnf(2106);
const int N = 500005;

int n;
vector<int> d[N], b[N];

void solv()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
d[i].clear();
b[i].clear();
}

map<int, int> mp;
for (int i = 1; i <= n; ++i)
{
int q;
cin >> q;
while (q--)
{
int x;
cin >> x;
if (x > 0)
d[i].push_back(x);
else
b[i].push_back(-x);
++mp[abs(x)];
}
reverse(all(d[i]));
}

ll ans = 0;
for (int i = 1; i <= n; ++i)
{
while (1)
{
if (d[i].empty() && b[i].empty())
break;
if (!d[i].empty() && !b[i].empty() && d[i].back() == b[i].back())
{
ans += (sz(d[i]) - 1);
ans += (sz(b[i]) - 1);
d[i].pop_back();
b[i].pop_back();
}
else if (b[i].empty() || (!d[i].empty() && d[i].back() < b[i].back()))
{
if (mp[d[i].back()] == 1)
ans += sz(b[i]);
else
ans += (sz(d[i]) - 1);
d[i].pop_back();
}
else
{
if (mp[b[i].back()] == 1)
ans += sz(d[i]);
else
ans += (sz(b[i]) - 1);
b[i].pop_back();
}
}
}

for (auto it = mp.begin(); it != mp.end(); ++it)
{
if (it->se >= 2)
++ans;
}

cout << ans << "\n";
}

int main()
{
#ifdef SOMETHING
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif // SOMETHING
ios_base::sync_with_stdio(false), cin.tie(0);

int tt = 1;
cin >> tt;
while (tt--)
{
solv();
}
return 0;
}``````

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

``````
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<utility>
#include<set>
#include<unordered_set>
#include<list>
#include<iterator>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<bitset>
#include<random>
#include<map>
#include<unordered_map>
#include<stdio.h>
#include<complex>
#include<math.h>
#include<cstring>
#include<chrono>
#include<string>
#include<climits>

using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimization("unroll-loops, no-stack-protector")
//#pragma GCC target("avx,avx2,fma")

typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpii;
typedef vector<vi> vii;
typedef vector<bool> vb;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound

#define endl "\n"
#define all(v) v.begin(), v.end()
#define sum(v) accumulate(all(v), 0LL)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define pop_count(n) __builtin_popcount(n)

#define rep(i, a, n) for (int i = a; i < n; i++)
#define rev(i, a, n) for (int i = n - 1; i >= a; i--)
#define vin(v) for(auto &it:v) cin>>it;
#define vin_1(v) rep(i,1,v.size())cin>>v[i];
#define vout(v) rep(i,0,v.size())cout<<v[i]<<' ';cout<<'\n';
#define vout_1(v) rep(i,1,v.size())cout<<v[i]<<' ';cout<<'\n';
#define yes cout<<"YES"<<'\n'
#define no  cout<<"NO"<<'\n'

#define INF 10000000000000007
const ll mod = 1000000007;

//***************************************Template Ends********************************************//

bool sortbysec(const pii &a,const pii &b){return (a.ss < b.ss);}

a = a % mod; b = b % mod;
return (((a + b) % mod) + mod) % mod;
}

ll mod_mul(ll a, ll b){
a = a % mod; b = b % mod;
return (((a * b) % mod) + mod) % mod;
}

ll modPower(ll a, ll b){
ll res = 1;
while(b > 0){
if(b&1)res = res*a % mod;
a = a*a % mod;
b = (b >> 1);
}
return res%mod;
}

struct cmp {
bool operator()(const ll& x, const ll& y) const {
return (abs(x) < abs(y));
}
};

void solve()
{
ll n; cin >> n;
map<ll,ll> m;
vii a;

for(ll i = 0; i < n; i++){
ll sz; cin >> sz;
vi v;
while(sz--){
ll x; cin >> x;
m[abs(x)]++;
v.pb(x);
}
a.pb(v);
}

ll ans = 0;
for(auto it : m){
ans += (it.ss > 1);
}

for(auto v : a){

multiset<ll,cmp> s;
ll neg = 0, pos = 0;

for(auto x : v){
neg += (x < 0);
pos += (x > 0);
s.insert(x);
}

while(s.size()){
ll x = *s.begin();
s.erase(s.begin());
neg -= (x < 0);
pos -= (x > 0);

if(m[abs(x)] > 1){
if(x > 0)ans += pos;
else ans += neg;
}
else{
if(x > 0)ans += neg;
else ans += pos;
}
}
}
cout << ans << endl;
return;
}

int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cout.precision(30);
cout.setf(ios::fixed);
auto ti_start = std::chrono::high_resolution_clock::now();
ll t;
t = 1;
cin >> t;
while(t--){
solve();
}
auto ti_end = std::chrono::high_resolution_clock::now();
std::chrono::duration<float> duration = ti_end - ti_start;
#ifndef ONLINE_JUDGE
cout << endl;
printf("[%0.3fms]",duration.count() * 1000.0f);
#endif
return 0;
}``````

## Chef and Ants CodeChef Solution in PYTH 3

``````import sys
# import math as mt
# from collections import Counter, deque
# from itertools import permutations
# from functools import reduce
# from heapq import heapify, heappop, heappush, heapreplace

def getInt(): return int(getInput())
def getInts(): return map(int, getInput().split())
def getArray(): return list(getInts())

# sys.setrecursionlimit(10**7)
# INF = float('inf')
# MOD1, MOD2 = 10**9+7, 998244353

tc = getInt()

for _ in range(tc):

n = getInt()
lines = []
for __ in range(n):
lines.append(getArray()[1:])

mp = dict()
for line in lines:
for ant in line:
if abs(ant) in mp:
mp[abs(ant)] += 1
else:
mp[abs(ant)] = 1

ans = 0

for i in mp.values():
if i >= 2:
ans += 1  # Collision at Origin

for line in lines:

# order -> farthest to closest
neg = []
pos = []
for ant in line:
if ant < 0:
neg.append(ant)
else:
pos.append(ant)
pos.reverse()

while True:

try:
if abs(neg[-1]) < pos[-1]:
closest = neg[-1]
else:
closest = pos[-1]
except:
if not neg and not pos:
break
if not neg:
closest = pos[-1]
if not pos:
closest = neg[-1]

if mp[abs(closest)] >= 2:
if closest < 0:
ans += len(neg)-1
else:
ans += len(pos)-1
else:
if closest < 0:
ans += len(pos)
else:
ans += len(neg)

if closest < 0:
neg.pop()
else:
pos.pop()

print(ans)``````

## Chef and Ants CodeChef Solution in C

``````#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
typedef long long (ll);
void merge2(ll arr[],ll l,ll m,ll r,ll ind[],ll y[])
{
ll i,j,k,n1,n2;
n1=m-l+1;
n2=r-m;
ll L[n1],R[n2],L1[n1],L2[n1],R1[n2],R2[n2];
for(i=0;i<n1;i++)
{
L[i]=arr[l+i];
L2[i]=ind[l+i];
L1[i]=y[l+i];
}
for(j=0;j<n2;j++)
{
R[j]=arr[m+1+j];
R2[j]=ind[m+1+j];
R1[j]=y[m+1+j];
}
i=j=0;
k=l;
while(i<n1&&j<n2)
{
if(L[i]<R[j])
{
arr[k]=L[i];
ind[k]=L2[i];
y[k]=L1[i];
i++;
}
else if(L[i]>R[j])
{
arr[k]=R[j];
ind[k]=R2[j];
y[k]=R1[j];
j++;
}
else
{
if(L2[i]<R2[j])
{
arr[k]=L[i];
ind[k]=L2[i];
y[k]=L1[i];
i++;
}
else
{
arr[k]=R[j];
ind[k]=R2[j];
y[k]=R1[j];
j++;
}
}
k++;
}
while(i<n1)
{
arr[k]=L[i];
ind[k]=L2[i];
y[k]=L1[i];
i++;
k++;
}
while(j<n2)
{
arr[k]=R[j];
ind[k]=R2[j];
y[k]=R1[j];
j++;
k++;
}
}
void sort2(ll arr[],ll l,ll r,ll ind[],ll y[])
{
if(l<r)
{
ll m=l+(r-l)/2;
sort2(arr,l,m,ind,y);
sort2(arr,m+1,r,ind,y);
merge2(arr,l,m,r,ind,y);
}
}
int main()
{
ll a,b,c,d,e,f,g,h,i,j,k,l,m,n;
scanf("%lli",&a);
for(;a;a--)
{
scanf("%lli",&d);
f=0;
m=1000000;
ll z[m],y[m];
for(e=m=0;e<d;e++)
{
scanf("%lli",&g);
for(h=0;h<g;h++)
{
scanf("%lli",&z[m]);
y[m]=e;
m++;
}
}
ll x[m];
for(e=0;e<m;e++)
{
if(z[e]<0)
{
z[e]=0-z[e];
x[e]=0;
}
else x[e]=1;
}
ll w[m][2];
sort2(z,0,m-1,y,x);
ll s[d][2];
for(e=0;e<d;e++)
s[e][0]=s[e][1]=0;
for(e=m-1,i=j=0,k=z[m-1]+1,l=d,n=y[e];e>=0;e--)
{
if(z[e]<k||y[e]!=l)
{
s[n][1]+=i;
s[n][0]+=j;
i=x[e];
j=1-i;
k=z[e];
l=y[e];
n=y[e];
}
else
{
if(x[e]==1)
i++;
else
j++;
}
w[e][1]=s[y[e]][1];
w[e][0]=s[y[e]][0];
}
if(m>1&&z[0]==z[1]&&y[0]<y[1])
{
g=w[0][1];
w[0][1]=w[0][0];
w[0][0]=g;
}
for(e=1;e<m-1;e++)
{
if(z[e]==z[e-1]&&z[e]==z[e+1]&&y[e-1]<y[e]&&y[e]<y[e+1])
{
g=w[e][1];
w[e][1]=w[e][0];
w[e][0]=g;
}
else if(z[e]==z[e-1]&&z[e]<z[e+1]&&y[e-1]<y[e])
{
g=w[e][1];
w[e][1]=w[e][0];
w[e][0]=g;
}
else if(z[e-1]<z[e]&&z[e]==z[e+1]&&y[e]<y[e+1])
{
g=w[e][1];
w[e][1]=w[e][0];
w[e][0]=g;
}
}
if(m>1&&z[m-2]==z[m-1]&&y[m-2]<y[m-1])
{
g=w[m-1][1];
w[m-1][1]=w[m-1][0];
w[m-1][0]=g;
}
for(e=0;e<m;e++)
{
f+=w[e][1-x[e]];
}
for(e=g=h=0;e<m;e++)
{
if(z[e]>g)
{
g=z[e];
if(h>1)f++;
h=1;
}
else
{
h++;
}
}
if(h>1)f++;
printf("%lli\n",f);
}
return 0;
}``````

## Chef and Ants 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
{
public static class Line{
int id;
int side;
Line(int id,int side) {
this.id=id;
this.side=side;
}
}
public static void main (String[] args) throws java.lang.Exception
{
while(t-->0) {
ArrayList<Integer>[] positiveAnt = new ArrayList[n];
ArrayList<Integer>[] negativeAnt = new ArrayList[n];
//  int[][] line = new int[n][];
HashMap<Integer,ArrayList<Line>> mp = new HashMap<>();
for(int i=0;i<n;i++) {
positiveAnt[i] = new ArrayList<>();
negativeAnt[i] = new ArrayList<>();
int m = Integer.parseInt(s[0]);
//  line[i]= new int[m];
for(int j=0;j<m;j++) {
int v=Integer.parseInt(s[j+1]);
//  line[i][j]=v;
if(v>0) {
if(mp.containsKey(v)) {
ArrayList<Line> val = mp.get(v);
mp.put(v,val);
} else {
ArrayList<Line> val = new ArrayList<>();
mp.put(v,val);
}
} else {
if(mp.containsKey(-v)) {
ArrayList<Line> val = mp.get(-v);
mp.put(-v,val);
} else {
ArrayList<Line> val = new ArrayList<>();
mp.put(-v,val);
}
}
}
//  Collections.sort(positiveAnt[i]);
//  Collections.sort(negativeAnt[i]);
}
//  printMap(mp);
long ans =0;
for(int k : mp.keySet()) {
ArrayList<Line> ant = mp.get(k);
//  printArray(ant);
if(ant.size()==1) {
int tl = positiveAnt[ant.get(0).id].size()+negativeAnt[ant.get(0).id].size();
if(ant.get(0).side==1) {
int idx1 = search(negativeAnt[ant.get(0).id],-k);
if(idx1<0) {
continue;
} else if(idx1>=negativeAnt[ant.get(0).id].size()) {
ans+=(long)(idx1);
} else {
ans+=(long)(idx1+1);
}
} else {
int idx1 = search(positiveAnt[ant.get(0).id],k);
if(idx1<0) {
ans+=(long)(positiveAnt[ant.get(0).id].size());
} else if(idx1>=positiveAnt[ant.get(0).id].size()) {
continue;
} else {
ans+=(long)(positiveAnt[ant.get(0).id].size()-idx1-1);
}
}
// System.out.println(ans);
} else {
ans++;
for(Line l : ant) {
int tl = positiveAnt[l.id].size()+negativeAnt[l.id].size();
if(l.side==1) {
int idx = search(positiveAnt[l.id],k);
ans+=(long)(positiveAnt[l.id].size()-idx-1);
} else {
int idx = search(negativeAnt[l.id],-k);
ans+=(long)(idx);
}
// System.out.println(ans);
}
}
//  System.out.println(ans);
}
System.out.println(ans);
}
}
public static int search(ArrayList<Integer> a,int n) {
int lo=0;
int hi=a.size()-1;
while(lo<=hi) {
int mid = (lo+hi)/2;
if(a.get(mid)==n) {
return mid;
} else if(a.get(mid)<n) {
lo=mid+1;
} else {
hi=mid-1;
}
}
return hi;
// if(hi<0 || hi>=a.size()) {
//     return -1;
// } else if(a.get(hi)==n) {
//     return hi;
// } else {
//     return -1;
// }
}
public static void printMap(HashMap<Integer,ArrayList<Line>> mp) {
for(int k : mp.keySet()) {
System.out.println(k+" --> "/*mp.get(k)*/);
printArray(mp.get(k));
}
}
public static void printArray(ArrayList<Line> mp) {
for(Line l : mp) {
System.out.println(l.id+" "+l.side);
}
}
}``````

## Chef and Ants CodeChef Solution in PYPY 3

``````t = int(input())
for i in range(t):
n = int(input())
d = {}
l = []
for j in range(n):
neg = 0
a = list(map(int, input().split()))
for k in range(a[0]):
if a[1+k] < 0:
neg += 1
if abs(a[1+k]) in d:
d[abs(a[1+k])].append([j+1, 0])
else:
d[abs(a[1+k])] = [[j+1, 0]]
else:
if a[1+k] in d:
if d[a[1+k]][-1][0] == j+1:
d[a[1+k]][-1][1] = 2
else:
d[a[1+k]].append([j+1, 1])
else:
d[a[1+k]] = [[j+1, 1]]
l.append([neg, a[0]-neg])
k = list(d.keys())
k.sort()
co = 0
for j in k:
if len(d[j]) == 1 and d[j][0][1] != 2:
if d[j][0][1] == 0:
l[d[j][0][0]-1][0] -= 1
co += l[d[j][0][0]-1][1]
else:
l[d[j][0][0]-1][1] -= 1
co += l[d[j][0][0]-1][0]
else:
co += 1
for k in d[j]:
if k[1] == 0 or k[1] == 2:
l[k[0]-1][0] -= 1
co += l[k[0]-1][0]
if k[1] == 1 or k[1] == 2:
l[k[0]-1][1] -= 1
co += l[k[0]-1][1]
print(co)``````

## Chef and Ants CodeChef Solution in PYTH

``````t = int(raw_input())
for i in range(t):
N = int(raw_input())
C = [[0,0] for x in range(N)]
A = []
for k in range(N):
st = raw_input().split()
m = int(st[0])
for p in range(1,m+1):
n = int(st[p])
if n < 0:
n = -n
C[k][0] += 1
A.append([n,k,0])
else:
C[k][1] += 1
A.append([n,k,1])
# endif
# endfor p
# endfor k
A.sort()
sz = len(A)
A.append([-1,0,0])
tot = 0
v = 0
p = 0
while p < sz:
nv = A[p][0]
if nv > v:
v = nv
if A[p+1][0] == v:
coll = True
tot += 1
else:
coll = False
# endif
# endif
d = A[p][2]
L = A[p][1]
C[L][d] -= 1
if coll:
tot += C[L][d]
else:
tot += C[L][1-d]
# endif
p += 1
# endwhile
print tot
# endfor i
``````

## Chef and Ants CodeChef Solution in C#

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

public class Test
{
public static void Main()
{
Main(Console.In);
}

public static int[] removedStart;
public static int[] removedEnd;
public static SortedDictionary<int, List<int>> originTimeToLines;

{
for (var t = int.Parse(input.ReadLine()); t > 0; t--)
{
var lines = new List<int>[n];
for (var i = 0; i < n; i++)
{
lines[i] = inputLine;
}

Console.WriteLine(TestCase(lines));
}
}

public static void AddNextOriginTime(List<int>[] lines, int lineIndex)
{
var line = lines[lineIndex];
bool hasCollision = false;
var originTime = 0;
if (removedEnd[lineIndex] < line.Count)
{
originTime = line[removedEnd[lineIndex]];
hasCollision = true;
}
if (removedStart[lineIndex] - 1 >= 0)
{
var otherCollisionTime = -line[removedStart[lineIndex] - 1];
if (!hasCollision || hasCollision && otherCollisionTime < originTime)
{
originTime = otherCollisionTime;
hasCollision = true;
}
}

if (hasCollision)
{
List<int> lines2;
if (originTimeToLines.TryGetValue(originTime, out lines2))
{
}
else
{
originTimeToLines.Add(originTime, new List<int>() { lineIndex });
}
}
}

public static long TestCase(List<int>[] lines)
{
removedStart = new int[lines.Length];
removedEnd = new int[lines.Length];

originTimeToLines = new SortedDictionary<int, List<int>>();

for (var i = 0; i < lines.Length; i++)
{
var line = lines[i];
var middle = line.BinarySearch(0);
if (middle < 0)
{
middle = ~middle;
}
removedStart[i] = middle;
removedEnd[i] = middle;

}
//1345294336
long totalCollisions = 0;

while (originTimeToLines.Count > 0)
{
//originTimeToLines.Dump("originTimeToLines");
var originTime = originTimeToLines.Keys.First();
var lineIndices = originTimeToLines[originTime];
originTimeToLines.Remove(originTime);

if (lineIndices.Count == 1)
{
var lineIndex = lineIndices[0];
var line = lines[lineIndex];

int leftBucketStart;
int rightBucketEnd;

if (originTimeToLines.Count > 0)
{
var nextOrigin = originTimeToLines.Keys.First();
// Find the ants which will cross the origin before any other line does
leftBucketStart = line.BinarySearch(0, removedStart[lineIndex], -nextOrigin, Comparer<int>.Default);
if (leftBucketStart < 0)
{
leftBucketStart = ~leftBucketStart;
}
else
{
leftBucketStart++;
}

rightBucketEnd = line.BinarySearch(removedEnd[lineIndex], line.Count - removedEnd[lineIndex], nextOrigin, Comparer<int>.Default);
if (rightBucketEnd < 0)
{
rightBucketEnd = ~rightBucketEnd;
}
}
else
{
leftBucketStart = 0;
rightBucketEnd = line.Count;
}

var antsToLeft = removedStart[lineIndex] - leftBucketStart;
var antsToRight = rightBucketEnd - removedEnd[lineIndex];
var antsFarLeft = leftBucketStart - 0;
var antsFarRight = line.Count - rightBucketEnd;

totalCollisions += (long)antsToLeft * (long)antsToRight + (long)antsToLeft * (long)antsFarRight + (long)antsToRight * (long)antsFarLeft;
//new { antsToLeft, antsToRight, leftBucketStart, rightBucketEnd }.Dump();
//totalCollisions.Dump(\$"total collisions (+ {antsToLeft}*{antsToRight} + {antsToLeft}*{antsFarRight} + {antsToRight}*{antsFarLeft} from left/right multiplication on line {lineIndex})");
removedStart[lineIndex] = leftBucketStart;
removedEnd[lineIndex]  = rightBucketEnd;

if (originTimeToLines.Count > 0)
{
}
}
else
{
// Collision between multiple lines

foreach (var lineIndex in lineIndices)
{
var line = lines[lineIndex];
if (removedStart[lineIndex] - 1 >= 0 && line[removedStart[lineIndex] - 1] == -originTime)
{
// left ant is colliding at origin
removedStart[lineIndex]--;
var antsFarLeft = removedStart[lineIndex] - 0;
totalCollisions += 1 * antsFarLeft;
//totalCollisions.Dump(\$"total collisions (+{antsFarLeft} after left ant turned around at origin on line {lineIndex})");
}
if (removedEnd[lineIndex] < line.Count && line[removedEnd[lineIndex]] == originTime)
{
// right ant is colliding at origin
removedEnd[lineIndex]++;
var antsFarRight = line.Count - removedEnd[lineIndex];
totalCollisions += 1 * antsFarRight;
//totalCollisions.Dump(\$"total collisions (+{antsFarRight} after right ant turned around at origin on line {lineIndex})");
}

}

totalCollisions++;
//totalCollisions.Dump("total collisions (+1 from origin collision)");
}
}

}
}
``````

## Chef and Ants CodeChef Solution in NODEJS

``````process.stdin.resume();
process.stdin.setEncoding('utf8');

var lineEnd = '\n';
var data = '';
process.stdin.on('data', function (chunk) {
data += chunk;
});

process.stdin.on('end', function () {
solve(data);
});

function prepare(input) {
let lines = input.split(lineEnd);
let t = parseInt(lines[0]);
let tests = [];
let curLine = 1;
for (let i = 0; i < t; i++) {
let n = parseInt(lines[curLine]);
curLine++;
let l = [];
for (let j = 0; j < n; j++) {
let ants = lines[curLine]
.split(' ')
.map(s => parseInt(s));
ants.shift();
l.push(ants);
curLine++;
}
tests.push(l);
}
return tests;
}
function dubmCalc(lines) {
let lineObjs = [];
let ants = [];
lines.forEach((line, lineIndex) => {
let lineObj = { left: 0, right: 0 };
line.forEach(antX => {
ants.push({ x: antX, line: lineObj, dist: Math.abs(antX) });
if (antX < 0) {
lineObj.left++;
}
else {
lineObj.right++;
}
});
lineObjs.push(lineObj);
});
ants = ants.sort((a, b) => a.dist - b.dist);
return calcAnts(ants);
}
function calcAnts(ants) {
let res = 0;
let bundle = [];
for (let i = 0; i < ants.length; i++) {
const ant = ants[i];
if (bundle.length == 0 || bundle[0].dist == ant.dist) {
bundle.push(ant);
}
else if (bundle.length > 0) {
res += calcBundle(bundle);
bundle = [ant];
}
}
res += calcBundle(bundle);
return res;
}
function calcBundle(bundle) {
let res = 0;
if (bundle.length == 1) {
let ant = bundle[0];
if (ant.x < 0) {
res += ant.line.right;
ant.line.left--;
}
else {
res += ant.line.left;
ant.line.right--;
}
}
else {
res++;
bundle.forEach(ant => {
if (ant.x < 0) {
res += ant.line.left - 1;
ant.line.left--;
}
else {
res += ant.line.right - 1;
ant.line.right--;
}
});
}
return res;
}
function solve(input) {
let tests = prepare(input);
let res = tests.map(t => dubmCalc(t));
res.forEach(r => console.log(r));
}``````

## Chef and Ants CodeChef Solution in GO

``````package main

import (
"bufio"
"fmt"
"os"
"sort"
)

var writer *bufio.Writer = bufio.NewWriter(os.Stdout)

func printf(f string, a ...interface{}) { fmt.Fprintf(writer, f, a...) }
func scanf(f string, a ...interface{})  { fmt.Fscanf(reader, f, a...) }

func main() {
defer writer.Flush()
var testCases int
for scanf("%d\n", &testCases); testCases > 0; testCases-- {
var antColony AntColony
var numLines int
scanf("%d\n", &numLines)
for line := 0; line < numLines; line++ {
var numAnts int
scanf("%d", &numAnts)
line := make(Line, numAnts)
for antIdx := 0; antIdx < numAnts; antIdx++ {
var ant Ant
scanf("%d", &ant.Position)
line[antIdx] = ant
}
scanf("\n")
}
collisions := antColony.getCollisions()
printf("%v\n", collisions)
}
}

type Ant struct {
Position int
}

type Line []Ant

func (line Line) addAnt(ant *Ant) {
line = append(line, *ant)
}

type AntColony struct {
Colony []Line
// map from absolute position to occurences
PositionOccs map[int]int
}

func (antColony *AntColony) addLine(line Line) {
antColony.Colony = append(antColony.Colony, line)
// increment position-occ map for all ants in line
if antColony.PositionOccs == nil {
antColony.PositionOccs = make(map[int]int)
}
for _, ant := range line {
absPos := absInt(ant.Position)
_, posExists := antColony.PositionOccs[absPos]
if !posExists {
antColony.PositionOccs[absPos] = 0
}
antColony.PositionOccs[absPos]++
}
}

func absInt(x int) int {
if x < 0 {
return -x
}
return x
}

func (antColony *AntColony) getPositionOccs(ant *Ant) int {
absPos := absInt(ant.Position)
return antColony.PositionOccs[absPos]
}

func (antColony *AntColony) willReflect(ant *Ant) bool {
willReflect := antColony.getPositionOccs(ant) > 1
return willReflect
}

// collisions on point O which forces to make U path
func (antColony *AntColony) getCenterCollisions() int64 {
// fmt.Println(antColony.PositionOccs)
collisions := 0
for _, occ := range antColony.PositionOccs {
collisions += boolToInt(occ > 1)
}
return int64(collisions)
}

func maxInt(x, y int) int {
if x > y {
return x
}
return y
}

func boolToInt(truth bool) int {
if truth {
return 1
}
return 0
}

func sgn(x int) int {
if x < 0 {
return -1
}
return 1
}

func (l Line) Len() int           { return len(l) }
func (l Line) Swap(i, j int)      { l[i], l[j] = l[j], l[i] }
func (l Line) Less(i, j int) bool { return absInt(l[i].Position) < absInt(l[j].Position) }

func (line Line) getCollisions(antColony *AntColony) int64 {
sort.Sort(line)
collisions := int64(0)
leftCount, rightCount := 0, 0
// single pass to populate +,-
for _, ant := range line {
if sgn(ant.Position) == -1 {
leftCount++
} else {
rightCount++
}
}
// -,s +,s/r
// -,u -,s/r
// +s, -s/r
// +u, +s/r
for _, ant := range line {
if sgn(ant.Position) == -1 {
leftCount--
} else {
rightCount--
}
reflects := antColony.willReflect(&ant)
antSign := sgn(ant.Position)
if reflects {
antSign *= -1
}
if antSign == -1 {
collisions += int64(rightCount)
} else {
collisions += int64(leftCount)
}
// no special case needed for equal
}
return collisions
}

// more of crossings
func (antColony *AntColony) getCollisions() int64 {
collisions := antColony.getCenterCollisions()
for _, line := range antColony.Colony {
selfCollisions := line.getCollisions(antColony)
collisions += selfCollisions
}
return collisions
}``````
##### Chef and Ants CodeChef Solution Review:

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

Find on CodeChef

##### Conclusion:

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