Get Time
statistics_w  Match Editorial
2002 TopCoder Invitational
Online Round #1, Part 2

Friday, October 11, 2002

The Problems

Whisper  discuss it
Used as: Level 1
Value 300 points
Submission Rate 295/324 (91.05%)
Success Rate 154/295 (52.20%)
High Score eduar09 for 289.89 points
Average Points 221.85

169 out of 323 coders who opened Whisper, received 0 points.

The problem was straightforward enough for Level 1 problem and solution should involve no complicated algorithms or recursion (well unless one would did something very complicated and unnecessary). Nevertheless the problem had only about 50% success rate, which is attributed to the number of special cases one should consider when solving this problem.

The first thing to do to solve this problem is to return "not as whisper" if first 5 characters are not equal to "/msg ". Actually it would be a good idea to convert entire string to lower case before you do anything. Most of the fast and successful solutions chose the following tactics to solve the problem: Create a new string = "/msg " + name + " " and check if the message starts with this string. If it does, check if name used to create this string is longer than the best so far and memorized it if it is longer. When you have finished checking all the names, the "best so far" variable would be empty of no solutions are found or would have the longest name of the person to send the message to.

Execution  discuss it
Used as: Level 2
Value 550 points
Submission Rate 183/324 (56.50%)
Success Rate 107/183 (58.47%)
High Score SnapDragon for 499.13 points
Average Points 317.76

208 out of 315 coders who opened Execution, received 0 points.

Reference implementation: slavik (practice room)

I think the hardest part to solve this problem was to correctly parse the input. I think the best way to go about doing it is to append entire string array into a single string and then work with it. The grammar of the input was enforced by the problem statement so it would be enough to only look for specific characters inside the string like 'B','(','{','}'.

The recursive function shall be build to take a string and return a number of iterations inside this string.
Start going through the string char by char and do the following:
Maintain the state of the scope:

      Set initial scope to 0
if '{' found, increment scope state
if '}' found, decrement scope state
if scope==0 (it means you are NOT inside the nested loop)
do the following:
if 'B' found count++;
if '(' found, read number of iterations inside the
loop into a temp variable "last_loop"
if '{' found, start_loop = current postion
if '}' found, count += last_loop * call to
myself(new string(start_loop , current position) )
Return "count" when entire string is parsed.
To solve this problem correctly one should realize
that a number inside a "for" structure is a 64 bit integer.
For C++ coders I have seen 3 approaches on how to read this number:
1. sscanf( str.c_str(), "%lld", &y ); (by SnapDragon)
2. atoll(str.c_str())
3. Create a for loop to build a 64 bit number digit by digit.
Decimal  discuss it
Used as: Level 3
Value 900 points
Submission Rate 54/324 (16.67%)
Success Rate 33/54 (61.11%)
High Score SnapDragon for 845.10 points
Average Points 622.13

198 out of 231 coders who opened Logical, received 0 points.

Reference implementation: SnapDragon


The solution to this problem is straightforward once you know what to look for. To solve this problem we should remember how we were taught to dive two numbers in elementary school:

  1. Dived two numbers by finding the whole part and a reminder (The whole part can be ignored for the purpose of this problem.
  2. Go to Step 1 with new dividend = reminder multiplied by 10.

To find the repeating sequence we just have to keep track of the reminders. Once you have found a reminder, which you have seen before, the sequence will repeat itself indefinitely.

Check how many divisions were done between two identical reminders and see if this number falls into lower and upper bound.

By slavik
TopCoder Member