2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Please review and suggest improvements. \$\endgroup\$ – Jashman Singh Brar Sep 29 at 10:56
  • 1
    \$\begingroup\$ I can't see any c++ specific code in your question besides using namespace std;, which is discouraged anyways. \$\endgroup\$ – πάντα ῥεῖ Sep 29 at 11:11
  • 1
    \$\begingroup\$ @πάνταῥεῖ are you saying this isn't c++? I am high schooler and still learning. Why is using namespace std discouraged? \$\endgroup\$ – Jashman Singh Brar Sep 29 at 11:14
  • \$\begingroup\$ This isn't c++ but merely c code. Regarding the using namespace std; read up here please. \$\endgroup\$ – πάντα ῥεῖ Sep 29 at 11:19
  • \$\begingroup\$ @πάνταῥεῖ I am using code blocks as my IDE and gcc as compiler. It states the language as c++11 instead of c. Keeping language aside, I am just asking for algorithmic optimization and that I think is kinda universal for all languages. \$\endgroup\$ – Jashman Singh Brar Sep 29 at 11:23
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer, I was loosing hope for answer. I used scanf because it has lower buffer then cin \$\endgroup\$ – Jashman Singh Brar Sep 29 at 14:25
  • \$\begingroup\$ @JashmanSinghBrar There are currently 2 votes to close this question as off-topic. Because you are a very beginner I explained things for you, otherwise I would have voted to close as well. We can only review working code here and it's not clear that your code works. StackOverflow.com does answer questions about code that isn't working. \$\endgroup\$ – pacmaninbw Sep 29 at 14:32
  • \$\begingroup\$ I have edited the code as you mentioned \$\endgroup\$ – Jashman Singh Brar Sep 29 at 14:32
  • \$\begingroup\$ Please dont' edit a question after it has been answered. See the code review rulls at codereview.stackexchange.com/help/someone-answers. You might want to look at all the help there. \$\endgroup\$ – pacmaninbw Sep 29 at 14:35
  • 1
    \$\begingroup\$ my code works and I am not that beginner, the thing is that the information among hackerrank community is being contradicted here \$\endgroup\$ – Jashman Singh Brar Sep 29 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.