# 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<iostream>
#include<vector>
#include<fstream>
#include<algorithm>
#include<string>
#include<cmath>
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;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch - '0';
while (true) {
ch = getchar();
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 < x; i++)
{
sum += (x - 1) / i;
}
return sum;
}

unsigned long long Luwistvis(int n)
{
unsigned long long sum1 = 0;
int k = 1;
bool first = true;
for (int i = pow(n, 2) / 4; 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;
}

-
Could you please translate the names of the functions Luwia, Luwistvis and Kentistvis to english? –  Nobody Apr 12 '14 at 9:50
is_even, for_even, for_odd –  Michael Abramishvili Apr 12 '14 at 9:52
This strikes me as the sort of problem that requires optimization of the algorithm rather than the code itself. Rather than basically generating and counting all the matrices that fit the conditions, you need to figure things out mathematically, so the program itself does a relatively simple computation on the inputs. –  Jerry Coffin Apr 12 '14 at 17:27

## 2 Answers

Well you have lots of code in your loop that only happens once.
You could manually hoist this out of the loop and decrease the size of the loop once.

unsigned long long Luwistvis(int n)
{
unsigned long long sum1 = 0;
int k = 1;
bool first = true;
for (int i = pow(n, 2) / 4; i >= n - 1;)
{
if (i != pow(n, 2) / 4)
{
sum1 += 2 * func2(i);

}
//
// This only happens on the first iteration
else
{
sum1 += func2(i);
}

//
// This only happens on the first iteration
if (first)
{
i -= 1; first = false; continue;
}
i -= (k + 2);
k = k + 2;
}
return sum1;
}

1. Yank that stuff out of the loop it will probably make it fast.
2. If you must have branches in a loop then make the true branch the one that happens most frequently.
• This is because when the CPU reaches a branch it caries on executing instructions (in predictive mode (all modern machines)) until the value of the condition is evaluated.
• If the value was true then you predicted write and no harm.
• If the condition evaluates to false then you have to throw away your predictive work and execute the other branch
• Note: This is totally invisible at the code level but can give significant speed ups.
• So for best result put frequent code in the true branch (there compiler extension to help with this).

Step 1: Yank the first iteration.

unsigned long long Luwistvis(int n)
{
unsigned long long sum1 = 0;
int k = 1;
bool first = true;

// Do first iteration outside the loop.
int i;
{
i = (pow(n, 2) / 4);
if (i != pow(n, 2) / 4)
{
sum1 += 2 * func2(i);

}
//
// This only happens on the first iteration
else
{
sum1 += func2(i);
}

//
// This only happens on the first iteration
if (first)
{
i -= 1; first = false; continue;
}
i -= (k + 2);
k = k + 2;
}

for(; i >= n - 1;)
{
if (i != pow(n, 2) / 4)
{
sum1 += 2 * func2(i);

}
//
// This only happens on the first iteration
else
{
sum1 += func2(i);
}

//
// This only happens on the first iteration
if (first)
{
i -= 1; first = false; continue;
}
i -= (k + 2);
k = k + 2;
}
return sum1;
}


Step 2: Remove dead code

unsigned long long Luwistvis(int n)
{
unsigned long long sum1 = 0;
int k = 1;
bool first = true;

// Do first iteration outside the loop.
int i;
{
i = (pow(n, 2) / 4);
sum1 += func2(i);
i -= 1;
}

for(; i >= n - 1;)
{
sum1 += 2 * func2(i);
i -= (k + 2);
k = k + 2;
}
return sum1;
}


Step 3 re-factor to look nice

unsigned long long Luwistvis(int n)
{
int                k    = 1;
int                i    = (pow(n, 2) / 4);
unsigned long long sum1 = func2(i);

for(--i; i >= n - 1;)
{
sum1 += 2 * func2(i);
i    -= (k + 2);
k     = k + 2;
}
return sum1;
}


This function:

unsigned long long func2(int x)
{
unsigned long long sum = 0;
for (int i = 1; i < x; i++)
{
sum += (x - 1) / i;
}
return sum;
}


Is doing a huge loop.
I bet there is a formula that expresses that intent and can be done quicker than a loop. Work out what the formula is and use that instead.

-

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 <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>


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.

-