LEQEX - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Author: Sachin Yadav
Tester: Dishank Goel
Editorialist: Dishank Goel

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Bit-Manipulation

PROBLEM:

You are given N right-angled isosceles colored triangles numbered from 1 to N. For each triangle, the two equal sides have a length of 1 unit. The Color of i-th triangle is given by C_i.

To create a tower, we choose some consecutive (2 \times k)+1 triangles for any k \geq 0. We then pick some 2 \times k of them (these need not be consecutive), and form k pairs of triangles such that both triangles in pair have the same color. Also, each of the 2 \times k should be in exactly one pair. Then the two triangles in each pair are joined to form squares and these k squares are placed one upon other. The one remaining triangle is placed as a roof to the tower. This results in a tower of the height of k.

Find the maximum height of the tower that can be formed.

QUICK EXPLANATION:

In the required tower, parity of exactly 1 color is odd and rest even. We maintain the parity of subarray indexed from 0 to i and find if there is any array indexed j to i which satisfies the mentioned property.

EXPLANATION:

The main aim of the problem is to find the maximum length of subarray which has the frequency of all the colors even except for a single colour which has an odd frequency. The one with odd frequency will form the top of the tower.

Now, we somehow need to maintain the frequency of all colors for a subarray. We only need the parity i.e odd or even, so for each color, we can have 1 for odd frequency and 0 for even frequency.

Let us think of maintaining the parity of each colour as maintaining a number of 30 bits (since we have at max 30 different colours) where ith bit represents the parity of ith colour. Let’s call this number as parity_count for any subarray. For example,

If an array has C = {5, 4, 2, 2, 3, 2, 1, 3, 2, 7, 4, 9, 9, 9}, it’s parity_count is

1 0 0 0 1 0 1 0 1

So, we can store the frequency now. But we need to find the subarray that has maximum length having only single bit 1 and all the others 0 in parity_count. Because this will correspond to having a single colour odd number of times and all the rest even times.

Now, we maintain the parity of 0 to i-1 subarray and for ith element, we change the parity of C_ith bit in parity_count.

Since we are adding the C_ith colour at ith element, if the C_ith bit of parity_count for 0 to i-1 subarray was even, it will now become odd (So the bit changes from 0 to 1) and vice-versa. Consider the example,

C = {1,1,2,3}

And the 5th element is 4.

parity_count _{4} = 01100

parity_count _{5} = parity_count _{4} \oplus 00010 = 01110

At this step, we need to find a subarray indexed j to i which has maximum length and its parity_count only has a single bit set.

We know such subarray (indexed j to i) will have parity_count that has only single bit set. Let, parity_countj to i = m

Here, m can be 1000.. , 0100.. , 0010.. and so on.

If there is some j for the current i for which such m exists, the length of the subarray will be (i - j).

So we know the parity_count for j to i, it will be one of the possible values m. And we also know the parity_count for 0 to i. Now since taking xor is basically addition in modulo 2,

parity_count0 to j-1 \oplus parity_countj to i = parity_count0 to i

parity_count0 to j-1 \oplus m = parity_count0 to i

parity_count0 to j-1 = parity_count0 to i \oplus m

We can go over through every possible value of m and find out if we have encountered the value (parity_count0 to i \oplus m) previously for some j. If we have, the subarray length is (i-j).

For this, we maintain a Hash Map which stores the values of parity_count for 0 to i subarray as key and i as value.

We only add parity_count value in the Hash Map if it does not exist already because if it exists, the new index will be larger than before and the subarray length (i - j) will be lesser.

We can maintain the maximum length of all such subarrays.

Time Complexity : O(N \times C)

ALTERNATE EXPLANATION:

We can also maintain a Binary Search Tree to store the values of parity_count. It will have O(log(n)) search time instead of O(1) in Hash Map.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int UI;
unordered_map<int,unsigned int> least_idx;
UI req_set[30];
int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    for(int i=0; i<30; i++) 
        req_set[i]=(1U<<i);
    int T; cin>>T;
    while(T--)
    {
        least_idx.clear();
        least_idx[0]=-1;
        int N; cin>>N;
        int arr[N]; for(int i=0; i<N; i++){ cin>>arr[i];  arr[i]--; }
        UI answer=0;
        UI pre_xor=0;
        for(int i=0; i<N; i++)
        {
            pre_xor^=(1U<<arr[i]);
            if(least_idx.find(pre_xor)==least_idx.end())
                least_idx[pre_xor]=i;
            UI req_xor;
            for(int j=0; j<30; j++)
            {
                req_xor=pre_xor^req_set[j];
                if(least_idx.find(req_xor)!=least_idx.end())
                    answer=max(answer, i- least_idx[req_xor]);
            }
        }
        cout<<answer/2<<"\n";
    }
    return 0;
}
Tester's Solution 
for i in range(int(input())):
    n = int(input())
    c = list(map(int, input().split()))
    d = {}
    d[0] = -1
    curr_parity = 0
    ans = 0
    for i in range(n):
        curr_parity ^= 1 << (c[i]-1)
        for t in range(30):
            val = 1 << t
            if(val^curr_parity in d.keys()):
                ans = max(ans, i - d[val^curr_parity])
        if curr_parity not in d.keys():
            d[curr_parity] = i
    print(ans//2)
4 Likes