Questions Tagged With cook62https://discuss.codechef.com/tags/cook62/?type=rssquestions tagged <span class="tag">cook62</span>enTue, 22 Sep 2015 05:06:53 +0530Submit button unavailablehttps://discuss.codechef.com/questions/75251/submit-button-unavailable<p>Why there is no submit button on problems of COOK62 in practice section??<br>
You may check here <a></a><a href="https://www.codechef.com/problems/STACKS">https://www.codechef.com/problems/STACKS</a><a></a></p>ankurverma1994Mon, 21 Sep 2015 00:41:04 +0530https://discuss.codechef.com/questions/75251/submit-button-unavailablecook62submit_failureFRGTNLNG - Editorialhttps://discuss.codechef.com/questions/75211/frgtnlng-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/FRGTNLNG">Practice</a><br>
<a href="http://www.codechef.com/COOK62/problems/FRGTNLNG">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/kostya_by">Kanstantsin Sokal</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/darkshadows">Lalit Kundu</a></p>
<h1>DIFFICULTY:</h1>
<p>Cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>Basic Programming</p>
<h1>PROBLEM:</h1>
<p>You have acquired a dictionary of $N$ words of a forgotten language. Meanwhile, you also know $K$ phrases used in modern languages. For each of the words of the forgotten language, your task is to determine whether the word is still in use in any of these $K$ modern phrases or not. Each phrase has $L$ words given in input.</p>
<h1>EXPLANATION:</h1>
<p>================ <br>
First, you just need to store all the $N$ words of the forgotten language and all the phrases. For each each word, then, you can traverse over all phrases and check if its present in any one of them. You can also build a single array of all the words from all phrases and then check for each forgotten language word if its present in the array or not.</p>
<p>If you want it to more efficient you can store all phrase words in a set where insertion is $O(\text{log}(\text{size}))$ and checking if a string is present or not is also $O(\text{log}(\text{size}))$.</p>
<p>For implementation, you need to know basic programming concepts and syntax of a language of your choice. You should know about arrays, conditionals, loops, input/output to solve this problem.</p>
<p>First, we include implementations in three popular programming contest languages.</p>
<p><strong>C++ code</strong></p>
<pre><code>#include <iostream>
#include <vector>
using namespace std;
int main() {
int T;
cin >> T;
for (int cas = 1; cas <= T; cas++) {
// we use 'cas' because 'case' is a keyword
int N, K, L;
// allocate more than necessary
// note that phrases[i] is a vector of strings.
vector < string > phrase[55];
//array of forgotten words
string forgotten[109];
cin >> N >> K;
for (int i = 0; i < N; i++) {
cin >> forgotten[i];
}
for (int i = 0; i < K; i++) {
cin >> L;
for (int j = 0; j < L; j++) {
string S;
cin >> S;
phrase[i].push_back(S);
}
}
for (int i = 0; i < N; i++){
string answer = "NO";
//traverse over all phrases
for(int j = 0; j < K; j++){
//traverse over phrase[j]
for(int k = 0; k < phrase[j].size(); k++){
if(phrase[j][k] == forgotten[i])
answer = "YES";
}
}
cout << answer << (i==N-1 ? "\n" : " ");
}
}
}
</code></pre>
<p><strong>Java Code</strong> </p>
<p>Note that java.util.Scanner provides an easy way to tokenize and read the input. However, for problems with huge inputs and strict time limits, it is not recommended because it is slow. Instead, one should use BufferedReader, like so:</p>
<pre><code>import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static String[] data;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(<a href="http://System.in">System.in</a>));
int testCases = Integer.parseInt(bufferedReader.readLine());
while (testCases-- > 0) {
//get N and K
int forgottenLanguageWordsCount, modernLanguagePhrasesCount;
data = bufferedReader.readLine().split(" ");
forgottenLanguageWordsCount = Integer.parseInt(data[0]);
modernLanguagePhrasesCount = Integer.parseInt(data[1]);
//build array
String[] forgottenWords = bufferedReader.readLine().split(" ");
//build a single list with all words from all phrases
List<String> modernWordsList = new ArrayList<>();
for (int i = 0; i < modernLanguagePhrasesCount; i++) {
data = bufferedReader.readLine().split(" ");
int totalWordsInPhrase = Integer.parseInt(data[0]);
//add to list
modernWordsList.addAll(Arrays.asList(data).subList(1, totalWordsInPhrase + 1));
}
//use .contains method to check if present in list or not
for (int i = 0; i < forgottenLanguageWordsCount; i++) {
if (modernWordsList.contains(forgottenWords[i])) {
System.out.print("YES");
} else {
System.out.print("NO");
}
System.out.print((i + 1 == forgottenLanguageWordsCount) ? "\n" : " ");
}
}
}
}
</code></pre>
<p><strong>Python code</strong></p>
<pre><code>T = input()
for cas in xrange(1,T+1):
N, K = map(int, raw_input().strip().split())
forgotten = raw_input().split()
allWordsfromPhrases = []
for i in xrange(K):
allWordsfromPhrases += raw_input().split()
ans = ""
for i in xrange(N):
if forgotten[i] in allWordsfromPhrases: ans += "YES "
else: ans += "NO "
print ans
</code></pre>
<p>Python is ridiculously easy in this problem. Note that the python code has a bit of different flavor, specifically the for..else statement.</p>
<h1>Suggestions</h1>
<p>I will directly quote <a href="http://www.codechef.com/users/kevinsogo">kevinsogo</a> from one of his editorials. </p>
<p>Now that you've learned that many, many things can go wrong even for such a simple problem, how does one go about preventing it?</p>
<p>Well, for one, it is usually hard to write a completely correct code in the first try. Therefore one should always test the code before submitting it! For example, use the sample data. The sample data is provided for two reasons:</p>
<ul>
<li>To ensure that you are following the input/output format correctly, and</li>
<li>To ensure that you at least get some small inputs correctly.</li>
</ul>
<p>However, if you pass the sample input, it doesn't mean you'll pass the actual input! So it still lies upon the contestant to ensure that their program will pass whatever kind of test case the judge can give to it. So if the judge returns WA, try making some inputs yourself, until you find one where your program fails. Then start debugging from there. In other problems, it is sometimes useful to make random input generators.</p>
<p>Also, there is the occasional problem that tests how well you follow instructions and handle many tricky edge cases. In such problems, speed/minute optimizations are secondary to correctness, so things like readability/<a href="http://en.wikipedia.org/wiki/Modular_programming">modularity</a> more important, at the expense of efficiency. See the sample programs above as examples, which were written partly with readability in mind.</p>
<h1>COMPLEXITY</h1>
<p>================ </p>
<p>If we implement a brute force solution, there are worst case $\text{MAXL} * \text{MAXK}$ words and for each forgotten word, we do a linear search. So total complexity is $\text{MAXL} * \text{MAXK} * \text{MAXN}$. <br>
Using set, complexity can be reduced to $\text{MAXL} * \text{MAXK} + \text{MAXN} * \text{log}(\text{MAXL}*\text{MAXK})$.</p>
<h1>AUTHOR'S, TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/COOK62/Setter/FRGTNLNG.cpp">setter</a> <br>
<a href="http://www.codechef.com/download/Solutions/COOK62/Tester/FRGTNLNG.cpp">tester</a> </p>darkshadowsSat, 19 Sep 2015 21:52:38 +0530https://discuss.codechef.com/questions/75211/frgtnlng-editorialfrgtnlngcook62editorialbasic-progstringscakewalkSTACKS - Editorialhttps://discuss.codechef.com/questions/75205/stacks-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/STACKS">Practice</a><br>
<a href="http://www.codechef.com/COOK62/problems/STACKS">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/kostya_by">Kanstantsin Sokal</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/darkshadows">Lalit Kundu</a></p>
<h1>DIFFICULTY:</h1>
<p>Simple</p>
<h1>PREREQUISITES:</h1>
<p>binary search, data structures</p>
<h1>PROBLEM:</h1>
<p>Mike likes to compose his disks in stacks, but there's one very important rule: The disks in a single stack must be ordered by their radiuses in a <b>strictly</b> increasing order such that the top-most disk will have the smallest radius. </p>
<p>Mike initiates an empty set of disk stacks. Mike processes the disks in the given order $A_1, A_2, ..., A_N$ using the following pattern:</p>
<ul>
<li>If there is at least one stack such that Mike can put the current disk on the top of the stack without making it invalid, then he chooses the stack with the smallest top disk radius strictly greater than the radius of the current disk, and puts the current disk on top of that stack.</li>
<li>Otherwise, Mike makes a new stack containing only the current disk. </li>
</ul>
<p>Your task is to output the set of the stack top disk radii after the algorithm is done in non-decreasing order. </p>
<h1>QUICK EXPLANATION:</h1>
<p>====================== <br>
We build our solution incrementally and at each step we maintain an sorted array $S$ storing the top radii of all the stacks present. Using binary search, we can find the correct stack for a new disk. After replacing the top radii of such a stack, array $S$ still remains sorted.</p>
<h1>EXPLANATION:</h1>
<p>================ <br>
We are going to build our solution incrementally. That is, at each step we'll store the stacks we already have formed and then find the correct position for a disk and put it there.</p>
<p>Now, from the example, given in the problem statement, it should be pretty clear that we need not store all the radii present in a stack. Since, we just need to output the top radii, and also where a new disk goes also depends on the top radii, we can just store the top radii of each of the stack currently formed.</p>
<p>Let's say we have an array $S_1, S_2, ..., S_k$ which currently stores the top radii of all stacks currently formed in sorted order. And now, we want to insert a new disk with radius $x$ into this structure. So, we need to find smallest $S_j$(<em>i.e.</em> smallest $j$, since $S$ is sorted) such that $S_j > x$. And we update $S_j = x$. We know that $S_{j-1} \le x$ and $S_{j+1} \gt x$, so array $S$ still remains sorted after the update. So, at each step we apply binary search to find such an index $j$ and update the value $x$. If there is no such index found, we just create a new entry at the end of the array.</p>
<pre><code>A[N] = input
S[N]
current_size = 0
for i=0 to N-1:
// find the first idx in the sorted array S, such that S[idx] > a[i].
// this can be done using a simple binary search.
int idx = binarySearch(size, a[i]);
S[idx] = A[i]
if(idx==size) size++;
for i=0 to size-1:
print S[i]
//searches for first index idx such that S[idx] > val
int binarySearch(size, val):
int lo = 0, hi = size - 1;
int ans = size;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (a[mid] > x) {
ans = mid;
hi = mid - 1;
}
else {
lo = mid + 1;
}
}
return ans;
}
</code></pre>
<p>You can also use built-in function $\text{upper\_bound}$ instead of binary search. Also, we can solve this problem using <a href="http://www.cplusplus.com/reference/set/multiset/">multiset</a>. We just have to perform simulation. So, first, let's try to write our algorithm in pseudo code first and then we'll try to think about what kind of data structure do we need to implement that algorithm efficiently:</p>
<pre><code>A[N] = input
Data Structure DS;
for i=0 to N-1:
x = Find in DS smallest number greater than A[i]
if no such number:
DS.insert(A[i])
else:
//we place A[i] on the stack with top radii x
DS.delete(x)
DS.insert(A[i])
print DS in sorted order
</code></pre>
<p>Now, we just need to think what kind of data structure DS is. It should efficiently insert values, delete values and for a given value find smallest number greater than value. If you know STL, <a href="http://www.cplusplus.com/reference/set/set/">set</a> is such a data structure which keeps its elements sorted and can insert, delete, find operations in O(\text{log}(size))$. But, set doesn't keep duplicates, while we need to keep duplicates, so we use <a href="http://www.cplusplus.com/reference/set/multiset/">multiset</a>. A multiset allows duplicate values.While deleting in a multiset, if you delete by value, all occurences of value are deleted. So, we should first find a value, which will return an iterator and then we'll delete by iterator.</p>
<pre><code>A[N] = input
multiset <int> myset;
multiset <int>::iterator it;
for i=0 to N-1:
//here we first insert and then we find smallest number greater than A[i]
myset.insert(A[i])
it = myset.find(A[i])
//right now, it points to A[i]
//since multiset keeps elements ordered
//so, next element should be the element we are looking for
//also, sets have bidirectional iterators and can be incremented/decremented easily
it++;
//no such element present
if it == myset.end():
DS.insert(A[i])
else:
myset.erase(it)
//traverse over multiset to print values
//values inside multiset are already sorted
for(it=myset.begin(); it!=myset.end(); it++)
print (*it)
</code></pre>
<h1>COMPLEXITY:</h1>
<p>================ <br>
$O(N \text{log} N)$, since each operation on multiset takes $O(\text{log}N)$, or in case of binary search, it takes $O(\text{log}N)$ at each step.</p>
<h1>PROBLEMS TO SOLVE:</h1>
<p>================ <br>
Problems involving binary search: <br>
<a href="https://www.codechef.com/MARCH15/problems/STRSUB">STRSUB</a> <br>
<a href="https://www.codechef.com/LTIME22/problems/ASHIGIFT">ASHIGIFT</a> <br>
<a href="https://www.codechef.com/AUG15/problems/STETSKLX">STETSKLX</a> </p>
<p>Problems involving STL containers: <br>
<a href="https://www.hackerrank.com/challenges/median">Running Median</a> <br>
<a href="https://www.codechef.com/COOK51/problems/ANUMLA">ANUMLA</a> </p>
<h1>AUTHOR'S, TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/COOK62/Setter/STACKS.cpp">setter</a> <br>
<a href="http://www.codechef.com/download/Solutions/COOK62/Tester/STACKS.cpp">tester</a> </p>darkshadowsSat, 19 Sep 2015 19:10:33 +0530https://discuss.codechef.com/questions/75205/stacks-editorialsimplebinary-searchcook62stackseditorialSPRNMBRS - Editorialhttps://discuss.codechef.com/questions/75203/sprnmbrs-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/SPRNMBRS">Practice</a><br>
<a href="http://www.codechef.com/COOK62/problems/SPRNMBRS">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/kostya_by">Kanstantsin Sokal</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/darkshadows">Lalit Kundu</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy-medium</p>
<h1>PREREQUISITES:</h1>
<p>number theory, euler totient</p>
<h1>PROBLEM:</h1>
<p>$\phi(N)$ is defined as the number of positive integers less than or equal to N that are coprime with N. Let's call a positive integer $N$ a super number if $N$ can be divided by $\phi(N)$ without a remainder. You are given two positive integers $L$ and $R$. Your task is to find count of super numbers in the range $[L, R]$. </p>
<h1>QUICK EXPLANATION:</h1>
<p>====================== <br>
Note that $\phi(N) = N*\frac{(p_1 - 1) * (p_2 - 1) * ... * (p_n - 1)}{p_1*p_2*...*p_n}$. That means, $(p_1 - 1) * (p_2 - 1) * ... * (p_n - 1)$ should divide $p_1*p_2*...*p_n$ which is possible only when </p>
<ul>
<li>$n=0$ </li>
<li>$n=1$ and $p_1=2$</li>
<li>$n=2$ and $p_1=2$ and $p_2=3$.</li>
</ul>
<p>That is, count numbers of form $N = 2^a * 3^b$ where $a \gt 0$ and $b \ge 0$ in range $[L, R]$ which can be done in $log_{2}{R}*log_{3}{R}$.
Also don't forget to count $N = 1$ if in range $[L, R]$.</p>
<h1>EXPLANATION:</h1>
<p>================ <br>
You need to know about about two important properties of <a href="https://en.wikipedia.org/wiki/Euler's_totient_function">Euler's Totient Function</a> $\phi(n)$.</p>
<ul>
<li>The function $\phi(n)$ is multiplicative <em>i.e.</em> if $\text{gcd}(m, n) = 1$, then $\phi(mn) = \phi(m) * \phi(n)$.</li>
<li>Let's see what is value of $\phi(p^k)$ where $p$ is a prime and $k \ge 1$. $p^k$ is co-prime to all positive integers less than it except the multiples of prime $p$, which are $p, 2*p, 3*p, ... p^{k-1}*p$. Therefore, $\phi(p^k) = p^k - p^{k-1}$.</li>
</ul>
<p>Using above two properties, we can define $\phi(n)$ for a general $N = p_1^{k_1}, p_2^{k_2}, ..., p_n^{k_n}$(where $p_i$ are distinct primes). We know, using multiplicative property that <br>
$\phi(N) = \phi(p_1^{k_1})*\phi(p_1^{k_1})* ...* \phi(p_n^{k_n})$ <br>
which can be written as </p>
<p>$\phi(N) = p_1^{k_1}*(1-\frac{1}{p_1})* p_2^{k_2}*(1-\frac{1}{p_2})* ... * p_n^{k_n}*(1-\frac{1}{p_n})$ <br>
which is same as <br>
$\phi(N) = N*\frac{(p_1 - 1) * (p_2 - 1) * ... * (p_n - 1)}{p_1*p_2*...*p_n}$.</p>
<p>Now, for $\phi(N)$ to divide $N$, $(p_1 - 1) * (p_2 - 1) * ... * (p_n - 1)$ should divide $p_1*p_2*...*p_n$. Let's say we don't include $2$ as any of the $p_i$, then of course, its never possible because all primes $p_i$ will be odd and $p_i -1$ is even for all primes.</p>
<p>So, we need to include $p_1 = 2$. So we want $(p_2 - 1) * ... * (p_n - 1)$ to divide $2*p_2*...*p_n$, where all $p_2, p_3, ... p_n$ are odd. This can happen when </p>
<ul>
<li>$n=0$, <em>i.e.</em> $N=1$. </li>
<li>$n=1$ and $p_1=2$, <em>i.e</em> $N$ is a power of $2$.</li>
<li>$n=2$ and $p_1=2$ and $p_2=3$, <em>i.e</em> $N$ is product of powers of $2$ and $3$.</li>
</ul>
<p>Now, we just have to count numbers of this form in range $L$ to $R$. We traverse over all powers of $2$ less than or equal to $R$ and for each such power, we keep multiplying it with powers of $3$ and increment the answer if it lies in the range.</p>
<pre><code>L, R = input
answer = 0
value = 2
while( value < = R )
current = value
while current <= R:
if L <= current <= R:
answer ++
current *= 3
value *= 2
//we haven't included N=1 in our answer
if L <= 1 <= R:
answer ++
print answer
</code></pre>
<h1>COMPLEXITY:</h1>
<p>================ <br>
There are $log_{2}{R}$ powers of $2$ we are considering and for each such power we can in worst case consider $log_{3}{R}$ values. So, an upper bound on complexity can be said as $log_{2}{R}*log_{3}{R}$.</p>
<h1>PROBLEMS TO SOLVE:</h1>
<p>================ <br>
<a href="https://www.codechef.com/COOK29/problems/EXGCD">EXGCD</a> <br>
<a href="https://www.codechef.com/LTIME26/problems/PUPPYGCD">PUPPYGCD</a></p>
<h1>AUTHOR'S, TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/COOK62/Setter/SPRNMBRS.cpp">setter</a> <br>
<a href="http://www.codechef.com/download/Solutions/COOK62/Tester/SPRNMBRS.cpp">tester</a> </p>darkshadowsSat, 19 Sep 2015 18:06:32 +0530https://discuss.codechef.com/questions/75203/sprnmbrs-editorialsprnmbrscook62number-theoryeditorialeasy-mediumREIGN2 - Editorialhttps://discuss.codechef.com/questions/75208/reign2-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/REIGN2">Practice</a><br>
<a href="http://www.codechef.com/COOK62/problems/REIGN2">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/kostya_by">Kanstantsin Sokal</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/darkshadows">Lalit Kundu</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy-Medium</p>
<h1>PREREQUISITES:</h1>
<p><a href="https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/">dynamic programming</a>, greedy</p>
<h1>PROBLEM:</h1>
<p>There are $N$ castles that can be conquered by George. He has decided to conquer exactly $K$ castles during the next $K$ days, an aim he plans to achieve by conquering one castle every day for the next $K$ days. <br>
As reported by King George's spies, $A_i + (j - 1) * B_i$ enemy knights will be protecting the $i^{th}$ castle during the $j^{th}$ day. When attacking a castle, if the King sends as many knights as those defending it, it's sufficient to be conquer that castle. Another requirement is that one knight cannot be sent to conquer two different castles. </p>
<p>As you are the king's trusted advisor, you can choose a set of $K$ castles, that the king should conquer. After you provide a set of castles, George will choose the order in which he will conquer them. You can assume that George always chooses the order which minimizes the total number of knights used during all the conquests. </p>
<p>Your task is to find the maximum possible total number of knights that can be used during the campaign and reached by delegating a set of $K$ castles to conquer. Also, you are not sure about the value of $K$, so you should find the optimal answer for each $K = 1, 2, ... , N$. </p>
<h1>QUICK EXPLANATION:</h1>
<p>====================== <br>
First sort arrays $A$ and $B$ in decreasing order of $B$ while preserving the mutual connectedness of $A_i$ and $B_i$. After that, we define $f(i, j)$ as maximum number of knights required for king to conquer a subset of $j$ castles from first $i$ castles. We can easily define recurrence relation and base cases of this DP solution.</p>
<h1>EXPLANATION:</h1>
<p>================ <br>
First of all let's observe the strategy of king. He is given a set of $K$ castles and two arrays $A_1, A_2, ..., A_K$ and $B_1, B_2, ..., B_K$ are given. For conquering castle $i$ on day $j$ he has to send $A_i + (j - 1)*B_i$ knights. His aim is to decide such an ordering of conquering such that total number of knights required is minimised.</p>
<p>Now, he has to pay $A_i$ for each castle $i$ independent of which day he conqueres it on. So, the ordering depends only on $B_i$. If we think of a greedy approach we should first conquer those castles with highest $B_i$ since, as the day number increases $(j-1)*B_i$ will also increase. So, this is the the strategy of king: <strong>Conquer all $K$ castles in non-increasing order of</strong> $B_i$.</p>
<p>Now, moving onto solving the problem. Let's solve for a particular $K$. So, we have to choose $K$ castles out of $N$ such that using king's approach maximum number of knights are used. Now, a greedy approach which selects only of basis of $A_i$ or $B_i$ would be certainly wrong. We should, by now, be thinking on terms of dynamic programming.</p>
<p>Now, if you remember subset sum DP, we kept our states as $(i, j)$ denoting that we are solving for first $i$ elements and we need to form a sum $j$. If we try to think on similar terms here, we should keep our states as $(i, j)$ denoting that we are solving for first $i$ elements and we need to select $j$ castles to maximise knights required according to king's strategy. Now, we have to make a decision that either we select $i^{th}$ castle or not. If we select it, do we know what its going to contribute <em>i.e.</em> how many knights are going to be required? For that we should know on which day king will conquer this castle. Now, here is the interesting part: if we sort the initial arrays in decreasing order of $B_i$, then we'll be sure that according to king's strategy $i^{th}$ castle will be conquered on last day because all other castles that will be selected will have $B_j$ less than $B_i$.</p>
<p>So, we first sort arrays $A$ and $B$ in decreasing order of $B$ while preserving the mutual connectedness of $A_i$ and $B_i$. After that, we define $f(i, j)$ as maximum number of knights required for king to conquer a subset of $j$ castles from first $i$ castles.</p>
<p>Recurrences can be define easily as:</p>
<pre><code>f(i, j) = max(
\\don't select i'th castle
f(i - 1, j)
\\select i'th castle, add the cost
f(i - 1, j - 1) + (A[i] + (j - 1)*B[i])
)
</code></pre>
<p>Realising base cases is very easy. So, we calculate $f(N-1, i)$ for all $i = 1, 2, ..., N$ and print them.</p>
<h1>COMPLEXITY:</h1>
<p>================ <br>
Since there are $N^2$ states and transition cost between states is constant time, total complexity is $O(N^2)$.</p>
<h1>PROBLEMS TO SOLVE:</h1>
<p>================ <br>
<a href="https://www.codechef.com/problems/KGP14D">KGP14D</a> <br>
<a href="https://www.codechef.com/problems/KGP14H">KGP14H</a> <br>
<a href="https://www.codechef.com/JULY15/problems/MCHEF">MCHEF</a> <br>
<a href="https://www.codechef.com/COOK61/problems/CARDLINE">CARDLINE</a> </p>
<h1>AUTHOR'S, TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/COOK62/Setter/REIGN2.cpp">setter</a> <br>
<a href="http://www.codechef.com/download/Solutions/COOK62/Tester/REIGN2.cpp">tester</a> </p>darkshadowsSat, 19 Sep 2015 20:15:02 +0530https://discuss.codechef.com/questions/75208/reign2-editorialdynamic-programminggreedycook62reign2editorialeasy-mediumSUBGRAPH - Editorialhttps://discuss.codechef.com/questions/75320/subgraph-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/SUBGRAPH">Practice</a><br>
<a href="http://www.codechef.com/COOK62/problems/SUBGRAPH">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/kostya_by">Kanstantsin Sokal</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/darkshadows">Lalit Kundu</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium-Hard</p>
<h1>PREREQUISITES:</h1>
<p>DP on trees, graphs</p>
<h1>PROBLEM:</h1>
<p>You are given an undirected graph $G$ of $N$ nodes and $M$ edges. It's guaranteed that no multiple edges or self-loops appear in the graph as well as that the graph is connected. There's one more restriction on the graph: any node of $G$ belongs to at most one simple cycle in $G$.</p>
<p>Your task is to count the subsets of nodes in $G$, such that the nodes in the subset are connected (you can reach any node of the subset from any other node of the subset only by moving to adjacent nodes that belong to the subset) and contain no more than $K$ nodes. </p>
<h1>QUICK EXPLANATION:</h1>
<p>================ <br>
<strong>Cycle main node</strong> <br>
Each cycle has the main node: it's a node, which, if we make the graph $G$ rooted, will be connected to some node of the cycle, which is an ancestor cycle for our cycle.</p>
<p>For each cycle main node $v$, we define $\text{f}(v, k)$ as the number of subgraphs rooted at node $v$ and having $k$ nodes in it. This $k$ also includes non-main nodes and not just the nodes in compressed tree.
For each non-main node, we define we define $\text{g}(v, k)$ as the number of subgraphs rooted at node $v$ and having $k$ nodes in it and these subgraphs don't have any of the nodes of $\text{cycle}[v]$. That means, it only depends on the main nodes that come out of node $v$. So, we can recursively define $\text{g}(v, k)$ based on values of $f$.</p>
<p>Now, for recursively calculating values of $f$, we consider each subsegment of cycle of main node $v$ and, then for all subsegments, for all nodes in current subsegment calculate number of subgraphs using values of $g$. If such a subsegment has node $v$ in it, then we add the value calculated to $f(v)$.</p>
<p>Add to answer the values calculated by considering each subsegment.</p>
<h1>EXPLANATION:</h1>
<p>================ <br>
DP solution to realise in this problem is a little difficult. I am going to explain author's solution here. <br>
First lets discuss an easier problem which says: Given a tree calculate number of subtree's with exactly $K$ nodes. Here we need to use DP on tree. For each node $v$, we define $\text{dp}(v, k)$ as number of subtrees with $k$ nodes and $v$ as root. Now, we can define recurrence relation for this. Let's say for node $v$, there are direct children nodes $u_1, u_2, ... u_n$. Now, to form a subtree with $k+1$ nodes rooted at $v$, lets say direct children nodes contribute $a_1, a_2, ..., a_n$ nodes, where $a_1 + a_2 + ... + a_n = k$, in this case we add to $\text{dp}(v, k)$ the value $\text{dp}(u_1, a_1)*\text{dp}(u_2, a_2)*...*\text{dp}(u_n, a_n)$. We should do this for all possible $a_1, a_2, ..., a_n$.</p>
<p>To do this, we create one more DP here $\text{dp1}(i, j)$ as number of ways to choose a total of $j$ nodes from subtrees defined by $u_1, u_2, ..., u_i$. The recurrence can be defined as $\text{dp1}(i, j) = \sum_{k=0}^{K} \text{dp1}(i-1,j-k)*\text{dp}(i, k)$. So, in terms of pseudo code we can write something like:</p>
<pre><code>dp[N][K+1]
void rec(int cur_node){
dp[cur_node][1]=1
for(all v such that v is children of cur_node)
rec(v)
dp_buffer[K] = {0}
for i=0 to K:
for j=0 to K-i:
dp_buffer[i + j] += dp[i]*dp[v][j]
dp[cur_node] = dp_buffer
}
</code></pre>
<p>Hence, our problem is solved. We do something similar in our given graph, but since cycles are involved, we need to do something improvised. You should here notice that if we compress all cycles to form a single node, then our graph is a tree, say $T$. You should also note that non-bridge edges in $G$ are the edges which will be the edges of tree $T$.</p>
<p>First, a definitions I'll be using: <br>
<strong>Cycle main node</strong> <br>
Each cycle has the main node: it's a node, which, if we make the graph $G$ rooted, will be connected to some node of the cycle, which is an ancestor cycle for our cycle. Or, in other words after rooting $G$, if I apply DFS then main node of a cycle will be visited earliest. For example, in following image nodes $1$, $2$, $5$, and $9$ are main nodes, if $G$ is rooted at node $1$.</p>
<p><img height="50%" src="http://i.imgur.com/Vvp8wcM.png" width="50%"></p>
<p>All other nodes can be called as non-main nodes.</p>
<p>Now, first we parse cycles in graph $G$, which means compressing each cycle to a cycle main node and for each cycle store the vertices in it. Let's denote by $\text{cycle}[v]$ as the cycle id of node $v$. Now, we are going to compute DP on this compressed tree and at the same time also maintain data about the cycles in it.</p>
<p>So, we define $\text{f}(v, k)$ for all main nodes $v$, the number of subgraphs rooted at node $v$ and having $k$ nodes in it. This $k$ also includes non-main nodes and not just the nodes in compressed tree. Now, we cannot just calculate function $f$ recursively using its own definition, we need to also include the fact that main node $v$ is not just a single node but a cycle.</p>
<p>So, for non-main nodes $v$, we define $\text{g}(v, k)$ as the number of subgraphs rooted at node $v$ and having $k$ nodes in it and these subgraphs don't have any of the nodes of $\text{cycle}[v]$. That means, it only depends on the main nodes that come out of node $v$. So, we can recursively define $\text{g}(v, k)$ based on values of $f$. This DP is quite similar to what we discussed in the easier problem. So, in terms of pseudo code we can write:</p>
<pre><code>g[N][K]
void rec(int cur_node, int prev){
g[cur_node][1]=1
for(all edges e incident with cur_node):
//we just want to consider children of cur_node
//which are main nodes
if e is the edge (cur_node, prev) or if e is not a bridge:
continue
u = neighbor of v via edge e
rec(u, v)
dp_buffer[K] = {0}
for i=0 to K:
for j=0 to K-i:
dp_buffer[i + j] += g[i]*f[u][j]
g[cur_node]=dp_buffer
}
</code></pre>
<p>Now, that we have calculated $g$ array at current main node, lets see how we will calculate $f$ for the current main node again, based on recursive definition. Now, you should notice how we can make subgraphs at a main node. For example, in the following image, the six different color curves denote which non-main nodes are we going to include in our subgraph at node $v$. <br>
<img height="50%" src="http://i.imgur.com/0GYLBMQ.jpg" width="50%"></p>
<p>So, the different subgraphs we have made are:</p>
<ul>
<li>color pink: $v$, $S(u_3)$, $S(u_1)$, where $S(x)$ denotes the subtree of node $x$.</li>
<li>color green: $v$, $S(u_1)$, $S(u_2)$, $S(u_3)$</li>
<li>color red: $v$, $S(u_1)$</li>
<li>color blue: $v$, $S(u_1)$, $S(u_2)$</li>
<li>color yellow: $v$, $S(u_2)$, $S(u_3)$</li>
<li>color cyan: $v$, $S(u_3)$</li>
</ul>
<p>You should notice that we are considering all subsegments in cycle of node $v$(because we need subgraph connected) and then for each subsegment we can use $g$ to calculate number of subgraphs which include subtrees of all these nodes. Also, if for a subsegment main node lies in that segment we can use it to calculate $f$ for main node $v$.</p>
<p>Lets formalise things a bit. Let's say you are considering subsegment of nodes formed by nodes $u_1, u_2, ..., u_n$. We already have calculated $g(u_i, k)$ for all $i$ and $k$. Now, at this step we'll also be adding the subgraphs caused by this subsegment to our final answer. We define $h(k)$ as number of such subgraphs with $k$ nodes. So, the subgraph we are considering is formed by $S(u_1), S(u_2), ..., S(u_n)$. So, for calculating $h(k+n)$ we assume that we have choosen $a_1, a_2, ..., a_n$ from each of these subtrees, where $a_1 + a_2 + ... + a_n = k$, so to $h(k+n)$, we add $g(u_1, a_1) * g(u_2, a_2) * ... * g(u_n, a_n)$. Now, we should do this for all possible sets of $a_i$. </p>
<p>Again, for calculating this we can do very similar to what we did in the easier problem in beginning.</p>
<pre><code>h = g(u_1)
for i = 2 to n:
dp_buffer[K] = {0}
for j = 1 to K:
for k = 1 to K-i:
dp_buffer[j + k] += h[j]*g(u[i], k)
h = dp_buffer
//at this step dp_buffer stores h(k) for the set of nodes
//u_1, u_2, u_3, ... u_i
//so to our final answer we should add this whole array h
for j = 1 to K:
ans[j] += h[j]
//if subsegment u_1 to u_i contains main-node v
//then to f(v, i) we should add h(i) for all i
if subsegment u_1 to u_i contains main-node v:
for j = 1 to K:
f(v, j) += h[j]
</code></pre>
<p>We do the above process for all possible $u_1$ <em>i.e.</em> all possible subsegment starts. You need to take care of a few things:</p>
<ul>
<li>Be sure to count the whole cycles as a subsegment only once(it can be done to iterating through the whole cycle only from the main node of the cycle)</li>
<li>Be sure to consider $g(u_i, k)$ for $k \ge 1$, <em>i.e.</em> node $u_i$ is present always(otherwise chain will not be connected).</li>
</ul>
<p>So, in this way we we'll have iterated over all possible subsegments which can possibly contribute to the answer. Now, we just have to take sum of $\text{ans}[i]$, for all $i \le K$.</p>
<h1>COMPLEXITY</h1>
<p>================ <br>
Let's say $l$ is size of cycles and $n$ is number of cycles. <br>
Then for each subsegment of cycle <em>i.e.</em> a total of $l^2$ subsegments, we do a computation of $K^2$. Also, for calculating $g$ for each non-main node, we do a computation of $K^2$, where non-main nodes could be atmost $N$. <br>
So, our complexity is $O(n * (l^2 * K^2) + N * K^2)$ which we can say is less than $O(n * (l * L * K^2) + N * K^2)$ $=$ $O((N * L * K^2) + N * K^2)$ = $O(N * L * K^2)$.</p>
<h1>AUTHOR'S, TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/COOK62/Setter/SUBGRAPH.cpp">setter</a> <br>
<a href="http://www.codechef.com/download/Solutions/COOK62/Tester/SUBGRAPH.cpp">tester</a> </p>darkshadowsTue, 22 Sep 2015 05:06:53 +0530https://discuss.codechef.com/questions/75320/subgraph-editorialeditorialsubgraphdynamic-programminggraphtreecook62medium-hard