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:

_  
_ _ 
_____

And the answer is: 4.

Here is the code:

```
#include
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 > 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; ktemp)
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

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.

StackExchange Code Review Q#64551, answer score: 6