Class 02 solutions

A.java

import java.util.PriorityQueue;
import java.util.Scanner;


public class A {

	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		
		while (true) {
			int N = in.nextInt();
			
			if (N == 0) {
				break;
			}

			PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

			
			for (int i = 0; i < N; i++) {
				minHeap.add(in.nextInt());
			}
			
			long totalCost = 0;
			
			while (minHeap.size() > 1) {
				int smallestNumber = minHeap.poll();
				int secondSmallestNumber = minHeap.poll();
				int cost = smallestNumber + secondSmallestNumber;
				totalCost += cost;
				minHeap.add(cost);
			}
			
			System.out.println(totalCost);
		}
	}

}

B.java

import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Scanner;

public class B {

	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		
		while (true) {
			int N = in.nextInt();
			
			if (N == 0) {
				break;
			}
			
			/* You'll see why this is a linked hash map later */
			LinkedHashMap<String, Integer> classCombinationMap = new LinkedHashMap<String, Integer>();
			
			int tempSorter[] = new int[5];
			int maxCombinationCount = 0;
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < 5; j++) {
					tempSorter[j] = in.nextInt();
				}
				
				Arrays.sort(tempSorter);
				
				/* Build a unique string that represents the class combination for this student */
				
				StringBuilder sb = new StringBuilder();
				
				for (int j = 0; j < 5; j++) {
					sb.append("" + tempSorter[j]);
				}
				
				String classString = sb.toString();
				
				/* See if this class combination string has been run into before, and if so, increment its counter */
				
				int classStringCount = 0;
				
				if (classCombinationMap.containsKey(classString)) {
					classStringCount = classCombinationMap.get(classString);
				}
				
				classCombinationMap.put(classString, classStringCount+1);
				
				/* Keep track of the highest combination frequency */
				
				maxCombinationCount = Math.max(maxCombinationCount, classStringCount+1);
			}
			
			/* Now count the number of class combinations with maxCombinationCount occurrences.
			 * Since this is a linked hash map, traversing the values is quicker than a normal hash map */
			
			int numberOfCombinationsWithMaxCombinationCount = 0;
			
			for (int x : classCombinationMap.values()) {
				if (x == maxCombinationCount) {
					numberOfCombinationsWithMaxCombinationCount += maxCombinationCount;
				}
			}
			
			System.out.println(numberOfCombinationsWithMaxCombinationCount);
		}
	}

}

C.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;


public class C {
	
	/* Added 10 to the maximum size for good measure */
	public static final int MAX_FRIENDS = 100010;
	
	int sets[] = new int[MAX_FRIENDS];
	int sizeOfSets[] = new int[MAX_FRIENDS];
	int nextId = 0;

	public void union(int s1, int s2) {
		sets[s2] = s1;
	}
	
	public int find(int index) {
		if (sets[index] == index) {
			return index;
		}
		
		return sets[index] = find(sets[index]);
	}

