# Forming output of lines based on input

I have homework, in which I get number of cases and then four numbers. Each number tells how many rows there are in each column

For example: 2 2 3 3 should be viewed like this:

    _ _
_ _ _ _
_ _ _ _


Wherever there are lines that can be joined in one, I have to do this, and write out minimum number of lines required to make that kind of sketch.

So the above would be:

  __
____
____


And the correct answer is 3.

A more complicated example:

3 1 2 1


Should be viewed as:

_
_   _
_ _ _ _


Joining the lines:

_
_ _
_____


Here is the code:

#include <iostream>
using namespace std;

int main()
{
unsigned long long int stPrimerov = 0;
cin >> stPrimerov;
unsigned long long int *totalRows = new unsigned long long int[stPrimerov];

for (unsigned long long int i = 0; i < stPrimerov; i++)
{
//totalRows[i] = 0;
unsigned long long int a, b, c, d;
cin >> a >> b >> c >> d;
/*a = rand() % 100000000;
b= rand() % 100000000;
c= rand() % 100000000;
d = rand() % 100000000;*/

unsigned long long int temp = 0;
unsigned long long int array[4] = { a, b, c, d };
for (int k = 0; k<4; k++)
{
if (array[k]>temp)
temp = array[k];
}

//totalRows[i] = 0;
/*int* aArray = new int[temp];
int* bArray = new int[temp];
int* cArray = new int[temp];
int* dArray = new int[temp];*/
unsigned long long int ttr = 0;
for (unsigned long long int l = 0; l< temp; l++)
{
int aa, bb, cc, dd;
if (l < a) aa = 1;
else aa = 0;
if (l < b) bb = 1;
else bb = 0;
if (l < c) cc = 1;
else cc = 0;
if (l < d)dd = 1;
else dd = 0;

if (aa == 0 && bb == 0 && cc == 0 && dd == 0) {continue; }
else if (aa == 0 && bb == 1 && cc == 0 && dd == 1) { ttr += 2; continue; }

else if (aa == 1 && bb == 0 && cc == 0 && dd == 1) { ttr += 2; continue; }
else if (aa == 1 && bb == 0 && cc == 1 && dd == 0) { ttr += 2; continue; }
else if (aa == 1 && bb == 0 && cc == 1 && dd == 1) { ttr += 2; continue; }

else if (aa == 1 && bb == 1 && cc == 0 && dd == 1) { ttr += 2; continue; }
else{ ttr+= 1; continue; }

}
totalRows[i] = ttr;

}

for (unsigned long long int a = 0; a < stPrimerov; a++)printf("%d\n",totalRows[a]);
//system("pause");
return 0;
}


I have to make it faster.

Example input:

3
2 1 6 4
0 1 1 1
3 9 8 11


Result:

7
1
12


Number of cases can be up to 104 and number of rows up to 108.

• You are using printf without including stdio.h It is also expecting an int but receives long long unsigned int. Use %llu instead of %d. Oct 2 '14 at 17:10
• Can you provide more explanation of your expected results? What is the result of your first example 2 2 3 3, is it 3? Why is 2 1 6 4 7? Why isn't the least amount of lines always the highest amount of rows?
– Carl
Oct 2 '14 at 18:21
• @carl I have added more examples, I hope that clarifies. In the case of 2 1 6 4 there is one common line on the bottom, then one unique line for the left most column because it doesn't connect with the third column due to second column being smaller. Then 3 shared lines between the left most two columns then 2 unique lines for the third column: 1 + 1 + 3 + 2 = 7. Oct 2 '14 at 22:33
• @EmilyL. Thanks. One more thing, the joining of 3 1 2 1 doesn't make sense to me. Why is there a second line on the first row? It seems to have appeared from nowhere.
– Carl
Oct 3 '14 at 0:07
• @carl fixed. I was too fast making it up. Oct 3 '14 at 6:33

## Cause of your performance issue

As this is homework, I don't want to give away the whole solution but I'll tell you where the problem is and if you need more help, just comment and I'll see what I can do.

You can have up to $10^4$ test cases and the number of rows can go up to $10^8$. You're better off assuming your examiner will actually use such a test case. More than likely they will.

Looking at your code you have two for-loops.

This one:

for (unsigned long long int i = 0; i < stPrimerov; i++)

and this one:

for (unsigned long long int l = 0; l< temp; l++)

where temp is $\max_{\forall i}(row_i)$. So the worst case is when: temp = 10E8, and then the inner loop is executed stPrimerov=10E4 times, resulting in $10^{12}$ iterations through the inner loop. Now that's a lot.

Instead of this for (unsigned long long int l = 0; l< temp; l++) you must realize that there are only 4 interesting points that you need to look at, and those are l=array[x]. So by looking at the values in the array and how they differ, you will be able to determine how many lines are necessary without checking each row. So if you can replace the inner for loop with some smart checking, you can reduce from $10^{12}$ to $10^{4}$ loop iterations which should make even the hardest test cases run in under half a second. :)

Try to think of it for yourself for a while and come back later if you're still stuck and look at the hints below.

