Google Code Jam - Africa Qualification Round 2010
The Google Code Jam is an interesting option to work on some challenging problems.
With the first qualification round coming up at May 7th, it's time to look at the Africa qualification round, to see what to expect.
You have 24 hours to solve three rather simple problems. Solving two problems brings you into the next round.
I will present my Java solutions. The Code Jam site provides the code of every contestant.
Store Credit
read problem description
You just need two nested loops to find the matching articles. Just a finger exercise.
- for (int i = 0; i < items.size(); i++) {
- for (int j = i + 1; j < items.size(); j++) {
- // is this the right shopping?
- int newSum = items.get(i) + items.get(j);
- if (newSum == credit) {
- return "Case #" + caseNr + ": " + (i + 1) + " " + (j + 1);
- }
- }
- }
Reverse Words
read problem description
Just reverse a list of words? Guess that's doable. Well, the code is not elegant, but it works.
- for (int i = 1; i <= cases; i++) {
- out.writeBytes("Case #"+i+": ");
- String[] words = in.readLine().split("\\ ");
- List<String> wordList = Arrays.asList(words);
- Collections.reverse(wordList);
- for(Iterator it = wordList.iterator(); it.hasNext();){
- out.writeBytes(it.next()+" ");
- }
- out.writeBytes("\n");
- }
T9 Spelling
read problem description
The first task with a little challenge. You have to insert a break when you have letters on the same numeric button. So I checked if the previous button is the same as the recent on. If yes, insert a break. So you can separate AB (2 22) from BA (22 2). That's all.
- public class T9Spelling {
- /**
- * @param args
- */
- static HashMap<String, String> t9Map;
- public static void main(String[] args) throws NumberFormatException,
- IOException {
- FileInputStream inFile = new FileInputStream(new File(
- "C-large-practice.in"));
- DataInputStream in = new DataInputStream(inFile);
- FileOutputStream outFile = new FileOutputStream(new File("out.txt"));
- DataOutputStream out = new DataOutputStream(outFile);
- int cases = Integer.parseInt(in.readLine());
- t9Map = new HashMap<String, String>();
- fillMap();
- for (int i = 1; i <= cases; i++) {
- out.writeBytes("Case #" + i + ": ");
- String t9, t9last = "";
- String text = in.readLine();
- for (int j = 0; j < text.length(); j++) {
- t9 = t9Map.get(String.valueOf(text.charAt(j)));
- // do we need a break? (letters are on same button)
- if (j > 0 && (t9.charAt(0)) == t9last.charAt(0)) {
- out.writeBytes(" ");
- }
- out.writeBytes(t9);
- t9last = t9;
- }
- out.writeBytes("\n");
- }
- }
- public static void fillMap() {
- t9Map.put("a", "2");
- t9Map.put("b", "22");
- t9Map.put("c", "222");
- t9Map.put("d", "3");
- t9Map.put("e", "33");
- t9Map.put("f", "333");
- t9Map.put("g", "4");
- t9Map.put("h", "44");
- t9Map.put("i", "444");
- t9Map.put("j", "5");
- t9Map.put("k", "55");
- t9Map.put("l", "555");
- t9Map.put("m", "6");
- t9Map.put("n", "66");
- t9Map.put("o", "666");
- t9Map.put("p", "7");
- t9Map.put("q", "77");
- t9Map.put("r", "777");
- t9Map.put("s", "7777");
- t9Map.put("t", "8");
- t9Map.put("u", "88");
- t9Map.put("v", "888");
- t9Map.put("w", "9");
- t9Map.put("x", "99");
- t9Map.put("y", "999");
- t9Map.put("z", "9999");
- t9Map.put(" ", "0");
- }
- }
Round 1 was quite simple, wasn't it? There's still time to register.
See you in the contest.
- Login to post comments
Comments
Christian Harms - Mon, 04/26/2010 - 22:23
What is considered cheating?
Collaborating with anyone else during the contest is strictly prohibited and will result in your disqualification. This includes discussing or sharing the problem statements or solutions with others. Creating or participating with multiple accounts is also prohibited. If we believe that you have undermined the integrity of the contest, we reserve the right to disqualify you. Use your best judgment. If you have a question about whether something is allowed, please ask an administrator.
Hoping your solution will not kick you out of the normal contest in europe ...
Nico Heid - Tue, 04/27/2010 - 11:47
They displayed EVERY solution in any language for Africa 2010.
The even discussed the solution for Round 2, and how to solve it.
So I doubt that this has any relevance to future Code Jams.
And we are not "during" the contest.
Christian Harms - Tue, 04/27/2010 - 19:30
Ok, I should read the first sentence carefully: ... during the contest ... see you in round 2!