	public void run() throws Exception {
		/* Using BufferedReader this time because the input is line-by-line */
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(in.readLine());
		
		for (int count = 0; count < N; count++) {
			HashMap<String, Integer> personId = new HashMap<String, Integer>();
			Arrays.fill(sets, 0); /* Important to reinitialize the global data structures for every test case */
			Arrays.fill(sizeOfSets, 0);
			nextId = 0;

			int M = Integer.parseInt(in.readLine());
			
			for (int i = 0; i < M; i++) {
				String[] newFriends = in.readLine().split(" ");
				
				int personA = -1;
				
				if (personId.containsKey(newFriends[0])) {
					personA = find(personId.get(newFriends[0]));
				} else {
					personA = nextId++;
					sets[personA] = personA; /* initialize into their own set */
					sizeOfSets[personA] = 1;
					personId.put(newFriends[0], personA);
				}
				
				int personB = -1;

				if (personId.containsKey(newFriends[1])) {
					personB = find(personId.get(newFriends[1]));
				} else {
					personB = nextId++;
					sets[personB] = personB; /* initialize into their own set */
					sizeOfSets[personB] = 1;
					personId.put(newFriends[1], personB);
				}
				
				/* Case 1: they are already friends */					

				
				if (find(personA) == find(personB)) {
					System.out.println(sizeOfSets[find(personA)]);
				}
				
				/* Case 2: they are becoming friends */
				
				else {
					sizeOfSets[find(personA)] += sizeOfSets[find(personB)];
					union(find(personA), find(personB));
					System.out.println(sizeOfSets[find(personA)]);
//					for (int j = 0; j < 4; j++) { System.out.print(sizeOfSets[j] + " "); } System.out.println();
				}
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		new C().run();
	}

}

D.cc

// Sonny's test solution to CCPC 2008, Problem D
// September 16, 2008

#include <iostream>
#include <vector>
#include <set>
#include <cassert>

using namespace std;

int main()
{
    int t;
    cin >> t;

    for (int i = 0; i < t; ++i)
    {
        int n, m;
        cin >> n >> m;

        // this edge hash assumes |V| < 32, problem says |V| <= 8
        // (is that bound kind of low, or am I missing something?)
        vector<int> edges(m, 0);
        vector<int> sum(m, 0);

        // read in matrix, count incidence for each edge, and create hash to
        // check for duplicate (parallel) edges
        int x;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                cin >> x;
                assert(x == 0 || x == 1);
                sum[j] += x;
                edges[j] = (edges[j] << 1) | x;
            }

        // check that each edge connects two vertices, and is unique
        set<int> uedges;
        bool good = true;
        for (int j = 0; j < m; ++j) {
            if (sum[j] != 2) { good = false; break; }
            uedges.insert(edges[j]);
        }

        if (uedges.size() != m) good = false;

        if (good)   cout << "Yes" << endl;
        else        cout << "No" << endl;
    }

    return 0;
}

E.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class E {
	static class Submission implements Comparable< Submission >{
		int contestant;
		int problem;
		int time;
		String verdict;

		public Submission(int contestant, int problem, int time, String verdict){
			this.contestant = contestant;
			this.problem = problem;
			this.time = time;
			this.verdict = verdict;
		}

		public boolean isCorrect(){
			return verdict.equals("C");
		}

		public boolean isIncorrect(){
			return verdict.equals("I");
		}

		@Override
		public String toString(){
			return contestant + " " + problem + " " + time + " " + verdict;
		}

		@Override
		public int compareTo(Submission o) {
			if(this.contestant > o.contestant)
				return 1;
			else if(this.contestant < o.contestant)
				return -1;
			else if(this.problem > o.problem)
				return 1;
			else if(this.problem < o.problem)
				return -1;
			else if(this.time > o.time)
				return 1;
			else if(this.time < o.time)
				return -1;
			else return 0;
		}
	}

	static class Contestant implements Comparable< Contestant >{
		int number;
		int penaltyTime;
		int[] problems = new int[9];
		int solved = 0;

		int currentPenalty = 0;
		int previousProblem = -1;

		void addSubmission(Submission submission){
			// reset current penalty if it is a new problem (all problems come in order for this contestant)
			if(previousProblem != -1 && submission.problem != previousProblem)
				currentPenalty = 0;

			if(submission.isCorrect()){
				int index = submission.problem - 1;
				if(problems[index] == 0){
					problems[index] = 1;
					penaltyTime += currentPenalty + submission.time;
					solved++;
				}
			}else if(submission.isIncorrect()){
				currentPenalty += 20;
			}

			previousProblem = submission.problem;
		}

		@Override
		public String toString(){
			return number + " " + solved + " " + penaltyTime;
		}

		@Override
		public int compareTo(Contestant o) {
			if(this.solved > o.solved)
				return -1;
			else if(this.solved < o.solved)
				return 1;
			else if(this.penaltyTime > o.penaltyTime)
				return 1;
			else if(this.penaltyTime < o.penaltyTime)
				return -1;
			else if(this.number > o.number)
				return 1;
			else if(this.number < o.number)
				return -1;
			else return 0;
		} 
	}

	public static void main(String[] args) throws NumberFormatException, IOException{
		final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		//final BufferedReader in = new BufferedReader(new FileReader("in_test.txt"));
		int numTestCases = Integer.parseInt(in.readLine());
		// read blank line
		in.readLine();

		for(int testCase = 1; testCase <= numTestCases; testCase++){
			List< Submission > submissions = new ArrayList< Submission >();

			String line;
			while((line = in.readLine()) != null && !line.equals("")){
				String[] s = line.split(" ");
				submissions.add(new Submission(
						Integer.parseInt(s[0]),
						Integer.parseInt(s[1]),
						Integer.parseInt(s[2]),
						s[3]
						));
			}

			List< Contestant > scoreboard = getScoreboard(submissions);

			StringBuilder builder = new StringBuilder();
			for(int i = 0; i < scoreboard.size(); i++){
				builder.append(scoreboard.get(i).toString());
				if(i < scoreboard.size() - 1)
					builder.append("\n");
			}

			if(testCase < numTestCases)
				builder.append("\n");

			System.out.println(builder.toString());
		}
	}

	static List< Contestant > getScoreboard(List< Submission > submissions){
		Collections.sort(submissions);
		List< Contestant > scoreboard = new ArrayList< Contestant >();

		if(!submissions.isEmpty()){
			Contestant contestant = null;
			for(int i = 0; i < submissions.size(); i++){
				Submission submission = submissions.get(i); 

				if((contestant == null) || (submission.contestant != contestant.number)){
					contestant = new Contestant();
					contestant.number = submission.contestant;
					scoreboard.add(contestant);
				}

				contestant.addSubmission(submission);
			}
			Collections.sort(scoreboard);
		}

		return scoreboard;
	}
}