## Hint #2

Let's consider an easier problem. Let the input be the same, but all columns are either 0 or k high. Like this:


3
0 3 3 0
0 4 0 4
9 0 9 9
Result :

3  (3*1)
8  (4*2)
18 (9*2)
Now this is easy, just count the number of streaks of non zero columns. There is one streak that is two wide in the first case. There are two streaks that are one column wide in the second set. And there are two streaks in the last case, one that is one column wide and one that is two columns wide. Then multiply the number of streaks by the height of the columns.

## Hint #3

Given four columns of (possibly) unique heights, the rows can be split into at most 4 sections where each column in the section is either zero or equally tall as the other columns. With these two hints you should be able to figure out how to calculate the answer without checking every row in the inner loop.

I haven't tested this, but here's an idea that should help with performance: instead of comparing aa, bb, ..., variables using if-else, convert to bits, and use a switch, something like this:

for (unsigned long long int l = 0; l< temp; l++)
{
int bits = getBits(l, 4, array);

switch (bits) {
case 0:
break;
case 5: // 0b0101
case 9: // 0b1001
case 10: // 0b1010
case 11: // 0b1011
case 13: // 0b1101
ttr += 2;
break;
default:
ttr++;
}
}


Where getBits can be a function like this:

int getBits(int num, int len, unsigned long long int limits[])
{
int bits = 0;
for (int i = 0; i < len; ++i)
{
bits <<= 1;
if (num < limits[i])
{
++bits;
}
}
return bits;
}


### Naming

The variable names are awful. It's hard to tell what this code is supposed to do.

### Replace long type names with shorter aliases

This type name is too long: unsigned long long int

Give it a shorter name using typedef:

typedef unsigned long long int longint;


This is more than just for convenience. It's good encapsulation: the real type of longint will be hidden in your implementation, if you realize you need to change it later, you can change in place, which is less error-prone.

### Don't using namespace std;

You should not do this:

using namespace std;


The recommended practice is to use the std:: prefix, for example std::cin.

• Have you tested this? I don't believe that is the cause of OP's performance issue. Rather the inner most for-loop should be replaced with a smarter solution. I haven't had time to look really close yet but this should be an $\mathcal{O}(n)$ problem but OP is using (what looks like) a $\mathcal{O}(n^2)$ algorithm... It's an interesting problem. I'll have a look-see later :) Oct 2 '14 at 17:19
• I don't have a c++ compiler with me now, so I couldn't test. I'll mention that in the post. Oct 2 '14 at 17:21
• I find this useful: ideone.com :) Oct 2 '14 at 17:22
• Don't do this:

unsigned long long int *totalRows = new unsigned long long int[stPrimerov];


In most cases, it's not necessary to perform dynamic memory allocation yourself in C++. Another major problem with this is that you don't use delete anywhere, giving you a memory leak. C++ is not a garbage-collected language, so you must always do this on your own.

delete [] totalRows;


Instead, use an std::vector or another storage container:

std::vector<unsigned long long int> totalRows(stPrimerov);


As @janos has mentioned, you should use a typedef for that integer type. You may also consider something from the <cstdint> library.

(Even if you cannot use storage containers in homework, it may help you in the future.)

• This isn't very readable as a single line:

for (unsigned long long int a = 0; a < stPrimerov; a++)printf("%d\n",totalRows[a]);


It may take others some time to separate the loop statement and body. Instead, have the body on its own line and with curly braces.

for (unsigned long long int a = 0; a < stPrimerov; a++)
{
printf("%d\n",totalRows[a]);
}


While it is okay to put certain statements on a single line, it's not good to do it every time you'd like. Keep in mind that code is meant to be read vertically, not horizontally. Try to keep each line as short, but relevant, as possible.

First thing you must realize that you don't want to make the code faster. You want to make it right.

• Factor out the actual solution into a function (doPrimer for example). main should look along the lines of

int main()
{
unsigned long long int stPrimerov = 0;
cin >> stPrimerov;
while (stPrimerov > 0) {
unsigned long long columns[4];
auto result = doPrimer(rows);
std::cout << result;
--stPrimerov;
}
}


See that a totalRows array automagically disappears.

• A for (int k = 0; k<4; k++) loop calculates a maximal value in the array. Must be also factored out into a function. Meanwhile, you don't have to calculate the maximum at all: break the essential loop when a height (l in your code) exceeds all columns (that is all your aa to dd become zeroes. BTW you testing this condition anyway).

• Names like a and aa signal that the role of those variables is not understood. I recommend keeping column height in a column[] array. And you don't need all those aa and friends at all:

Notice that number of strokes in the row is in fact a number of runs of high enough columns. Appending a sentinel column of height 0 gives a number of strokes equals to high enough to not high enough height transitions. In pseudocode (sentinel already appended):

row_strokes(heights, columns, height)
for (i = 0; i < columns - 1; i++)
if (heights[i] > height && heights[i] <= height)
++strokes;
return strokes

doPrimer(heights, columns)
while ((strokes = row_strokes(heights, columns, height) > 0)
total_strokes += strokes
++height