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; }