Chef and Ants CodeChef Solution

Problem -Chef and Ants 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>>

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 rnd(chrono::steady_clock::now().time_since_epoch().count());
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);}

ll modAdd(ll a, ll b){
    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()
{
    // your code goes here
    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 getInput(): return sys.stdin.readline().strip()
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
	{
		// your code goes here
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while(t-->0) {
		    int n = Integer.parseInt(br.readLine());
		    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<>();
		        String[] s = br.readLine().split(" ");
		        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) {
		                positiveAnt[i].add(v);
		                if(mp.containsKey(v)) {
		                    ArrayList<Line> val = mp.get(v);
		                    val.add(new Line(i,1));
		                    mp.put(v,val);
		                } else {
		                    ArrayList<Line> val = new ArrayList<>();
		                    val.add(new Line(i,1));
		                    mp.put(v,val);
		                }
		            } else {
		                negativeAnt[i].add(v);
		                if(mp.containsKey(-v)) {
		                    ArrayList<Line> val = mp.get(-v);
		                    val.add(new Line(i,-1));
		                    mp.put(-v,val);
		                } else {
		                    ArrayList<Line> val = new ArrayList<>();
		                    val.add(new Line(i,-1));
		                    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;

	public static void Main(TextReader input)
	{
		for (var t = int.Parse(input.ReadLine()); t > 0; t--)
		{
			var n = int.Parse(input.ReadLine());
			var lines = new List<int>[n];
			for (var i = 0; i < n; i++)
			{
				var inputLine = input.ReadLine().Split().Skip(1).Select(int.Parse).ToList();
				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))
			{
				lines2.Add(lineIndex);
			}
			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;

			AddNextOriginTime(lines, i);
		}
		//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)
				{
					AddNextOriginTime(lines, lineIndex);
				}
			}
			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})");
					}
					
					AddNextOriginTime(lines, lineIndex);
				}

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

Chef and Ants CodeChef Solution in NODEJS

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

// your code goes here
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 reader *bufio.Reader = bufio.NewReader(os.Stdin)
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
			}
			antColony.addLine(line)
			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!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn