I started working on this problem a while ago, and ran into the issue of keeping track of unique pairs of cows that are valid for two-cow teams winning.
What’s the most efficient way to keep track of the pairs of cows? I’m currently using Java.
I’ve run into this problem in a few other problems, and have done some pretty inconvenient solutions (2d arrays), so I’m just wondering if there’s a better way to do it.
In this problem, the bounds are pretty small, so I don’t think an efficient solution is necessary. What other problems are you having trouble with optimization?
Perhaps a TreeSet could suffice.
Since the bounds are low, the question is not really about efficiency but what’s the easiest solution.
First to make sure you count unique pairs: for each pair (a, b) if b>a swap a and b so that a < b.
Some options in Java are:
boolean[26][26] visited array where you convert each character to an int, and another frequency counterHash/TreeSet<Integer> where you combine two characters into an int with binary e.g. (a<<8) + bMap<Char, Set<Char> > visitedSet<Pair<Char, Char> > where you make your own Pair classSet<String> where you concatenate two characters into a StringI would go with either option 1 or 2 above, the other solutions could be useful for other problems but are overkill here. 2D arrays are not that bad to work with.