Codeforces: 268A. Games

This problem is from codeforces: http://www.codeforces.com/problemset/problem/268/A

This is a simple math problem. Almost every solution needs to store the colours of home and away. Counting the occurrences that the home colour is the same as another away-colour.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import java.io.*;
import java.util.*;
 
public class CodeForces268A
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(rr.readLine());
        int[] h = new int[n];
        int[] a = new int[n];
        for (int i = 0; i < n; i ++)
        {
            String[] s = rr.readLine().split(" ");
            h[i] = Integer.parseInt(s[0]);
            a[i] = Integer.parseInt(s[1]);
        }
        int cnt = 0;
        for (int i = 0; i < n - 1; i ++)
        {
            for (int j = i + 1; j < n; j ++)
            {
                if (h[i] == a[j])
                {
                    cnt ++;
                }
                if (h[j] == a[i])
                {
                    cnt ++;
                }
            }
        }
        System.out.print(cnt);
    }
}

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

public class CodeForces268A
{
    public static void main(String[] args) throws IOException
    {
		BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(rr.readLine());
		int[] h = new int[n];
		int[] a = new int[n];
		for (int i = 0; i < n; i ++)
		{
			String[] s = rr.readLine().split(" ");
			h[i] = Integer.parseInt(s[0]);
			a[i] = Integer.parseInt(s[1]);
		}
		int cnt = 0;
		for (int i = 0; i < n - 1; i ++)
		{
			for (int j = i + 1; j < n; j ++)
			{
				if (h[i] == a[j])
				{
					cnt ++;
				}
				if (h[j] == a[i])
				{
					cnt ++;
				}
			}
		}
		System.out.print(cnt);
    }
}

This Java solution yields AC in 78 ms. The following Python code is even faster, based on the zip function on two lists.

a=[1,2,3,4]
b=[5,6,7,8]
zip(a,b)
   [(1, 5), (2, 6), (3, 7), (4, 8)]
c=[1,2]
zip(a,c)
   [(1, 1), (2, 2)]

We can see that the zip returns a list with minimal size of two list and each element in the new list is the tuple (a data-structure that cannot be altered) which is formed from two original lists by taking each element.

Therefore, we can count the answer by sum of the multiplication of each element in the zipped list.

#!/usr/bin/env python
h = [0] * 101
a = [0] * 101
for _ in xrange(int(input())):
    x, y = map(int, raw_input().split())
    h[x] += 1
    a[y] += 1
print sum(x[0]*x[1] for x in zip(h, a))

This Python code is even faster, AC in only 46ms.
The following is even shorter.

n = input()
a = [map(int, raw_input().split()) for i in xrange(n)]
print sum([[j[1] for j in a].count(i[0]) for i in a])

–EOF (The Ultimate Computing & Technology Blog) —