For Beginners in [Topcoder]

Things you must know before competing in topcoder.

For Beginners in

topcoder

Overview

Well, I think there is an urgent need for such an article on topcoder which focuses on those who just joined this great competition arena and are new to the world of online , time-constrained programming contest.

Lots and lots of beginners join topcoder everyday but many of them lose to others as they don’t have sufficient knowledge and “tricks” to help save their time.

Also many of the beginners are used to the old C language and the outdated 8-bit or 16-bit compilers like Turbo C.

However, topcoder works on the upgraded environment and so, many of you find it difficult to implement your algorithms by using vectors, and STL algorithms in C++ on topcoder.

So this article will mainly focus on the things (including some best “tips and tricks”), one must know before starting to code here so as to successfully challenge other competitors.

Here’s the list of topics we’ll cover:

Editor Plugins

Many of the beginners say that they waste too much of their coding time on writing the class structure as specified in the question.I, myself, faced the same problem when I joined topcoder and gave my 1st SRM.Its a great loss especially for 250-point problems, where by the time you finish writing the class structure, many of your room competitors must have even submitted their solutions.

The topcoder editor plugins come for your rescue!

They are pre-written java plugins ,that will automatically write the class structure in your code and also give you many advanced capabilities like using cut-copy-paste in your code and also a timer to keep you aware of the time constraints.

There are many such plugins available here, though I’d personally recommend the “Kawigi Edit”.You can go through all the plugins in detail and their installations procedures here: http://www.topcoder.com/tc?module=Static&d1=applet&d2=plugins

top

Using Vectors

If you’re a C coder , then you must start learning C++ and its advanced features like STL to be able to successfully compete here and save your precious time while coding.The STL or (Standard Template Library) takes you to an entire new world of time-saving data structures and quick pre-written algorithms.

The most commonly used data structure in the problems here are vectors.

We’ll discuss vectors in brief and see how much they are analogous to arrays.

Basically, a vector is a container-class that can generate or ‘contain’ an array of any data-type.You can imagine a vector as a simple 1-Dimensional array of objects.

While defining vectors, the size of the vectors may not be specified unlike in arrays when the size is required.For e.g.,

int series[100]
vector series;

In both cases, series is an array of integers.In the 2nd case, its called a “vector” of int. Similarly, there can be vectors of float,char,string and other data-types and even vector itself! For e.g,

vector< vector  > series;	//series is equivalent to a double-dimensional integer array.

top

Iterators

Before, we start discussing in detail, we must know one of the basic concept of vectors … ITERATORS.

Iterators: They are just equivalent to C-pointers except that they are specifically designed for STL container classes only.

You can treat iterators just like you treat pointers in C.The syntax for initializing the iterator is :

vector::iterator (iterator-name);

Also there are 2 common functions associated with iterators:

begin() : It returns an iterator pointing to the 1st element of the array

end() : It returns an iterator pointing to the last element of the array

Below is an example of iterators:

vector arr;

vector::iterator it;

for(int i=0;i < 5;i++)

  arr.push_back(i);

it=arr.begin();

for(int i=0;i < 5;i++)

cout<<*(it+i);

Output:

01234

As you can see, you can treat iterators just like pointers.You can use the ‘*’ operator to get the value of the element to which the iterator is pointing to and you can use the common post or pre increment(++) and decrement operators(–) to shift the iterator to the next or the previous element respectively.

Ok so assuming that you now know how iterators work, we further proceed to discuss I/O operations in vectors.

top

I/O in vectors

Vectors supports following methods of inserting and erasing data.Check out the example below and go through the comments carefully:


vector  array;

array.push_back(10); // push_back() function inserts the value '10' to the end of the vector array

array.assign(10,42); // assign() function inserts 10 copies of value '42' to the vector (overwriting the vector)

vector ::iterator it;

it=array.begin();

array.insert(it+5,97); // insert() function inserts the value '97' to the position to which the iterator is pointing to.

