CCC '19 S5:Triangle: The Data Structure

Question

This problem is from [CCC2019]: https://dmoj.ca/problem/ccc19s5/ (Canadian Computing Contest 2019) and I have implemented it in C++.

I used sequence [A054237]: https://oeis.org/A054237/table to compute the indexes of sub-triangles.

In a parallel universe, the most important data structure in computer science is the triangle. A triangle of size M M consists of M M rows, with the i t h i^{th} row containing i i elements. Furthermore, these rows must be arranged to form the shape of an equilateral triangle. That is, each row is centred around a vertical line of symmetry through the middle of the triangle. For example, the diagram below shows a triangle of size 4:

A triangle contains sub-triangles. For example, the triangle above contains ten sub-triangles of size 1, six sub-triangles of size 2 (two of which are the triangle containing ( 3 , 1 , 2 ) (3,1,2) and the triangle containing ( 4 , 6 , 1 ) (4,6,1) ), three sub-triangles of size 3 (one of which contains ( 2 , 2 , 1 , 1 , 4 , 2 ) (2,2,1,1,4,2) ). Note that every triangle is a sub-triangle of itself.

You are given a triangle of size N N and must find the sum of the maximum elements of every sub-triangle of size K K .

Please review and suggest edits.

#include<stdio.h>


int rec(int x)
{
    return (x*(x+1))/2;             //sum of n natural numbers
}
int main()
{   int n,k;                   //n=height of triangle  k=height of sub-triangles   ne= number of elements
    int t1=0;
    int t2=0;
    std::scanf("%d %d",&n,&k);
    int ne=rec(n);
    int rk=rec(k);                  //rk=number of elements in sub-triangle
    int nt=ne-rk-1;         //ior[]=array to store index of row     nt=number of sub-triangles
    unsigned long int e[ne],gval,sum=0;  //e[]=array to store elements   gval=greatest element of sub-triangle    sum=sum of gvals
    gval=0;
    for(int i=0;i<ne;i++)
        scanf("%ld",&e[i]);
    for(int rt=0,ior=0;ior<nt;rt++)
    {
        for(int ioc,r=0; r<=rt && ior<nt; r++,ior++)
        {   ioc=0;
            for(int ct=0;ioc<rk;ct++)
            {
                for(int c=0;c<=ct && ioc<rk;ioc++,c++,t2++)
                {
                    if(gval<e[t2])gval=e[t2];
                }
                t2+=rt;
            }
            sum+=gval;
            t1++;
            t2=t1;
            gval=0;
        }
    }
    std::printf("%ld",sum);
    return 0;
}

Answer 1

Welcome to Code Review.

As stated in the comments, the code is the C programming language, not C++. C is a procedural language and C++ is an object oriented lanugage originally based on C. We can tell from the first line,

#include <stdio.h>

In C++ this file would be <cstdio> but generally we would not be using it because represents an older form of input/output that has been replaced in C++.

C++ generally uses

#include <iostream>

which provides std::cin as input and std::cout as output.

The functions printf() and scanf() generally are not used in C++. FYI scanf() and printf() are not members of the std namespace and std::scanf() does not compile in many compilers.

Complexity
It might be better if there was a function to get the input and another function to process the input. This would lead to less variables being declared in main() and functions that are shorter, easier to read debug and maintain.

Variable Declarations
The line of code:

    unsigned long int e[ne],gval,sum=0;

Is difficult to maintain, it would be better if it was multiple lines.

    unsigned long e[ne];
    unsigned long gval;
    unsigned long sum=0;

Also one should choose either long or int but not both. It would be best if gval was also initialized.

Variables should be declared as needed, for instance the variable gval should be defined inside the first inner for loop as shown below:

Variable Names
Rather than providing comments to explain what the variables are, give the variables meaningful names longer than 2 characters.

This makes the code much easier to read, debug and modify.

Spacing
The vertical and horizontal spacing of the code is all crammed together which makes it very difficult to read add vertical spacing after declarations and after logic blocks.

In expressions there should be spaces around binary operators as shown below.

int main()
{   int n,k;                   //n=height of triangle  k=height of sub-triangles   ne= number of elements
    int t1=0;
    int t2=0;

    scanf("%d %d", &n, k);

    int ne=rec(n);
    int rk=rec(k);
    int nt=ne-rk-1;

    unsigned long e[ne];
    unsigned long sum=0;

    for(int i = 0; i < ne; i++)
    {
        scanf("%ld",&e[i]);
    }

    for(int rt = 0, ior = 0; ior < nt; rt++)
    {
        for(int r=0; r<=rt && ior<nt; r++,ior++)
        {
            int ioc = 0;
            unsigned long gval = 0;
            for(int ct=0; ioc <rk; ct++)
            {
                for(int c = 0; c <= ct && ioc < rk; ioc++, c++, t2++)
                {
                    if(gval < e[t2])
                    {
                        gval = e[t2];
                    }
                }
                t2+=rt;
            }
            sum += gval;
            t1++;
            t2 = t1;
        }
    }
    printf("%ld", sum);
    return 0;
}