Competitive Programming Tutorials: Solving a problem

Hello, Fellows. NefariousPie here. Today we’re going to talk about the approach to solve a problem. This section is not necessarily for Competitive coding only. You can approach any programming problem in this way. None of the competitive programming tutorials going to teach you this. People tend to figure this out themselves most of the time. But we shall leave no stone unturned.

This approach is called “A seven-step approach”. Now, don’t think the name is “seven-step” because of the name of the website. I did not invent this method. Actually, I learned this method while reading documentation from Duke University, North Carolina.

Seven-step Approach

You can not just read a problem and then think of a coding solution for it in your head. If it’s a very basic problem, with no brain works. Then it might work. But, for problems which are more complex, this method is not going to help you.

Seven Step Approach to solve a competitive programming problem
Seven-step Approach

First, let me explain every step. After that, we are going to solve the problem following this method. One of the problems is going to be a basic programming question. People solve this kind of questions in practice labs. The next question is going to be from a competitive coding contest. Solving real problems is always the best way of learning for any competitive programming tutorials.

Work On The Example By Hand

Take a look at the problem. Divide the problem into small instances. Take a good look at the given data. Try to relate them. Finding the relation is the first step to solving a problem. While you are doing this, your brain has figured out something already. This process helps you to solve a problem as a human being. None of the competitive programming tutorials can help you to develop this skill. It totally depends upon your problem-solving capability.

Write Down Your Thoughts

Writing down your thoughts help you to develop the Algorithm quickly. You don’t have to write the whole thing. No need to follow any particular structure. Just write down the important parts. This document can help you to debug your code if something goes wrong.

Search For Patterns

No matter what the problem is there will be a repetitive pattern. Programming is all about finding this pattern in your question. Once you have found it. Voilà! Your algorithm is ready. If you practice enough and follow competitive programming tutorials you will be able to see the patterns pretty quickly.

Check By hand

After your algorithm is ready you can’t start your coding then and there. You have to check whether the test cases are generating the correct output. For competitive programming questions, one or more than one test cases will be provided. But, for normal problems, you may have to generate your own test case and check whether your answer is correct.

Translate into code

When your algorithm is generating correct output, now you will go for writing the code. Your code will start by taking inputs through STDIN. Translate your thoughts in code using loops, condition, functions.

Run Test Case

Run multiple test cases to make sure that your code is working correctly. But always remember one thing: “no amount of test cases can guarantee that code is absolutely correct”. You may find out that after submitting the code in a contest, some cases are generating the wrong answer. Here’s a thing you need to do for this kind of situation. If you’re practising in your home, try to solve the problem completely. But in Competitive Coding contests, the limited time will be an issue. So, if you have 40-50% cases generating correct output, submit your code. That extra time can be used in solving the next problem.

Debugging

Debugging is the most important part of coding. You have to debug your code if it’s generating any Compilation Error, Wrong Output, Presentation Error etc. Depending upon the problem you may have to debug your a fragment of your code, any particular function or even your algorithm.

Lets put it into practice

We are going to Solve our first programming problem. Throughout this blog series, we are going to solve a lot of problems. For me, it’s not possible to show you these 7 steps for every problem. But, you should follow this while solving any problem by yourself.

Write a program to calculate the perimeter of shape (with a finite number of sides) where co-ordinates of every point are given.

Explanation

Calculate the perimeter of a specific shape is easy. You have the formulas to back you up. But, Solving it using the coordinates of the points is different. Here you have to understand the problem by drawing this in a paper.

An example of competitive programming problem

Let’s write the important point we have figured out from the problem.

  • First, we have to Calculate the distance between every 2 connected points.
  • We have to add all the distances to calculate the perimeter.
  • Input should be taken as float or double. Because the output can be a fractional number.
  • Repeating sub-sequence: for every 2 adjacent points, we have to calculate the distance. Initialize result as 0. Keep adding the distance value to the result.
  • Useful Formula: the distance between two points.
distance = Sqrt((X1 - X2)^2 + (Y1-Y2)^2)

Other points to remember

The result depends upon the order of the input.

A n illustration describing the problem
As the shape is different, the perimeter will not be the same

Solving The Problem

First, we will define the distance function. We are going to use the mentioned formula. The return type of function should be float/double.

float distance(float X1,float Y1,float X2, float Y2)
{
    return sqrt((X2-X1)*(X2-X1) + (Y2-Y1)*(Y2-Y1));
/*for use sqrt() function we have to include <math.h> header file*/
}

