Competitive Programming
The beginner’s guide for competitive programming part3
As discussed earlier, I am writing my approach for one problem now. So that the thought process can be identified and one can get idea how to find optimized approach to get AC.
Problem statement: we are required to find number of pairs (i,j) such that substring Si to Sj is having cnt(0)=cnt(1)*cnt(1). Obviously given string is having only 0s and 1s and cnt(X)= number of Xs in that string.
PREREQUISITES:
Prefix Sums, Sliding Window, brute-force, amortization.
PROBLEM:
Given a string SSS of length NNN consisting of characters ‘0’ and ‘1’ only. Find the number of non-empty substrings of SSS such that cnt0=cnt1∗cnt1cnt_0 = cnt_1*cnt_1cnt0=cnt1∗cnt1 where cntccnt_ccntc denote the frequency of character ccc in substring.
EXPLANATION
Let us assume cnt1=xcnt_1 = xcnt1=x for some substring. Then cnt0=x2cnt_0 = x²cnt0=x2, hence the length of substring should be cnt0+cnt1=x2+xcnt_0+cnt_1 = x²+xcnt0+cnt1=x2+x since we cannot have any other character in substring. Hence, we can surely reject all substrings whose length cannot be written as x2+xx²+xx2+x for some integer xxx.
Get Rushabh Daxini’s stories in your inbox
Join Medium for free to get updates from this writer.
Now, we can see, the maximum value of xxx such that x2+x≤Nx²+x \leq Nx2+x≤N is around N\sqrt{N}N. So, what we can do is to try all possible values of xxx and for each xxx, consider all substrings of SSS with length x2+xx²+xx2+x and out of these, count the number of substrings which contain exactly xxx occurrences of character ‘1’. We can see, that this substring shall contain exactly x2+x−x=x2x²+x-x = x²x2+x−x=x2 occurrences of character ‘0’ then, which satisfies our requirement.
For doing this, we have two ways, sliding window 218, and prefix-sums 149. In the sliding window, we can make a counter variable counting the number of occurrences of character ‘1’ in the current range. Both of these allows us to consider all substrings of a specific length in O(N)O(N)O(N) time.
It can be seen, that we need to consider N\sqrt{N}N
different lengths of substrings and considering substrings of each length takes O(N)O(N)O(N) time, we have solved this problem in O(N∗N)O(N*\sqrt{N})O(N∗N) time.
TIME COMPLEXITY
The time complexity is O(N∗N)O(N*\sqrt{N})O(N∗N) per test case.
Solution
