What is the approach to solve CLONEME for 30 and 100 pts?
1 Like
I can tell you a 30 point method, though it will time out for 100 points. It is very cheeky but it works for 30 points.
What I did was create a BIT for storing cumulative sum of elements of array a in mod 3.
i.e. if the array is {4,3,5,3,2}, then create a BIT for array “mod”->{4%3,3%3,5%3,3%3,2%3} now we for each query we calculate the sum from a to b and from c to d, if the sums differs less than 3, we sort them and check if they are same else we print “NO”. It runs pretty good for first 2 tasks but time outs for third.
2 Likes
Nice Approach ! 
You can use persistent segment tree for each sorted subarray [1…i].
To get persistent segment tree of [i..j] = segment tree[i...j] - segment tree[1...i-1]
for comparison use, two prime hashing technique.
first I am dividing subarray into two parts and compare both subarray.
if (subarray_length == 1)
so answer is 'YES'
else if( both subarray are having different hash value means both of them)
having atleast one different element in each subarray so ans = "NO"
else if (one of them having different hash)
one having different hash value, I will check further after dividing that subarray into two parts.
Happy Coding
2 Likes
Here is an approach that should work for 30 pts:
- Have 2 arrays of to keep track of frequency of elements in both range a to b and c to d.
- Count the difference between the number of elements, if it is greater than 2, then answer is NO, if difference is 0, answer is YES.
- If difference is only 1, then we see if there is an element between the mismatched elements, if yes, then answer is NO else answer is YES.
You can also ignore the overlapping parts, to further optimize the solution.
I used a cheeky approach which is not 100% correct but is correct with very high chance. I created 3 arrays: the first A_1 is prefix sum of each element, 2nd A_2 one is prefix sum of square and the third A_3 is the prefix sum 6-th power. Then for each query, I assume they are different in at most one place and use A_1 and A_2 solve for the different elements and use A_3 to check if they are really different in one place.
2 Likes
can anyone explain me why im getting TLE…
link to my code https://www.codechef.com/viewsolution/14046795
I don’t this the checking for difference of 1 element is efficient enough. Can you please share the link to your code(in case it fetched you 100 points)?
To find if the 2 subarrays are equal we can use hashing.
One important thing is to notice is that if 2 subarrays are same or differ by one element then all the other elements must occur even number of times. So you can do a XOR of the ranges. Now there are ways to find the 2 elements which occur odd number of times Link. Now we can get 2 numbers and we can check if these are the 2 numbers by cross-checking with hash and xor.
2 Likes
How did you check if there is a mismatch of one element or not?
1 Like
It is just for 30 pts. I got WA, I’m pretty sure it was an issue with implementation and not logic. Didn’t have enough time in the end to debug it.
To check if there’s only one mismatch:
Assume there’s one mismatch. To get those mismatched elements (a,b), [a in (l1,r1), b in (l2,r2)]
sumofsq(l1 to r1) - sumofsq(l2 to r2) = asq - bsq
sum(l1 to r1) - sum(l2 to r2) = a-b
So you get a, b from here (You have a+b and a-b) . They have to be integers if it’s a single mismatch.
First, to compare the two subarrays (l1,r1) and (l2,r2), we hash them before hand.
So, one such way is, h(l to r) = sigma(ai ^ k)%bigprime l <= i <=r and choose a k that you want, say 45, and prime 1e9+7. Low probability of collision because 1e5 queries. h(l1 to r1) = h(l2 to r2) => Those subarrays are same when sorted.
If the hashes are same, you’re done. Otherwise,
Let H1 = h(l1,r1), H2 = h(l2,r2)
Now to check if there is only one mismatch, check if (H1-a^k)%P = (H2-b^k)%P. If it is not, then there are more mismatches.
If they’re equal, then there is only one mismatch and you know a,b.
Now your job is to check if position of ‘a’ in l1 to r1 is same as ‘b’ in ‘l2’ to ‘r2’. You can do this offline using seg/fenwick tree, by sorting the queries with respect to the values for whose position is to be found. And then insert them one by one and you get the position one by one with a sum query from l to r.
O(nlogn + qlognq)
11 Likes
This is just the brute force approach. Are you sure you know how to analyse time complexity of a program? Here b-a = c-d can be equal to N for every query and your code easily times out as the number of operations is QNlogN.
I’ll tell you the overkill way to do it 
I used persistent segment trees to get (sum, product mod, xor) of first k numbers in a range if the range were to be sorted. Basically, I was using this triplet (sum, product mod, xor) as a unique hash for n numbers, having this hash, I binary searched index in the query range(as both ranges in a query have equal length) and at each mid I compared left part hash (1 to mid - 1) and right part hash(mid + 1 to b - a + 1) of both ranges, if comparison is not equal mismatch is incremented and search continues till mismatch <= 1.
I modified the famous Spoj’s MKTHNUM problem’s persistent segment tree solution to get the kth number and this hash triplet as well, as sum, product and xor are associative and commutative, I can get hash for subrange l to r in query range by performing subtraction, inverse multiplication and xor each on query®, query(l-1)
Complexity was O((N + Q)logNlogNlogN) with a very high constant, but by lowering the mod value and precalculating the modular inverses, I got it down to O((N + Q)logNlogN) which barely passed after a lot of optimisation
3 Likes
My solution for 30pts:
- Mapping pair<number, count> to a value of [1…n].
- Use Mo’s algorithm to sort all query
- Compress n (max 10^5) value to array 1564. Each value of mapping (1), we can use as one bit.
- Each query just compare those bit
My solution
@bansal1232 taking modulus is just a way of mapping the number, I mean you could take mod with any prime number. for example, 1 is mapped to 1, 2 is mapped to 2 3 is mapped to 0 and so on. And when we sum the range if the sums are not closed than 3 we can simply discard them.
I actually have similar solution with you mate, except I used hashing (P^i * a[i]) to check for similarity, same with persistent tree. Used two primes for hashing to lessen clash, see my solution
A very intuitive and nice solution is as follow:
First let us make a prefix sum , sum of squares, sum of 3/2 powers and denote them by sum,sum2,sum3/2 respectively. Now when these three are equal for a given l1,r1,l2,r2 i.e (sum[r1]-sum[l1-1]==sum[r2]-sum[l2-1] )&&(sum2[r1]-sum2[l1-1]==sum2[r2]-sum2[l2-1] )&&(sum3/2[r1]-sum3/2[l1-1]==sum3/2[r2]-sum3/2[l2-1] ) then ans is YES.
Else, Let us assume EXACTLY one mismatch.Now find the values of the mismatched elements(let them be a in [l1,r1] and b in [l2,r2]).These can be calculated using the sum and sum of square equations.Now if our assumption is corrct(of exactly one mismatched element) then a and b must come out to be integers and also they must satisfy the sum3/2 equation.Also they must share atleast one common index in both the ranges(Think why!).This can be checked using any suitable method.If these conditions are ture ans is YES.Else ans is NO.
1 Like
But how could you able to avoid collision? And what will happen if I assume any other number rather than 3?