Top Coder Problem - WolfDelaymaster

During my last SRM 593 on TopCoder I found the medium problem quite interesting and I was happy that I have been able to solve it relatively quickly using the technique of Dynamic Programming.

Solving this problem taught me two important lessons:

1. The power of Dynamic Programming
2. The trap of over-optimization

The interesting thing is that I didn't realize the second lesson until I wrote this post so I am really glad I decided to write it.

I am going to quickly describe my solution.

The problem statement: WolfDelaymaster (Why register on TopCoder?)
My solution: WolfDelaymaster implementation.

The definition of the problem suggest an immediate recursive implementation.

You can first check that the string satisfy the first condition. You start checking against "wolf", then "wwoollff" and so on. Considering that the maximum input string is 50 characters the biggest string to test against contains 12 times each individual character.

1. For each positive integer n, the string which consists of n copies of 'w', then n copies of 'o', then n copies of 'l', and finally n copies of 'f' is a valid word.

If this test fail, we can use the second rule and split the original string in two parts and recursively check them. It is important to try all the possible split points that are multiple of 4 (there are no valid strings shorter than 4 characters).

1. The concatenation of two valid words is a valid word.

This is the initial implementation:

Does this implementation works?

Yes, it works!

Are you concerned about the performance implication of having two recursive branches?

I was and for some reasons I decided to apply the technique of dynamic programming in order to speed up the program. You can learn more about dynamic programming on Wikipedia. It basically consist of caching the intermediate result of computation to quickly cut the recursion tree.

Here the implementation (addition highlighted).

Does this effort was required?

Absolutely not!!! The original implementation was good enough.

What is the worst case?

The worst case is a string that is invalid with a length of 50 characters like "fofflwllwooowowwwllllwlwllwwlwwfwwfwofwwfolowlolwo".

The execution time of the original algorithm on the worst case is: 0.0110 seconds.
The execution time of the optimized algorithm on the worst case is: 0.00056 seconds

Dynamic programming is powerful as it improved the speed of the algorithm of a factor of 19 but in this case it was not necessary. This is the biggest mistake I made. I wasted a lot of time that I could have spent on the next problem.

It is worth to mention that the problem could have being solved in an iterative way but for some reasons the I didn't get it during the competition and the recursive implementation was more natural for me.

