Max counters

[frek]

Task description:

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,
max counter − all counters are set to the maximum value of any counter.
A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
if A[K] = N + 1 then operation K is max counter.
For example, given integer N = 5 and array A such that:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)
The goal is to calculate the value of every counter after all operations.

Write a function:

vector<int> solution(int N, vector<int> &A);

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as a vector of integers.

For example, given:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000];
each element of array A is an integer within the range [1..N + 1].

I wrote two correct solutions. this one's time complexity is a little better and lesser than O(N^2):

 std::vector<int> solution(int N, std::vector<int>& A) 
{
	std::vector res(N, 0);
	bool setMax = false;
	int max_val{ 0 };
	std::size_t i{ 0 };

	while (i < A.size()) {
		for (; i < A.size(); ++i)
			if (A[i] >= 1 && A[i] <= N)
				max_val = std::max(++res[A[i] - 1], max_val);
			else if (A[i] == N + 1) {
				setMax = true;
					break;
			}

		if (setMax) {
			for (auto& r : res)
				r = max_val;
			setMax = false;
		}
		i++;
	}

	return res;
}

int main() {
	std::vector A{ 3, 4, 4, 6, 1, 4, 4 };
	auto res{ solution(5, A) };

	return 0;
}

Do you have an idea how to make it O(N), please?

[DizzyDon]

#include <iostream>
#include <vector>
using namespace std;

vector<int> solution(int N, vector<int> &A) {
    vector<int> v(N);
    int m = 0;
    for (int n: A)
        if (n == N + 1)
            for (int& x: v) x = m;
        else  if (++v[n - 1] > m)
            m = v[n - 1];
    return v;
}

int main() {
    vector<int> w {3, 4, 4, 6, 1, 4, 4};
    auto v = solution(5, w);
    for (int n: v) cout << n << ' ';
    cout << '\n';
}

[jonnin]

big - O ... what are you counting? That is often critical to the result you cook up.
If its number of times you touch the counters, it cannot get to O(N) because the touch every element command could come up every operation (nonsense but apparently legal). That gives N*N -- for every command, you touch every array element in that case.

So the question bounces... do you know a trick to set all the counters without touching them all?
But to what do you set the counters when it is a touch all command? I would think you have to track the max of all counters all the time; you certainly don't want to go looking for that since you can keep track of it as you increment various counters.

the best I can come up with would be a hokey thing where you track the operations on all the counters a different way. so for counter A[n] you may have incremented it a couple of times, nothing for a while, then set it to max (say its 100), then incremented it, then set it to max again (say 200 this time)... and so on. So you don't actually do any of the increments or sets, just track them in some kind of container of the inputs. Then you resolve the inputs in some way that avoids setting the ones that do not change. So for example if you have the full 100k elements and 10 commands, at the end, most of the elements are either zero or set to the max at some point. WHen you print the results, all the ones set to 0 or max you just print that value, never actually bothering to set the values and burn time. The others you resolve via the commands. How to arrange the code to do this is going to be tricky, and weird, but I believe it is possible. At the *very least* you can track elements that are never incremented and give them all the last 'set to max' known value (track this as you go)... zero if never set to max.

[lastchance]

#include <iostream>
#include <vector>
using namespace std;

vector<int> solution( int N, const vector<int> &A )                  // O( max( M, N ) )
{
   vector<int> counter( N, 0 );
   int mx = 0, lastmx = 0;
   for ( int a : A )                                                 // O(M)
   {
      if ( a == N + 1 ) 
      {
         lastmx = mx;
      }
      else
      {
         int am = a - 1;
         if ( counter[am] < lastmx ) counter[am] = lastmx + 1;
         else                        counter[am]++;
         if ( counter[am] > mx ) mx = counter[am];
      }
   }
   for ( int &c : counter ) if ( c < lastmx ) c = lastmx;           // O(N)
   return counter;
}

int main()
{
   vector<int> A = { 3, 4, 4, 6, 1, 4, 4 };
   for ( int e : solution( 5, A ) ) cout << e << ' ';
}

[DizzyDon]

Very nice! I didn't think it was possible.

[ne555]

> this one's time complexity is a little better and lesser than O(N^2)
no, your solution is O(N^2)

this is O(N^2)

for K in range(0, n):
   for L in range(0, n):
     //... 

this is also O(N^2)

for K in range(0, n):
   if K%2 = 0:
     for L in range(0, n):
       //... 

and this too is O(N^2)

for K in range(0, n):
   if rand() < 1/50:
     for L in range(0, n):
       //... 

> the touch every element command could come up every operation (nonsense but apparently legal).
you have no information available to say what input is nonsense or not.

[jonnin]

you have no information available to say what input is nonsense or not.


Unless I misread it, having all of them that command would just set them all to zero every iteration over and over. That seems like nonsense to me. Nothing would ever get incremented.

[ne555]

you read correctly, but what I mean is that you don't know what's a common or rare input