Questions Tagged With ltime43https://discuss.codechef.com/tags/ltime43/?type=rssquestions tagged <span class="tag">ltime43</span>enSat, 31 Dec 2016 21:43:51 +0530SBSWAP - Editorialhttps://discuss.codechef.com/questions/89661/sbswap-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/SBSWAP">Practice</a> <br>
<a href="https://www.codechef.com/LTIME43/problems/SBSWAP">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>MEDIUM-HARD</p>
<h1>PREREQUISITES:</h1>
<p>Trees, Sqrt-decomposition</p>
<h1>PROBLEM:</h1>
<p>For a given tree with $N$ nodes and weight assigned to them, the goal is to handle $Q$ queries, each of one of the following $3$ types: either for given node $v$ return the sum of values in $v$’s subtree, or for given node $v$ and integer $x$, add $x$ to values of all nodes in $v$’s subtrees, or for a given two nodes $v, u$ swap their subtrees if they are disjoint or print $-1$ otherwise.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Use sqrt-decomposition to handle the queries. There are at least a few approaches to that, but the idea is to maintain a data structure of size at most $O(\sqrt Q)$ rebuilding it in $O(N)$ time when it exceeds the size limit. Handle each query in the linear time in terms of the size of this data structure. This leads to $O(\sqrt Q \cdot N + Q \cdot \sqrt Q)$ time solution </p>
<h1>EXPLANATION:</h1>
<h1>Subtask 1</h1>
<p>In the first subtask we have both $N$ and $Q$ at most $1000$, so a very direct approach is possible. For each query adding values to all nodes in a subtree and for each query asking for the sum of values in some subtree we can just traverse the given subtree in $O(N)$ time. For a query representing a swap of subtree of nodes $v$ and $u$, we can first in $O(N)$ time check if one of them is ancestor of the other, which happens if and only if these subtrees are not disjoint. In this case we return $-1$, otherwise, we can explicitly remove these subtree from their parents and attach them to their new parents in the tree. Since each query can be handled as described in $O(N)$ time, the total time complexity is $O(Q \cdot N)$.</p>
<h1>Subtask 2</h1>
<p>In the second subtask we have $N \leq 10^5$ and $Q \leq 10^5$, but no swap queries to handle. In this case we can linearize the input tree using $dfs$. The idea is that each time $dfs$ discovers a node we append it to the linear representation and each time $dfs$ exists from a node we also append it there. Thus each node $v$ appears in this order exactly twice and the range of entries between these two occurrences of $v$ is a linear representation of $v$’s subtree. Having this linear representation of the whole tree, we can build a segment tree from this representation and answer both required queries in this subtask in $O(\log(N))$ time per single query. This results in $O(Q \cdot \log(N))$ total time complexity.</p>
<h1>Subtask 3</h1>
<p>In the last subtask constraints for $N$ and $Q$ are the same as in the second subtask, however a query swapping two subtrees is allowed here. This makes the problem significantly harder.</p>
<p>One can try different approaches here including: link-cut trees, some variations of splay-trees, treaps and similar, which may be successful - you can take a look at successful submissions from the contest where contestants used treap and link-cut trees. One more easy approach is to use technique called sqrt-decomposition. There are also various approaches using this concept, like for example very interesting tree compressions (not covered here). One possibility application of sqrt-decomposition is used in <a href="https://www.codechef.com/download/Solutions/LTIME43/Setter/SBSWAP.cpp">my solution</a> and described below. The solution is documented, so you refer to it for implementation details. The general idea is the following: </p>
<p>We are going to maintain a data structure $S$, which is a list of ranges corresponding to some subtrees of the input tree. These ranges will be build using linear tree representation. Let $enter[v]$ be the index where $v$ occurs for the first time in the linear representation and $exit[v]$ the index where it occurs last there. Initially, we put only one range corresponding to the whole tree to $S$. This range can be represented as two endpoints: $[enter[1], exit[1]]$. Whenever any query involving a subtree of $v$ has to be handled, what we do first is to “isolate" $v$’s ranges from ranges in $S$. </p>
<p>The process of isolating has to result in $S$ having a range with left endpoint equal to $enter[v]$ and a range (the same or not) with the right endpoint corresponding to $exit[v]$. This can be done in $O(S)$ time by iterating over ranges in $S$. </p>
<p>Also, with each range we are going to keep the number of vertices entered within in, sum of values of vertices entered within it and the accumulated value added to this range from queries adding values to subtrees. All these informations can be updated dynamically in $O(1)$ time when we slice some range into parts in order to isolate a range. Moreover, these information are sufficient to answer all queries. Notice that in order to find the sum of values in $v$’s subtree it is sufficient to first isolate $v$’s ranges and then summing up values of all ranges between range containing $enter[v]$ and ending with the range containing $exit[v]$. The query adding value of $x$ to $v$’s subtree can be performed analogously. </p>
<p>The last remaining query type is the one swapping subtrees of $v$ and $u$. First we isolate their ranges. Then we check if the subtrees intersect, which can be done by checking if a range containing any endpoint of one of them lies between segments corresponding to endpoints of the other. If this is the case we print $-1$, otherwise perform a swap of these two blocks of ranges, i.e. we take the first block of ranges as all ranges between the range containing $enter[v]$ and the range containing $exit[v]$. The second block consists of all ranges between the range containing $enter[u]$ and the range containing $exit[u]$. We swap these two blocks in $S$. </p>
<p>Each of the queries can be handled in $O(S)$ time when performed as described above. However, with each query the size of $S$ grows by at most $4$, so the queries becomes more costly after some time. The trick to prevent this is to rebuild $S$ from scratch after $O(\sqrt Q)$ queries. The process of rebuilding results in a new tree with new linear representation and $S$ containing again just one range. This process can be done in $O(N)$ time - refer to [my solution] for implementation details. This assures that $S$ is always of size $O(\sqrt Q)$, so the total time complexity of the solution is $O(\sqrt Q \cdot N + Q \cdot \sqrt Q)$.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><br>
Setter's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME43/Setter/SBSWAP.cpp">here</a>. <br>
Tester's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME43/Tester/SBSWAP.cpp">here</a>. </p>pkacprzakSat, 31 Dec 2016 21:43:51 +0530https://discuss.codechef.com/questions/89661/sbswap-editorialsbswaplink-cut-treeltime43treesqrt-decomptreapeditorialmedium-hardFLYMODE - Editorialhttps://discuss.codechef.com/questions/89649/flymode-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/FLYMODE">Practice</a> <br>
<a href="https://www.codechef.com/LTIME43/problems/FLYMODE">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>SIMPLE</p>
<h1>PREREQUISITES:</h1>
<p>Sorting, sweep line</p>
<h1>PROBLEM:</h1>
<p>For a list of $N$ positive consecutive heights: $h_1, h_2, \ldots, h_N$ denoting some heights at which a plane was during its flight and knowing that between heights $h_i$ and $h_{i+1}$ it was flying the shortest path between these height, which means it was at every height between these two ones once, find the maximum integer $K$, such that the plane was $K$ times at some height during the flight.</p>
<h1>QUICK EXPLANATION:</h1>
<p>For every pair of consecutive heights $h_i, h_{i+1}$ add each of these heights as either opening or closing time event to a list of all events, let’s call it $E$, happening in time. Sort $E$ and process it using sweep line keeping track of the number of current opened events that has not been closed. The result is the maximum number of opened events during this process.</p>
<h1>EXPLANATION:</h1>
<h1>Subtask 1</h1>
<p>In this subtask $N$ is at most $1000$ and we know that each $h_i \leq 1000$. This allows the following approach:</p>
<p>Let $K$ be the result to the problem and $H$ be the set of some candidate heights such that the plane was at some $h \in H$ exactly $K$ times. If $H$ is not too big, then we can for each $h \in H$ check how many times the plane was at height $h$ by iterating over all two consecutive input heights $h_i, h_{i+1}$ and counting the number of such pairs that contain $h$. The answer to the problem is the maximal such count. This approach has the time complexity of $O(|H| \cdot N)$, but how to chose $H$? Well, we can take advantage of the fact that $h_i \leq 1000$. Important thing to notice is that the height on which the plane was the most number of times can be a real number, not integer. However, the crucial observation is that we can put to $H$ all positive integers not greater than $1000$ and also floating points exactly between them, so $1.5, 2.5, \ldots$. Is turns out that these candidate heights are sufficient because all input heights are integers.</p>
<h1>Subtask 2</h1>
<p>In the second subtask $N$ can be at most $10^5$ and each $h_i \leq 10^9$, so method described above will take too much time. The crucial observation to approach the problem is to notice that if $K$ is the answer to the problem, there exists height $h$ for which there exists $i$ such that $\min(h_i, h_{i+1}) \le h \le \max(h_i, h_{i+1})$ and the plane was at height $h$ exactly $K$ times. Thus the problem can be reduced to finding a point which is covered by most of these height pairs and returning the maximum size of such cover. Let’s think of pairs of consecutive heights as segments from the smaller to the larger height. Notice that changing height from $h_i$ to $h_{i+1}$ corresponds to one such segment. Moreover, the reduced problem can be easily solved using a <a href="https://en.wikipedia.org/wiki/Sweep_line_algorithm">sweep line</a> algorithm by sorting all endpoints of the segments, then processing them from left to right counting the number of opened segments and returning the maximal such count during this process. The complexity of this solution is $O(N \cdot \log(N))$ dominated by the sorting phase.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><br>
Setter's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME43/Setter/FLYMODE.cpp">here</a>. <br>
Tester's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME43/Tester/FLYMODE.cpp">here</a>. </p>pkacprzakSat, 31 Dec 2016 18:41:47 +0530https://discuss.codechef.com/questions/89649/flymode-editorialsortingflymodeltime43simpleeditorialline-sweepMSTQS - Editorialhttps://discuss.codechef.com/questions/89653/mstqs-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/MSTQS">Practice</a> <br>
<a href="https://www.codechef.com/LTIME43/problems/MSTQS">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>MEDIUM</p>
<h1>PREREQUISITES:</h1>
<p>Graph theory, Minimum Spanning Tree, Kruskal's algorithm</p>
<h1>PROBLEM:</h1>
<p>This problem is all about <a href="https://en.wikipedia.org/wiki/Minimum_spanning_tree">Minimum Spanning Tree</a>, which we call $MST$ here. For a given graph $G$ with $N$ vertices and $M$ weighted edges, the goal is to handle $Q$ queries. Each query can either assign $0$ weight to given existing edge in $G$ or assign to a given edge its original weight, or ask for the weight of $MST$ of the current graph $G$.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Take a closer look at how does <a href="https://en.wikipedia.org/wiki/Kruskal's_algorithm">Kruskal’s algorithm</a> work and notice that the answer for each query asking for the weight of the current $MST$ can be computed by running Kruskal’s algorithm only on edges with zero weight and edges in the initial $MST$ of $G$.</p>
<h1>EXPLANATION:</h1>
<h1>Subtask 1</h1>
<p>In the first subtask we have $N \leq 200, M \leq 2000$ and $Q \leq 2000$, so we can just keep track of the current weights of the edges while performing queries and for each query asking for the weight of the current $MST$, we can run any fast algorithm computing $MST$ from the scratch, for example <a href="https://en.wikipedia.org/wiki/Kruskal's_algorithm">Kruskal’s algorithm</a>. This solution has time complexity of $O(Q \cdot f(N, M))$, where $f(N, M)$ is the complexity of used $MST$ algorithm on a graph with $N$ vertices and $M$ edges. Notice that this results in $O(Q \cdot M \cdot \log^*(M))$ time for Kruskal's algorithm even when full sorting is performed only at the beginning.</p>
<h1>Subtasks 2 and 3</h1>
<p>In these subtasks we have $N \leq 2000$, $M \leq 2 \cdot 10^5$ and $Q \leq 20000$.</p>
<p>The following approach can be used to solve both of these subtasks, the only difference is that in the last subtask one have to handle restoring original weights of edges, which is just a little bit more straightforward implementation.</p>
<p>Let’s first compute $MST$ of the initial graph before performing any queries and let $T$ be this $MST$. The crucial observation is that at any point while handling the queries, the weight of the $MST$ of the current graph can be computed by running <a href="https://en.wikipedia.org/wiki/Kruskal's_algorithm">Kruskal’s algorithm</a> on edges with zero weight at this point and edges of $T$. </p>
<p>Why is this observation correct? Well, if we take a closer look at how does this algorithm work, we can see that it iterate over a list of given edges in ascending order of their weights and put the current edge into the result if and only if it connects not yet connected components of $G$. So if we run it on edges with zero weight and edges from $T$, it will merge some components using some of these zero edges first and then try edges from $T$ if necessary. Since the algorithm is only merging components, it follows that no edge not it $T$ with non-zero edge at this point will be used by the algorithm, because after processing edges with zero weights, some edges from $T$ might not be needed, but if any two components still require to be merged, the algorithm will do it with an edge from $T$ just as it did in the initial graph. </p>
<p>Thus in order to solve the problem, one can maintain the list of edges with zero weights updating it when necessary - this can be done in $O(1)$ time if for example a linked list is used, and for each query asking for the weight of the current $MST$ run <a href="https://en.wikipedia.org/wiki/Kruskal's_algorithm">Kruskal’s algorithm</a> on at most $O(Q + N)$ edges. Theoretically this results in $O(Q \cdot (Q + N) \cdot \log^*(N))$ complexity, but notice that in order for $K$ zero edges to be processed by the algorithm, we have to perform $K$ queries adding them first, so the factor of $Q^2$ is divided by some constant of at least $4$ here.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><br>
Setter's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME43/Setter/MSTQS.cpp">here</a>. <br>
Tester's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME43/Tester/MSTQS.cpp">here</a>. </p>pkacprzakSat, 31 Dec 2016 19:35:31 +0530https://discuss.codechef.com/questions/89653/mstqs-editorialmediumltime43graphkruskalmstmstqseditorialCodeChef Plans the Date and Time for Contests a Year Ahead of Timehttps://discuss.codechef.com/questions/72046/codechef-plans-the-date-and-time-for-contests-a-year-ahead-of-time<p>I have found that CodeChef actually plans their contest much ahead of time. For example<br>
</p><ul>
<li><a href="http://www.codechef.com/DEC16">The December Challenge 2016 has been set from Friday, 2nd December, 2016 15:00 to Saturday, 12th December, 2016 15:00 (IST)</a></li>
<li><a href="http://www.codechef.com/COOK77">The December Cook-Off 2016 has been set from Sunday, 18th December, 2016 at 21:30 to Monday, 19th December, 2016 at 00:00 (IST)</a></li>
<li><a href="http://www.codechef.com/LTIME43">The December Lunchtime 2016 has been set on Friday, 25th December, 2016 from 11:00 A.M. to 2:00 P.M. (IST)</a>
</li></ul>
I found this by mistyping the date for <a href="http://www.codechef.com/COOK59">COOK59</a> as <a href="http://www.codechef.com/COOK60">COOK60</a> instead and then I started experimenting from there after I saw that the July Cook-Off has already been planned. It seems that December 2016 is the last month for which contests have been planned. Are these dates and times subject to change or will these be the exact time for the contests in December 2016? Thank you for looking at this!<p></p>noble_mushtakMon, 22 Jun 2015 03:08:30 +0530https://discuss.codechef.com/questions/72046/codechef-plans-the-date-and-time-for-contests-a-year-ahead-of-timecontestltime43SUPVIL - Editorialhttps://discuss.codechef.com/questions/89644/supvil-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/SUPVIL">Practice</a> <br>
<a href="https://www.codechef.com/LTIME43/problems/SUPVIL">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>CAKEWALK</p>
<h1>PREREQUISITES:</h1>
<p>Basic programming</p>
<h1>PROBLEM:</h1>
<p>For a given list $N$ people, where each is either a superhero or a villain, joining the fight between superheroes and villains in the given order, decide which side wins or if the fight ends up with a draw. Superheroes win immediately at the earliest time when there are $2$ more superheroes fighting than villains. Villains win immediately at the earliest time when there are $3$ more villains fighting than superheroes. If none of these cases happens, then the fight results in a draw.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Whenever a person joins the fight check if one of the sides wins. If yes, print the name of winning group, otherwise continue. If no side wins after all people joined, print draw.</p>
<h1>EXPLANATION:</h1>
<p>Solutions to both subtasks are based on the approach described in quick explanation, but they differ complexity of checking if one side wins.</p>
<h1>Subtask 1</h1>
<p>In the first subtask $N$ is at most $500$, so after every person joining the fight, one can count the number of superheroes already fighting and villains already fighting, and then decide if either of the sides wins. This results in $O(N^2)$ solution, because for each of $N$ people joining the fight, in $O(N)$ time we are counting the number of superheroes and villains already fighting.</p>
<h1>Subtask 2</h1>
<p>In the second subtask $N$ is at most $10^5$, so counting people from the scratch after every joining person will take too much time. However this can be easily avoided by keeping track of counters of superheroes and villains already fighting. After each person joining the fight, we increment exactly one of these counters depending on the type of the joining person and check if either group wins using these counters. This approach works in $O(N)$ time.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><br>
Setter's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME43/Setter/SUPVIL.py">here</a>. <br>
Tester's solution can be found <a href="https://www.codechef.com/download/Solutions/LTIME43/Tester/SUPVIL.cpp">here</a>. </p>pkacprzakSat, 31 Dec 2016 17:39:47 +0530https://discuss.codechef.com/questions/89644/supvil-editorialltime43basic-progsupvileditorialcakewalk