问题描述:

I have wanted to try some challenges on Codility and started from beginning. All assignments were relatively easy up to the one called MaxCounters. I do not believe that this one is especially hard although it is the first one marked as not painless.

I have read the task and started coding in C# language:

`public static int[] maxPart(int N, int[] A){`

int[] counters = new int[N];

for(int i = 0; i < A.Length; i++){

for(int j = 0; j < counters.Length; j++){

if(A[i] == counters[j] && (counters[j] >= 1 && counters[j] <= N )){

counters [j] = counters [j] + 1;

}

if(A[i] == N + 1 ){

int tmpMax = counters.Max ();

for(int h = 0; h < counters.Length; h++){

counters [h] = tmpMax;

}

}

}

}

return counters;

}

Having 3 loops of course makes it really slow, but lets leave it for later. My concern is how I understood this like this and all the other people see it like on this question here.

From the assignment's description.

it has 2 actions:

- increase(X) counter X is increased by 1,
- max counter all counters are set to the maximum value of any
counter.

which occur under conditions:

- 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.

Both conditions are stated in the code above. Obviusly it is wrong but I am confused, and I do not know how could I understand it differently.

Why is this code wrong, what am I missing from task description?

One of the top rated answers looks like this:

`public int[] solution(int N, int[] A) {`

int[] result = new int[N];

int maximum = 0;

int resetLimit = 0;

for (int K = 0; K < A.Length; K++)

{

if (A[K] < 1 || A[K] > N + 1)

throw new InvalidOperationException();

if (A[K] >= 1 && A[K] <= N)

{

if (result[A[K] - 1] < resetLimit) {

result[A[K] - 1] = resetLimit + 1;

} else {

result[A[K] - 1]++;

}

if (result[A[K] - 1] > maximum)

{

maximum = result[A[K] - 1];

}

}

else

{

// inefficiency here

//for (int i = 0; i < result.Length; i++)

// result[i] = maximum;

resetLimit = maximum;

}

}

for (int i = 0; i < result.Length; i++)

result[i] = Math.max(resetLimit, result[i]);

return result;

}

This code results with 100% on Codility.

Question:

I would like to know how the author knew from the task to use `result[A[K] - 1]`

? What would `resetLimit`

represent?

Maybe I completely misunderstood the question due to my English I am not sure. I just can not go over it.

EDIT:

Based on my code provided, how did I misunderstood the assignment? Generally I am asking for explanation of the problem. Whether to explain what needs to be done, or take the code as correct result and provide and explanation why is this done this way?

In my opinion you somehow mixed the index of the counter (values in `A`

) and the value of the counter (values in `counter`

). So there is no magic in using `A[i]-1`

- it is the value `X`

from the problem description (adjusted to 0-based index).

My naive approach would be, the way I understood the problem (I hope it makes clear, what your code is doing wrong):

```
public static int[] maxPart(int N, int[] A){
int[] counters = new int[N];
for(int i = 0; i < A.Length; i++){
int X=A[i];
if(X>=1 && X<=N){ // this encodes increment(X), with X=A[i]
counters [X-1] = counters [X-1] + 1; //-1, because our index is 0-based
}
if(X == N + 1 ){// this encodes setting all counters to the max value
int tmpMax = counters.Max ();
for(int h = 0; h < counters.Length; h++){
counters [h] = tmpMax;
}
}
}
}
return counters;
}
```

Clearly, this would be too slow as the complexity is`O(n^2)`

with `n=10^5`

number of operations (length of the array `A`

), in the case of the following operation sequence:

```
max counter, max counter, max counter, ....
```

The top rated solution solves the problem in a lazy manner and does not update all values explicitly every time a `max counter`

operation is encountered, but just remembers which minimal value all counters must have after this operation in `resetLimit`

. Thus, every time he must increment a counter, he looks up whether its value must be updated due to former `max counter`

operations and makes up for all `max counter`

operation he didn't execute on this counter

```
if(result[A[K] - 1] < resetLimit) {
result[A[K] - 1] = resetLimit + 1;
}
```

His solution runs in `O(n)`

and is fast enough.

您可能感兴趣的文章：

- How to Check the empty text fields before uploading image or video in android?
- javascript - drop draggable div just after confirm dialog message
- oracle adf - Two Criteria in on jsf page
- Jena ARQ query execution extension
- php - No error shown when updating and deleting
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**-
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?
- git svn - git svn fetch does not fetch a Subversion commit message modified after initial clone
- java me - Why I am getting the bad length exception when I am running this application?
- java - How to get string.format to complain at compile time
- ruby on rails - Trigger observer of parent class on change
- python - Issue with URL pattern in Django with webmonkey tutorial