Table of Contents

ExplanationImplementation

Official Analysis (Java)

Explanation

We can calculate the amount of milk produced by each cow and put all of them in a vector in the format of a 2-tuple: (amount, cow_name).

After sorting, we can traverse the array once to see which cow produced the second-smallest amount of milk.

Warning: Weak test data

Make sure that your solution outputs Tie for both these test cases:

4
Bessie 1
Elsie 1
Daisy 2
Gertie 3
7
Bessie 1
Elsie 1
Daisy 2
Gertie 2
Annabelle 3
Maggie 4
Henrietta 4

Implementation

Time Complexity: O(Nlog⁡N)\mathcal{O}(N \log N)

C++

#include <bits/stdc++.h>


using namespace std;


constexpr int COW_NUM = 7;


int main() {
	ifstream read("notlast.in");
	int N;
	read >> N;

Java

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


public class NotLast {
	static class Cow {
		public String name;
		public int amt;


		public Cow(String name, int amt) {
			this.name = name;

Python

COW_NUM = 7


with open("notlast.in") as read:
	raw = {}
	for _ in range(int(read.readline())):
		name, amt = read.readline().split()
		amt = int(amt)
		if name not in raw:
			raw[name] = 0
		raw[name] += amt

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum