| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Hello everyone.
Reference: here
problem statement:
An array is good if all subarrays have atleast 1 element in them whose frequency is 1.
Good : 1,2,1
Good: 1,2,5,2,4,3,4
Bad: 1,2,3,1,2,3
O(N^2) solution is easy but can anyone share a better approach for this question.
Thank you.
Wrong Approach ! Thanks @ScoobyDoobyDoo
[3 2 4 2 4 3 2 4 2 4] Subarray of size 5 is good, size 4 is not
By good subarray I mean that it contains at least one unique element. The whole array needs to be good, so it has to contain an unique element. Find this element, now each subarray containing it is good, so we can just recursively repeat our algorithm for the elements to the left and to the right. This is pretty easy to do in $$$O(n \log n)$$$ complexity.
but won't be it quadratic if unique element is not in the middle like quick select worst case is O(n^2) if good pivot is not chosen
I think that it would not be possible to get guranteed time complexity of NlogN. And also in that reference link there is clearly said that expected time complexity so may be this could referred to time complex.. of randomized algorithms. Still I didn't have think too much about it so it can possible to get guranteed lower bound of NlogN.
So for time being this quick sort type solution would do better.
Yes, but there is quite well known trick to search simultaneously from the left border and the right border, so we make O(smaller part) so it will sum up to $$$O(n \log n)$$$.
Hi Anadi, We can maintain a min array and a right bound array (Lets say mn[n] , R[n]) While checking the ith index, we find its previous element with same value and next with same value (Lets say Prev[i] , Next[i] in O(nlog(n))) Then we update all elements in the range — [Prev[i], i] with max(R[j],Next[i] — 1) for each j in the range. In the min array we maintain the left most index with R[j] = i => mn[i] = j So, while checking the ith element, Prev[i] should be less than or equal to mn[i — 1] otherwise subarray — [mn[i — 1] , i] would not have any unique element. We can iteratively do the process in O(nlog(n)) time. I would love for you to check this approach.
I am not sure, probably don’t understand your approach. I cannot see why your approach wouldn’t fail on some easy test like $$$2$$$, $$$3$$$, $$$2$$$, $$$3$$$.
Not sure, but it seems a good implementation can guaranteed O(n logn) solution .
If there exist multiple unique elements, select one which is closest to middle index.
Otherwise, let suppose if there is only 1 unique element which is at leftmost index, then it is obvious that we get result just after one recursion as we can't find any unique element in next recursive call.
In general we can guaranteed, that if such unique element is find at kth index, recursion depth will not exceed k. so if k < logn, then complexity is obviously O(nlogn).
I know this seems quite abstract, but may be there is some mathematical proof of it.
Here's a counterexample where the recursion depth is $$$n/2$$$:
2 1 3 2 4 3 5 4 6 5 7 6 7
After each step, there's a unique value at the second index.
Expanding a little bit more on the following statement:
Yes, but there is quite well known trick to search simultaneously from the left border and the right border, so we make O(smaller part) so it will sum up to $$$O(n \log n)$$$.
Argument:
You start looking for a unique element from both ends simultaneously: $$$1, n, 2, n - 1, 3, n - 2...$$$.
Suppose you spot the unique element at position $$$i$$$. At this step you did $$$2 \cdot min(i, n - i)$$$ operations to check for each element if it is unique on this interval or not.
Then you run the algorithm recursively to the left and to the right. Notice that: $$$ min(i, n - i) \leq min(|left|, |right|)$$$ so basically the cost of each step is proportional to the smallest resulting interval.
Now to compute the complexity, suppose that every time you inspect an element you add a coin on it if it belongs to the minimal interval in that iteration. The number of check operations you will do in the end is proportional to the number of coins (in particular close to twice the number of coins).
Each time a coin is added on top of an element, it means the interval where this element was located was merged with a bigger interval, then its size increased in at least twice. So the number of coins $$$k$$$ must satisfy that $$$2^k \leq n$$$, then $$$k \leq \log_2 n$$$. Then in total the number of coins is $$$O(n \cdot \log n)$$$ which is indeed the complexity of this algorithm.
Notice that this analysis is pretty much the same as the technique of merging smaller to larger (usually on trees), just backwards.
Can somebody explain this part? Till now what I have understood (maybe wrong) is we are searching from the left border and right border i.e checking first i elements and last i elements, but how can we check element at position i is unique in complete array if we have only traversed first i and last i elements.
Can somebody please clear my doubt?
You can for instance precompute for each element the indices of its previous and next identical elements. Then to check that an element is unique in a subrange, it suffices to check that the precomputed indices fall outside of that subrange.
Not getting this!
"So the number of coins k must satisfy that 2^k ≤ n, then k ≤ log2n."
Shouldn't it be:
every time a coin is added, we have atleast 1 mirror element in larger interval
then k coins imply 2*k <= n, which is k <= n/2
Your reasoning is not wrong, but doesn't provide a good upper bound. You can do better.
Suppose an element has $$$k$$$ coins. It means it belonged $$$k$$$ times to the smallest side. The last time you added a coin to it the length of the interval containing it was $$$a_k$$$ and the length of the other side was $$$b_k \geq a_k$$$, but then it implies that in the previous step all $$$a_k + b_k$$$ elements were in one side, so when we add the previous coin the size of the interval was $$$a_{k -1} \geq a_k + b_k \geq 2\cdot a_k$$$. So we know the size of the intervals when we add a coin as we move backwards at least increased twice. This argument is enough to proof that the maximum number of coins added to an element is $$$O(\log_2 n)$$$
What's the constraint on Array elements? I mean what is the range of A[i]?
Whatever they may be but we can use coordinate compression and bring them in the range [1, n].
No that's not my point. I mean suppose N is in order of 10^5 and A[I] is in the range [1,100], then we can get some idea about how many elements are repeated and all.
gotcha.
might be useful: cs stackexchange answer
similar to one of the mentioned solutions.
Create an array of next occurrence of each element then using segment tree descent we can find first unique element in l-r in logn. Now recurrence will be T(n)=T(n-1)+O(logn) which will be O(nlogn)
How are you going to find the first unique element in logN?
Can there be any O(N) solutions?
Checking for the existence of a unique element itself would probably take $$$O(n \log n)$$$, or at least $$$\omega(n)$$$ time (deterministically), so if you want to avoid randomized solutions (including hash tables), the answer is probably no.
Yeah I'm having a problem similar to this, I tried the O(NlogN) way but it turns out to be TLE
link to question
Very well explained editorial
Thank you, got it AC ^_^
You might be finding the frequency each time (for checking if an element is unique), which would give TLE, since you do $$$O(n)$$$ work instead of $$$O(\min(i, n - i))$$$ work. As pointed out in one of the above comments, you'll need to maintain the indices of the previous equal element and the next equal element.
It might also be the case that you're not performing constant factor optimizations (or inadvertently doing too many unnecessary memory accesses — for instance, while using map).
:D thank you so much man, that really helped me.