Chef and Ants ANTSCHEF SOLUTION Code Chef

Chef and Ants ANTSCHEF SOLUTION Code Chef

Chef has been researching ant colonies for many years and finally discovered all their secrets.

An ant colony consists of NN distinct lines (numbered 11 through NN) that pass through a point OO, which is the queen’s home. For each valid ii, there are MiMi ants on the ii-th line.

For each valid ii and jj, the jj-th ant on the ii-th line initially has a non-zero coordinate Xi,jXi,j with the following meaning:

  • The distance of this ant from OO is |Xi,j||Xi,j|.
  • Let’s choose a direction along the ii-th line from OO. The exact way in which this direction is chosen does not matter here, it only needs to be the same for all ants on the same line.
  • If Xi,jXi,j is positive, this ant is at the distance |Xi,j||Xi,j| from OO in the chosen direction. Otherwise, it is at this distance from OO in the opposite direction.

In other words, two ants jj and kk on a line ii are at the same side of OO if the signs of Xi,jXi,j and Xi,kXi,k are the same or on opposite sides if the signs are different.

All ants move with the same constant speed. Initially, all of them are moving towards OO. Whenever two or more ants meet (possibly at OO), all of these ants turn around and start moving in the opposite directions with the same speed. We call this a collision. Even if an ant reaches OO without meeting an ant there, it keeps moving in the same direction. An ant may change direction multiple times.

Help Chef find the total number of collisions between ants. Note that even if more than two ants meet, it counts as only one collision.

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • NN lines follow. For each valid ii, the ii-th of these lines contains an integer MiMi, followed by a space and MiMi space-separated integers Xi,1,Xi,2,…,Xi,MiXi,1,Xi,2,…,Xi,Mi.

Output

For each test case, print a single line containing one integer ― the number of collisions between ants.

Constraints

  • 1≤T≤1,0001≤T≤1,000
  • 1≤N≤2⋅1051≤N≤2⋅105
  • 1≤Mi≤5⋅1051≤Mi≤5⋅105 for each valid ii
  • 1≤|Xi,j|≤1091≤|Xi,j|≤109 for each valid i,ji,j
  • Xi,j<Xi,j+1Xi,j<Xi,j+1 for each valid i,ji,j
  • the sum of NN over all test cases does not exceed 2⋅1052⋅105
  • the sum of M1+M2+…+MNM1+M2+…+MN over all test cases does not exceed 106106

Subtasks

Subtask #1 (30 points): N=1N=1

Subtask #2 (70 points): original constraints

Example Input

1
2
2 -2 1
1 2

Example Output

2

Explanation

Example case 1: First, the ants on the first line collide at the coordinate −1/2−1/2 and change directions. Finally, ant 22 on the first line collides with the only ant on the second line; this happens at OO. No collisions happen afterwards.

Solution

Program Python:

t = int(input())
import collections
while(t>0):
    n = int(input())
    x = collections.defaultdict(int)
    c = []
    diff=0
    b=[]
    for j in range(n):
        ans=0
        r=0
        a = input().split()
        
        
        for i in range(len(a)):
            a[i] = int(a[i])
            if(i==0):
                continue
            if(int(a[i])<=0):
                ans+=1
            else:
                r+=1
            
            x[abs(a[i])]+=1
            # if(x[abs(a[i])]==1):
            #     diff+=1
        c.append(a[1:])
        b.append(ans)
        b.append(r)
    result=0
    d=[]
    if(n==0):
        print(ans*r)
    # print(n,len(b))
    else:
        for i in range(n):
            ppass=0
            npass=0
            for j in range(len(c[i])):
                if(x[abs(c[i][j])]==1):
                    if(c[i][j]>0):
                        ppass+=1
                    else:
                        npass+=1
                else:
                    if(c[i][j]>0):
                        result+=len(c[i])-j-1
                    else:
                        result+=j
                
                d.append(abs(c[i][j]))
            # print(result)
            result+=npass*ppass
            # print(result)
            p=0
            q=len(c[i])-1
            pcol=0
            ncol=0
            # print(p,q)
            while(c[i][p]<=0 and c[i][q]>0):
                if(abs(c[i][p])>abs(c[i][q])):
                    if(x[abs(c[i][p])]==1):
                        if(c[i][p]<=0):
                            result+=pcol
                    else:
                        ncol+=1
                    p+=1
                elif(abs(c[i][p])<abs(c[i][q])):
                    if(x[abs(c[i][q])]==1):
                        if(c[i][q]>0):
                            result+=ncol
                    else:
                        pcol+=1
                    q-=1
                else:
                    if(c[i][p]<0 and x[abs(c[i][p])]>1):
                        ncol+=1
                    if(c[i][q]>=0 and x[abs(c[i][q])]>1):
                        pcol+=1
                    p+=1
                    q-=1
                if(p>=len(c[i]) or q<0):
                    break
            # print(p,q)
            while(p<len(c[i])):
                if(x[abs(c[i][p])]==1):
                    if(c[i][p]<=0):
                        result+=pcol

                p+=1

            while(q>-1):
                if(x[abs(c[i][q])]==1):
                    if(c[i][q]>0):
                        result+=ncol
                q-=1
            # print(len(c[i]),result)

                
        # result=result//2
        # print(result)
        for i in range(len(d)):
            if(x[d[i]]>1):
                result+=1
                x[d[i]]=0

        print(result)
    t-=1


