Obvious Competitive Coding things from non obvious angles …….
Any question as far as “competitive” programming is concerned, is the hybrid of an already well known algorithm followed by binding it with the logical stuff, presented in an absolutely new way. Somewhat like a chef mixing up different ingredients in different proportions at different times in order to make something new.
One thing which is worth noting is that in the short span of the time of coding round, it is impractical that one can think of a new concept so, if you lack in the algorithmic section then this article can not help you out in such a situation.
What is the article about ?
The efforts made here will not explain you any new concept. Work here aims to provide you insights of the problem with a new way, if not for all the problems but will surely for the some. Maybe you were able to solve the problem but wouldn’t give any attention to these points. Moreover the logical stuff behind the solution has been discussed.
Prerequisites
Anyone who has taken an active step in the competitive coding field and is quite comfortable with the basic programming along is good to go. Familiarity with sieve of Eratosthenes would also work just fine. As it is been taken as reference here.
A prejudgement on the article is not encouraged and you are suggested to go along with the article on its own pace.
Generating VS Filtering
The concepts here are explained with an associated problem. Starting with what the problem wants, given n numbers of the array. The value of max(x-y) is required to be calculated with both x and y belonging to the n elements of the array.
Brute force approach is the easy one, starting to iterate for all possible values for x from the set and then for each value of x, iterating for each value of y from the set and thus finding the maximum of all such values for the function (x-y). This takes n² computations to reach to the answer.
But a quite obvious answer to it can be obtained in n computations, as for the function x-y, answer will be maximum, when x be the maximum among the n values and simultaneously y being the minimum of the n terms. This problem is very easy but underlies a very important concept. Here notice that, we directly go with the state which will give us our answer and do not waste any iteration. Just going on with the answer and no useless thing is computed. Thus making our success ratio 1. The O(n) approach also requires some logic (that when you will get the required answer for the function, here x being the maximum and y be the minimum over n values) instead of just mere coding, which is what makes it competitive coding.
Continuing with examples of well known primes ………
Aim is to find from the numbers 2 to n, which are the primes.
Version -1:Going with the standard definition of any prime. Checking for each number x, if it is divided by any of the number between 2 to x-1. Doing this for all the numbers, x being from 2 to n. Now this is clearly an O(n²) operation in total. This just uses the way how a number is defined as prime.
This version does not use any sort of logic, just go on doing what the question demands. This is the brute force approach for the problem, just bare coding is done and nothing else.
Version -2: When any number is written as product of two numbers then one is less than equal to √n while other being greater than equal to it. So if their is one factor in the range 1 to √n then other will be in range √n to n and vice versa also. It is now which region to choose, no. of iterations required for the former one are quite less than that of the later one. This enables us to do the same task in O(√x) for each x and O(n √n) in total for all the numbers from 2 to n.
Now a change that must be noticed is, this version now requires more of the features of the concerned problem, primes here. Be it the fact of the ranges of factors, one between 1 to √n and other within √n to n. Overall complexity being O(n √n).
Version -3: Till this point we were filtering for the right value which divides the number, i.e. for each number checking for all possibilities, followed by choosing the one which is factor (divides completely) and if found any, then marking number as non prime, else is a prime. One very important thing to be noted here is that here our success ratio, is very less and as it takes many iterations to find the right value which divides the number or to conclude that no such value exists.
But what if we just hold back and think of the other way around, and use the factor to mark the numbers which it divides. Now what the iterations are doing is for each number in the range, now will mark its multiple as the non prime, till they are in the given range.
At each iteration here will definitely mark some numbers as non-prime. This is my favorite version also because transition from the previous version to this one uses the same knowledge about the problem, just the thing here is that we are removing all the useless computations in this problem reference. And the success rate is increased as no iteration is being waste.
Now with this step we have achieved a complexity of O(n log(n)) with no extra information about the behavior of the question from its previous version but just opting for a way to generate the answer instead of filtering them out from the all possibilities. Also no step should be taken in such a direction which will not give us answer in the later stages.
But the thing where it lacks is, even if we find one such factor for the number we can certainly say that the number is not prime. So here also some extra computations are done.
Version -4:Every effort from now is to use the previous done work and to work around the fact that we are calculating the no. of factors for any n , more than one (if there are) in spite that we can continue our work with one factor only(if there is any).
Using more information about the problem , if we are iterating for those numbers which have factors ,now this doesn’t do any useful work because it’s the repeated part as their own factor would already do this part in their iteration.So only iterating for those multiples which have no factors .i.e. are prime, so this version now uses concepts about the problem related stuff.
And also iterating for the numbers from 2 till √n is done because the maximum among the range is n. Using the same property of product, one being less than equal to √n and other being greater than that, we come to this conclusion.
Iteration for the multiples of i starts from i*i , because the multiples such as the 2*i , 3*i ,4*i …. (i-1)*i will be already marked when we are iterating for the values 2 , 3, 4 …. (i-1) respectively. And as the values require to do so 2, 3 , 4 .…(i-1) would already have been marked before the iteration for i so no worries here!
The complexity for this version now comes out to be O(n log(log(n))).
But here also the overall algorithm lacks at one place as the numbers which have more than one prime factor will be marked by each one of them and this can also be saved further !!!.
Version -5:For any number n, if is a composite one, then its marking will be done while we are iterating for the [ n/(lowest prime factor of n) ]. In this way for any number n either it will be not marked (i.e. the case of prime) or will be marked by the number [ n/(lowest prime factor of n) ] which is unique.
More of its implementation can be found here. Although this algorithm is quite complex but the way used is worth to be studied and can be used out at many other problems as well.
Quite interestingly at last, the whole thing could be just done in O(n) only !!!!.
Every time a more efficient version of any problem is seen, will be either doing the generation rather than filtration or will be using more of the features , properties of the problem and thus making the algorithm more and more confined to solve that problem only, than a similar general problem. Because the filtration would even work for similar problems as well because it just consider all of the possibilities rather than considering only the ones which would affect our answers depending on the problem. So if you want the generation process strong then firstly it will require more information about the problem.
So just hold on for a while and see how the code you just wrote works, does it go for filtering from all the possibilities of the answer. Or it does go just for that one thing which will constitute the final answer, the generation of answer.
Constraining the constraints:
This one is a very small concept but can prove very useful many times. Its just equivalent to chopping off that extra task which a question carries, other than the main crux .
A general idea for any problem setter to make sure that the constraints do not conclude anything about the logic behind that question, is to add holes. So this is done by adding loose constraints and now your task is to reduce it to the compact form and to adjust the things so that the useful information is not lost as well.
A typical example is, problem having n elements forming a array, limit of n be 10⁵ order. With each element of the array can be up to 10⁹. Also only comparison operator are involved within the elements then mapping of the numbers ranging from 1 to 10⁹ is done to 1 to 10⁵(order of n only !!). So now what was first up to 10⁹ now reduces to 10⁵. This task supplements the logic behind the question as this provides a restriction that you first need to solve this part then only you can get ahead in the problem. Quite a good example of it is this.
Some related problems which along with the algorithmic part requires you to first add an extra constraint on a variable involved in the question.
If you loved the article, show some ❤ Feel free to comment down any doubts.
About Me: I am a passionate coder, always willing to help. Chilling with my buddies and listening to quality songs is what I do in my free time.
