Questions Tagged With dec14https://discuss.codechef.com/tags/dec14/?type=rssquestions tagged <span class="tag">dec14</span>enWed, 11 Nov 2015 13:45:41 +0530GOODGAL - Editorialhttps://discuss.codechef.com/questions/58552/goodgal-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/GOODGAL">Practice</a> <br>
<a href="http://www.codechef.com/DEC14/problems/GOODGAL">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/pavel1996">Pavel Sheftelevich</a> <br>
<strong>Tester 1:</strong> <a href="http://www.codechef.com/users/xiaodao">Minako Kojima</a> <br>
<strong>Tester 2:</strong> <a href="http://www.codechef.com/users/shiplu">Shiplu Hawlader</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>HARD</p>
<h1>PREREQUISITES:</h1>
<p>Graphs</p>
<h1>PROBLEM:</h1>
<p>You are given a graph and you have to decide if it is a <a href="http://en.wikipedia.org/wiki/Halved_cube_graph">halved cube graph</a> which is a subgraph of <a href="http://en.wikipedia.org/wiki/Hypercube_graph">hypercube graph</a> formed by connecting pairs of verices at distance exactly two from each other in the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph.</p>
<h1>CHARACTERIZATION</h1>
<p>Let Qd be a hypercube of order d and let Hd be a halved cube of order d.</p>
<p>Let's consider a hypercube graph Qd first. Qd has n = 2^d vertices and there is a very handful way of defining it. Let vertices of Qd be the set of all binary strings of length d. We connect two vertices if and only if their corresponding binary strings differ by exactly one bit. Based on this definition, it is easy to see that Qd is a d-regular graph with 2^d-1 * d edges and diameter d.</p>
<p>Let's consier a vertex v of Qd. In order to know how to form a halved cube, we want to know how many vertices are at distance exactly two from v. Our handful definition shows that there are binomial(d, 2) vertices at distance two from v, because there are binomial(d, 2) binary strings different on exactly two bits from the string assigned to v.</p>
<p>You can try to construct one such graph it by hand. For example H3 is a complete graph over 4 vertices.</p>
<h1>QUICK EXPLANATION:</h1>
<p>You can implement the algorithm described in this <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/halved-cubes.pdf">paper</a>.</p>
<h1>EXPLANATION:</h1>
<p>All fact below are based on the <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/halved-cubes.pdf">paper</a>. I don't give here a complete solution, because it is well presented in the paper.</p>
<p>You can assume that d >= 5, because we can recognize every Hd for d < 5 which is really easy.</p>
<p>It is known than Hd has 2^(d-1) cliques of size d.</p>
<p>Here is a sketch of the algorithm:</p>
<p>The algorithm works in steps:</p>
<p>Input: graph G on n vertices</p>
<ol>
<li>We identify all cliques of size d in G</li>
<li>We construct a new graph G' in the following way. For any cluque C found in step 1, we add a new vertex and join it to every vertex of C. The edges added in this process are all edges of G` - we remove all old edges of G at the end.</li>
<li>We check if G` is a hypercube. If it is, G is a halved cube, otherwise G is not a halved cube.</li>
</ol>
<p><a href="http://www.fmf.uni-lj.si/~klavzar/preprints/halved-cubes.pdf">Paper</a> describes every step with all details. In order to understand the logic behind the construction in step 2 let's consider any clique C. If G is a halved cube graph, then all pairs of vertices in C are at distance 2 in the corresponding hypercube graph. Based on this fact, it is easy to see that in there must be a vertex u in Qn such that u is as distance 1 from any of vertices in C. Please check the <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/halved-cubes.pdf">paper</a> for more details.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>To be uploaded soon.</p>
<h1>RELATED PROBLEMS:</h1>
<p>To be uploaded soon.</p>pkacprzakTue, 16 Dec 2014 06:16:45 +0530https://discuss.codechef.com/questions/58552/goodgal-editorialgraphdec14hardeditorialKALKI - Editorialhttps://discuss.codechef.com/questions/58413/kalki-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/PROBLEMCODE">Practice</a><br>
<a href="http://www.codechef.com/CONTESTCODE/problems/PROBLEMCODE">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/nssprogrammer">Snigdha Chandan</a> <br>
<strong>Tester 1:</strong> <a href="http://www.codechef.com/users/xiaodao">Minako Kojima</a><br>
<strong>Tester 2:</strong> <a href="http://www.codechef.com/users/shiplu">Shiplu Hawlader</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>CHALLENGE</p>
<h1>PREREQUISITES:</h1>
<p>Graph, Trees, Approximation, Ad-Hoc radio networks</p>
<h1>PROBLEM:</h1>
<p>You are given a set of N points on a plane. Each point is unique and it is denoted by its x and y coordinates. You can think of each point as a radio transmitter. Your task is to connect the points in a tree and your score is based on the following:</p>
<p>Let's consider a vertex v and let u be the farthest direct neighbor of v in the tree. Let d(u, v) be the distance between v and u. Then node v transmits a radio wave of a circular shape with a center in v and a radius d(u, v). Since all nodes in the tree transmit their radio waves, each node is covered by a positive number of these waves. Your task is to construct a tree in such a way, that the number of waves covering a node v is minimal, where v is a node which is covered by the most waves among all nodes in a tree.</p>
<h1>QUICK EXPLANATION:</h1>
<p>This is a very hard problem. It is proven that approximate the result within better than logarithmic factor is also very hard. If you are interested in the complexity of the problem, you can check it <a href="http://link.springer.com/chapter/10.1007%2F11963271_2">here</a></p>
<h1>EXPLANATION:</h1>
<p>In order to come up with a really simple solution, you can try any heuristic which runs in the time limit or combine them and select the best one for a current case.</p>
<p>Example heuristics:</p>
<ol>
<li>
<p>Greedy. Try to construct a tree connecting node v (which is already in the tree) to a node u which is the closest one node to v on the plane. The intuition here is that by selecting the closest neighbors, we try to minimize radiuses of radio waves transmitted by nodes, and we expect that the smaller the radiuses are, the less waves will cover a single node.</p>
</li>
<li>
<p>MST. Based on the same intuition as above, we can try to build a MST over a complete graph on given n nodes.</p>
</li>
</ol>
<p>More sophisticated solutions:</p>
<p>You can try to implement an algorithm from this great paper: <a href="http://www.disco.ethz.ch/publications/DIALM2005b.pdf">Minimizing Interference in Ad Hoc and Sensor Networks</a></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>To be uploaded soon.</p>
<h1>RELATED PROBLEMS:</h1>
<p>To be uploaded soon.</p>pkacprzakMon, 15 Dec 2014 19:22:01 +0530https://discuss.codechef.com/questions/58413/kalki-editorialradio-networksgraphchallengetreeoptimizationeditorialdec14DIVIDEN - Editorialhttps://discuss.codechef.com/questions/58550/dividen-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/DIVIDEN">Practice</a> <br>
<a href="http://www.codechef.com/DEC14/problems/DIVIDEN">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/pavel1996">Pavel Sheftelevich</a> <br>
<strong>Tester 1:</strong> <a href="http://www.codechef.com/users/xiaodao">Minako Kojima</a> <br>
<strong>Tester 2:</strong> <a href="http://www.codechef.com/users/shiplu">Shiplu Hawlader</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>MEDIUM</p>
<h1>PREREQUISITES:</h1>
<p>Geometry, Binary search, Angles</p>
<h1>PROBLEM:</h1>
<p>You are given an integer 0 < N < 360 denoting an angle. Your task is to decide if it is possible to divide this angle <a href="http://en.wikipedia.org/wiki/Compass-and-straightedge_construction">using only a straightedge and compass</a> into N equal angles of size 1 degree. If it is possible, then you have to provide this contruction.</p>
<h1>BONUS</h1>
<p>If you want to watch a very nice video about constructing using only a straightedge and compass, please look <a href="https://www.youtube.com/watch?v=6Lm9EHhbJAY">here</a>.</p>
<h1>QUICK EXPLANATION:</h1>
<p>First we want to decide if it is possible to do this construction. Using a well-known fact, we argue that it is only impossible to do this if N % 3 == 0. In order to prove that, we will show how to construct an angle of size 1 degree if N % 3 != 0. Moreover, knowing when it is possible can lead us to an easier construction based on dividing the original angle until we construct an angle of size 1 with sufficient precision. </p>
<h1>EXPLANATION:</h1>
<p>Based on a well known result that <a href="http://en.wikipedia.org/wiki/Compass-and-straightedge_construction#Angle_trisection">trisecting an arbitrary angle is impossible</a> we argue that the only case when the construction is impossible is when N % 3 == 0. </p>
<p>If N % 3 == 0, then construction is impossible because it implies that we can trisect the angle of size 3 - contradiction.</p>
<p>So we assume that N % 3 != 0. We will show that in that case we can construct an angle of size 1 which implies that we can divide the angle of size N into N equal angles of size 1.</p>
<p>First <a href="http://www.quora.com/How-do-you-construct-an-angle-of-36-degrees-using-only-a-ruler-and-a-compass">construct an angle of size 36</a>.</p>
<p>Next, <a href="http://www.wikihow.com/Construct-a-60-Degrees-Angle-Using-Compass-and-Ruler">construct an angle of size 60</a> and <a href="http://www.wikihow.com/Construct-a-Bisector-of-a-Given-Angle">bisect</a> it in order to get an angle of size 30.</p>
<p>Using these two angles construct an angle of size 6 using subtraction 36 - 30 = 6.</p>
<p>Next, use bisection to divide an angle of size 6 into in order to get an angle of size 3.</p>
<p>Finally, since N % 3 != 0, we can construct an angle of size 1 using an angle of size N and an angle of size 3 - because you can construct an angle of size N - 1 if N % 3 == 2 or you can construct an angle of size N + 1 if N % 3 == 1. In any case, you can use subtraction to construct an angle of size 1.</p>
<p>It is clear that if you have an angle of size 1, you can "fill" the orginal angle of size N with N angles of size 1.</p>
<p>Ok, we proved that it is possible to construct an angle of size 1 if N % 3 != 0. We can implement this construction proof in order to output the exact steps, but it is quite complicated. The second method which was widely used by contestants is to bisect an angle of size N until you construct an angle of size 1 with sufficient precision, which is a lot easier to implement.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>To be uploaded soon.</p>
<h1>RELATED PROBLEMS:</h1>
<p>To be uploaded soon.</p>pkacprzakTue, 16 Dec 2014 04:46:32 +0530https://discuss.codechef.com/questions/58550/dividen-editorialbinary-searchmediumeditorialgeometryanglesdec14CAPPLE - Editorialhttps://discuss.codechef.com/questions/58423/capple-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/CAPPLE">Practice</a><br>
<a href="http://www.codechef.com/DEC14/problems/CAPPLE">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/ma5termind">Sunny Agarwal</a><br>
<strong>Tester 1:</strong> <a href="http://www.codechef.com/users/xiaodao">Minako Kojima</a><br>
<strong>Tester 2:</strong> <a href="http://www.codechef.com/users/shiplu">Shiplu Hawlader</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>CAKEWALK</p>
<h1>PREREQUISITES:</h1>
<p>Adhoc</p>
<h1>PROBLEM:</h1>
<p>You are given a multiset S of N numbers. Your task is to erase all elements from S. If all elements in S have the same value, you can erase all of them in one move. In the other case, you are allowed to make one specific action: pick any subset A of S such that all elements in A have the same value x, and change values of all elements in A to some y, such that y < x and there is at least one element in S with a value y. Your task is to return the minimum possible number of moves after which S is empty.</p>
<h1>QUICK EXPLANATION:</h1>
<p>The answer for this question is the number of distinct values in S.</p>
<h1>EXPLANATION:</h1>
<p>The first observation is that in order to erase all elements of S you have to reduce S to another multiset in which all elements have the same value.</p>
<p>Let d be the number of distinct elements in S. </p>
<p>The second observation is that you have to make at least d moves, because if you made k < d moves, then there exists a move and a value x in S such that you didn't pick x in that move, so you cannot erase it.</p>
<p>The third observation is that you can erase all elements of S in exactly d moves. For example, we can do the following:</p>
<p>Let x_1 < x_2 < ... < x_{d-1} < x_d be the values of elements in S.</p>
<p>In first move we pick all elements with value x_d and we reduce their values to x_{d-1}. In the second move, we pick all elements with value x_{d-1} and we reduce their values to x_{d-2} and so on. After d-1 steps all elements in S have value x_1 and in one move we can erase them.</p>
<p>Based on the second and the third observation we conclude that the minimum number of moves to do the task is d.</p>
<p>Time Complexity:</p>
<p>O(N) time complexity per one testcase. Since all values are small (up to 10^5) you can count the number of distinct elements using a simple look-up array.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>To be uploaded soon.</p>
<h1>RELATED PROBLEMS:</h1>
<p>To be uploaded soon.</p>pkacprzakMon, 15 Dec 2014 19:43:35 +0530https://discuss.codechef.com/questions/58423/capple-editorialad-hocdec14editorialcakewalkChef Under Pressure - CHEFPRES TLEhttps://discuss.codechef.com/questions/64935/chef-under-pressure-chefpres-tle<p>can you please tell me why LCA by RMQ giving TLE , and lca by naive approach is AC .i think logarithmic time must AC then leaner O(N) for every query.</p>
<p>LCA by RMQ : <a href="http://www.codechef.com/viewsolution/5595001">my source-rmq-TLE</a></p>
<p>LCA by naive : <a href="http://www.codechef.com/viewsolution/6316592">my source-naive-AC</a></p>joney_000Thu, 19 Feb 2015 19:13:30 +0530https://discuss.codechef.com/questions/64935/chef-under-pressure-chefpres-tlermqgraphchefprestlelcadec14SEAGCD - Editorialhttps://discuss.codechef.com/questions/58496/seagcd-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/SEAGCD">Practice</a><br>
<a href="http://www.codechef.com/DEC14/problems/SEAGCD">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/sereja">Sergey Nagin</a><br>
<strong>Tester 1:</strong> <a href="http://www.codechef.com/users/xiaodao">Minako Kojima</a><br>
<strong>Tester 2:</strong> <a href="http://www.codechef.com/users/shiplu">Shiplu Hawlader</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>MEDIUM</p>
<h1>PREREQUISITES:</h1>
<p>Number theory</p>
<h1>PROBLEM:</h1>
<p>You are given 4 integers: N, M, L, R. Your task is to count the number of arrays consisting of N elements less or equal M, for which the greatest common divisor of all elements in one such array is a number in range [L, R]. Since this number can be quite big, calculate it modulo 10^9 + 7.</p>
<h1>QUICK EXPLANATION:</h1>
<p>At the first look the problem may look quite difficult, but actually it is not. The crucial thing here is to look at it a little out of box and define two tables:</p>
<p>Let A[d] be the number of arrays consisting of N elements less or equal M, for which the greatest common divisor of all elements is divisible by d.</p>
<p>Let B[d] be the number of arrays consisting of N elements less or equal M, for which the greatest common divisor of all elements is equal d.</p>
<p>I encourage you to come up with a solution based on these two definitions. If you want a more briefly description, please check the next section.</p>
<h1>EXPLANATION:</h1>
<p>For the definitions of A[d] and B[d] please check the previous section.</p>
<p>First observe that for a fixed d, A[d] equals (M / d)^N, because for every position in an array, you can choose any of M / d elements from range [1..d] (there are M / d elements divisible by d in that range).</p>
<p>Let's assume, that you want to compute B[d] and you have already computed B[2 * d], B[3 * d], ..., B[k * d], where k is a maximum number for which k * d <= M.</p>
<p>Let S := B[2 * d] + B[3 * d] + ... + B[k * d]</p>
<p>In order to compute B[d], we just need to observe that B[d] = A[d] - S. It is very clear if you look again at the definitions of A[d] and B[d].</p>
<p>Based on the above fact, we can compute B[d] in a decreasing order of d, i.e. d = M, M - 1, M - 2, ..., 1.</p>
<p>Using this method, you can write a really nice and compact solution (remember to calculate
the answer modulo 10^9 + 7):</p>
<p>In the following code, mypow(a, b) is a function which compute (a^b) mod (10^9 + 7) using fast exponentiation. </p>
<p>First snippet presents an idea in pseudo-code of an implementation while the second one represents my solution and it is fast enough to pass all testcases and it is written in C++. Pseudo-code omits calculating the result modulo 10^9 + 7 in order to achieve better readability.</p>
<p>Pseudo code:
</p><pre>answer = 0;
for(d = M; d >= 1; --d)
A[d] = mypow(M / d, N);
S = 0;
k = 2 * d;
while(k <= M)
S += B[k];
k += d;
B[d] = A[d] - S;
if(d >= L && d <= R)
answer += B[d];
print answer
</pre><p></p>
<p>C++ code:</p>
<p>You have to be aware of time limit here, so calculate modulo only if needed and do not compute A[d] for every d, because if M / d1 == M / d2, then A[d1] = A[d2].</p>
<pre>int answer = 0;
int last = -1;
int power;
for(int d = M; d >= 1; --d)
{
int div = M / d;
if(div != last)
{
power = mypow(div, N);
last = div;
}
A[d] = power;
int S = 0;
int k = 2 * d;
while(k <= M)
{
S += B[k];
if(S >= MOD) S %= MOD;
k += d;
}
B[d] = A[d] - S;
if(B[d] < 0) B[d] += MOD;
if(B[d] >= MOD) B[d] %= MOD;
if(d >= L && d <= R)
{
answer += B[d];
if(answer >= MOD) answer %= MOD;
}
}
cout << answer << endl;
</pre>
<p>Time Complexity:</p>
<p>The time complexity here is O(M * log(M)) per one testcase, because we loop over M values in the main loop and the inside while-loop takse O(log(M)) time. Also computing A[d] takes O(M * log(M)) time.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>To be uploaded soon.</p>
<h1>RELATED PROBLEMS:</h1>
<p>To be uploaded soon.</p>pkacprzakMon, 15 Dec 2014 22:50:26 +0530https://discuss.codechef.com/questions/58496/seagcd-editorialdec14mediumnumber-theoryeditorialRIN - Editorialhttps://discuss.codechef.com/questions/60251/rin-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/RIN">Practice</a> <br>
<a href="http://www.codechef.com/DEC14/problems/RIN">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/cgy4ever">Gaoyuan Chen</a> <br>
<strong>Tester 1:</strong> <a href="http://www.codechef.com/users/xiaodao">Minako Kojima</a> <br>
<strong>Tester 2:</strong> <a href="http://www.codechef.com/users/shiplu">Shiplu Hawlader</a> <br>
<strong>Editorialist 1:</strong> <a href="http://www.codechef.com/users/mogers">Miguel Oliveira</a> <br>
<strong>Editorialist 2:</strong> <a href="http://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>HARD</p>
<h1>PREREQUISITES:</h1>
<p>Max-flow, Graphs</p>
<h1>PROBLEM:</h1>
<p>You are given N courses and M semesters. X[i][j] is the expected grade which you will get for completing the i-th course in j-th semester or -1 if i-th is not taught in j-th semester.
You are also given K prerequisites. Each one is in form (i, j) and means that course i has to be taken before course j.</p>
<p>Your task is to compute the maximum possible expected average grade if you have to take every course exactly once.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Model the problem and prerequisites as <a href="http://en.wikipedia.org/wiki/Minimum_cut">min-cut</a> / <a href="http://en.wikipedia.org/wiki/Maximum_flow_problem">max-flow</a> problem and find a max-flow in it corresponding to the maximum achievable expected sum of grades.</p>
<h1>EXPLANATION:</h1>
<p>First, let's ignore the dependencies. The answer is just the maximum grade per course in any of the semesters, which is trivial to compute but let's put this in another perspective: </p>
<blockquote>
<p>For each course, the best grade is <strong>100 - (minimum grade we lose by picking one of the semesters)</strong>. </p>
</blockquote>
<p>To model this as a network flow graph, we do 4 things:</p>
<ol>
<li>Create a vertex for each pair (course <em>i</em>, semester <em>j</em>).</li>
<li>Create a source vertex which is connected to the first semester of each course <em>i</em> by an edge with capacity <strong>100 - grade(i, 1)</strong>.</li>
<li>For every semester <em>j</em> from 2 to <strong>M</strong>, connect the vertices of each course <em>i</em> from semester <strong>j-1</strong> to <strong>j</strong> with capacity <strong>100 - grade(i, j)</strong> or <strong>100</strong> if the course is not available (it's the same as having grade 0, recall that it's guaranteed there is a solution).</li>
<li>Create a sink vertex and connect the last semester of each course to it, with infinite capacity.</li>
</ol>
<p>Consider the following example with 3 courses and 3 semesters:</p>
<pre><code>3 3
10 70 100
80 50 40
80 20 40
</code></pre>
<p><img alt="alt text" src="http://discuss.codechef.com/upfiles/codechef_rin2.png"></p>
<p>The corresponding graph is depicted in the above picture. The maximum flow is equal to the combined grade loss for all courses. We pick semester 3 for course 1 (zero loss), and semester 1 for courses 2 and 3 (loss 20+20).
The maximum grade average we can get is <strong>(N * 100 - maxflow) / N</strong>. In this case: (3*100 - 40) / 3 ~= 86.67.</p>
<p><strong>- Returning to the problem, why does this help?</strong></p>
<p>If we model the problem this way, we can also include the course dependencies. Suppose there are dependencies 1->2 and 1->3. The best we can do is course 1 in semester 2 and courses 2 and 3 in semester 3 for (70+40+40)/3 average.</p>
<p><strong>- If there are dependencies 1->2 and 1->3, then courses 2 and 3 can never be done in the first semester.</strong></p>
<p>This implies that the minimum grade loss for courses 2 and 3 is <strong>not bounded</strong> by its grades in semester 1. This is the same as changing the capacities associated to semester 1 of courses 2 and 3 to infinity.</p>
<p><strong>- Why do we pick semester <em>j</em> for course 1?</strong></p>
<p>The combined grade loss of doing course 1 in semester 2 + courses 2 and 3 in semester 3 is less than doing course 1 in semester 1 + courses 2 and 3 in semesters 2 or 3. </p>
<p>In terms of network flow, this means that</p>
<ul>
<li>if we pick semester <em>j = 1</em>, then courses 2 and 3 are not bounded by grade loss in semester 1. To combine the grade loss by picking semester 1, we connect vertex (course 1, semester 1) to (course 2, semester 2) and (course 3, semester 2) with infinite capacity.</li>
<li>if we pick semester <em>j = 2</em>, then courses 2 and 3 are not bounded by grade loss in semesters 1 and 2. Same as above but connecting (course 1, semester 2) to courses 2 and 3, semester 3.</li>
<li>picking semester <em>j = 3</em> is not possible.</li>
</ul>
<p>The resulting network is the following</p>
<p><img alt="alt text" src="http://discuss.codechef.com/upfiles/codechef_rin3.png"></p>
<p>We can see that the maximum flow is 150. The best is to distribute the grade loss of course 1 in semester 2, flow 3, among courses 2 and 3 in semester 3. In fact, 70+40+40 = 300 - 150.</p>
<p>To give you another example, consider the input</p>
<pre><code>3 3 2
10 50 100
80 90 40
80 40 70
1 2
1 3
</code></pre>
<p>The best we can do course 1 at semester 1 (10) + course 2 at semester 2 (90) and course 3 at semester 3 (70) = 10+90+70. The resulting graph is </p>
<p><img alt="alt text" src="http://discuss.codechef.com/upfiles/codechef_rin4.png"></p>
<p>We can see that the maximum flow is 130 because in this case, it is better to distribute the grade loss of course 1 at semester 1, the flow 90, among the grade loss of courses 2 and 3 over semesters 2 and 3, respectively.</p>
<p>In a nutshell, we create a graph with N*M+2 vertices and use a standard maximum flow algorithm. The hard part was to realize how to build the network correctly.</p>
<p><strong>Proof sketch</strong>:</p>
<p>Since <a href="http://en.wikipedia.org/wiki/Maximum_flow_problem">max-flow</a> equals <a href="http://en.wikipedia.org/wiki/Minimum_cut">min-cut</a>, we can think of our problem as of finding a minimum cut in the above graph. Let P<sub>i</sub> be a path corresponding to i-th course, i.e. the path formed of edges corresponding to i-th course in all semesters. In order to prove the correction of the above construction, we can show two properties of the graph:</p>
<ol>
<li>For every 1 <= i <= N, min-cut contains exactly one edge from P<sub>i</sub>.</li>
<li>For every constraint (i, j), if min-cut contains the k-th edge of P<sub>i</sub>, then it contains the x-th edge of P<sub>j</sub>, where x > k i.e. j-th course is taken in later semester than i-th course.</li>
</ol>
<p>These two fact can be shown quite easily, but we will omit exact proofs here. Intuitively, if you pick any edge from P<sub>i</sub>, then P<sub>i</sub> is disconnected and there is no need for taking any other edge from it. Moreover, an edge (i, j) corresponding to a constraint, prevent us of taking course j before course i, because if you did it, then in order to make the graph disconnected, you would have to add the second edge of P<sub>j</sub> to min-cut which contradicts the first fact. </p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>To be uploaded soon.</p>
<h1>RELATED PROBLEMS:</h1>
<p>To be uploaded soon.</p>mogersMon, 29 Dec 2014 23:27:41 +0530https://discuss.codechef.com/questions/60251/rin-editorialgraphhardrineditorialmaxflowdec14XOR with subset.Not understanding the logic of dp!https://discuss.codechef.com/questions/76827/xor-with-subsetnot-understanding-the-logic-of-dp<pre><code></>dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]</>
</code></pre>
<p>How is this arrived at.Why does A[0...i-1] having value j necessarily mean that A[0...i] should also posses the value j?</p>
<p>And why is this :</p>
<p>if there exists a subset P of A[1..i - 1] such that F(P) = j ^ a[i], then F(P) ^ a[i] = j ? </p>getsugaWed, 11 Nov 2015 13:45:41 +0530https://discuss.codechef.com/questions/76827/xor-with-subsetnot-understanding-the-logic-of-dpdynamic-programmingdec14solvinglong-contesthelpXORSUB - Editorialhttps://discuss.codechef.com/questions/58422/xorsub-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/XORSUB">Practice</a><br>
<a href="http://www.codechef.com/DEC14/problems/XORSUB">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/darkshadows">Lalit Kundu</a><br>
<strong>Tester 1:</strong> <a href="http://www.codechef.com/users/xiaodao">Minako Kojima</a><br>
<strong>Tester 2:</strong> <a href="http://www.codechef.com/users/shiplu">Shiplu Hawlader</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>SIMPLE</p>
<h1>PREREQUISITES:</h1>
<p>DP, bits</p>
<h1>PROBLEM:</h1>
<p>You are given an array A of N integers and an integer K. Your task is to return the maximum possible value of F(P) xor K, where P is a subset of A and F(P) is defined as a xor of all values in P. If P is empty, then F(P) = 0.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Since each element of A has a value of at most 1000, we can use dynamic programming dp[i][j] := 1 if and only if there exists a subset P of A[1..i] such that F(P) = j. In order to get the result, we return max 1 <= j <= 1023 { dp[n][j] * (j ^ k) }</p>
<h1>EXPLANATION:</h1>
<p>Let dp[i][j] := 1 if and only if there exists a subset P of A[1..i] such that F(P) = j, otherwise 0</p>
<p>The first observation is that F(P) can be at most 1023 since any input number is at most 1000.</p>
<p>Initially we set all dp[i][j] := 0.</p>
<p>Next, we set dp[0][0] := 1, since a xor of the empty set is 0.</p>
<p>We iterate over all elements of A from left to right. For each A[i], we iterate over all possible values of the xor function i.e. a range from 0 to 1023 inclusive and update these values as follows:</p>
<pre><code>for i = 1 to N:
for j = 0 to 1023:
dp[i][j] = dp[i - 1][j] | dp[i - 1][j ^ a[i]]
</code></pre>
<p>The reason for this is that if there exists a subset P of A[1..i - 1] such that F(P) = j then there exists also a subset of A[1..i] such that F(P) = j or if there exists a subset P of A[1..i - 1] such that F(P) = j ^ a[i], then F(P) ^ a[i] = j, so there exists a subset P' of A[1..i] such that F(P') = j</p>
<p>At the end we have dp[n][j] for all 0 <= j <= 1023, and we can return a maximum value of dp[n][j] * (j ^ k) for all j.</p>
<p>Time Complexity:</p>
<p>The time complexity per one testcase is O(N * 1023);</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>To be uploaded soon.</p>
<h1>RELATED PROBLEMS:</h1>
<p>To be uploaded soon.</p>pkacprzakMon, 15 Dec 2014 19:41:28 +0530https://discuss.codechef.com/questions/58422/xorsub-editorialsimpledynamic-programmingdec14biteditorialSANSKAR - Editorialhttps://discuss.codechef.com/questions/58420/sanskar-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/SANSKAR">Practice</a><br>
<a href="http://www.codechef.com/DEC14/problems/SANSKAR">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/mendax">Jay Pandya</a><br>
<strong>Tester 1:</strong> <a href="http://www.codechef.com/users/xiaodao">Minako Kojima</a><br>
<strong>Tester 2:</strong> <a href="http://www.codechef.com/users/shiplu">Shiplu Hawlader</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY</p>
<h1>PREREQUISITES:</h1>
<p>DP, bits</p>
<h1>PROBLEM:</h1>
<p>Given a set S of N integers the task is decide if it is possible to divide them into K non-empty subsets such that the sum of elements in every of the K subsets is equal.</p>
<h1>QUICK EXPLANATION:</h1>
<p>We use dynamic programming to solve it. If the solution exists, each subsets has to have a sum of its elements equal to the sum of all elements in S divided by K. Let X be that value. Let dp[k][bitmask] = 1 if and only if it is possible to divide a subset A of S denoted by the bitmask into k subsets each with sum X or to divide A into k - 1 subsets of sum X and one subset of sum < X. For a single dp[k][bitmask] entry, we will iterate over all elements of S which are not in A and try to extend current solution. The answer is "yes" if and only if dp[K][bitmask denoting the whole set S] = 1, and because we try to extend dp states only for k < K, we are sure than dp[K][bitmask] denotes if it is possible to divide a subset denoted by bitmask into K subsets with equal sums (see explanation below). </p>
<h1>EXPLANATION:</h1>
<p>Let SUM be the sum of all elements in S. If SUM % K != 0, then the answer is "no" because there is no way to divide elements equally.</p>
<p>Let X = SUM / K.</p>
<p>Let dp[k][bitmask] = 1 if and only if it is possible to divide a subset A of S denoted by the bitmask into k subsets each with sum X or to divide A into k - 1 subsets with sum X and one subset with sum < X.</p>
<p>Initially all entries in dp are set to 0.</p>
<p>At the beginning, we set dp[0][0] = 1 because it is possible to create 0 subsets with equal sums using no elements.</p>
<p>In the main loop, we iterate over all values k = 0, 1, ..., K - 1 denoting the number of subsets for which we try to extend our solution and over all subsets of S denoted by a bitmask. Let A be a subset denoted by a bitmask. For a given dp[k][bitmask] we compute how much we have to add to the k+1th subset in order to get k+1 subsets, each with a sum X. We do that by subtracting k * X from the sum of elements in A. Then we iterate over all elements of S which are not in A and we try to extend our solution (see the code below):</p>
<p>Let a be an array denoting the set S. I omit the case when SUM % K != 0.</p>
<pre>for k = 0 to K - 1:
for bitmask = 0 to 2^n - 1:
if not dp[k][bitmask]:
continue
sum = 0
for i = 0 to n - 1:
if (bitmask & (1LL << i)):
sum += a[i]
sum -= k * x
for i = 0 to n - 1:
if (bitmask & (1LL << i)):
continue //there is nothing to extend
new_mask = bitmask | (1LL << i) //bitmask denoting a set with i-th element added
if sum + a[i] == x: //we can fill the k+1 th subset with elements of sum X using a set of elements denoted by new_mask
dp[k + 1][new_mask] = 1
else if sum + a[i] < x: //we can fill k subsets with elements of sum X and one subsets with sum < X using a set of elements denoted by new_mask
dp[k][new_mask] = 1
if dp[K][2^n - 1] == 1:
print "yes"
else:
print "no"
</pre>
<p>Time Complexity:</p>
<p>The time complexity per one testcase is O(K * 2^N * N)</p>
<h1>SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/DEC14/setter/SANSKAR.cpp">here</a>.</p>
<p>Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/DEC14/tester/SANSKAR.cpp">here</a>.</p>
<p>Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/DEC14/editorialist/SANSKAR.cpp">here</a>.</p>
<h1>RELATED PROBLEMS:</h1>
<p>To be uploaded soon.</p>pkacprzakMon, 15 Dec 2014 19:36:13 +0530https://discuss.codechef.com/questions/58420/sanskar-editorialdynamic-programmingbitdec14easyeditorialCHEFPRES - Editorialhttps://discuss.codechef.com/questions/58416/chefpres-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/CHEFPRES">Practice</a><br>
<a href="http://www.codechef.com/DEC14/problems/CHEFPRES">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/kamranmaharov">Kamran Maharov</a><br>
<strong>Tester 1:</strong> <a href="http://www.codechef.com/users/xiaodao">Minako Kojima</a><br>
<strong>Tester 2:</strong> <a href="http://www.codechef.com/users/shiplu">Shiplu Hawlader</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>MEDIUM</p>
<h1>PREREQUISITES:</h1>
<p>Trees, dfs</p>
<h1>PROBLEM:</h1>
<p>You are given a tree of N nodes and a special node B. Each node v has asocciated an unique integer, let's denote this integer by f(v). Your task is to provide an answer for each of q following queries. A single query consists of two integers, A and P. Let D(v) denotes the minimum distance between the unique path from A to v in the tree i.e. the minimum distance between A and any node on the path. The answer for a single query (A, P) is a node v for which f(v) = P and D(v) is minimum among all such nodes. If there is more than one such node, you should return the one with minimum number.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Root a tree in B using dfs. During this dfs compute dp[v][c] := minimum node u in v's subtree for which f(u) = c or INF if there is no such node.</p>
<p>Using second dfs, for each v and c, compute ans[v][c] := dp[u][c] where u is the first node on the path from v to B for which dp[u][c] != INF or -1 if no such node exists</p>
<p>For each query (A, P), return ans[A][P].</p>
<h1>EXPLANATION:</h1>
<p>The method mentioned in quick explanation is straightforward, but let's take a look why it works.</p>
<p>Consider a single query (A, P). Let dist(u) be a distance from node u to the root of the tree, i.e. to node B. Let's assume that the result for this query is a node v. Then D(v) <= dist(A), because A is the first node of the path to v. Since we are looking for a v for which D(v) is maximal, the best thing we can do is to search for it in A's subtree, because if there exists a v in that subtree for which f(v) = P, then D(v) = dist(A) and we cannot do better. If there is no such v in A's subtree, we search (based on the same argument) for the next greatest value of D(v) in a subtree rooted in the parent of A. We continue this process unless we find v, for which f(v) = P or we reach node B. If we reach B and doesn't find a node v for which f(v) = P, the answer is -1.</p>
<p>In order to do that, we compute dp[v][c] := minimum node u in v's subtree for which f(u) = c or INF if there is no such node.</p>
<p>If implemented naively, that method has O(n^2) running time, which may pass here, but we can do better.</p>
<p>Using the second dfs, for each v and c, compute ans[v][c] := dp[u][c] where u is the first node on the path from v to B for which dp[u][c] != INF or -1 if no such node exists. This is similar to path compression in union-find data structure.</p>
<p>Using ans table, we can answer any query in O(1) time.</p>
<p>Time Complexity:</p>
<p>Time complexity is O(N * K) because for each K, we visit every edge a constant number of times during precomputational phase and we answer each query in constant time.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>To be uploaded soon.</p>
<h1>RELATED PROBLEMS:</h1>
<p>To be uploaded soon.</p>pkacprzakMon, 15 Dec 2014 19:27:48 +0530https://discuss.codechef.com/questions/58416/chefpres-editorialdec14mediumtreeeditorialdfsCHEFBR - Editorialhttps://discuss.codechef.com/questions/58417/chefbr-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/CHEFBR">Practice</a><br>
<a href="http://www.codechef.com/DEC14/problems/CHEFBR">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/berezin">Dmytro Berezin</a><br>
<strong>Tester 1:</strong> <a href="http://www.codechef.com/users/xiaodao">Minako Kojima</a><br>
<strong>Tester 2:</strong> <a href="http://www.codechef.com/users/shiplu">Shiplu Hawlader</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY</p>
<h1>PREREQUISITES:</h1>
<p>DP</p>
<h1>PROBLEM:</h1>
<p>You are given a sequence S of length at most 100 consisting of integers which represents brackets. A negative integer -x is an opening bracket of type x while x is a closing bracket of type x.</p>
<p>A balanced sequence of brackets is defined as usual (see the full problem statement for clarity).</p>
<p>We call a subsequence s of S valid if and only if s is a balanced sequence of brackets. Your task is to count the number of valid subsequences of S modulo 10^9 + 7.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Define a dp[i][j] table where dp[i][j] := number of valid subsequence of S[i..j]. Notice that you can compute dp[i][j] if you know dp[i + 1][j] and positions of a closing bracket of type x in range from i + 1 to j if S[i] is an opening bracket of type x.</p>
<h1>EXPLANATION:</h1>
<p>Since input numbers can be quite large (up to 10^9) we want to compress them at the beginning in order to use them as array indices or use a hash table with O(1) lookup and insert time to do this.</p>
<p>Let pos[i][j][x] := list of positions of occurences of closing bracket of type x in S[i..j]</p>
<p>We can compute pos table in O(n^3) time using simple iteration over all 3 dimensions of it.</p>
<p>Let dp[i][j] := number of valid subsequences of S[i..j]</p>
<p>For simplicity, let's set dp[i][j] := 1 for i > j.</p>
<p>Let's assume that we have dp[i + 1][j] already computed. We want to extend it to dp[i][j]. There are two cases:</p>
<ol>
<li>We don't take a bracket at the i-th position, so dp[i][j] += dp[i + 1][j]</li>
<li>If the bracket at the i-th position is an opening bracket of type x, we can try to take it to our subsequence.</li>
</ol>
<p>While the first case is clear, the second one requires an explanation. If there are k closing brackets of type x in S[i + 1..j] we have k different possibilities to extend shorter subsequences, i.e. dp[i][j] += dp[i + 1][b - 1] * dp[b + 1][j] where b is a single position of a closing bracket of type x in S[i + 1..j]. Since we have pos table computed, we can get values for b using a quick lookup.</p>
<p>Time Complexity:</p>
<p>The time complexity is O(N^3) because computing pos and dp tables takes this much time and any other computation step doesn't have greater complexity.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>To be uploaded soon.</p>
<h1>RELATED PROBLEMS:</h1>
<p>To be uploaded soon.</p>pkacprzakMon, 15 Dec 2014 19:29:42 +0530https://discuss.codechef.com/questions/58417/chefbr-editorialdynamic-programmingdec14easyeditorial