Thursday, March 8, 2007 Match summaryAs 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 ProblemsCellularPhoneTarifUsed as: Division One - Level One: The main thing you needed to solve this problem was caution. To find the solution, you had to perform the following action:
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: 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.
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: 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:
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 '*'. |
|