Originally posted on my blog.
It was a good contest. 5 not so difficult, but at the same time not so easy to get full score kind of problems were there. After successfully completing the contest, lets have a quick small discussion on all 5 problems.
Quick Explanation of problem: Xenny is in exam and has n questions with different marks in paper. He needs 1 unit time to solve a questions and has k unit time to finish the test. He wants to score maximum marks and you are going to find this score – maximum score that he can get.
Solution: Since Xenny needs same amount of time for each question, this is not a knapsack problem. There are n questions and we want to choose k so as to have maximum marks, we can do this by greedy approach i.e. choose k questions with maximum marks. Hence simple sorting solves the problem. Wait, there is a catch. The time limit. Time limit was such that O(nlogn) solution will not get full score. Hence sort() in STL or qsort() didn’t solve the problem completely. Here you need a faster sorting method. And the method is Counting Sort which sorts in O(n). Its a simple method for sorting which stores the elements in different way. It is a kind of hashing. It works by counting the number of elements having distinct key values. Also you can have look for more explanation of this technique here.
Quick Explanation of problem: Given a number n, you have to find the composite number greater than that number.
Solution: This is again a simple problem. We will assume that we have list of prime number and checking the number to be prime can be done in O(1). We can see, if the n is prime, n+1 will definitely be composite (except for n=2). If n is not prime, then we are not sure about composite-ness (or prime-ness) of n+1, hence in that case we will check n+1 if it is prime. If it is prime, then n+2 has to be composite. Else n+1 was our answer. The only cases remain un-discussed are n = 0, 1 or 2 which we can easily hard code. Now finding all primes in given range! Catch!! Time limit!!!. Since the range of n was till 10^5, the O(n^2) solution would not have worked because at the end, we want an array of boolean-s in which ith index will tell if i is prime number or not. The best method for this situation was Sieve of Eratosthenes. This method is the method we learnt in third standard. Also you can have look for more explanation of this technique here.
Quick Explanation of problem: Given a and b, you have to find the prime factors of a raised to b, a^b.
Solution: The first step is the most important here. If you literally start with finding a^b and then its prime factorization, you are taking wrong step and your solution is not going to work since a and b are quite large numbers it will easily overflow the range of long long int too. If you give a little thought before solving, you will get that you just need to find factorization of a and then just multiply the powers of all prime numbers with b and output them. Remember the rule learnt in school: (a^m)^n = a^(m*n). The task of finding prime factorization of a is quite easy.
Quick Explanation of problem: Given a graph, check if you can visit all edges exactly once.
Solution: Given a thought, you will know that this task is only possible if we have # of entrance = # of exit to any node (except for start node and end node) i.e. in-degree should be equal to out-degree. It is little harder for me to explain this, so you have to check this yourself for some examples (but it is true, really). Since the given graph was un-directed, our task is even simpler. Just calculate degrees of all junctions if they are even or odd and check if # of junctions with odd-degree are 0 or 2. If # of junctions with odd degree = 0 or 2, possible; else Not-possible. This concept is Eulerian Path. Read this for detail explanation.
Quick Explanation of problem: Find the maximum number of pairs you can match without crossing the other pairs.
Solution: Again, in this problem too, you have to think hard first and then solve.This is a variant of standard problem called Longest Increasing Sub-sequence. I believe, you can map this problem with Longest Increasing Sub-sequence after reading this.
Solving the Longest Increasing Sub-sequence The dynamic programming solution will get partial points because it has a time complexity of O(n^2). But the same problem also has a O(nlogn) solution.
We hope you would have enjoyed this contest. The motto behind these contests is always Learning and we hope you got something to learn. Any feedback, suggestions about the contest or this blog are always welcome.
Author
{"8ef9177": "/users/pagelets/trending_card/?sensual=True"}