What is Competitive Programming?

Definition

Competitive Programming is a sport, which requires participants to program to solve computational problems. The score a participant gets is normally calculated based on how many problems he solved, the difficulty of the problems, the time he spends on each problem and the number of attempts he made before successfully solve each problem. Each problem is well-defined, clear and has concrete limits and constraints.

A competition can be held locally or globally. There are some annual global competitions, like IOI (International Olympiad in Informatics) – an individual-based contest for high-school students, ICPC (International Collegiate Programming Contest) – a team-based contest for college students, Google Code Jam – hosted by Google, Facebook Hacker Cup – from Facebook.

Example

Here is an example of a problem:

Problem statementAlice has n bags of candies. Each bag contains a number of candies. As she is going for a long vacation soon, she wants to prepare some candies to eat during the vocation. We know that her vocation will last m days, and she wants to eat 1 candy each day. Could you help her find out the least number of bags that she can bring so that her sweet tooth is satisfied?
Input formatThe first line contains 2 space-separated integers: n and m.
The second line contains n space-separated integer. The i-th integer represents the number of candies Alice has in the i-th bag.
Output formatPrint the minimum number of bags Alice can bring so that she has a candy to eat for each day of her vocation.
Constraints1 \leq n \leq 100.
1 \leq m \leq 1000.
1 \leq The number of candies in each bag \leq 200.
The total number of candies in all the bags \geq m.
Time limit1 second. (This means that your program should run in at most 1 seconds)
Memory limit64 megabytes. (Your program should use at most 64 MB of memory)
Example 1Input:
5 9
8 2 6 4 3
Output:
2
Example 2Input:
3 10
3 4 3
Output:
3

There are many ways to solve the above problem. I will present the one I think is the most simple:
First, we sort all the bags in the non-increasing order of the number of candies.
Then, we check if the number of candies in the biggest bag is \geq m. If it is, we output 1 as the result. If it is not, then we check if the total number of candies in the 2 biggest bags is \geq m. If it is, we output 2 as the result. If it is not, then we check the total number of candies in the 3 biggest bags and so on, until we find that the total number of candies in k biggest bags is \geq m.

Here is out solution written in C++:

#include<bits/stdc++.h>

using namespace std;

int a[105];
int n, m;

int main() {
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	
	sort(a + 1, a + n + 1);
	reverse(a + 1, a + n + 1);
	
	int sum_of_candies = 0;
	for (int i = 1; i <= n; ++i) {
		sum_of_candies += a[i];
		if (sum_of_candies >= m) {
			cout << i << endl;
			break;
		}
	}

	return 0;

}

Some websites to learn and practice Competitive Programming

Codeforces

Codechef

Atcoder

Leetcode

SPOJ

Hackerrank

and many others.

Leave a Reply