Match summary

As in Round 1, it was clear that any positive score would be enough to advance to the next round. Therefore, a lot of coders played it safe and made sure they submitted a correct solution to the easy. Most of them managed to qualify for the next round, with venkateshb being lucky enough to advance only because of his challenge points.

At the top of the table, RNGAN won the challenge by a tiny margin over msg555. bhzhan came in third about 100 points behind.

The Problems

CellularPhoneTarif

Used as: Division One - Level One:

Value 250

Submission Rate 45 / 45 (100.00%)

Success Rate 42 / 45 (93.33%)

High Score tloinuy for 249.32 points (1 mins 29 secs)

Average Score 230.85 (for 42 correct submissions)

The main thing you needed to solve this problem was caution. To find the solution, you had to perform the following action:

Compute the number of minutes you'll be charged for. The fact that you are charged 1 minute momentarily after the end of the previous minute means the number of minutes you are charged is the number of complete minutes you've talked plus one.
Compute the amount you are charged, adding up the following numbers:
- 5 cents for starting a call.
- 10 cents per minute if you've talked less than 5 minutes, or 50 cents if you've talked more than 5 minutes.
- If you've talked more than 5 minutes, add 3 cents for each such minute.

By carefully implementing this you get the problem's solution. A short of it version can look like:

public int calculatePrice(int seconds) {
    int mins = 1 + seconds  / 60;
    return 5 + 10 * Math.min(mins, 5) + Math.max(0, (mins - 5) * 3);
}

PulseDial

Used as: Division One - Level Two:

Value 500

Submission Rate 42 / 45 (93.33%)

Success Rate 31 / 42 (73.81%)

High Score Penguincode for 492.49 points (3 mins 31 secs)

Average Score 430.73 (for 31 correct submissions)

A solution to this problem consists of two parts. First, we need to determine the digits of the number. Second, we need to format the number according to the requirements. If you have the number as a string of digits, the second part becomes trivial:

if (ans.length() == 7)
    return ans.substring(0, 3) + "-" + ans.substring(3, 5) + "-" + ans.substring(5);
else 
    return "+" + ans;

Now lets move to the first part of the problem. Depending on the previous second, the phone can be in one of 2 possible states. If we had a pause during the previous second, the phone is in pause mode and is waiting for new pulses. Otherwise, the phone is "listening" and counting pulses. If we have a counter for consecutive pulses before this one, we increment it by one. The following table shows how the phone changes its state. Rows represent the state we had after the previous second, columns represent the signal we get during the current second. Count is the number of previous consecutive '-'s.

State / Signal	Pause ('*')	Pulse ('-')
Pause (count = 0)	The phone is still in pause, do nothing.	The phone starts receiving a digit. Set count to 1.
Digit (count > 0)	Digit is completely received. Append it to the phone number.	The phone is still in process of receiving the digit. Increase count by 1.

The only problem with this scheme is that it doesn't deal with the last digit if the raw number doesn't end with a pause. To avoid this bug, we just append a '*' to the end of the raw number representation. Java implementation of the scheme follows:

String number = "";
raw += '*';
int count = 0;
for (int i = 0; i < raw.length(); i++) {
    if (count == 0) {
        if (raw.charAt(i) == '-')
            count = 1;
    } else {
        if (raw.charAt(i) == '-')
            count++;
        else {
            count = 0;
            number += (count % 10); // Remember that 10 '-'s represent a '0'.
        }
        
    }
}

FireSimulation

Used as: Division One - Level Three:

Value 1000

Submission Rate 32 / 45 (71.11%)

Success Rate 24 / 32 (75.00%)

High Score fhoward for 952.60 points (6 mins 24 secs)

Average Score 771.93 (for 24 correct submissions)

This was a classical example of a simulation problem. To simulate the process you need to store the states of the cells. For each cell there are three possible states - it can be as clean as it was at the beginning, it can be on fire, or it can be completely burned. At the moment when the cell becomes completely burned, it spreads the fire to all neighboring cells (unless they were on fire before). So, we can represent the state of the cell in the following way:

0, if the cell never was on fire.
x, if the cell caught the fire x minutes ago.
-1, if the cell is completely burned.

At the moment 0, only (0, 0) cell has state equal to 1, and all other cells have state equal to 0. Then, for minute times we must simulate the process, which happens at the end of the minute.

This can be done in 2 steps. First, we increment by 1 the state of all cells which are already on fire. Then, for each cell which is completely burned (i.e., has the state greater than the corresponding number in the input), we spread the fire to all its neighbours (in other words, for all neighboring cells we set the state to 1 unless they were positive already). Repeating this process minute times we get the state of the field after minute minutes.

The only thing left now is to construct the final output. To do this, take the input array and go through it cell by cell. For each cell which has the state of -1, replace the corresponding character by '.'. If a cell has a positive state, replace the character in the output by '*'.

By Olexiy
TopCoder Member