The main function will solve the repetitive pattern. We have to use a loop. For that. But, most import thing is how we are taking the input. For now, let’s use a 2D array.

float point[10][2];
int n;
scanf("%d",&n);
for (int i = 0; i < n; ++i){
	scanf("%f%f",&point[i][0],&point[i][1]);
	}

Loop Part

We will start from the (array[0][0], array[0][1]) element. The adjacent point will be (array[1][0], array[1][1]). We will calculate the distance between them. Then will go to the next point. And apply the same steps.

float total_distance=0,d=0;
for (int i = 0; i < n-1; ++i){
	d = distance(point[i][0],point[i][1],point[i+1][0],point[i+1][1]);
	total_distance += d;
	}

Doing so will calculate the distance from 0-th to the n-th point. But, there’s one side left to calculate. The side from n-th point to 0-th point.

A sub part of the competitive programming problem
d = distance(point[0][0],point[0][1],point[n-1][0],point[n-1][1]);
total_distance += d;
printf("%f\n",total_distance);

Voilà! Your code is complete. Now it’s your task to assemble them together and give it a test run. If you find any problem in the code, let us know in the comment section.

Problem 2

Generate an array of a given size with equal count and sum of odd and even numbers

Explanation

Given an integer N, the task is to find an array of length N that contains the same count of odd and even elements with an equal sum of even and odd elements in the array. Print -1 if no such array is possible.

Test Cases

Input: N = 4
Output: 1 2 5 4v
Explanation:
Even elements of the array — {2, 4}, S(even) = 6
Odd elements of the array — {1, 5}, S(odd) = 6

Input: N = 6
Output: -1
Explanation:
There are no such arrays exist, which contains 3 even elements and 3 odd elements with equal sum

Solving The Problem in Pen Paper

If there’s N elements in the array, There should be N/2 odd elements and N/2 even elements. Only then it will be possible to have same count of Even and Odd number in the array.

So, if N = 5 (Odd number); N/2 = 2 (as integer value). That means there will be 2 even and 2 odd number. And there will be one empty space. So, that space needs to be filled up with either an even or odd number. That will lead to the scenario where no. of odd numbers no. of even numbers. So, N can not be an Odd number. And N can not be a number where N/2 = an odd number.

Valid/In valid test cases

As the sum of odd numbers of an odd number is an odd number, It’s an invalid input. So, the only valid input for N is where N = Multiple of 4.

Repetitive Pattern

illustration describing the solution and algorithm

So we will just put the 1-st N/2 even numbers in the even positions of the array. Then we will put 1-st N/2-1 Odd numbers in the odd position of the array. The last odd number will be (sum of even numbers – the sum of odd numbers).

Code

Input
int n;
scanf("%d",&n);
odd_even_array(n); /*Calling the function where main logic will be written*/
Checking for valid/Invalid input
if(n%4!=0)
   {
       printf("-1");
       return -1;
   }
/*only numbers that are multiple of 4 are the valid input*/
Initializing the Array
 int *arr = malloc (sizeof (int) * n);
     int even_sum = 0, odd_sum = 0;
/*putting the 1-st N/2 even numbers in the even positions*/
     for(int i=0;i<n; i+=2)
     {
         arr[i+1] = (i+2);
         even_sum += (i+2);   
     }
/*putting the 1-st N/2-1 odd numbers in the odd positions*/
     for (int i = 0; i < n-2; i+=2)
     {
         arr[i] = i+1;
         odd_sum += (i+1);
     }

Closure

 arr[n-2] = (even_sum - odd_sum);
/*calculating the last odd number and printing the result*/
     for (int i = 0; i < n; i++)
     {
          printf("%d ",arr[i]);
     }
     return 1;

So, this is where the second blog of competitive programming tutorials ends. Hope you have enjoyed it. If you find out any issues with the code or logic let us know in the comment section. We will meet again with a new blog. Until then read some competitive programming tutorials, practise some coding.

Here’s a link that contains some basic problems on the array. Try to solve them if you are a beginner. Adiós!

To CHECK out the previous article on competitive coding click here.

6 thoughts on “Competitive Programming Tutorials: Solving a problem”

    1. No, ma’am. The programming language I’ve used is C. HTML is not a language that we can use for competitive programming purpose.

Leave a Comment

Your email address will not be published. Required fields are marked *