Questions asked by AnonymousBunnyhttps://discuss.codechef.com/questions/asked-by/74683/anonymousbunny/?type=rssQuestions asked by <a href="/users/74683/anonymousbunny" >AnonymousBunny</a>enTue, 01 Mar 2016 02:19:54 +0530INOI 2015 resultshttps://discuss.codechef.com/questions/64504/inoi-2015-results<p>So, the scores of INOI have been sent to the participants individually. How did you guys do? Share your scores here. Let's make a guess about the cutoff.</p>
<p>My story was a bit sad-- I got a zero, which was what I expected since the code I submitted for P2 was the raw undebugged version (which I didn't get time to polish up). However, turns out that it only required a few tweaks to work (my debugged code: <a href="http://ideone.com/MaHnLi">http://ideone.com/MaHnLi</a> ; parts in comments are the portions I couldn't debug and included in my submission)-- the debugged code now gives the correct answer for all testcases! I mailed them in the hope that they would make these minor fixes, to which they said they can't. So I guess a zero it is. So close. :(</p>
<p>Anyways, here are some of the scores I know of:</p>
<p>Sreejato Bhattacharya (me): 0 </p>
<p>Sagnik Majumder (dibyo_99): 120</p>
<p>Mriganka Basu Roy Chowdhury (mbrc): 200</p>
<p>Debjit Paria (debjit99): 100</p>
<p>Others willing to share their scores here? Also, I believe Sameer Gulati and Malvika Raj Joshi both got 200?</p>
<p>(Sorry if this was a double post; I can't find any similar posts made recently.)</p>AnonymousBunnySat, 14 Feb 2015 19:29:45 +0530https://discuss.codechef.com/questions/64504/inoi-2015-resultsinoi2015finding shortest path in a graph with good and bad edgeshttps://discuss.codechef.com/questions/74583/finding-shortest-path-in-a-graph-with-good-and-bad-edges<p>Hi everyone!</p>
<p>I've been stuck on this problem for a while: <a href="http://wcipeg.com/problem/ccc11s2p2">http://wcipeg.com/problem/ccc11s2p2</a></p>
<p>Basically, you're given a weighted undirected graph with n vertices and m edges (n<=1600, m<=10^5) where some of the edges are good and others bad. You have to find the shortest path between two vertices among all such paths whose sum of weights of bad edges is at most a given threshold S (S<=3600).</p>
<p>I tried modifying Dijsktra's algorithm (add a vertex to the visited set only if the sum of bad edges on the path from the source to that vertex is at most S)- but it's not too hard to find testcases for which this fails.</p>
<p>Any help will be appreciated. Thanks :)</p>AnonymousBunnySun, 30 Aug 2015 22:30:22 +0530https://discuss.codechef.com/questions/74583/finding-shortest-path-in-a-graph-with-good-and-bad-edgesgraphdijkstrahelpshortest-pathSWPERMS - Editorialhttps://discuss.codechef.com/questions/79746/swperms-editorial<p></p><h2>Problem link:</h2> <a href="https://www.codechef.com/IPC15P3A/problems/SWPERMS">Contest</a> <br> <a href="https://www.codechef.com/problems/SWPERMS">Practice</a> <p></p>
<p></p><h2>PROBLEM:</h2><p></p>
<p>A permutation <b>P= (p[1], p[2], ..., p[n])</b> of <b>(1, 2, ..., n)</b> is written on a blackboard. You have <b>m</b> pairs of integers <b>(x_i, y_i)</b>. At any stage you can choose a pair <b>(x, y)</b> and swap the values of <b>p[x]</b> and <b>p[y]</b> (note that <b>P</b> is still a permutation after this operation). Initially <b>P= (1, 2, ..., n)</b>. Find the number of different permutations you can obtain after finite number of operations.
<br><br> </p> <p> </p><h2>TL;DR:</h2> <p>
Consider an undirected graph with vertices <b>1, 2, ..., n</b> where there is an edge between <b>x</b> and <b>y</b> for each given pair <b>(x, y)</b>. Let $c_1, c_2, \cdots , c_t$ be the sizes of the connected components of this graph. The answer will be $(c_1)!\cdot (c_2)! \cdots (c_t)!$
<br> <br> </p> <p> </p><h2> FULL SOLUTION: </h2> <p>
Let's consider the graph where the vertices are labelled <b>1, 2, ..., n</b> and pairs are edges. Note that swapping a pair <b>(x, y)</b> is equivalent to switching the labels of the vertices across the corresponding edge. <br> <br>
<b>Observation 1:</b> If there is no path from <b>u</b> to <b>v</b> in this graph, it is not possible to get a permutation <b>P</b> where <b>P[u]= v</b>. <br>
<b>Proof:</b> Suppose otherwise that it is possible to apply the swaps in some order that the label of vertex <b>u</b> is at the position of vertex <b>v</b> . Let $ t_1, t_2, ..., t_k$ be the successive vertices with which <b>u</b> was swapped- this means the edges $u-t_1, t_1-t_2, \cdots , t_{k-1}-t_k$ and $t_k-v$ are all present in our graph, i.e. there is a path from <b>u</b> to <b>v</b>. Contradiction. <br> <br></p>
<p>From observation 1, we find out that if <b>u</b> and <b>v</b> are in different connected components their positions cannot be interchanged. We can now treat each connected component separately. Let $f(i)$ be the number of ways the <b>i</b>'th component can be permuted, then the answer will be simply $f(1) \cdot f(2) \cdots f(t)$ where <b>t</b> is the number of connected components.</p>
<p>Now we shall prove that all possible permutations of a component can be obtained after finitely many operations, i.e. all $k!$ permutations of a connected component of size <b>k</b> can be attained. Note that this is equivalent to proving that if the graph is connected, all $n!$ permutations are achievable. <br> <br></p>
<p><b>Claim:</b> If the graph is connected, all permutations of <b>1, 2, ..., n</b> can be obtained. <br>
<b>Proof:</b> There are probably multiple ways to prove this. Here's a simple one. We'll prove that for all <b>u≠v</b>, it is possible to apply the swaps in such a way that the positions of all other elements are unchanged and those of <b>u</b> and <b>v</b> are interchanged. Since the graph is connected, there exists a simple path $t_1, t_2, ..., t_k$ from <b>u</b> to <b>v</b>. Apply the operations $u-t_1, t_1-t_2, ...., t_{k-1}-t_k, t_k-v$ - this brings the label of <b>u</b> to the position of <b>v</b> and the label of <b>v</b> to the position of $t_k$. Apply the operations $t_k-t_{k-1}, t_{k-1}-t_{k-2}, ..., t_1-u$ again- now all other labels are at their original positions and those of <b>u</b> and <b>v</b> were interchanged. Thus we can always say <b>(u, v)</b> is one of the pairs given to us (even though it isn't)- because there exists a sequence of allowed operations which has the exact same effect. Now we can simply claim to have all $\binom{n}{2}$ pairs available and it's easy to get to the conclusion. <br> <br></p>
<p>This claim shows that the number of permissible permutations of the <b>i</b>'th connected component is $(c_i)!$ where $c_i$ is its size. Thus, the answer is $(c_1)! \cdot (c_2) ! \cdots (c_t)!$ where <b>t</b> is the number of connected components. This can be found in <b>O(m+n)</b> with a plain dfs.</p>AnonymousBunnyTue, 01 Mar 2016 01:58:10 +0530https://discuss.codechef.com/questions/79746/swperms-editorialeditorialad-hocipc15p3aswpermsswpermeasyGROADS- Editorialhttps://discuss.codechef.com/questions/79749/groads-editorial<p></p><h2>Problem link:</h2> <a href="https://www.codechef.com/IPC15P3A/problems/GROADS">Contest</a> <br> <a href="https://www.codechef.com/problems/GROADS">Practice</a> <p></p>
<p></p><h2>PROBLEM:</h2><p></p>
<p>Given an unweighted undirected graph, an edge <b>u-v</b> is called interesting iff for all other vertices <b>w</b>, <b>w</b> is connected to either <b>u</b> or <b>v</b> (or maybe both). Find the number of interesting edges. </p>
<p></p> <p> </p><h2>TL;DR:</h2> <p> </p>
<p>At least one of the vertices in any interesting edge must have degree $\geq n/2$ where <b>n</b> is the total number of vertices, and the number of such vertices is pretty small.
<br> </p> <p> </p><h2> FULL SOLUTION: </h2> <p></p>
<p>Let's see how to find the number of interesting edges passing through a fixed vertex <b>v</b> in <b>O(m+n)</b>. Make an array <b>cnt[1 ... n]</b> where <b>cnt[i]=0</b> for all <b>i</b> initially. For each vertex <b>u≠v</b> which is not a neighbor of <b>v</b>, add 1 to <b>cnt[w]</b> for all <b>w</b> that is a neighbor of <b>u</b>. After this is done, <b>cnt[i]</b> will store the number of non-neighbors of <b>v</b> adjacent to <b>i</b>. Now note that in an interesting edge <b>u-v</b>, <b>u</b> must be connected to all vertices <b>v</b> isn't connected to, so <b>u-v</b> will be interesting iff <b>cnt[i]= n-1-degree(v)</b>. Unfortunately we cannot do this for every vertex because that could take up to <b>O(n^2)</b> time. <br> <br></p>
<p><b>Observation:</b> If <b>u-v</b> is an interesting edge, the degree of at least one of <b>u</b> and <b>v</b> is $\geq n/2$. <br>
<b>Proof:</b> If the degrees of <b>u</b> and <b>v</b> are both less than n/2, they are adjacent to less than $n/2+n/2= n$ vertices in total, so this edge cannot be interesting.
<br> <br>
The key fact now is that the number of vertices with degree $\geq n/2$ is quite small: in fact it's at most $4m/n$ (otherwise the sum of degrees would exceed $4m/n \cdot n/2= 2m$). Since $n(n-1)/2\geq m$, we have $n \geq O(\sqrt{m}) \implies m/n \leq O(\sqrt{m})$. This gives us a simple $O((m+n)\sqrt{m})$ solution: iterate over all vertices with degree $\geq n/2$, find the number of interesting edges passing through this vertex and add it to the answer. You must be careful about double counting some of the edges (or you could just insert the edges in a set and print the size of the set).</p>AnonymousBunnyTue, 01 Mar 2016 02:19:54 +0530https://discuss.codechef.com/questions/79749/groads-editorialipc15p3agraphsgroadseasyeditorial