Блог пользователя MODDI

Автор MODDI, история, 2 года назад, По-английски

Given an array of size n, with elements between 1 and n find the maximum number of elements that occur exactly twice in any subarray. Constraints (1 <= n <= 100000)

6
1 3 1 3 2 1
Output: 2 (subarray 1-4, 1-5)

12
5 5 1 3 9 9 9 1 3 5 2 1
Output: 3 (subarray 1-9, 2-10, 2-11)

I have partial points, running O(n^2) solution shown below.

        int ans = 0;
	for(int i = 0; i < n; i++){
		map<int,int> cnt;
		int cans = 0;
		for(int j = i; j < n; j++){
			cnt[arr[j]]++;
			if(cnt[arr[j]] == 2)
				cans++;
			else if(cnt[arr[j]] == 3)
				cans--;
				
			ans = max(ans, cans);
		}
	}
	cout<<ans<<endl;

Any ideas how to solve the problem in O(n log n).

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Auto comment: topic has been updated by MODDI (previous revision, new revision, compare).

»
2 года назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

[When you try your best and misread the question. AND this is my first comment on CF. Kms :(]

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    How would you check occurrences between merged segments if they get sorted? For instance, if one segment in the merge was 4,1,4,3 and another segment was 3,1,4,3. After those individual segments are sorted, they would be 1,3,4,4 and 1,3,3,4, but as you merge, you can't see that 1,4,3,3,1,4 is a valid subarray which contains all 3 elements twice.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Should be doable with dp.

Fisrt notice we can always have an optimal segment starting with a value that contributes to the answer. The proof would be : if it s not true, cut the first value, we get same cost.

Now define dpi = maximum cost of a segment starting with i. Let's try to see where we value at pos i contributes. We have 2 cases , there is a value in that rage contributing at a larger index, or we continue with our lives at the next position availbile. Thus we should be able to take maximum dpi in a range for all value >= x. This is doable with segtrees.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

First, let's create some sort of a nxt[] array where nxt[i] = the smallest j such that j>i and a[j]==a[i](basically the index of the next occurrence of an element in the array). Then let's go through the elements in reverse order (just iterate from n to 1) then we will try to fix the current i as the starting of our subarray and nxt[i] as the ending of this subarray. Now we should find the answer of this segment magically and just maximize so that we find our final answer.

And here is one way this magic might work: We can observe that we should only care about the nearest the 3 occurrences of an element (the ones with smaller indices greater than i (our current fixed start) ). (because 4 or more occurrences will act as 3 occurrences).

Let's have this magical array toBeSummed[] which is initially filled with 0's. toBesummed[i] should have one of three values: -1 0 1 throughout the process.

If this index contains either the nearest (first j greater than i) or the fourth or more occurrence then toBeSummed[i] should be equal to 0.

If this index contains the second nearest occurrence of this number (the second smallest j greater than i) then toBeSummed[i] should be equal to 1.

If this index contains the third nearest occurrence of this number (the third smallest j greater than i) then toBeSummed[i] should be equal to -1.

Then the magical answer for a subarray should be the sum of the elements in toBesummed from i till nxt[i]. (Keep in mind that we update the vales of toBeSummed[i] as we move throughout the array (we just have to update 3 values at a time moving from i to i-1 and these values are nxt[i],nxt[nxt[i]] nxt[nxt[nxt[i]]] ) To support the range sum (from i to nxt[i]) and to support the updates (we change the values of toBeSummed) we can create a segment tree or some data structure that would support such operations. Please tell me if something is unclear!

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    By 'this index' you mean the current position i we are at in the for loop, right?

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    I have achieved 7/20 with this code, it fails on the first test case in my blog

    int ans = 0;
        for(int i = n - 1; 1; i >= 0; i--){
            int l = i, r = nxt[i];
            if(nxt[i] != -1)
                update(1, 0, n-1,nxt[i], 1);
            if(nxt[nxt[i]] != -1)
                update(1, 0, n-1, nxt[nxt[i]], -1);
            if(nxt[nxt[nxt[i]]] != -1)
                update(1, 0, n-1, nxt[nxt[nxt[i]]], 0);
            if(r == -1)
                r = n - 1;
            ans = max(ans, query(1, 0, n-1, l, r));
        }
        cout<<ans<<endl;
    
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      One thing is that if nxt[i] is -1 then simply skip this i. Another thing is to check if nxt[nxt[i]](third if) is equal to -1 in order to not get runtime error.

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Using the code below I got 14/20, for the last 6 cases it gave wrong answer.

        int ans = 0;
            for(int i = n -1; 1; i >= 0; i--){
                int l = i, r = nxt[i];
                if(nxt[i] == -1)
                    continue;
                update(1, 0, n-1,nxt[i], 1);
                if(nxt[nxt[i]] != -1)
                    update(1, 0, n-1, nxt[nxt[i]], -1);
                if(nxt[nxt[i]] != -1 && nxt[nxt[nxt[i]]] != -1)
                    update(1, 0, n-1, nxt[nxt[nxt[i]]], 0);
                if(nxt[nxt[i]] == -1){
                    int r = n - 1;
                    while(query(1, 0, n-1, r, r) == -1 || query(1, 0, n-1, r, r) == 0)
                    {
                        r--;
                        if(r < l)
                            break;
                    }
                    if(r >= l)
                    ans = max(ans, query(1, 0, n-1, l, r));
                        r--;
                    while(query(1, 0, n-1, r, r) == -1 || query(1, 0, n-1, r, r) == 0)
                    {
                        r--;
                        if(r < l)
                            break;
                    }
                    if(r >= l)
                        ans = max(ans, query(1, 0, n-1, l, r));
                }
                else{
                    int r = nxt[nxt[i]]-1;
                    while(query(1, 0, n-1, r, r) == -1 || query(1, 0, n-1, r, r) == 0)
                    {
                        r--;
                        if(r < l)
                            break;
                    }
                         
                    if(r >= l)
                        ans = max(ans, query(1, 0, n-1, l, r));
                    r--;
                    while(query(1, 0, n-1, r, r) == -1 || query(1, 0, n-1, r, r) == 0)
                    {
                        r--;
                        if(r < l)
                            break;
                    }
                    if(r >= l)
                        ans = max(ans, query(1, 0, n-1, l, r));
                }
            }
            cout<<ans<<endl;
        
        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Seems like we should make our segment tree to search for the best ending within the query and not only range sum from i to nxt[i] (editing the segment tree should work)... sorry for this :(

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Define $$$dp[r][l]$$$ (r > l) as the number of elements that occur exactly twice on subsegment [l, r]. Consider the transition from $$$dp[r][l]$$$ to $$$dp[r + 1][l]$$$: If there is exactly one $$$a[r + 1]$$$ on subsegment [l, r], then $$$dp[r + 1][l] = dp[r][l] + 1$$$. If there are exactly two $$$a[r + 1]$$$ on subsegment [l, r], then $$$dp[r + 1][l] = dp[r][l] - 1$$$. Otherwise, $$$dp[r + 1][l] = dp[r][l]$$$.

Let i, j, k (i < j < k < r + 1) be the last 3 occurrences of $$$a[r + 1]$$$ before (r + 1). From the transition above, $$$dp[r + 1][p] = dp[r][p] + 1$$$ if (j + 1 <= p <= k);

$$$dp[r + 1][p] = dp[r][p] - 1$$$ if (i + 1 <= p <= j);

and $$$dp[r + 1][p] = dp[r][p]$$$ otherwise.

Let's scan the array from left to right and maintain this DP in a 1D array: when we transition from index x to x + 1, we just need to increment/decrement some subsegments of the DP array (determined by $$$a[x + 1]$$$ and i, j, k, all of which can easily be maintained). After the modifications, we just need to query the maximum value of the whole DP array, and take the greatest result out of those for all x. All of this can be done quite easily with a segment tree. Although you need to be careful when there are less than 3 occurrences of $$$a[x + 1]$$$ before (x + 1).

Code

Also, can you please send the problem source?