// In this case, it will insert '97' to the index position 5 , i.e. the 6th element from the front.

array.pop_back();  // pop_back() function simply erases the last element of the vector

array.erase(it+3); // erase() function erases the element to which the iterator is pointing to.

//In this case, its the element at index position 3 i.e. the 4th element from the front.

top

Important STL Algorithms

Now lets us go through some of the important pre-defined algorithms in vectors ,which can definitely save you lots of time.These algorithms are stored in a library called “standard template library”, and hence ,are called “STL Algorithms”.For using these algorithms, you may need to include the header file “algorithms.h” in your code.However,this is not true for all the compilers.So include that only if necessary.

Now,check out the code below along with the comments:


// NOTE : WATCH() is a user-defined macro-function that simply prints the vector array passed to it.

vector  array;

vector ::iterator high,low,ind,size;

bool exist;

for(int i=0;i < 10;i++)

 array.push_back(10-i);	// inserts values 10,9,8,7,6,5,4,3,2,1 to the vector array

WATCH(array);

cout<<"size = "< <array.size(); // returns the current size of the vector i.e. the number of elements in it

sort(array.begin(),array.end()); // sorts the vector in ascending order.So now the vector is 1,2,3,4,5,6,7,8,9,10

WATCH(array);

high=max_element(array.begin(),array.end()); // returns an iterator to the maximum element in the array

cout<<"highest element = "<<*high<<endl;

low=min_element(array.begin(),array.end());  // returns an iterator to the minimum element in the array

cout<<"lowest element = "<<*low<<endl;

exist=binary_search(array.begin(),array.end(),6); // returns true if 6 exists in the array else return false.

// Useful when you only need to know the existence and not the position as it uses a fast binary search algorithm.

cout<<"exist = "<<exist<<endl;

reverse(array.begin(),reverse.end()); // simply reverses the entire vector

WATCH(array);

ind=find(array.begin(),array.end(),4); // returns an iterator to the element in the vector where '4' exists.

cout<<"ind = "<<ind-array.begin()<<" &value = "<<*ind;

Here’s the output: array : 10 9 8 7 6 5 4 3 2 1

size = 10

array : 1 2 3 4 5 6 7 8 9 10

highest element = 10

lowest element = 1

exist = 1

array: 10 9 8 7 6 5 4 3 2 1

ind = 6 &value = 4

So congrats ! You now know enough information about vectors to understand and code using C++ vectors without any difficulty.

And for those of you, who are curious about the WATCH() macro, here’s the code:

#define WATCH(x) {cout< <#x<<" : ";for(int i=0;i<x.size();i++)cout<<x[i];cout<<endl;}

top

Strings Class

Now that we’re done with vectors, let us jump to another most often used C++ feature. This is the strings class.

C++ strings are equivalent C-strings or character array ,only thing is that it has a class and member functions & overloaded operators of its own that offers a lot more flexibility for operating on them.

Lets discuss about initializing and manipulating strings with the helping of the following code.


// NOTE : WATCH() is again a user-defined macro that prints the string under double-quotes( " " ) in the screen.

string text; // initially text contains garbage. So it must be initialized before you use it.

text.assign(10,'*'); // inserts 10 copies of '*' to the string text

WATCH(text);

text = "we"; // "=" is an overloaded assignment operator for strings.

// You can assign values to string simply by using this operator.

// No need to go for strcpy() function in C, everytime you want to initialize the string.

WATCH(text);

text += " love top coder"; // "+=" operator can be used for appending to strings

// without the need of using strcat() function //in C.

WATCH(text);

cout< <"size = "<<text.size()<<endl; // size() function returns the number of characters in the string 'text'

text.insert(3,"all "); // insert the string "all " to the index 2 in the string 'text' without overwriting anything

WATCH(text);

text.erase(0,12); // erases 12 characters starting from index 0 in the string 'text'

WATCH(text);

text.erase(3); // erases the element with index value 3 in the string 'text'

