UVa 11340 Newspaper challenge (sum of letter values in an article)

Question

I am solving the UVA 11340 problem:

Problem Description

News agency pays money for articles according to some rules. Each character has its own value (some characters may have value equals to zero). Author gets his payment as a sum of all character’s values in the article. You have to determine the amount of money that news agency must pay to an author.

Input

The first line contains integer N (0 < N ≤ 5), it is a number of tests. Each test describes an integer K (0 < K ≤ 100), the number of paid characters. On next K lines there are table of paid characters and its values (character values are written in cents). If character can not be found in the table, then its value is equal to zero. Next, there is integer M (0 < M ≤ 150000). Next M lines contain an article itself. Each line can be up to 10000 characters length. Be aware of a large input size, the whole input file is about 7MB.

Output

For each test print how much money publisher must pay for an article in format ‘x.yy$’. Where x is a number of dollars without leading zeros, and yy number of cents with one leading zero if necessary. Examples: ‘3.32$’, ‘13.07$’, ‘71.30$’, ‘0.09$’.

Code

My code is written using Java. I used HashMap data structure. But I am getting Time Limit Exceeded (TLE) error from the online judge. I am not seeing any other place to make improvement for better timing. Can anyone help me to find my mistake that is causing TLE? Or is there a better algorithm to solve this problem?

import java.util.HashMap;
import java.util.Scanner;

public class UVA11340 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0)
        {
            int k=sc.nextInt();
            HashMap<Character, Integer> map=new HashMap<>();
            for(int a=0;a<k;a++)
            {
            String s=sc.next();
            int v=sc.nextInt();
            map.put(s.charAt(0),v);
            }
            int l=sc.nextInt();
            double cost=0;
            sc.nextLine();
            for(int b=0;b<l;b++)
            {
                String str=sc.nextLine();
                for(int i=0;i<str.length();i++)
                {
                    char c=str.charAt(i);

                    cost=cost+(map.get(c)==null?0:map.get(c));
                }
            }
            cost=cost/100;
            System.out.printf("%.2f$\n",cost);
        }
        sc.close();
    }
}

Answer 1

I am going to focus only on the time aspect of your code, not the style or anything else, as that is not what you have asked for. i hope there will be others who will comment on that too.

Obvious Culprits

1. Character and Integer. Primitive to Object boxing costs time! Plus, a HashMap only has amortized constant lookup time, not true constant lookup time. What you want here is a pure old int array, somehow indexable by chars. That's possible, pretty easily, in fact. Plus, you are reinitializing the HashMap on the turns of your test counter loop. You could just call clear() on it, if you end up using it at all. For an array, however, reinitializing it is the way to go when clearing it (reinitialization is amortized constant time (including GC), not linear like clearing the array. It's linear time in both cases for the HashMap, and there's additional GC overheads).

2. Lots and lots of I/O in a tight loop. That's always a bad idea, as I/O form most performance bottlenecks. Maybe you should take the input in separately before you do the processing?

3. (2) brings us to using separate methods. Now that your I/O and program logic have become loosely coupled, you can easily separate them into 2 functions. Trust me, a function call overhead is not too much of a problem here. (I don't do this is my "Improved (?) code below" as it's mostly a stylistic issue, but you should).

4. java.util.Scanner uses pattern matching and regexes under the hood. Those can be pretty slow. For faster I/O, you want java.io.BufferedReader and family.

Suggestion

1. You know, this is a financial calculation. doubles are liable to roundoff errors. You should be using java.math.BigDecimal for financial calculations and java.text.DecimalFormat for formatting numbers. However, in the interest of performance, I'll let this one slide. I don't do this in the code I provide below either.

2. You should really have some sort of Exception handling. You should also consider JDK 7's try-with-resources statement, which I use, to simplify resource cleanup.

Improved (?) Code

My implementation will trade time for space, which means that more memory will be consumed in exchange for faster execution speed. With the test input available on the UVA online debugging portal (the one for the UVA Online Judge), this code takes ~100ms (Measure-Command on PowerShell) or ~180ms (time through bash on WSL) to cover all test cases, including JVM start-up time. I use Java 1.8, like the UVA platform. The run times are safely much lower than the 1 second of runtime offered by the Online Judge.

import java.io.*;
public class UVA11340 {
    public static void main(String[] args) {
        try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
            int t = Integer.parseInt(br.readLine());
            //System.out.printf("Reading %d inputs\n", t);
            int tableSize = 0xFF;//Extended ASCII table size
            while(t-- > 0) {
                int k = Integer.parseInt(br.readLine());
                //System.out.printf("Reading %d characters for table\n", k);
                int[] table = new int[tableSize];
                for(int a = 0; a < k; ++a){
                    String in=br.readLine();
                    //System.out.println("Read map line:"+new String(in));
                    table[in.charAt(0)] = Integer.parseInt(in.substring(2/*in.indexOf(' ')+1*/, in.length()).trim()/*for bug in input*/);
                }
                int l = Integer.parseInt(br.readLine());
                //System.out.printf("Reading %d lines\n", l);
                double cost = 0.0;
                for(int b = 0; b < l; ++b){
                    String str = br.readLine();
                    int strLength = str.length();
                    //System.out.println("Read input line:"+new String(str));
                    for(int i = 0; i < strLength; ++i){
                        cost += table[str.charAt(i)];//lookup cost of char
                    }
                }
                System.out.printf("%.2f$\n", (cost / 100.0));
            }
        }
        catch(IOException ioe){
            ioe.printStackTrace();
        }
    }
}

I left in the debugging print statements as I feel that they make for reasonable documentation. Side note: Please use functions and proper variable names, like the ones I introduced.

Note:

This has not been tested with the UVA Online Judge, only on my PC.

PowerShell screenshot of timed run:

Bash on WSL screenshot of timed run: