From Progteam

Revision as of 20:34, 29 March 2008 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by jinho.

Problem Number 3067
Sorter: hjfreyer
Source: Unknown
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3067

Japan is problem number 3067 on the Peking University ACM site.

This solution gives correct answers for all the input I tested, but exceeds the time limit on PKU.

The problem : Given a list of roads connecting cities on the west and east coasts of Japan, calculate the number of intersections. The cities are placed in numerical order down the coast.

This solution represents the input as an array, where if cities n and m are connected by a road, then array[n][m] = 1 . A road intersects with any road contained in the sub-array formed by the upper left corner, starting from the row and column following n and m.

If anyone can think of a way of optimizing this solution or just a more efficient method, please post ^__^ .

import java.util.*;

public class Main{
	public static Scanner in;
	public static int theCount[][] = new int[1001][1001];
	public static void main(String[] args){
		in=new Scanner(System.in);
	public static void doStuff(){
		int T=in.nextInt();
		for(int i = 0; i < T; i++){
			int N = in.nextInt();
			int M = in.nextInt();
			int K = in.nextInt();
			int[][] cross = new int[N+1][M+1];
			for(int j = 0; j < K; j++){
				int n = in.nextInt();
				int m = in.nextInt();
				cross[n][m] = 1;
			for(int p = 0; p<=N; p++){
				for(int q = 0; q<=M; q++){
					theCount[p][q] = -1;
			System.out.print("Test case " + (i+1) +": " );
			solve(cross, N, M);
	public static void solve(int[][] cross, int N, int M){
		int count = 0;
		for(int i = 0; i <= N; i++){
			for(int j = M; j > 0; j--){
				if(cross[i][j] == 1){
					count += countEm(cross, i, j, M);
	public static int countEm(int[][] array, int n, int m, int M){
		int count = 0;
		if(theCount[n][m]  != -1){
			return theCount[n][m];
			for(int i = 0; i < n; i++){
				for(int j = M; j > m; j--){
					count += array[i][j];
			theCount[n][m] = count;
			return count;

Well I was looking at this problem, and after discussing with Hunter a bit, it seems that this problem can be reduced to the DNA Sorting problem. For instance if you have a list of the edges, and you sort using say the "N" values as the key, then the degree of unsortedness is equivalent to how many intersections there are. However Hunter solved DNA Sorting using the naive method, which worked for that problem since the string was limited to 50 characters, but doesn't work here since the list could potentially have thousands of edges in it. So yeah...at this point I'm stumped. Hunter said that Prof. Siegel mentioned some nifty tree data structure that would do the trick, but I didn't quite understand what he meant. Anyone else have any ideas?

Yay! Finally conquered Japan. The dastardly PKU people made some of the inputs require longs, which is what tripped me up. Also PKU doesn't seem to like comments either. Here's the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef struct {
	int n;
	int m;
} hw;    //stands for "highway"

int compareN(const void* a, const void* b)
	if(((hw*)a)->n == ((hw*)b)->n)
 		return (((hw*)a)->m - ((hw*)b)->m);
		return(((hw*)a)->n - ((hw*)b)->n);

long long merge_inv(int* array, int p, int q, int r)    //all this function does is the merge procedure from merge-sort except it also counts inversions
	int n1, n2, i, j, k, counted;
	long long inv;
	n1 = q - p + 1;
	n2 = r - q;
	int L[n1+1];
	int R[n2+1];
	for (i = 0; i < n1; i++)
		L[i] = array[p+i];
	for (j = 0; j < n2; j++)
		R[j] = array[q+j+1];
	L[n1] = INT_MAX;
	R[n2] = INT_MAX;
	i = j = inv = 0;
	for (k = p; k <= r; k++) {
		if (R[j] < L[i]) { inv += n1 - i; }    //counting inversions here
		if (L[i] <= R[j]) {
			array[k] = L[i];
		} else {
			array[k] = R[j];
	return inv;

long long count_inv(int* array, int p, int r)
	long long inv;
	int q;
	inv = 0;
	if (p < r) {
		q = (p+r)/2;
		inv += count_inv(array, p, q);
		inv += count_inv(array, q+1, r);
		inv += merge_inv(array, p, q, r);
	return inv;

int main()
	int t, n, m, k, i, j;
	long long tot;
	scanf("%d", &t);
	int cnt;
	cnt = 0;
	while (cnt < t)
		scanf("%d %d %d", &n, &m, &k);
		hw* h = (hw*)malloc(sizeof(hw) * k);

		for (i = 0; i < k; i++) {
			scanf("%d %d", &h[i].n, &h[i].m);

		qsort(h, k, sizeof(hw), compareN);
		int japan[k];
		for (i = 0; i < k; i++) {
			japan[i] = h[i].m;
		tot = count_inv(japan, 0, k-1);
		printf("Test case %d: %lld\n", ++cnt, tot);    //change "%lld" to "%I64d" when submitting to PKU

	return 0;

Personal tools