WATCH(text);

subtext=text.substr(3,5); // Extracts the substring of 5 consequtive characters starting from index 3.

// No modification is done to the string 'text'

WATCH(subtext);

subtext.replace(1,3,"ompute"); // replace the 3 consequtive characters starting from index 1

 // in the string 'subtext' , with the new string "ompute"

WATCH(subtext);

exist=subtext.find("mp"); // returns the index of first occurence of the string "mp" in the string 'subtext'

cout<<"exist = "<<exist;

Now, here’s the output :

text = “**********”

text = “we”

text = “we love top coder”

size = 17

text = “we all love top coder”

text = “top coder”

text = “topcoder”

subtext = “coder”

subtext = “computer”

exist = 2

And lastly, there’s one more function to tell you about in strings. In case, you ever feel the need of switching to and from the C-strings or character array, you can use the following function :


string cpptext;

char ctext[100];

ctext=cpptext.c_str(); // c_str() function converts 'string' to a character array

cpptext=ctext; // for converting from a character array to string, simply use the assignment operator

So to-be-topcoders, you’re now done with strings also. 🙂

Now lets move forward to our last time-saving trick of coding.

Let us deal with macros now.

top

Making best use of MACROS

I guess you all coders are already aware of what macros are and so I don’t have to go to the basics I feel.

But just for the sake of nothing, I say, MACROS are “pre-processed commands”, i.e. they are processed before even the compilation starts.

Now let me tell you how you can make best use of macros in your program to save your coding time and help you earn more points.

All you have to do it is to replace all those code-pieces which you use most frequently in your programs by some short & fast-n-easy-to-write macros.

For e.g., consider the following chunk of code:


vector arr;

vector::iterator a;

vector farr;

vector::iterator b;

vector str;

vector::iterator c;

arr.push_back(10);

farr.push_back(4.5);

str.push_back("topcoder");

for(int i=0;i<arr .size();i++)

{

for(int j=0;j<farr.size();j++)

{

for(int k=0;k<str.size();k++)

{

//do some stuff

}

}

 }

Now consider this code:

VI arr;

VIi a;

VF farr;

VFi b;

VS str;

VSi c;

arr.pb(10);

farr.pb(4.5);

str.pb("topcoder");

REP(i,arr)

REP(j,farr)

REP(k,str)

//do some stuff

Now think for yourself how much time it will take for you to write the code in the 1st case and in the 2nd case.

In which case, it is less ? 2nd case.

By what margin ? Huge.

So whats the catch ? It saves lots of time and get you earn more points.

Now you must be wondering , what all strange tags I have used in the 2nd case.They dont at all seems like C++ commands.

Well they’re not! But you can “define” them. Like this:


#define VI vector

#define VF vector

#define VS vector

#define VIi VI::iterator

#define VFi VF::iterator

#define VSi VS::iterator

#define pb push_back

#define REP(i,a) for(int i=0;i<a .size();i++)

So all you have to do to make the 2nd case ,a valid C++ code, is to define these macros before you start your code.And the 2nd case will not only become a valid C++ code, but in fact it will work exactly the way as the 1st case will.Hence,they both are exactly same and does the same thing!

Of course, you dont have to write it every time you open a problem in the competition arena because then it’d be useless and in fact it’d be consuming more of your precious time rather than saving it.

If you’re using an editor like KawigiEdit, then you can pre-define these macros before the contest starts and save it as the KawigiEdit default template for C++ problems.So every time , you open a problem in the competition arena with KawigiEdit plugged on, these macros will automatically appear in your code beforehand and you can simply write your code in the short-hand time-saving format.

Or if you dont like using Editors, then you can yourself copy-paste these macros in the coding area from any textpad in your computer.It will only take less than 5 seconds, but in return it will save you minutes of coding time.

So you’re free to write down as many macros you like and use them in your code while competing.But since you’re a beginner, I’m giving you some of the few macros which I and many other coders, frequently use in their codes.So here it is:


