Counting matrices

I need help optimizing my code to run faster (it works but I get Time Limit Exceeded) for this problem.

(Don't pay attention to readInt() function, its only used for fast input)

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include
#include
#include
#include
#include
#include
using namespace std;
int T, N;

int readInt() {
    bool minus = false;
    int result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch  '9') break;
        result = result * 10 + (ch - '0');
    }
    if (minus)
        return -result;
    else
        return result;
}

bool Luwia(int x) { return x % 2 == 0; }

int func1(int x)
{
    return x - 1;
}

unsigned long long func2(int x)
{
    unsigned long long sum = 0;
    for (int i = 1; i = n - 1;)
    {
        if (i != pow(n, 2) / 4)
        {
            sum1 += 2 * func2(i);

        }
        else
        {
            sum1 += func2(i);
        }

        if (first)
        {
            i -= 1; first = false; continue;
        }
        i -= (k + 2);
        k = k + 2;
    }
    return sum1;
}

unsigned long long Kentistvis(int n)
{
    unsigned long long sum2 = 0;
    int k = 0;
    for (int i = pow(n, 2) / 4; i >= n - 1;)
    {
        sum2 += 2 * func2(i);
        i -= (k + 2);
        k = k + 2;
    }
    return sum2;
}

int main() {
    cin >> T;
    while (T--)
    {
        N = readInt();
        if (Luwia(N)) printf("%llu\n", Luwistvis(N));
        else printf("%llu\n", Kentistvis(N));
    }

    return 0;
}

A good part of this review will not be about optimization but about style. The speed of your program should not be worse after you apply the changes though. First of all, you should order your headers by alphabetic order: this will allow you to check whether a header is inluded or not without having to search for it longer than needed:

#include 
#include 
#include 
#include 
#include 
#include 

Writing using namespace std; is bad practice especially in header files: it will pollute the namespace and may cause name clashes. Moreover, you don't even need it except for std::cin. Writing std:: is no longer and it's also good practice to put it before any standard function, including C legacy functions (std::printf, std::pow...).

In C++, you don't need to write return 0; at the end of your main function. If the compiler reaches the end of main and don't find any return statement, it will automagically add return 0;.

Your function names are not really good:
* As noted in the comments, you shouldn't mix languages in code. C++ is an English language, therefore, you should rename Luwia, Luwistvis and Kentistvis to is_even, for_even and for_odd.

Moreover, for_even and for_odd do not tell what the functions actually do but merely say that you should give even or odd numbers to them. You should give more meaningful names.

You should really rename func1 and func2. The names don't give any clue about what these functions do, and the name of the parameters do not help at all. Also, you should be consistent when naming your parameters: func2 takes int x while Luwistvis takes int n, which is not consistent.

You do not use func1 at all. You should remove it since it does not seem to add anything (and it's faster to write x-1 whatsoever, which I assume is what you actually did in func2).

In your main, you use std::cin for input for std::printf for output. You should be consistent and use std::cout which is the idiomatic C++ way to output values to the console.

You can refactor this loop:

int k = 0;
for (int i = pow(n, 2) / 4; i >= n - 1;)
{
    sum2 += 2 * func2(i);
    i -= (k + 2);
    k = k + 2;
}

First of all, you can put the int k = 0 in the first part of the for loop since it won't be needed after the loop. Then, you increment k before decrementing i, that will save you from repeating k + 2. Also, you can replace k = k + 2 by k += 2 (use compound assignement operators when you can). Finally, you can put the k incrementation and i decrementation in the last part of the for loop:

for (int i = pow(n, 2) / 4, k = 0;
     i >= n - 1;
     k += 2, i -= k)
{
    sum2 += 2 * func2(i);
}

That say, I don't think it looks really nice either.

Some more tidbits:

• std::pow(n, 2) is good, it shouldn't be different from n*n on any decent compiler, and is somehow more expressive.

• In Luwistvis, you compute pow(n, 2) / 4 at every iteration of your for loop. While some compilers may perform loop optimizations, you should define a constant instead.

• It does not make any difference for integers, but for other types, pre-increment (++i) may be faster than post-increment (i++). Therefore, you should always use pre-increment, unless you explicitly need post-increment.

Overall, someone else will probably be able to give you a way to optimize the algorithm instead of optimizing the code. Choosing the good algorithm is the best way to achieve the best performance.

StackExchange Code Review Q#46994, answer score: 5