MODDI's blog

Olympiad Problem
By MODDI, history, 2 years ago, In English

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

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How we will create the segment tree, I don't follow

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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;
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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;
        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 :(

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Yes, I thought of that and used it in this code, but I didn't change the segment tree, instead, I used set, and it gets 15/20. Code https://pastebin.com/z34qDiqF How would you edit the segment tree, any ideas?

            → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here's the problem link: https://mendo.mk/Task.do?id=890, it's from the Macedonian Olympiad, there are quite a few problems over the years sadly English isn't available for almost all of them. Also, your solution passed all the test cases.

    → Reply