USACO 2016 December Contest, Silver Problem 2. Cities and States

Problems and Contests
#1

This is the question
and `This is the solution
I am new to programming in general and didn’t understand the logic behind the if statement (there’s only a single if statement in the entire code) can anyone give a test case through which I can understand the use of that if statement.

`

#2

Hello! I don’t know how long you have been doing programming, but if I’m assuming less then a month of USACO, I don’t think silver problems are really the things to solve right now. This problem is fairly straightforward. The if is just if the two states are special pairs.

I did this by using HashMap<String,String> states = new HashMap<>() where the key is the full name and the value is the abbreviation.

1 Like
#3

Ohk, I didn’t quite looked at the difficulty level. Will watch out for that. :+1:

#4

I was just saying because bronze to silver is a big jump. This problem is really straight forward though. Just if you were given an input, how would you do it manually?

#5

I was using brute force like by creating a map of state code to the list of cities having that state code. Then iterating over the map and over all the cities (for a particular state code) and find the cities that satisfies the condition.
But was tle.

#6

Ahh, I see how I solved this again. There is an optimization that I used. I made a HashMap with String and Integer. Bring will be the first 2 letters of the actual name + the 2 letter string of the abbreviation. The integer is how many times this string occurs. I did this because since we’re taking the first two letters, it is possible for there to be multiple. I think if you saw my code you might understand it more.
Sorry for using Scanner, I didn’t learn BR at that time. sc1.next is getting the next String in the input.

import java.util.Scanner;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.HashMap;

public class Cities_And_States {
	public static void main(String args[]) {
		try {
			Scanner sc1 = new Scanner(new File("./citystate.in"));
			PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("./citystate.out")));
			HashMap<String,Integer> city = new HashMap<>();
			int length = sc1.nextInt();
			
			for(int x = 0; x < length;x++) {
				String first = sc1.next().substring(0,2);
				String second = sc1.next();
				String finale = first + second;
				
				if(city.get(finale) == null) {
					city.put(finale, 1);
				}
				else {
					city.put(finale, city.get(finale) + 1);
				}
			}
			int count = 0;
			for(String x:city.keySet()) {
				String goal = reverse(x);
				if (city.get(goal) != null && !(x.substring(2,4).equals(goal.substring(2,4)))) {
					count = count  +(city.get(x) * city.get(goal));
				}
			}
			pw.println(count/2);
			pw.close();
		}
		catch(Exception e) {
			e.getStackTrace();
		}
	}
	public static String reverse(String a) {
		String start = a.substring(0,2);
		String end = a.substring(2,4);
		return end + start;
	}
}```