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