Tearing Down a Problem

In this section, let's take a simple example problem from CodeForces and try to understand the following nuances involved:

Problem Statement

The Problem Statement is precisely what it suggests, i.e., an explanation of the problem for which the code has to be written. Usually, these statements are written as a story, which can be annoying sometimes. Still, I guess they're just trying to judge how fast the reader can extract valuable information from the whole thing.

For instance, in the above example, the crux of the problem is that we'll be given a positive integer W, and we need to answer if it's possible to find two even positive integers that sum up to the given W.

Input Format

There will almost always be the involvement of a few variables in the problem statement, which will be given to the code as input. This section talks about what will be the format in which the input will come in. In the example above, it's still a bit simpler because there's just one integer.

But imagine if there were 4-5 integers to be taken as input and maybe a few strings also. Then, it'll be essential to know in what order and format to expect the input, correct? Because this is the only way we'll be able to match the order and format of input in our code.

Output Format

We all know that the point of this is that we have to solve the problem given in the Problem Statement by writing code that processes the input appropriately to generate the correct output.

This section explains what exactly the code should print in different cases. In the above example, as you can see, the problem setter asks us to print YES if it's possible to find such two numbers; otherwise, NO.

Constraints

This section specifies the limitations or boundaries that define the range of valid inputs for a problem. They determine the conditions under which a solution must operate. Constraints are crucial because they help set realistic expectations for the size and complexity of the input data.

In simpler terms, constraints answer questions like:

1. How big can the input be?
   1. For example, in this problem, it is written: 1 ≤ W ≤ 100
   2. This means that W won't be greater than 100 in this case.
2. Are there any specific conditions or rules for the input data?
   1. Constraints may include additional rules, such as restrictions on the size of arrays, the length of strings, or other input properties.
   2. Other additional constraints could be that the input will always be a prime number, or N other things.

Understanding constraints is essential because it guides the participant in designing a solution that not only solves the problem but does so efficiently within the specified limits. It helps prevent solutions that may work for small inputs but fail or become too slow for larger, more realistic data sets.

Time Limit

Speaking of efficient solutions in the paragraph above, let's cover Time Limit next. As you can see in the screenshot on the top, the time limit mentioned for this problem is 1 second per test.

Now, as we read before, our code is going to be tested using multiple different tests. Having a time limit of 1 second per test means that the code should be able to generate the output within the limit of 1 second for each test. If it takes longer for any of the tests, then the verdict will be Time Limit Exceeded. ⏰

This part of the system tests whether the code is efficient enough or not.

Let's try it out.

I hope that all the aspects explained above are clear now. Let's dive into the solution now.

We need to think about what conditions W needs to follow so that there exists at least 1 pair of positive even integers that sum up to W.

If we sum up 2 even integers, the resultant will also always be even, right? Then, doesn't that mean that getting a pair of desired positive even numbers is possible only if W is an even number? 🤔

Let's try a few examples:

1. For W = 6, the integers could be 4 and 2.
2. For W = 10, the integers could be 8 and 2.
3. We could always choose W - 2 and 2 if we try to find a pattern.

Let's write the code down quickly.

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int w; cin >> w;

	if((w%2) == 0)
		cout << "YES\n";
	else
		cout << "NO\n";
    return 0;
}

What do you think? Is the code correct? Well, the answer is NO.

Let's try again!

What did we miss on the first try? We were on the right track, but when solving DSA problems, we must be careful to cover all the edge cases. In this particular problem, the pattern we observed made sense but wasn't applicable if the value of W is 2.

For W = 2, we won't be able to represent it as a sum of 2 positive even integers, and clearly, our code will print YES because 2 is even; that's why we got Wrong Answer on submitting the code.

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int w; cin >> w;

	if((w%2) == 0 and w > 2)
		cout << "YES\n";
	else
		cout << "NO\n";
    return 0;
}

Yay! it worked this time.

Remember the gym analogy from the previous chapter? Don't forget to go and try to submit on your own!