#define VF vector

#define VVF vector

#define VD vector

#define VVD vector

#define VI vector

#define VVI vector

#define VS vector

#define VVS vector

#define LL long long

#define LD long double

#define LI long int

#define INF (int)1e9+1

#define FOR(i,a,b) for(int i=a;i<b ;i++)

#define REP(i,n) FOR(i,0,n)

#define pb push_back

#define itr iterator

#define sz size()

#define all(x) x.begin(),x.end()

#define WATCH(x) {cout<<"WATCHING:"<<#x<<":";for(int i=0;i<x.size();i++){cout<<x[i]<<"..";}}

#define PEEK(x) {cout<<#x<<"="<<x;}

#define GI ({int t;scanf("%d",&t);t;})

#define GF ({float t;scanf("%f",&t);t;})

These macros are usually enough for your codes.However, you can still add more to it according to your convenience.

Note that the last 5 macros, make use of console I/O operations like cout and cin and hence they are of no use in topcoder.However, they can help you in other coding events where you have to take the input and print the output from and to the console,respectively.The macros GI,GF and GS can help you for this cause.Consider the following code:


int a,b;

vector c;

scanf("%d",&a);

scanf("%d",&b);

for(int i=a;i < b ;i++)

{

int t;

scanf("%d",&t);

c.push_back(t);

}

Now consider this code , in which we have used I/O macros :


int a=GI,b=GI;

VI c;

FOR(i,a,b)

c.pb(GI);

So people! Thats it. Surprised to see how proper use of macros can effectively reduce the amount of code you have to write ?

Well you better be.

Finally, also note that the macros WATCH(x) and PEEK(x) are debugging macros and they are useful when you are trying to debug your code and you need to print most of the intermediate variables and vector arrays frequently.

top

Conclusion

So that’s all.If you’ve sincerely gone through the points explained in this article then I’m sure you won’t find any difficulty at all in coding in the topcoder format.

All you have to worry about now are the algorithms and that purely depends on how sharp your brain is and how much are you able to practice and polish your skills.

For that purpose, topcoder has lots n lots of practice room available in their competition arena. When you log in, spend your time in solving those practice questions and also seeing the best solutions for those problems which are also available there.

So finally, lets get a brief summary of the things we have noted so far:

  • Always use an EDITOR plugin before any competition (Recommended : Kawigi Edit).Link: http://www.topcoder.com/tc?module=Static&d1=applet&d2=plugins
  • Instead of arrays , try to use vectors as much as possible. Make efficient use of all the STL algorithms for time-saving code.
  • Use strings instead of character array wherever possible.
  • Make efficient use of macros. Remember, they can reduce your coding time by amounts you’d have never imagined.
  • Use practice rooms as long as possible to polish your skills.
  • Finally, there are lots of algorithms tutorials available in topcoder in the “Educational Content” section.Spend some time going through them also.

So people, thats all for this article.I hope all of you who are beginners, must have found this article really helpful. 🙂

Now get back to your work and start some serious “Top-Coding”.Good Luck!

My Details:

 

Abhishek Shrivastava
108107073@nitt.edu
http://delta.nitt.edu/~jereme

Advertisements

5 comments on “For Beginners in [Topcoder]

  1. Nice post 🙂

    But do note that you use vectors and strings, you get the additional overhead as well.

    Sometimes, changing from vectors to arrays can lower your running time quite a bit 🙂

  2. Pingback: For Beginners in [Topcoder] « Abhishek Shrivastava

  3. Thank you for interesting post. Got some new interesting things
    Although I use Java,)
    I have a question about editor. Kawigi Edit is nice editor, but I’d like to experience other one. I mean Eclipse.
    I’ve followed almost all steps on http://fornwall.net/eclipsecoder/ except
    updating part. I have Eclipse Indigo version.
    So could someone explain everything step by step….how to install Eclipse Coder editor

    I’ll be very thankful.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s