Getting started with Competitive Programming: Understanding Problem Statement

What better way to start than by knowing what does the term "Competitive Programming" mean ?
Competitive programming can be briefly defined as solving a specified problem in one of the permitted programming languages under well defined time and memory constraint.

This post will emphasize on how to interpret various parts of problem presented and subsequently extract useful and necessary information for an effective solution. To give an idea about how problems are presented, I'll go ahead with one of the problems, Chef and Party from the contest CodeTrix II.

The problem is structured as follows:

Problem Statement

There will be a problem statement which will likely have a background story along with it to make the problem statement interesting. Sorry to say this can also be used as a tool to divert the user's thinking away from the fundamental problem. The problem "chef and party" has the following statement.

" Chef has decided to host a party on the eve of Christmas. But at his party more guests have come than he had invited, let the total number of guests who have arrived be N. So he is not able to pay the bill of all the guests. The chef decides to pay the bill of only K guests. Chef tells his best friend to select K guests whose bill the chef will pay.
The maximum bill of a particular guest does not exceeds 2000."

This statement after removing the background story and other unnecessary details can be reduced to:

"Chef will only pay for K out N guests and you need to find those K guests"

Input Description

This section usually explains the structure of the input. Besides input structure it also contains the meaning of the variable used in the problem statement. Sometimes the meaning can also be a part of problem statement. The input description is:

• The first line of the input contain T test cases.The description of T test cases follows.
• For each test case, first line contains the total number of guests who came at the party N.
• The next line contains space separated individual bills of the N guests.
• The next line contains the value of K
• The next line contains K space separated integers

 After understanding the input description, you should quickly jump to the "example" section and take a look at the sample input. The following is the input for the problem in example section.

  2                                 // No of test cases (T)
  10                                // total number of guests (N)
  20 30 50 30 10 5 78 98 345 1000   // individual bills of guests
  4                                 // No.of guests chef will pay for
  1 4 7 8                           // the indexes of the guest
  5
  600 700 400 300 230
  2
  2 3

So 2 denotes the total number of test cases. From the input description we can conclude that each test case will be of 4 lines.  The test case 1 has been made bold. So your program must take input in this form itself.
After this it's better to the read the explanation for the test case if it is present.  This should give you a fair idea about what is expected from you in the solution.

Output Description

Along the same lines output description specifies the structure of the output. Read the output description very carefully as you'll have to strictly abide by the specification. Any deviation will lead to wrong answers. The output description for problem is:

• For each test case, output a single line containing the total bill the chef will pay

Now again jump to the output section in the "example" section to understand the output better.

Constraints

This section will is meant to give an idea about what data type you'll need to use to accommodate the input of the problem and other variables used in your solution program. 

• 1 ≤ T ≤ 100
• 1 < N ≤ 100
• 1 < K < N

Since all of these variables (numbers) are well within the range of 'int', so taking 'int' would suffice.

Finally, the time and memory constraints of the problem statement mean that your solution should terminate properly within the time limit and should not use more memory than that specified besides obviously outputting the correct answer to get your solution accepted. More details on this sometime later...

For your reference a solution to the above problem is given below:

#include<stdio.h>   int arr[101]; // as there can be maximum of 100 guests   int main() {     int t, i;     scanf("%d", &t);  // take input for number of test cases           while(t--)     {   // for each test case: take input, calculate and print output         int n;         scanf("%d", &n);         for (i =0; i < n; i++)             scanf("%d", &arr[i]);         int k, index;         int sum = 0;         scanf("%d", &k);         for (i = 0; i < k; i++)         {             scanf("%d", &index);             sum += arr[index-1];         }         printf("%d\n", sum);  // print the output per test case     }     return 0; }

Getting Started with VIM

Vim is an awesome text editor, oh wait it's just much more than a text editor.

Before i begin this post doesn't not include commands and all but just an advice as to how to approach learning Vim.

VIM as such provides just bare minimum functionality and is not so cool, but again it's upto you to configure  Vim according to you and make it cool. Vim also supports tons of plugins that bring along a lot more functionality than just simple Vim.

What not do do...

One of the biggest mistake one can make while starting with Vim is to approach it just like other text editors like sublime, Gedit etc and it is because Vim is different is that is why it's awesome.

Vim is a modal editor which means it has different modes and a key may take special role according to the mode.

Also in Vim you simply do everything from Keyboard so say Goodbye to you mouse. Everything you do in vim is doable by not moving your fingers from the home row, yes exactly you don't even need arrow keys because moving is done using h,j,k,l keys and this is the main reason behind increase in productivity as you are not wasting time moving you hand back and forth between your mouse/arrow keys. 

How to begin ?

Vim stores the configuration in a file called .vimrc (also know as a dot file, literally because of the dot) present in your home directory. This simply text file dictates what will the behavior of Vim when launched.  Initially you should use somebody else's dot files and once you get your hands on and have fair bit experience you can start to tweak the configuration according to your needs.

Initially if you want you can use my vim setup: https://github.com/harsimrans/dotvim

Also initially you should not make Vim as your primary text editor because if you do so you'll hate Vim, like from the bottom of your heart. your productivity will drop not because vim is complicated but because you are just not used to it. So take out some free time and start playing around with Vim and probably after a few days you'll feel comfortable.

Browse through the Internet, there are tons of articles about basic Vim commands and go through a couple of them before you start using Vim.

REMEMBER invest some time in Vim , play with it and get comfortable with Vim. Then make Vim your primary editor. Believe me you will realize your productivity increase than before even if it's little.

Productivity after vim  = c * productivity before vim, where Obviously c >> 1 :P

Things to do before and after installing Ubuntu

After almost running out of space allocated for Ubuntu and somewhat messing my machine (started to crash a lot) just because I'm not a good maintainer, i decided to change the partition structure for the new install.

Deciding on how much space you need

This is a crucial step in installation. You should try and allocate enough space for the Linux distribution you are installing to avoid the pains of resizing the partitions. Sometime people even reinstall the whole distribution instead of resizing the partitions.

In my previous install i had allocated 40GB for the Linux partition. Installing software and a couple of virtual machines i was on the verge of running out of space. Also since i was to re-install so i decided to given even more space.

 

How my partitions are laid out

Also i decided to make a separate home partition, so that i don't loose my data if i need to reinstall or shift to a different distribution.

So i decided to make 3 separate partitions:

1. About 40GB partition for root, where all the software installations will reside.
2. About 60GB partition for home, so that my data resides in a separate partition.
3. Since i have 6GB RAM , so about 5GB of swap space.

This is how my partitions are laid out on the disk.

Installation Process

The installation process is very easy for Ubuntu and now a days almost every distribution has made their installation process easier than before. So no problems here once your know how to layout your partitions.

After Installation

Surprisingly this time out of the box i could manipulate brightness settings otherwise you'll need to fix that too.
There are a few things you might want to do after you install Ubuntu. Here is a list of what i did.

1. After installation adjust basic settings according to your need. Go to settings and make changes to power management, display, launcher settings etc.
2. Enable Mutiverse.
   
3. There are some 3rd party codecs or plugins required for essential softwares to work. Install "ubuntu-restricted-extras", this should take of almost everything you'll need from flash to codecs for audio and video files. But be warned that it might not be legal in some countries, because of software patents.
4. When ever you install a package or remove a packages, remember there may be packages that are no longer needed (mostly installed along as dependencies). Make sure to remove those too.

Hopefully this time i will try hard not to screw my installation.