This is a possible implementation adapted from the winner of the competition (I didn't test it using the TopCoder system tests).

The time of the iterative version on the worst case is: 7.1E-06

This version is absolutely the quickest version!

Configuring the TopCoder Arena for C# developers

If you read my previous post (Learning Algorithms with TopCoder - Getting Started Guide) you are probably motivated in solving TopCoder problems and putting yourself under test. You probably created an account and tried the arena and you quickly realized that the experience is not that great.

Why?

• You have to read the text of the problem inside the arena
• You have to manually create the class and copy the method signature
• Testing the code with the examples is a manual process in the arena
• Debugging against the examples force you to code all the examples manually
• You have to copy the code from Visual Studio into the Coding Area

This is tremendously annoying!

Fortunately, there is a solution to these problems using some arena plugins. It is a little bit annoying to setup but once done your coding experience is vastly improved and you can finally focus on writing algorithms.

You can find some only-text documentation at the following link:
http://www.topcoder.com/contest/classes/ExampleBuilder/ExampleBuilder.html

First of all, download the TopCoder.zip file and extract it into C:\TopCoder

The folder contains an empty Visual Studio .NET 4.5 C# console application and a folder jars with the plugin code.

In this post, I want to explain step by step how to configure the TopCoder arena to be able to start solving SRM problems in TopCoder using C# and Visual Studio.

Launch the arena and open the Editor options.

Add a new editor with the following information:

• Name: ExampleBuilder
• EntryPoint: codeprocessor.EntryPoint
• ClassPath: C:\TopCoder\jars\CodeProcessor.jar;C:\TopCoder\jars\FileEdit.jar; C:\TopCoder\jars\ExampleBuilder.jar

Select the new editor and click Configure.

Insert the entry point fileedit.EntryPoint and the processor class tc_plugin.ExampleBuilder

Then, click Verify.

Press OK and then Click Configure.

Specify the enter directory to C:\TopCoder, check "Write the problem description using HTML" and check "Write the Problem Description to separate file" with extension html.

Click the Code Template tab, select the C# language.

Copy the template code from here but feel free to customize it as you like.

Save everything.

Now you have everything set up and you are ready to code.

Open one of the past SRM: Practise Rooms > SRMs.

Select one of the problem.

The default editor will launch by default. Make sure that you select C# as your language.

Change your editor to ExampleBuilder.

This will trigger the creation of two files:

• A C# source file with the problem and the tests
• An html file with the description of the problem

You can open the html file and read the problem statement in your favourite browser (maybe in a separate screen if you have a multi-monitor setup).

At this point, you can open the TopCoder Visual Studio solution and include the file in the project.

You can see that all the examples has been automatically added as tests and the only thing that you need to do is to provide the implementation of the algorithm in the method.

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class BinaryCode 
{
    public string[] decode(string message) 
    {
        // IMPLEMENTATION GOES HERE  
        string[] res = new string[0];
        return res;
    }
    
    // BEGIN CUT HERE

    public static void Main(String[] args) 
    {
        try  
        {
            eq(0,(new BinaryCode()).decode("123210122"),new string[] { "011100011",  "NONE" });
            eq(1,(new BinaryCode()).decode("11"),new string[] { "01",  "10" });
            eq(2,(new BinaryCode()).decode("22111"),new string[] { "NONE",  "11001" });
            eq(3,(new BinaryCode()).decode("123210120"),new string[] { "NONE",  "NONE" });
            eq(4,(new BinaryCode()).decode("3"),new string[] { "NONE",  "NONE" });
            eq(5,(new BinaryCode()).decode("12221112222221112221111111112221111"),
                  new string[] { "01101001101101001101001001001101001",                  
                                 "10110010110110010110010010010110010" });
        } 
        catch(Exception exx)  
        {
            Console.WriteLine(exx);
            Console.WriteLine(exx.StackTrace);
        }
        Console.ReadKey();
    }
    ...

    // END CUT HERE
}

You can see the results of the tests simply running the project with F5.

How do you actually submit your code?

Click Compile and the source code will be automatically copied into the arena.

Finally click Submit.

To summarize, once you setup your development machine like I explained in this post you will be able to open any TopCoder problem, start coding your algorithm immediately and have a lot of fun. During a competition, this technique can also save you a lot of time and increase the chance of getting an higher score.

Enjoy coding!

Andrea

Learning Algorithms with TopCoder - Getting Started Guide

I have lots of friends who are passionate developers and every so often we discuss about

algorithms design and how important this is. The TopCoder platform offers a very good opportunity to put yourself under test, improve your skills and compete among other coders around the world. Everyone is pretty excited when I explain them about the platform and they seems willing to try it out but for some reasons this does not happen.

Let me be clear now.

Do you know what is the reason?

The answer is that...

They are frightened!

Saying that you don't have time is not an excuse because a competition is just 90 minutes long and everyone can give it a try. They are coders so why should they be scared of coding?

Why?

The reason is because they "don't feel ready to compete". They fell they need to do additional learning before actually competing otherwise they hurt their reputation and self-esteem. This is perfectly reasonable and I completely understand these feelings because this is how I constantly feel. TopCoder problems are usually very difficult and this fear of failing is completely blocking them.

So what?

What they don't consider is that TopCoder is not only a competing platform but also a learning platform. Once registered you have access to all the exercises from previous competitions with solutions completely explained, you can try them on your own without competing, you have access to lots of tutorials. There are tons of materials. You will be never ready so after trying few exercises I recommend to try a SRM (Single Round Match) competition. Competing really change the game and makes you more aware of your true skills. You are then able to identify areas of improvement, practise and then compete again. At the end of the day, you are always and constantly learning!

TopCoder is a learning platform!

Competitions can be seen as just a way of learning but you are not forced to compete.

However, if you are ambitious and you are truly committed to becoming a great coder, like I am sure you are, competing is the best way to put yourself under test and really find your potentials and limitations.

If you are scared you probably are not really serious of becoming a great coder.

It does not matter how strong you become compared to others. What matters is constantly learning and improving yourself.

This idea is also clearly expressed by the founder of TopCoder, Jack Hughes:

"TopCoder intends to help developers increase their skill level as well as increase their value to employers"

Then what?

If you read so far, it means that I convinced you to try TopCoder and in this post I would quickly introduce you to the platform.

First of all, you need to register.

Open the following website and click on Register Now in the top right corner: http://community.topcoder.com/tc

TopCoder allows you to learn and compete in many different areas. If you want to practise your algorithmic skills just select "I want to compete on TopCoder" and then follow the procedure where you will be asked to provide all your personal details.

Once registered, you can login into the website.

Expand the Competitions menu item and enter into the Algorithm category and then into the Single Round Matches section. It is probably a good idea to read the Overview page and then the Algorithm Competition Guide.

You can access to all the past problems clicking the Match Archive link under Statistics. In addition, you can also read the code submitted by all the people who participated to the competition. This is a lot of stuff!

There are also an interesting set of tutorials about algorithms that you can find in the Tutorials page.

However, there is nothing better than actually trying a problem yourself.

If you want an experience that is similar to a rate event, you can launch the Arena clicking the O(n) image in the top-left corner or the Launch Arena link.

The Arena is written in Java and you need to have it installed.

In the arena you enter a practice room and you can submit your code to a problem and get a score of how well you did it. The biggest value of the practise room for a learning point of view is the ability to run the system tests and discover bugs in your algorithm. You can also challenge the code written by other coders to find bugs in their implementations.

More information here: Practising in the TopCoder arena.

You can code using one of the following languages: C++, Java, C#, VB or Python.

The platform has been recently updated to the latest version of the languages.

If you decide to compete, you will get a score and you will be ranked against all the other top coders. You can find statistics about your performance clicking on your login name in the top-right corner.

For example, the followings are my current statistics. As you can see, I am still quite weak. 

I hope with this post that I have stimulated your curiosity.

Happy coding and see you in the arena!

See how to configure the TopCoder Arena for C# developers.

Andrea

Top Coder Problem - Boxing

TopCoder is an amazing platform to challenge yourself.

I decided to start posting my solutions to problems with the following purposes:

• Stimulate myself to practice more
• Stimulate my friends to solve the problem
• Stimulate my friends to join TopCoder and challenge themselves
• Compare and contrast different solutions

Notes:

• TopCoder only accepts solution written in C# 2.0
• The problem statement is the exclusive and proprietary property of TopCoder. You need to login to see it.

TopCoder Problem:
Boxing

This problem was used for:
2004 TCO Online Round 3 - Division I, Level One


My solution:

Tests:

My solution is an usage example of the Greedy Algorithm Design Paradigm.

What is your solution?

2012 TopCoder Open - Qualifications

Yesterday, I participated to the Online Qualification Round 1C that is the first phase of the Worldwide 2012 TopCoder Open Turnament in the algorithm category.

If you look at the algorithm competition schedule you will see that 600 out of 2000 (the maximum number of participants per qualifications round) advances to the semifinals. My final position is 306 so I believe I advanced to semifinals but I didn't received yet an official communication from TopCoder.

The match has been intense but it has started in a very bad way. First, I opened the easy problem and I spent 15 minutes to find a solution. I couldn't come up with a solution. I was shocked because this is usually simple and I always had a first quick solution to it. I decided to move to the medium problem and the same happened. In that case, the text of the problem was too long and I hate this kind of problems so I decided to move on the hard problem. At that point, my hope was almost null because I never been able to solve a TopCoder hard problem. I focused all my remaining time to solve the hard problem and I submitted a solution and I got 448.50 points. I was happy because I knew that I discovered some subtle edge cases and I addressed them but I wasn't 100% sure that my code was fully functional (never I am).

Then the challenge phase. Only three people (included me) in the room (usually 20 people) did the hard problem. Three tentative to break my code has been done with a negative result (each person lost 25 points for this). I challenged the code of a guy that submitted a solution to the hard problem but without covering an edge case and I got 50 points. So my score became 494.80.

Then the system test. The system test is terrible because if only a single test case against a solution does not pass you automatically get a score of 0. Fortunately my code passed the system test.

I would like to share the problem and my code with you but unfortunately for copyright issues I can't. You have to register on TopCoder to have access to all the problems.

However, I can share with you my public profile information.

My total topcoder score in the algorithm category (a kind of average of all the competition you did)  is now 1167. As you can see, my last match has been significantly better than the previous. Solving the hard problem is a great achievement for me.

The most interesting chart is my global position relative to the others TopCoders (3520 out of 9334).  It is good to see that I am better positioned than the average TopCoder. My percentile is 62.2884%. As you can see I am very closed to the blue area (a score greater than 1200) and this is my next goal, an hard goal.

Competing on TopCoder is amazing and I like the adrenaline released during the competition. I strongly recommend the experience to any programmers. It doesn't matter what will be your score, what it matters is challenging yourself, improving yourself and having fun.