Program Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
static BufferedReader in;
    public static class Pair{
        long ele;
        long pn;
        boolean neg;
        int idx;
        public Pair(long ele,long pn,int idx,boolean neg){
            this.ele = ele;
            this.pn = pn;
            this.neg = neg;
            this.idx = idx;
        }
        public String toString(){
            return "["+ele+","+pn+","+neg+"]";
        }
    }
    public static long getCount(long a[],long x,boolean neg, int p){
        if(neg){
            int i = p+1;
            int j = a.length-1;
            long ans = a.length;
            x = Math.abs(x);
            while(i <= j){
                int mid = i+(j-i)/2;
                if(a[mid] > x){
                    ans = mid;
                    j = mid-1;
                }else{
                    i = mid+1;
                }
            }
            return a.length-ans;
        }else{
             int i = 1;
            int j = p;
            long ans = 0;
            x = -x;
            while(i <= j){
                int mid = i+(j-i)/2;
                if(a[mid] < x){
                    ans = mid;
                    i = mid+1;
                }else{
                    j = mid-1;
                }
            }
            return ans;
        }
    }
    public static void solve() throws Exception{
       String s[] = in.readLine().split(" ");
       int n = Integer.parseInt(s[0]);
        Map<Long,List<Pair>> map = new TreeMap<Long,List<Pair>>();
       long ans = 0;
       long line[][] = new long[n][];
       

       for(int i = 0; i < n; i++){
           s = in.readLine().split(" ");
           int m = Integer.parseInt(s[0]);
           long pos = 0;
           line[i] = new long[m+1];
           long part = 0;
           boolean flag = true;
           for(int j=1; j <= m; j++){
                line[i][j] = Long.parseLong(s[j]);
                if(flag && line[i][j] > 0){
                    part = j-1;
                    flag = false;
                }    
           }
           line[i][0] = part;
       }
       for(int i = 0; i < n; i++){
           long negative = line[i][0];
           long pos = line[i].length-1-negative;
           for(int j = 1; j < line[i].length; j++){
               long abs = Math.abs(line[i][j]);
               if(map.containsKey(abs)){
                   boolean neg = (line[i][j] < 0);
                    if(neg){
                        map.get(abs).add(new Pair(j-1,pos,i,neg));
                    }else{
                        map.get(abs).add(new Pair(line[i].length-1-j,negative,i,neg));
                    }
               }else{
                    List<Pair> list = new ArrayList<Pair>();
                    boolean neg = (line[i][j] < 0);
                    if(neg){
                       list.add(new Pair(j-1,pos,i,neg));
                    }else{
                           list.add(new Pair(line[i].length-1-j,negative,i,neg));
                    }
                    map.put(abs,list);
               }
           }
       }

        for(Map.Entry<Long,List<Pair>> e : map.entrySet()){
            List<Pair> list = e.getValue();
            if(list.size() == 1){
                int idx = list.get(0).idx;
                boolean neg = list.get(0).neg;
                int part = Integer.parseInt(line[idx][0]+"");
                ans += getCount(line[idx],e.getKey(),neg,part);               
                continue;
            }
            ans++;
            for(Pair p: list){
                ans += p.ele;
            }
        }

       System.out.println(ans);
    }
    public static void main(String[] args) throws Exception {   
        in = new BufferedReader(new InputStreamReader(System.in));
        int t = 1;
        t = Integer.parseInt(in.readLine());
        while(t-- > 0){
            solve();      
        }
    } 

}

Program C++:

#include<bits/stdc++.h>
using namespace std;

#define int  long long
vector<int>vec;
int dp[5000][5000];
int ch = 0;
int curr;
int n,k;

void solve()
{
int n;
cin>>n;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> >pq;
int arr[n+1][2];
for(int i = 0;i<n+1;i++)
{
    arr[i][0] = 0;
    arr[i][1] = 0;
}
    
int ans = 0;
int a;    
    

for(int i = 0;i<n;i++)
{
cin>>a;
for(int j = 0;j<a;j++)
{
    int q;
    cin>>q;
    if(q>0)
        arr[i+1][1]++;
    else
        arr[i+1][0]++;
    pq.push({abs(q),(q/abs(q))*(i+1)});
      
}

}
      
    int last = 0;
    while(pq.size()>0)
    {
        pair<int,int>curr = pq.top();
        pq.pop();
        
        if(last == curr.first || ((pq.size()!=0)&&(pq.top()).first == curr.first))
        {
             
            if(last!=curr.first)
                ans++;
            int i = abs(curr.second);
            if(curr.second>0)
            {

                ans+=(arr[i][1]-1);
                arr[i][1]--;
            }
            else
            {
                ans+=(arr[i][0]-1);
                arr[i][0]--;
            }
           
        }
        else
        {
            int i = abs(curr.second);
            //cout<<arr[i][0]<<ans<<curr.second<<endl;
            
            if(curr.second>0)
            {

                ans+=(arr[i][0]);
                arr[i][1]--;
            }
            else
            {
                ans+=(arr[i][1]);
                arr[i][0]--;
            }
        }
           
        last = curr.first;
    }
    cout<<ans;

}


signed main()
{
   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t=1;
    cin>>t;
    while(t--){
        solve();
        cout<<endl;
    }
}

January Long Challenge 2021

Leave a Comment