Questions Tagged With cdfi2016https://discuss.codechef.com/tags/cdfi2016/?type=rssquestions tagged <span class="tag">cdfi2016</span>enWed, 09 Nov 2016 18:37:30 +0530CDFI3 - Editorialhttps://discuss.codechef.com/questions/87248/cdfi3-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/CDFI2016/problems/CDFI3">Contest</a></p>
<h1>Difficulty</h1>
<p>MEDIUM</p>
<h1>Prerequisites</h1>
<p>Check if a point lies inside a triangle</p>
<h1>Quick Explination</h1>
<p>Find areas of the three triangles formed by the given points and the origin and check if their sum matches the area of outer triangle.</p>
<h1>Explination</h1>
<p>To check if the origin lies inside the triangle formed by the given coordinates, we need to find the area of the traingles formed by the three triangles i.e. the triangles formed by any two of the given triangles and the origin and check if the sum of these three areas equals the area of triangle formed by the given three coordinates.You can refer to <a href="http://www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/">Check whether a given point lies inside a triangle or not</a>.</p>
<p>There is only a single corner condition in the problem when all the three coordinates are on the origin.
In this case although the three points do not form a triangle but according to the problem statement the answer for this condition will be YES.
Given below is the solution to the problem in C++</p>
<pre><code>
#include<bits stdc++.h="">
#include<iostream>
using namespace std;
double areac(int x1,int y1,int x2,int y2,int x3,int y3)
{
return fabs((x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))/2.0);
}
bool inside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)
{
double A = areac (x1, y1, x2, y2, x3, y3);
/* Calculate area of triangle PBC */
double A1 = areac (x, y, x2, y2, x3, y3);
/* Calculate area of triangle PAC */
double A2 = areac (x1, y1, x, y, x3, y3);
/* Calculate area of triangle PAB */
double A3 = areac (x1, y1, x2, y2, x, y);
return (A == A1 + A2 + A3);
}
int main()
{
int x1,y1,x2,y2,x3,y3;
cin>>x1>>y1;
cin>>x2>>y2;
cin>>x3>>y3;
double m1 = (((double)(y2 - y1))/((double)(x2 - x1)));
double m2 = (((double)(y3 - y1))/((double)(x3 - x1)));
double m3 = (((double)(y3 - y2))/((double)(x3 - x2)));
if(m1 != m2)
{
bool ans = inside(x1,y1,x2,y2,x3,y3,0,0);
if(ans==true)
cout<<"Yes";
else
cout<<"No";
}
else
cout<<"Invalid Input";
return 0;
}
</code>
</pre>intayushWed, 09 Nov 2016 18:37:30 +0530https://discuss.codechef.com/questions/87248/cdfi3-editorialcdfi3cdfi2016mediumtriangleCDFI4 - Editorialhttps://discuss.codechef.com/questions/85967/cdfi4-editorial<h1>PROBLEM LINK</h1>
<p><a href="https://www.codechef.com/CDFI2016/problems/CDFI4">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>MEDIUM</p>
<h1>PREREQUISITES</h1>
<p>Prime Factorization, <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve</a></p>
<h1>PROBLEM</h1>
<p>Find the number of integers in the given range which have prime number of divisors.</p>
<h1>QUICK EXPLANATION</h1>
<p>Although L and R can be as high as 10^12 but R-L is <= 10^6, this allows us to iterate through the complete range and count the number of divisors of each number in the range.</p>
<h1>EXPLANATION</h1>
<p><strong>Approach 1:</strong></p>
<p>If a number N is divisible by D then either it has 2 factors(D and N/D) or it is square of D. Another thing to note is that if a number has 2 divisors x and y such that x < y, then x < sqrt(N) and y > sqrt(N). Using these 2 facts we can iterate through all the numbers in range [1, sqrt(R)] and count the number of factors for each of the number.
Working commented solution follows:</p>
<pre><code>
bool isPrime[10000];
void init() {
// Since range is very small so not used Sieve
for (int i = 2; i < sizeof(isPrime); ++i) {
int j = 2;
for (; j * j <= i; ++j) {
if (i % j == 0) {
break;
}
}
if (j * j > i)
isPrime[i] = true;
}
}
main() {
init();
int testCases, divisors[1000005];
scanf("%d", &testCases);
while(testCases--) {
long long L, R;
scanf("%lld%lld", &L, &R);
for(long long i=L; i<=R; i++)
divisors[i-L] = 0; //Initialize divisors of all numbers to 0
for(long long i=1; i*i <= R; i++) { // Iterate through 1 to sqrt(R)
long long square = i*i; // j starts with first number in range [L, R] which is multiple of i
for(long long j=( (L-1) / i + 1) * i; j <= R; j += i) { // Factors under consideration are i and j / i
if (j < square) continue; // Already counted because of 2 in else condition below
if( square == j ) // Just 1 factor
divisors[j-L] += 1;
else divisors[j-L] += 2; // Counting factors i and j / i
}
}
int ans = 0;
for(long long i = L; i <= R; i++)
if(isPrime[divisors[i-L]])
ans++;
printf("%d\n",ans);
}
}
</code>
</pre>
<p><strong>Approach 2:</strong></p>
<p>This approach is taken by more coders.</p>
<p>This is based on prime factorization of a number and then counting the total number of divisors. </p>
<p>Lets take an example:</p>
<p>Consider prime factors breakdown of 18 (2^1 * 3^2) </p>
<p>so total number of factors are (1+1) * (2 + 1) = 6 [Factors: 1, 2, 3, 6, 9, 18]. </p>
<p>Similarly if a number is p1^x1 * p2^x2 * p3^x3 * … then total number of factors is (x1+1) * (x2+1) * (x3+1) * … </p>
<p>Now if we generate all primes <= 10^6 using sieve and later use them to find out how many times it goes into each number in the given range, we know the number of divisors composed of primes <= 10^6. </p>
<p>We may have missed 1 prime number > 10^6 which might have fallen in the range as range goes as high as 10^12. But we are sure that there is only 1 such prime! So if we detect this case we can simply multiply our number of factors calculated so far by (1+1). </p>intayushThu, 13 Oct 2016 21:54:18 +0530https://discuss.codechef.com/questions/85967/cdfi4-editorialcdfi2016mediumsievecdfi4CDFI2 - Editorialhttps://discuss.codechef.com/questions/85968/cdfi2-editorial<h1>PROBLEM LINK</h1>
<p><a href="https://www.codechef.com/CDFI2016/problems/CDFI2">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>EASY</p>
<h1>PREREQUISITES</h1>
<p><a href="http://en.wikipedia.org/wiki/Greedy_algorithm">Greedy Algorithms</a></p>
<h1>PROBLEM</h1>
<p>You need to find the representation of a given integer <strong>N</strong> as a sum of powers of two up to <strong>2<sup>11</sup></strong> with the smallest number of summands (repetitions in representation are allowed).</p>
<h1>QUICK EXPLANATION</h1>
<p>The problem can be solved by greedy algorithm: at each step we should take the largest possible menu that we can. To prove this noticed that if we order two equal menus, say 4 and 4, then we can order instead one menu of cost 8. In this problem you can implement this approach in any way you like but the easiest and fastest way gives the following pseudo-code:</p>
<pre><code>
res = 0
for i = 11 to 0
res = res + N div 2i
N = N mod 2i
</code>
</pre>
<h1>EXPLANATION</h1>
<p>At first we reveal the answer and then will prove it in detail. Write <strong>N</strong> as <strong>Q * 2048 + R</strong>, where <strong>Q</strong> and <strong>R</strong> are non-negative integers and <strong>R < 2048</strong>. Then the answer is <strong>Q + bitCount(R)</strong>, where <strong>bitCount(X)</strong> is the number of ones in binary representation of <strong>X</strong>. If <strong>R = 2<sup>h[1]</sup> + 2<sup>h[2]</sup> + ... + 2<sup>h[K]</sup></strong> is a binary representation of R then the optimal representation of <strong>N</strong> is <strong>N = 2048 + ... + 2048 + 2<sup>h[1]</sup> + 2<sup>h[2]</sup> + ... + 2<sup>h[K]</sup></strong> where we have <strong>Q</strong> copies of <strong>2048</strong>. Let’s call this approach formula approach.</p>
<p>Another way to come up with this answer is to use <a href="http://en.wikipedia.org/wiki/Greedy_algorithm">Greedy Algorithm</a>. That is, at each step you should take the largest possible summand among <strong>{1, 2, 4, 8, ..., 2048}</strong> that is not greater than the current value of N and then subtract it from N. In fact, this problem is a special case of <a href="http://en.wikipedia.org/wiki/Change-making_problem">Change-making problem</a> and in general it should be solved using <a href="http://en.wikipedia.org/wiki/Dynamic_programming">Dynamic Programming</a> or <a href="http://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns">Integer Linear Programming</a> but this set of coin values is special and admit using of Greedy Algorithm as we will see below.</p>
<p>Now we discuss why both of these approaches are correct.</p>
<hr>
<h1>1. Formula Approach.</h1>
<p>Let’s prove that formula approach is correct. Consider some representation of N as a sum of allowed powers of two. Let there is exactly <strong>C[K]</strong> occurrences of 2<sup>K</sup> in this representation. Then we have</p>
<p><strong>N = C[0] * 1 + C[1] * 2 + C[2] * 4 + ... + C[11] * 2048</strong></p>
<p>Note that the total number of summands here is <strong>C[0] + C[1] + ... + C[10] + C[11]</strong>. Assume that for some <strong>K < 11</strong> we have <strong>C[K] >=2</strong>, that is, we have at least two copies of 2K in the representation of <strong>N</strong>. Since <strong>K < 11</strong> then the price <strong>2K+1</strong> is allowed. Hence we can replace two copies of <strong>2K</strong> by one copy of <strong>2K+1</strong> not changing the value of sum but decreasing total number of summands. Thus, for optimal representation we should have</p>
<p><strong>C[K] <= 1 for all K < 11</strong>....................(1)</p>
<p>We will show that under the constraints (1) representation of N is uniquely determined. Of course this unique representation will be the optimal one.</p>
<p>At first note that</p>
<p><strong>R = C[0] * 1 + C[1] * 2 + C[2] * 4 + ... + C[10] * 1024 <= 1 + 2 + 4 + ... + 1024 = 2047 < 2048</strong>.</p>
<p>Hence</p>
<p><strong>2048 * C[11] <= N < 2048 * (C[11] + 1)</strong></p>
<p>or</p>
<p><strong>C[11] <= N / 2048 < C[11] + 1</strong></p>
<p>which means by <a href="http://en.wikipedia.org/wiki/Floor_and_ceiling_functions#Equivalences">one of the definition of floor function</a> that <strong>C[11] = floor(N / 2048) = Q</strong>. So <strong>C[11]</strong> is uniquely determined under the constraints (1) and equals to <strong>Q</strong>.</p>
<p>Further note that due to (1) <strong>C[10]C[9]...C[1]C[0]</strong> is a binary representation of R and hence <strong>C[0], C[1], ..., C[10]</strong> are also uniquely determined under the constraints (1).</p>
<p>Thus we have found this unique representation.</p>
<h1>2. Greedy Approach.</h1>
<p>Now let’s see why greedy approach produces the same solution. Clearly at first several steps we will take the <strong>2048</strong> until we get a number strictly less than <strong>2048</strong>. Then we will consider powers of two in descending order starting from <strong>1024</strong> and take the current power of two if it is not greater than the current value of <strong>N</strong>. It is quite clear that this process generates exactly the binary representation of <strong>N</strong>. Thus the whole representation coincides with the constructed above.</p>
<p>There are several ways how to implement this algorithm in this problem. First one is simple but slower in general. Namely, we have an outer loop of the form <strong>while (N > 0)</strong>. Then at each iteration of this loop we simply check in one loop all allowed powers of two in descending order until we find the power of two, say <strong>2X</strong>, that is not greater than the current value of <strong>N</strong>. After that we decrease <strong>N</strong> by <strong>2X</strong> and increase answer by 1. The complexity of this approach is <strong>O(N / 2K-1 + K2)</strong> in the worst test case. This is because at first <strong>N / 2K-1</strong> steps we have only one iteration of inner loop (we break at <strong>2048</strong>) and then we have at most <strong>K</strong> steps for each of which we have at most <strong>K</strong> steps in the inner loop.</p>
<p>In second method we swap outer and inner loop of the first method. So we iterate over allowed powers of two in descending order and for each power of two we have an inner loop of the form <strong>while (N >= 2X)</strong> in the body of which we do the same as for the first method, that is, decrease <strong>N</strong> by <strong>2X</strong> and increase answer by 1. The complexity of this method is <strong>O(N / 2K-1 + K)</strong>. Strictly speaking the number of basic operations in this method is <strong>O(answer + K)</strong>. <strong>N / 2K-1 + K</strong> is an upper bound for the answer.</p>
<p>Analyzing second implementation of the greedy approach it is easy to see how to make it faster. For each power of two we have the following inner loop
</p><pre><code>
while N >= 2X do<p></p>
<p>N = N - 2X</p>
<p>res = res + 1</p>
<p>Clearly this equivalent to</p>
<p>res = res + N div 2X</p>
</code><p><code>N = N mod 2X
</code></p></pre>
Thus we obtain third implementation of the greedy algorithm with complexity <strong>O(K)</strong>.
Next we have <strong>bitCount(R) = C[0] + C[1] + ... + C[10]</strong>. Hence the total number of summands in this representation is <strong>Q + bitCount(R)</strong> as was announced earlier. The complexity of this method is <strong>O(K)</strong>, where <strong>K = 12</strong> is the total number of powers of two that we are allowed to use.<p></p>intayushThu, 13 Oct 2016 22:54:12 +0530https://discuss.codechef.com/questions/85968/cdfi2-editorialcdfi2016easygreedycdfi2