Questions Tagged With june18https://discuss.codechef.com/tags/june18/?type=rssquestions tagged <span class="tag">june18</span>enWed, 01 Aug 2018 02:16:43 +0530Doubt Regarding CCDSAP Scholarship Discount for June Long Challengehttps://discuss.codechef.com/questions/128803/doubt-regarding-ccdsap-scholarship-discount-for-june-long-challenge<p>This is regarding the 100% discount feature for CCDSAP announced for June Long Challenge. The criteria for availing the scholarship for Div 2 is 400+ points and highest rank in institution. Here is my doubt, I am the only student in my institution(school) participating in the contest, in this case only if I get 400+ points, will I be able to avail the scholarship or is there a minimum amount of participants from an institution in order for the institution topper to be selected ?</p>jagreetdgSat, 09 Jun 2018 22:20:32 +0530https://discuss.codechef.com/questions/128803/doubt-regarding-ccdsap-scholarship-discount-for-june-long-challengeccdsapjune18scholarshipHelp in Two Flowerhttps://discuss.codechef.com/questions/128929/help-in-two-flower<p>Can someone help me to figure out how do i Improve my code? i am only getting TLE in Two Cases.
<a href="https://www.codechef.com/viewsolution/18864036">link</a></p>rds_98Mon, 11 Jun 2018 17:28:57 +0530https://discuss.codechef.com/questions/128929/help-in-two-flowerhelpjune18Problem Sheokand and Stringhttps://discuss.codechef.com/questions/128938/problem-sheokand-and-string<p>Help me out with the test case for which the below mentioned code fails </p>
<p><a href="https://www.codechef.com/viewsolution/18830461">https://www.codechef.com/viewsolution/18830461</a></p>
<p>This problem is from JUNE 18 Division 2 Sheokand and String </p>sreekar1999Mon, 11 Jun 2018 17:55:30 +0530https://discuss.codechef.com/questions/128938/problem-sheokand-and-stringshkstrjune18Invitation to CodeChef June Long Challenge 2018!https://discuss.codechef.com/questions/128234/invitation-to-codechef-june-long-challenge-2018<p>Hello CodeChef Community!
We’re excited to announce the June Long Challenge 2018. We hope to see you all join us in these ten intense days of coding challenges. Joining me on the problem setting panel are:</p>
<ul>
<li>Problem Tester: <a href="https://www.codechef.com/users/mgch">mgch</a> (Misha Chorniy) </li>
<li>Problem Authors: <a href="https://www.codechef.com/users/adlet_zeineken">adlet_zeineken</a> (Adlet Zeineken), (Noszaly Aron), (Jitender Sheora), (Phuc Hong), (Rehijm Memmedli), <a href="https://www.codechef.com/users/teja349">teja349</a> (D Teja Vardhan Reddy), <a href="https://www.codechef.com/users/pieguy">pieguy</a> (David Stolp), <a href="https://www.codechef.com/users/barenuz">barenuz</a> (Ihor Barenblat),
<a href="https://www.codechef.com/users/ratingoverflow">ratingoverflow </a> (Tianyi Qiu)</li>
<li>Problem Editorialist: <a href="https://www.codechef.com/users/likecs">likecs</a> (Bhuvnesh Jain) </li>
<li>Statement Verifier: <a href="https://www.codechef.com/users/xellos0">xellos0</a> (Jakub Safin)</li>
<li>Russian Translator: <a href="https://www.codechef.com/users/xcwgf666">xcwgf666</a> (Sergey Kulik)</li>
<li>Mandarin Translator: <a href="https://www.codechef.com/users/huzecong">huzecong</a> (Hu Zecong) </li>
<li>Vietnamese Translator: VNOI Team </li>
</ul>
<h3>Contest Details:</h3>
<p><strong>Time:</strong> 1st June 2018 (1500 hrs) to 11th June 2018 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=CodeChef+June+Challenge+2018&iso=20180601T15&p1=44">timezone</a>. </p>
<p><strong>Contest link:</strong> <a href="https://www.codechef.com/JUNE18">https://www.codechef.com/JUNE18</a></p>
<p><strong>Registration:</strong> You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to <a href="https://www.codechef.com/signup">register</a> in order to participate.</p>
<p><strong>Prizes:</strong> Top 10 global and top 20 Indian winners get 300 Laddus each, with which the winners can claim cool CodeChef goodies. Know more here: <a href="https://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie.">https://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie.</a> (For those who have not yet got their previous winning, please send an email to winners@<a href="http://codechef.com">codechef.com</a>). First to solve each problem individually: 100 laddus (For problems common to both Divisions, only one user will get laddus for that problem).</p>
<p>Good Luck!<br>
Hope to see you participating!!<br>
Happy Programming!!</p>mgchFri, 01 Jun 2018 10:46:06 +0530https://discuss.codechef.com/questions/128234/invitation-to-codechef-june-long-challenge-2018june18long-contestSheokand and String june 2018 longhttps://discuss.codechef.com/questions/129031/sheokand-and-string-june-2018-long<p><a href="https://www.codechef.com/JUNE18B/problems/SHKSTR/">https://www.codechef.com/JUNE18B/problems/SHKSTR/</a>
Above is the link to the problem</p>
<p><a href="https://www.codechef.com/viewsolution/18863280">https://www.codechef.com/viewsolution/18863280</a></p>
<p>Above is the solution for the problem. I dont know why it is giving SIGSEV. It runs perfectly on my local machine. The implementation is that of Trie data structure. Please help.</p>satyamholmesMon, 11 Jun 2018 23:25:42 +0530https://discuss.codechef.com/questions/129031/sheokand-and-string-june-2018-longsigsevjune18NAICHEF - Editorialhttps://discuss.codechef.com/questions/128585/naichef-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/NAICHEF">Practice</a></p>
<p><a href="https://www.codechef.com/JUNE18B/problems/NAICHEF">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/adlet_zeineken">Adlet Zeineken</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>CAKEWALK</p>
<h1>Prerequisites</h1>
<p>Probability, Looping</p>
<h1>Problem</h1>
<p>You are given an N sided dice. You roll it twice and need to find the probability of getting A on the first throw and B on the second throw.</p>
<h1>Explanation</h1>
<p>The probability of obtaining a number on the consecutive throw of a dice is independent of each other. For more details, you may refer <a href="https://www.wyzant.com/resources/lessons/math/statistics_and_probability/probability/further_concepts_in_probability">here</a>. The probability of getting a number $X$ on throwing a $N$ sided dice is given by:</p>
<p>$$\text{Probability} = \frac{\text{Number of times X appears on the dice}}{N}$$</p>
<p>Thus, the overall probability of obtaining A on the first throw and B on the second throws is given by:</p>
<p>$$\text{Required Probability} = \frac{\text{Number of times A appears on the dice}}{N} * \frac{\text{Number of times B appears on the dice}}{N}$$</p>
<p>Thus, the problem reduces to finding the frequency of a number in an array. This can be easily done in $O(1)$ space complexity and $O(n)$ time complexity using a simple for loop as below</p>
<pre><code>
def count_frequency(array a, integer x):
count = 0
for number in a:
if number == x:
count += 1
return count
</code>
</pre>
<p>The constraints of the problem were such that all the operations can be done in integers only without any overflow issues.</p>
<h1>Time Complexity</h1>
<p>$O(n)$ per test case.</p>
<h1>Space Complexity</h1>
<p>$O(1)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/JUNE18/tester/NAICHEF.cpp">here</a>.</p>
<p>Editorialist's solution can be found <a href="https://github.com/likecs/Codechef-June-18-/blob/master/naive_chef.cpp">here</a>.</p>likecsWed, 06 Jun 2018 01:25:20 +0530https://discuss.codechef.com/questions/128585/naichef-editorialadlet_zeinekenjune18probabilitylikecseditorialcakewalkSheokand and String(SHKSTR) TLEhttps://discuss.codechef.com/questions/129112/sheokand-and-stringshkstr-tle<p>While solving this question I first used a Map (Key: Character, Value: TrieNode) to solve the problem. Considering O(1) insertion and lookup, my code should not have resulted in TLE but when I used an array of length 26 to store trie nodes, the code got accepted. So should I avoid using maps or dictionaries in CP and why? Is this because its time complexity for insertion and lookups is not exactly O(1)?</p>
<p><a href="https://www.codechef.com/viewsolution/18804544">Solution using Map</a>: 30 points</p>
<p><a href="https://www.codechef.com/viewsolution/18805239">Solution using array of length 26</a>: 100 points</p>baap_42Tue, 12 Jun 2018 11:20:54 +0530https://discuss.codechef.com/questions/129112/sheokand-and-stringshkstr-tlemapstriesshkstrjavajune18getting wa although using the same approach as online solution mentioned in editorialhttps://discuss.codechef.com/questions/129116/getting-wa-although-using-the-same-approach-as-online-solution-mentioned-in-editorial<p><a href="https://www.codechef.com/JUNE18B/problems/SHKSTR/">https://www.codechef.com/JUNE18B/problems/SHKSTR/</a> <a href="https://ideone.com/eFFVqJ">https://ideone.com/eFFVqJ</a> Here I am using unordered_map in trie to reduce unnecessary space but I have tried it directly also still getting wa. I am adding string no. to vector of strings at that position only if string having greater index than the last element in vector is lexicographically smaller than it</p>rogue_one1Tue, 12 Jun 2018 12:38:25 +0530https://discuss.codechef.com/questions/129116/getting-wa-although-using-the-same-approach-as-online-solution-mentioned-in-editorialtriejune18Help with Sheokand and String (SHKSTR)https://discuss.codechef.com/questions/129207/help-with-sheokand-and-string-shkstr<p>Hi, my solution fails for 2 of the large test cases. I am unable to identify what's wrong in my solution</p>
<p><a href="https://www.codechef.com/viewsolution/18880600" title="title"></a><a href="https://www.codechef.com/viewsolution/18880600">https://www.codechef.com/viewsolution/18880600</a> </p>
<p>Can someone please help me. <strong>Thanks</strong> a lot in advance :)</p>i_luv_sumit001Tue, 12 Jun 2018 20:15:51 +0530https://discuss.codechef.com/questions/129207/help-with-sheokand-and-string-shkstrjune18What's wrong with my submission of TWOFL(June Long)https://discuss.codechef.com/questions/129211/whats-wrong-with-my-submission-of-twofljune-long<p>I implemented the solution of Author given in the editorial, my implementation is same as of him, expect some minor changes in variable names but I keep failing a few test cases in Subtask-2 and 3 while Author's solution passes.</p>
<p>My Solution : <a href="https://www.codechef.com/viewsolution/18880653">https://www.codechef.com/viewsolution/18880653</a>
Author's Solution : <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JUNE18/setter/TWOFL.cpp">https://s3.amazonaws.com/codechef_shared/download/Solutions/JUNE18/setter/TWOFL.cpp</a></p>
<p>What am I doing wrong?</p>sorb1997Tue, 12 Jun 2018 20:29:27 +0530https://discuss.codechef.com/questions/129211/whats-wrong-with-my-submission-of-twofljune-longimplementationlong_challengejune18twoflJune long challenge - difficulthttps://discuss.codechef.com/questions/129343/june-long-challenge-difficult<p>Is it Just me, or did others too feel that the June long challenge for division 2 was a bit too difficult. Usually the first 3 questions are very simple, and another 3 questions are challenging, which would lead me to do about 6 questions per long challenge, but this time i could do only 4. Do you guys feel the same?, and what is the reason for this sudden increase in long challenge difficulty?. Keep in mind I'm new to codechef :).</p>aaronq8Wed, 13 Jun 2018 13:56:44 +0530https://discuss.codechef.com/questions/129343/june-long-challenge-difficultjune18Naive Chef: 3 Different Solutions with Comparisonhttps://discuss.codechef.com/questions/129386/naive-chef-3-different-solutions-with-comparison<p>A comparison of three different solutions for June Long Challenge Problem Naive Chef:</p>
<ol>
<li>Hashmap</li>
<li>Count manually</li>
<li>std::count</li>
</ol>
<p>Watch here: <a href="https://youtu.be/r9yvzd0tTJQ">https://youtu.be/r9yvzd0tTJQ</a></p>code_reportWed, 13 Jun 2018 18:45:24 +0530https://discuss.codechef.com/questions/129386/naive-chef-3-different-solutions-with-comparisonlong-challengenaichefjune18long-contestSHKSTR problem in editorialhttps://discuss.codechef.com/questions/129457/shkstr-problem-in-editorial<p>I have used almost the same approach as the online one. Instead of a vector, i just stored the first occurence of the alphabet and another field which told me the index of the first word which ends there.
But, I am getting a TLE for it. Could you help me find why it is happening?
The link to my solution <a href="https://www.codechef.com/viewsolution/18809047">https://www.codechef.com/viewsolution/18809047</a></p>nayan21gargThu, 14 Jun 2018 08:15:10 +0530https://discuss.codechef.com/questions/129457/shkstr-problem-in-editorialtrieshkstrjune18tlelikecsBIBOARD - Editorialhttps://discuss.codechef.com/questions/128863/biboard-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/BIBOARD">Practice</a></p>
<p><a href="https://www.codechef.com/JUNE18A/problems/BIBOARD">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/ratingoverflow">Tianyi</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>HARD</p>
<h1>Prerequisites</h1>
<p>Flows, Minimum Cut</p>
<h1>Problem</h1>
<p>You are given a grid consisting of $0$(white), $1$(black) and $?$(unknown). You are required to convert $?$ to $0$ or $1$ such that the following cost is maximised:</p>
<p>$$\sum_{i=1}^{\mathrm{min}(N, M)} C_{B, i} \cdot B_i + C_{W, i} \cdot W_i\,.$$</p>
<p>where $B_i$ denotes the number of ways to select a black square of size $i$, $W_i$ denotes the number of ways to select a white square of size $i$ and $C_{B, i}$ and $C_{W, i}$ arrays is provided in input.</p>
<h1>Explanation</h1>
<h2>Subtask 1: N * M ≤ 10</h2>
<p>A simple brute force which converts each $?$ to $0$ or $1$ and calculates the cost of the board is sufficient to pass this subtask. The time complexity of the above approach is $O(2^{NM})$.</p>
<h2>Subtask 2, 3: N * M ≤ 500</h2>
<p>The constraints are small and since the problem is related with maximisation, it hints towards either dynamic programming or flows based solution generally. We will use minimum cut to solve this problem. In case you are not familiar with the topic or its usage in the problem, please you through <a href="https://www.youtube.com/watch?v=kvPOyRQN2eA">this awesome video tutorial</a> by Anudeep Nekkanti.</p>
<p>Now, using the ideas similar in the video, we design the below algorithm.</p>
<ol>
<li>We iterate through each possible square in the grid. If it only consists of white or black cells, add the required cost depending on size to the answer. If it consists of some question marks as well, then we check if it can be converted to only white cells or black cells or both. We optimistically add the required white/black contribution to the answer. (Note that it is similar to the problem where we add all the possible contribution first to the answer, and in order to maximise the final answer, use the minimum cut algorithm to find the minimum contribution which needs to be taken back from the answer. This is the most important step of the problem.). Let the optimistic answer we calculated now be known as "initial ans".</li>
<br>
<li>Now, we construct a graph as follows. Consider a source of a white node and sink of a black node. For every optimistic conversion of a square to white/black you considered (by converting some $?$ to $0$ or $1$), add an edge between a new node to the corresponding white (source) or black (sink) node with the weight of the edge as the cost of that square. Also, add edges of weight INFINITY (some large constant) between every cell containing $?$ to the new node. To get an understanding of the graph construction, see the below diagram showing the graph for the sample case in the problem.</li>
<center><img height="300" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-11_at_1.26.10_AM.png" width="500"></center>
<br>
<li>The answer to the problem is "initial ans - maximum_flow of above graph".</li>
</ol>
<p>To understand why the above algorithm works, we will reason cutting of each edge in terms of minimum cuts and the rewards/penalties it provides.</p>
<p>It is sure that edges of weight INFINITY will never be considered in the minimum cut of the graph. So we consider the remaining 2 scenarios.</p>
<p></p><center><img height="150" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-05_at_9.44.21_PM.png" width="350"></center><p></p>
<p>This image shows the scenario where the edge containing white node (source) and the node representing an optimistic white square of length $L$ is cut. This implies one of the $?$ in the square chose to convert to $1$ instead of $0$. This can happen for whatever reason, for example - It might to costlier to cut the corresponding black edges to which the $?$ node also connects (such a node will exist otherwise there will be no path from white i.e. source to black i.e. sink).</p>
<p></p><center><img height="150" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-05_at_9.43.57_PM.png" width="350"></center><p></p>
<p>This case is similar to above case, just that instead one of the $?$ in the optimistic black square of length $L$ chose to convert to $0$ instead of $1$.</p>
<p>Thus the minimum cut in the above graph will contain edges which tell that the optimistic square which we considered for being white or black will not be actually white or black in the optimal selection because one of $?$ chose to convert to opposite colour. We must thus remove this minimum optimistic answer we added to "initial ans" to obtain the solution to the problem.</p>
<p>Let us now finally analyse the complexity of the above solution. For the worst case, the grid will only consist of $?$ as there are no edges coming out of $0$ or $1$ in the grid. Let $K = min(N, M)$. So there will be $N * M + (N - 1) * (M - 1) + \cdots + (N - K) * (M - K) = O(K^3)$ intermediate white and black nodes i.e. the ones connecting grid cells and also to the corresponding source or sink. For details of the proof, refer to <a href="https://www.geeksforgeeks.org/count-number-of-squares-in-a-rectangle/">this</a>. The number of edges in the graph will be $O(K^4)$ as there can be maximum $O(L^2)$ edges from an intermediate node representing the square of length $L$. Using Dinic Algorithm which has the worst complexity of $O(V^2 * E)$, the overall complexity of the solution will be $O(K^{10})$ ~ $O({(N * M)}^3)$. The hidden constant factor is very low and Dinic's algorithm suffices to solve the problem.</p>
<h3>Extra Observation</h3>
<p>Note that above solution using minimum cut also enables us to print one grid with required cost as well. The construction of such grid is simple. Just consider the edges from white (source) and black (sink) node to the intermediate nodes which are not part of the minimum cut. This means all the cells in the grid connected to it actually retained their preference to colour which was optimistically assigned before to them.</p>
<p>Once, you are clear with the above idea, you can see the editorialist implementation below for help. It also contains the part for printing a possible grid with the conversion of $?$ to $0$ or $1$.</p>
<h3>Author's Editorial for the problem</h3>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>Consider using the minimum cut algorithm. If n < m, swap them.</p>
<p>Let SB denote the prefix sum of CB, and SW is defined similarly.</p>
<p>We define the map S from integer to integer, where:</p>
<ol>
<li>
<p>When i>0 S[i]=SB[i];</p>
</li>
<li>
<p>When i<0 S[i]=SW[-i].</p>
</li>
</ol>
<p>For every grid (i,j), we try to determine the maximum length |l| such that (i,j)-(i+|l|,j+|l|) is a square with solid color. If it is black, l>0; otherwise, l<0.</p>
<p>Thus the answer is sigma{S[l[i][j]]}.</p>
<p>For every (i,j) we create nodes (i,j,l) for -n<=l<=n, and add edges for:</p>
<ol>
<li>
<p>For l<0, (i,j,l) -> (i,j,l+1) cost = inf - S[l];</p>
</li>
<li>
<p>For l>0, (i,j,l-1) -> (i,j,l) cost = inf - S[l];</p>
</li>
<li>
<p>S->(i,j,-n) cost = inf * 2</p>
</li>
<li>
<p>(i,j,n)->T cost = inf * 2</p>
</li>
</ol>
<p>Cutting an edge refers to choosing the corresponding l for (i,j).</p>
<p>Here for certain (i,j), we call the edges described above a "chain".</p>
<p>The reason for adding an inf to every edge is to avoid the cut having multiple edges on the same chain. However, each (i,j) cannot choose its value "l" arbitrary but must follow some constraints.</p>
<p>We first define dist((i,j),(k,l)) = max{i-k,j-l}.</p>
<p>So the constraints are:
1. When (i,j) is black (i.e. l[i][j] > 0), for k<=i and l<=j: l[k][l] > -dist((i,j),(k,l))</p>
<ol>
<li>
<p>When (i,j) is white (i.e. l[i][j] < 0), for k<=i and l<=j: l[k][l] < dist((i,j),(k,l))</p>
</li>
<li>
<p>For every individual (i,j), l[i][j] should take the number with maximum absolute value, while not violating rule 1 and 2.</p>
</li>
</ol>
<p>In the following part we use => sign to denote "lead to" relationship, i.e. A=>B is equivalent to "when A is true, B is true". So we rewrite rule 1 and 2:</p>
<ol>
<li>
<p>l[i][j] > 0 => l[k][l] >= -dist((i,j),(k,l))</p>
</li>
<li>
<p>l[i][j] < 0 => l[k][l] <= dist((i,j),(k,l))</p>
</li>
</ol>
<p>For rule 1, we just link edge : (i,j,0) -> (k,l,-dist((i,j),(k,l))) cost = inf * 2</p>
<p>Easy to see that if the rule is violated, there would be an S-T path.</p>
<p>For rule 2, we just link edge (k,l,dist((i,j),(k,l))) -> (i,j,0) cost = inf * 2</p>
<p>Easy to see that if the rule is violated, there would be an S-T path.</p>
<p>For rule 3: Every CB[i] and CW[i] is positive, so SB and SW are strictly increasing, thus every certain (i,j) will greedily take the value with maximum absolute value even if we don't interfere.</p>
<p>Thus, the minimum cut is the answer.</p>
<p>Dinic or ISAP algorithm is recommended and will find the answer very fast.</p>
</div></div>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h1>Time Complexity</h1>
<p>$O({(N * M)}^3)$</p>
<h1>Space Complexity</h1>
<p>$O({(N * M)}^3)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/JUNE18/setter/BIBOARD.cpp">here</a>.</p>
<p>Editorialist's solution can be found <a href="https://github.com/likecs/Codechef-June-18-/blob/master/binary_board.cpp">here</a>.</p>likecsMon, 11 Jun 2018 02:30:47 +0530https://discuss.codechef.com/questions/128863/biboard-editorialjune18hardminimum-cutlikecseditorialratingoverflowWRKWAYS - Editorialhttps://discuss.codechef.com/questions/128862/wrkways-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/WRKWAYS">Practice</a></p>
<p><a href="https://www.codechef.com/JUNE18A/problems/WRKWAYS">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/sanroylozan">Noszály Áron</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>MEDIUM</p>
<h1>Prerequisites</h1>
<p>Factorisation, Combinatorics</p>
<h1>Problem</h1>
<p>You are given $N$ workers and each of them has a deadline to complete the work, given by $d_i$ for $i^{th}$ worker. Each worker completes the work in $1$ day and on each day at most $1$ worker can work. You need to decide to the array containing the deadline for every worker such that the number of ways in which the workers can decide to work is $C$ and $d_n$ is minimised. Also, the array of deadlines should be sorted.</p>
<h1>Explanation</h1>
<p>Before proceeding towards the solution, we need to find the number of ways in which workers can decide to work for a given array $d_1 ≤ d_2 ≤ \cdots ≤ d_n$.</p>
<p>Consider the case for $n ≤ 3$. Let $d_1 = x, d_2 = y, d_3 = z$. We have the following dynammic programming solution</p>
<p>$$dp[x] = x$$</p>
<p>$$dp[x][y] = dp[x] * (y - x) + dp[x-1] * x = xy - x^2 + x^2 - x$$</p>
<p>$$dp[x][y] = xy - x = (y-1) * dp[x]$$</p>
<p>$$dp[x][y][z] = dp[x][y] * (z - y) + dp[x][y-1] * (y - x) + dp[x-1][y-1] * x$$
$$dp[x][y][z] = (xy - x)(z - y) + (xy - 2x)(y - x) + (xy - 2x - y + 2)x$$
$$dp[x][y][z] = (xyz - xz - 2xy + 2x) = (z - 2) * (xy - x)$$
$$dp[x][y][z] = (z - 2) * dp[x][y]$$</p>
<p>Using the above observations, it is clear that number of ways is $\prod_{i=1}^{i=n} {(d_i - i + 1)}$. We can even prove it combinatorially. The first person has $d_1$ choices, the second one has $(d_2 - 1)$ choices and so on. By the principle of multiplication, the number of ways comes out to be same.</p>
<p>Note the above solution clearly points out that $d_i >= i$. Thus for $C = 1$, the array is $(1, 2, 3, 4, \cdots)$.</p>
<p>Thus, the problem now reduces to finding an array $d_1 ≤ d_2 ≤ \cdots ≤ d_n$ such that $\prod_{i=1}^{i=n} {(d_i - i + 1)} = C$ and $d_n$ is minimised.</p>
<p>Instead of finding $d_1, d_2 \cdots d_n$, we will find sorted array, $d_1, (d_2-1), \cdots, (d_n-n+1)$, such that product of this sequence is $C$ and later add back $(i - 1)$ to every term to ensure that sequence is increasing.</p>
<h2>Subtask 1: N ≤ 10, C ≤ 100</h2>
<p>We can use dynamic programming based solution for this subtask. Let $dp[N][C]$ denote the minimised value of $d_n$ for which the sequence $d_1, d_2, \cdots, d_n$ has number of ways as $C$. The transitions are simple. Let $dp[N][C] = x$. So, we need to find the minimum value for the sequence with $(N - 1)$ terms and product as $(C/x)$. The possible candidates are the divisors of $(C/x)$. So, we try all possible candidates and update our answer whether or not it is possible to form an array with the tried candidate. Once, the dynamic programming table is built, we can simply backtrack it to print the answer.</p>
<p>The time compleixty of the above approach is $O(N * {\sigma_{0}{(C)}}^2)$, where $\sigma_{0}{(C)}$ denotes the number of divisors of $C$.</p>
<p>For details, you can refer to author's solution for the above approach.</p>
<h2>Subtask 2, 3: N ≤ ${10}^6$, C ≤ ${10}^9$</h2>
<p>We may see that for optimal answer, the sequence $d_1, (d_2-1), \cdots, (d_n-n+1)$, looks like the following for large $n$:</p>
<p>[zero or more numbers greater than 1] [bunch of ones] [zeros or more numbers greater than 1]</p>
<p><b>Outline of proof for above claim</b>: Basically we want to show that if we have a solution that is not in the above form, then there's a solution of the above form which has the same last element. We achieve this by moving the blocks of non $1$ elements as a unit, in this part, we will use the monotonicity of array $d$ as an argument to show that the blocks are indeed movable and don't break anything.</p>
<p>The above form is important because increasing $N$ actually just pushes more ones into the middle (if there were a better way to distribute the numbers we would have used it earlier). So to solve, we calculate the optimal sequence for smaller $N$ and then extend the "bunch of ones" in the middle.</p>
<p>In the worst case the above method's complexity is $O(N + (\text{number of prime factors of C}) * {\sigma_{0}{(C)}}^2)$. Because the number of prime factors in the range of ${10}^9$ is $30$ in the worst case and the number of divisors is $1000$ in the worst case, this gives around $3 * {10}^7$ operations per test case.</p>
<p>For more details, you can refer to the setter's or tester's solution below.</p>
<h3>Editorialist Solution: Based on solutions by contestants in the contest (Greedy approach)</h3>
<p></p>
<p><b>Incorrect Solution: Note that the below solution is wrong for small values of $N$. This is because it is not guaranteed that choosing the largest factor at every moment in the below solution will yield an optimal solution. It though will work for cases where $N > \log{C}$ as even the greedy approach will take $O\log{C}$ steps to check optimality for the answer. For details refer to the below comments for some counter cases. Note that in all the test case $N ≤ \log{C}$. </b></p>
<p>We will first store all the factors of $C$. Now, we traverse the factors one by one and check if we can form an array $d_1, (d_2-1), \cdots, (d_n-n+1)$, such that the last element is given factor. Is yes, we simply update the answer. Below is the pseudo-code for checking whether we can find an array with the last element as given factor $x$.</p>
<pre><code>
# facts store the factors of C.
# facts[idx] = x
def check(idx):
ptr = n
prod = c
while ptr > 0:
while prod % facts[idx] != 0
idx -= 1
prod /= facts[idx]
ans[ptr] = facts[idx] + ptr - 1
ptr -= 1
if idx != len(facts)-1 and facts[idx] == (facts[idx+1] - 1):
idx += 1
if idx == 0 or prod == 1:
break
return (prod == 1)
</code>
</pre>
<p>Let us analyse the above pseudo-code. We first try to greedily find the first largest factor of the remaining product. At first step it will be $facts[idx] = x$, the number we want to check. Since in final array we want $d_{(i-1)} ≤ d_i$ and we are finding array $(d_i - i + 1)$, the previous term can now contain a possible larger factor only if it is greater than the previous factor by $1$. The last condition just checks that if the product has become 1, then we know the trivial answer or if the factor to be considered is $1$, the product will remain same. Below is an example iteration of the above for $N = 8$ and $C = 36$. Let the factor to be checked is $x = 2$.</p>
<p>$$\text{facts} = {1, 2, 3, 4, 6, 9, 12, 18, 36}$$</p>
<p>$$\text{Step 1} = {\cdots, 2}$$</p>
<p>$$\text{Step 2} = {\cdots, 3, 2}$$</p>
<p>$$\text{Step 3} = {\cdots, 3, 3, 2}$$</p>
<p>$$\text{Step 4} = {\cdots, 2, 3, 3, 2}$$</p>
<p>Since the prod now becomes $1$ we break. To build the required array we add the offsets $(i - 1)$ to the array.</p>
<p>Thus, required array is $(1, 2, 3, 4, 6, 8, 9, 9)$. Note that this may or may not be the optimal solution. It just shows how we check if a given factor can form the series if it is the last term in the sequence.</p>
<p>The time complexity of the above approach will be $O({\sigma_{0}{(C)}}^{2} + N)$. This is because, for every factor, the checking will take $O(\log{C})$ step in the worst case as "prod" variable will decrease by a factor of atleast $2$ in each iteration. But the dominating factor will be the while loop which determines the optimal factor in each iteration and can take up to $\sigma_{0}{(C)}$ operations. The second term, $O(N)$, is for building the complete sequence containing the initial trivial part of $(1, 2, 3, \cdots)$ and printing the answer. The space complexity will be $O(N + sqrt(C))$.</p>
<p>Once, you are clear with the above idea, you can see the editorialist implementation below for help.</p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h1>Time Complexity</h1>
<p>$O(N + (\text{number of prime factors of C}) * {\sigma_{0}{(C)}}^2)$</p>
<h1>Space Complexity</h1>
<p>$O(sqrt(C) + 1000 * sqrt(C) + N)$, where $1000$ denotes the value of small $N$ used by author to solve problem by dynamic programming.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/JUNE18/setter/WRKWAYS.cpp">here</a>.</p>
<p>Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/JUNE18/tester/WRKWAYS.cpp">here</a>.</p>
<p>Editorialist's solution can be found <a href="https://github.com/likecs/Codechef-June-18-/blob/master/work_ways.cpp">here</a>. (<b> Incorrect </b>)</p>likecsMon, 11 Jun 2018 00:59:19 +0530https://discuss.codechef.com/questions/128862/wrkways-editorialmediumjune18combinatoricsobservsationsfactorizationlikecseditorialsanroylozanBINSHFFL - Editorialhttps://discuss.codechef.com/questions/128584/binshffl-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/BINSHFFL">Practice</a></p>
<p><a href="https://www.codechef.com/JUNE18B/problems/BINSHFFL">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/sanroylozan">Noszály Áron</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>EASY</p>
<h1>Prerequisites</h1>
<p>BFS/Floyd Warshall, Observations</p>
<h1>Problem</h1>
<p>You are to convert number $A$ to number $B$ using the following operation in the minimum number of steps:</p>
<ul>
<li>Write A as a binary number with arbitrary number of leading zeros (possibly none)</li>
<li>Shuffle the binary digits of the A in an arbitrary order. Call it $A'$</li>
<li>The output is $(A' + 1)$. Let us call this number as $X$.</li>
</ul>
<p>Remember the notation of $A'$ and $X$ as it is used everywhere in the editorial.</p>
<h1>Explanation</h1>
<h2>Subtask 1: A, B ≤ 128</h2>
<p>The problem asks to minimise the number of steps to go from $A$ to $B$. Generally, these type of problems can be easily modelled as a graph and perform BFS to find the answer. Here is a general idea:</p>
<p>Let us model each step as an edge from initial number to final number with an edge of some cost. So, the path with the smallest weight from source to destination is the required answer and also gives us a way to achieve the transition.</p>
<p>In this problem, we can just do what the operations ask us to do. Just all possible shuffling of the digits of A in binary representation and consider only those ones which give end result within the desired range ([0, 128]). Let us call this number as $X$. Add an edge of weight $1$ from $A$ to $X$. Build the complete graph based on all possible transitions. Make sure that this graph will be directed one as transforming from $A$ to $X$ might not be the same as transforming from $X$ to $A$ due to the last operation which adds $1$ to the result. Once, we have the directed graph, we can simply perform any all pair shortest path algorithm like BFS, Floyd Warshall (or Dynamic Programming as a graph is directed) and precalculate the answer for all possible cases. Once, the answers are precalculated, each test case can be answered in constant complexity. For more details, one can refer to the editorialist solution below.</p>
<p>The maximum number of edges from a number $A$ emerging out will be $7! = 5040$ in the worst case, but in practice, it will be quite less. The number of vertices in the graph will be $128$. Using Floyd Warshall algorithm the precomputation can be achieved in $O(128^3)$, i.e. $O(A^3)$. This is enough to solve this subtask.</p>
<h2>Subtask 2: A, B ≤ ${10}^{18}$</h2>
<p>The constraints in this subtask are quite large and the number of test cases also suggest we need a logarithmic approach. This leads us to write $A$ and $B$ in binary representation and finding some observations to proceed with the solution.</p>
<p>Let us first simplify the approach by trying to convert $A$ to $(B-1)$ as in the end $1$ would be added as part of the last operation.</p>
<p>We can see that in one step we can shuffle the digits of $A$ in such a manner that an extra $1$ is introduced in the binary representation of the newly formed number. This can be done by simply shuffling the digits to contain binary digit $1$ from the ${2}^{nd}$ position. For example: Let $A = 3$. In binary representation $A = 011$. We can shuffle the digits as $A' = 110$. On adding $1$, we get $X = 111$, i.e. $X = 7$. Thus, we can introduce a binary digit $1$ in one step.</p>
<p>Also, we can decrease any number of binary digit $1$ from $A$. This can be done by easily placing the required in the number of $1$ in towards the end, followed by a $0$ and then placing the digits in any order we like. For example: Let $A = 13$, i.e. $A = 1101$ in binary representation. Say we want to decrease one binary digit $1$, we can arrange the digits as $A' = 1011$. On adding $1$, we get $X = 1100$. If we wanted to decrease two binary digit $1$, we can arrange the digits as $A' = 0111$. On adding $1$, we get $X = 1000$. Thus, we decrease any number of binary digit $1$ in one step.</p>
<p>With the above 2 scenarios, the following is the algorithm-</p>
<ol>
<li>Find the number of ones in the binary representation of $A$ and $(B - 1)$. Let us denote then by $OA$ and $OB$</li>
<li>If $OA > OB$, then we can achieve the operation in $2$ steps. First decreasing the number of ones in the first step and then rearranging the digits in another step.</li>
<li>If $OA <= OB$, then we need $(OB - OA)$ steps to first make the number of ones equal (see decrease operation takes place at one step each). Finally, we can arrange the digits to achieve the desired number.</li>
</ol>
<p>The only corner case is as follows:</p>
<ol>
<li>If $B$ is $0$ then, we can't achieve the desired state whatever the value of $A$ is. Since we are adding $1$ in the last step we are guaranteed to have atleast one binary digit $1$ in binary representation. Thus the answer for this case is $-1$.</li>
<li>If $B$ is $1$ then, we can achieve the desired state only if $A = 0$, in one step. In another case, it is impossible as even though decreasing the number of binary digit $1$, the end result would be a number greater than $1$. So the answer is $1$ if $A = 0$, else $-1$.</li>
</ol>
<p>The number of ones in binary representation can be calculated using the below pseudo-code:</p>
<pre><code>
def count_ones(integer x):
ones = 0
while x > 0:
if x % 2 == 1:
ones += 1
x /= 2
return ones
</code>
</pre>
<p>The time complexity of the above pseudo-code will be $O(\log{x})$ as each iteration of the while loop decreases the value of $x$ by $2$.</p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h1>Time Complexity</h1>
<p>$O(\log{A} + \log{B})$ per test case.</p>
<h1>Space Complexity</h1>
<p>$O(1)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/JUNE18/setter/BINSHFFL.cpp">here</a>. (It will pass subtask 1 only and uses dynammic programming approach)</p>
<p>Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/JUNE18/tester/BINSHFFL.cpp">here</a>.</p>
<p>Editorialist's solution for subtask 1 can be found <a href="https://github.com/likecs/Codechef-June-18-/blob/master/binary_shuffle_sub_1.cpp">here</a>.</p>
<p>Editorialist's solution for full problem can be found <a href="https://github.com/likecs/Codechef-June-18-/blob/master/binary_shuffle_full.cpp">here</a>.</p>likecsWed, 06 Jun 2018 01:23:25 +0530https://discuss.codechef.com/questions/128584/binshffl-editorialeditorialfloyd-warshallbinary-numberslikecseasysanroylozanjune18TWOFL - Editorialhttps://discuss.codechef.com/questions/128821/twofl-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/TWOFL">Practice</a></p>
<p><a href="https://www.codechef.com/JUNE18A/problems/TWOFL">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/iloveksh">Stacy Hong</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>MEDIUM</p>
<h1>Prerequisites</h1>
<p><a href="https://en.wikipedia.org/wiki/Breadth-first_search">BFS</a>, <a href="https://en.wikipedia.org/wiki/Depth-first_search">DFS</a>, <a href="https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/">DSU</a>, Sorting</p>
<h1>Problem</h1>
<p>You are given a grid with numbers written on every cell. You are required to find the largest connected component on the grid such that it contains at most 2 distinct numbers in it.</p>
<p>Note that editorial refers to the flowers as numbers.</p>
<h1>Explanation</h1>
<h2>Subtask 1: N, M ≤ 100</h2>
<p>A simple brute force which considers every pair of different numbers and performs BFS on the grid to find the connected component and their sizes is enough to pass this subtask. Below is a pseudo-code for it.</p>
<pre><code>
def solve(c1, c2):
res = 0
for i in [1, n]:
for j in [1, m]:
if vis[i][j] or (a[i][j] != c1 and a[i][j] != c2):
continue
# perform bfs to find size of connected component containing c1 and c2
# update res variable with maximum value
return res
ans = 0
for c1 in [1, 100]:
for c2 in [i, 100]:
# also handle case of one color only.
ans = max(ans, solve(c1, c2))
</code>
</pre>
<p>The time complexity of the above approach is $O(n * m * {\text{Max(a[i][j])}}^{2})$.</p>
<h2>Subtask 2, 3: N, Q ≤ 2000</h2>
<p>The solution approach for last 2 subtasks is same. Just difference in implementation and constant factors can lead to passing subtask 2 only.</p>
<p>The full solution idea relies on the brute force solution above. Instead of doing a complete BFS on the grid every time based on the type of colour you need to consider, we store the edges containing different numbers and do BFS/DSU on it. Below are the 2 different approaches for it.</p>
<h3>Author/Tester Solution: DSU + Sorting/HashMap</h3>
<p>First find all connected components which have the same type of numbers. Store with each component the size of the component and the index of the component as well. This can be easily done with a BFS/DFS. Now create edges between 2 component which are adjacent to each other in the grid i.e. there exists a cell in component $1$ which is adjacent to a cell in component $2$. Store the edges in the following format:</p>
<p>$$\text{{Number in component 1, Number in component 2, Index of component 1, Index of component 2}}$$</p>
<p>To avoid doing the same computation again, store only the edges such that $\text{Number in component 1} < \text{Number in component 2}$. This will help to reduce the constant factor by 2 in your code.</p>
<p>Now, we traverse each edge based on the numbers they connect and perform DSU to find the maximum connected component. Below is the explanation of sample test case in the problem.</p>
<p></p><center>
<img height="150" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-05_at_4.27.54_PM.png" width="250">
<img height="150" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-05_at_4.28.08_PM.png" width="250">
</center><p></p>
<p>The left side image shows the different components formed after the first BFS is done. The second side image shows the result of performing DSU. So, once the BFS is done, we see that cell $(2, 1)$ containing $3$ is adjacent to cell $(1, 1)$ containing $1$, so we merge them using DSU. Again cell $(4, 1)$ containing $1$ is adjacent to cell $(4, 2)$ containing $3$ so, we merge them using DSU. The process continues as cell $(4, 3)$ containing $1$ is adjacent to $(4, 2)$ containing $3$ (which was already expanded before) and the component increases.</p>
<p>The only issue which needs to be taken care while implementing the above solution is resetting of DSU after every iteration. Doing it in naive manner i.e. resetting all the components to original sizes and parent as themselves will TLE even for subtask 2 as the complexity will be similar to subtask 1. Instead, we only restore the values whose parent or size changed while performing the DSU operation. This can be stored while performing the merge operation.</p>
<p>For more details, you can refer to the author's or tester's solution below.</p>
<p>The complexity of the above approach will be $O(n * m * log(n * m))$ as you will traverse each edge once. The logarithmic factor is due to sorting or using maps to store the edges. If you use hash-maps instead to store the edges, the complexity will be $O(n * m)$ but will large constant factor.</p>
<h3>Editorialist Solution: Edge-based Graph traversal</h3>
<p><b>UPDATE: This solution is slow. The author created a counter test against it. The time complexity will be $O(n^2*m^2)$ as pointed out in comments below. Even the test case provided is similar. Please refer to author's solution above for full problem. Will ask Codechef team to add that case in the practice section too for help.</b></p>
<p>Instead of forming any components or performing DSU or doing BFS like the normal way, we see simple observation in the brute force approach. If, each edge connecting adjacent cells in the grid, whether having same numbers or different numbers if traversed at most twice while determining the size, the complexity will be $O(8 * n * m)$ overall. Below is the detailed description of the idea:</p>
<p>First, select an edge in the grid. Find the numbers (at most 2) which will form the component. We will try to find the full component which contains this edge and make sure this component is traversed only once. For this, you start a normal BFS from each cell. You go to adjacent cell only if it is one of the 2 required numbers. While adding the node in the BFS queue, we all update the possible ways in which the edge could be traversed as part of the same component. So, cell $(3, 2)$ containing $2$ was visited from cell $(2, 2)$ containing $1$. But it could be traversed from cell $(3, 3)$ containing $1$ in future and will form the same component. So, we update all 4 directions of a cell can be visited in the same component before adding the cell in BFS queue. The BFS for a component is performed only if the edge was never traversed before in any component. The image below shows how the component is expanded in each step of BFS when the starting edge is selected as $(1, 2)$ and $(1, 3)$.</p>
<p></p><center>
<img height="100" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-10_at_12.57.35_PM.png" width="175">
<img height="100" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-10_at_12.57.26_PM.png" width="175">
</center>
<center>
<img height="100" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-10_at_12.57.41_PM.png" width="175">
<img height="100" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-10_at_12.57.47_PM.png" width="175">
</center>
<center>
<img height="100" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-10_at_12.57.54_PM.png" width="175">
<img height="100" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-10_at_12.58.00_PM.png" width="175">
</center><p></p>
<p>The time complexity of the above approach is $O(n^2*m^2)$ and will pass subtask 1 only.</p>
<p>Once, you are clear with the above idea, you can see the editorialist implementation below for help.</p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h1>Time Complexity</h1>
<p>$O(n * m)$</p>
<h1>Space Complexity</h1>
<p>$O(n * m)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/JUNE18/setter/TWOFL.cpp">here</a>.</p>
<p>Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/JUNE18/tester/TWOFL.cpp">here</a>.</p>
<p>Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/JUNE18/editorialist/TWOFL.cpp">here</a>. (Will TLE).</p>likecsSun, 10 Jun 2018 13:17:57 +0530https://discuss.codechef.com/questions/128821/twofl-editorialmediumjune18dsubfsiloveksheditoriallikecsVSN has a closed form solutionhttps://discuss.codechef.com/questions/129842/vsn-has-a-closed-form-solution<p>I'm not sure to class this as an editorial or whatever, but it's interesting. A well spent few hours digging into this.</p>
<p>I figured during the competition that VSN should have a closed form expression, a quadratic equation in something like 13 variables. It turns out that that is indeed true. After some mathematica magic I derived a “beautiful” formula that solved the problem. As mentioned in another question python3 has TLE problems with the binary search method, with the closed form solution python3 actually passes, albeit with a struggle: <a href="https://www.codechef.com/viewsolution/18916971">18916971</a>.</p>
<p>The formula in python form is</p>
<pre><code>2*cy**2*dx*px + 2*cz**2*dx*px - 2*cx*cy*dy*px - 2*cx*cz*dz*px +
2*cy*dy*px**2 + 2*cz*dz*px**2 - 2*cx*cy*dx*py + 2*cx**2*dy*py +
2*cz**2*dy*py - 2*cy*cz*dz*py - 2*cy*dx*px*py - 2*cx*dy*px*py +
2*cx*dx*py**2 + 2*cz*dz*py**2 - 2*cx*cz*dx*pz - 2*cy*cz*dy*pz +
2*cx**2*dz*pz + 2*cy**2*dz*pz - 2*cz*dx*px*pz - 2*cx*dz*px*pz -
2*cz*dy*py*pz - 2*cy*dz*py*pz + 2*cx*dx*pz**2 + 2*cy*dy*pz**2 -
2*cy**2*dx*qx - 2*cz**2*dx*qx + 2*cx*cy*dy*qx + 2*cx*cz*dz*qx -
2*cy*dy*px*qx - 2*cz*dz*px*qx + 4*cy*dx*py*qx - 2*cx*dy*py*qx +
2*dy*px*py*qx - 2*dx*py**2*qx + 4*cz*dx*pz*qx - 2*cx*dz*pz*qx +
2*dz*px*pz*qx - 2*dx*pz**2*qx + 2*cx*cy*dx*qy - 2*cx**2*dy*qy -
2*cz**2*dy*qy + 2*cy*cz*dz*qy - 2*cy*dx*px*qy + 4*cx*dy*px*qy -
2*dy*px**2*qy - 2*cx*dx*py*qy - 2*cz*dz*py*qy + 2*dx*px*py*qy +
4*cz*dy*pz*qy - 2*cy*dz*pz*qy + 2*dz*py*pz*qy - 2*dy*pz**2*qy +
2*cx*cz*dx*qz + 2*cy*cz*dy*qz - 2*cx**2*dz*qz - 2*cy**2*dz*qz -
2*cz*dx*px*qz + 4*cx*dz*px*qz - 2*dz*px**2*qz - 2*cz*dy*py*qz +
4*cy*dz*py*qz - 2*dz*py**2*qz - 2*cx*dx*pz*qz - 2*cy*dy*pz*qz +
2*dx*px*pz*qz + 2*dy*py*pz*qz - 2*dx*px*r**2 - 2*dy*py*r**2 -
2*dz*pz*r**2 + 2*dx*qx*r**2 + 2*dy*qy*r**2 + 2*dz*qz*r**2 +
sqrt((-2*cy**2*dx*px - 2*cz**2*dx*px + 2*cx*cy*dy*px + 2*cx*cz*dz*px -
2*cy*dy*px**2 - 2*cz*dz*px**2 + 2*cx*cy*dx*py - 2*cx**2*dy*py -
2*cz**2*dy*py + 2*cy*cz*dz*py + 2*cy*dx*px*py + 2*cx*dy*px*py -
2*cx*dx*py**2 - 2*cz*dz*py**2 + 2*cx*cz*dx*pz + 2*cy*cz*dy*pz -
2*cx**2*dz*pz - 2*cy**2*dz*pz + 2*cz*dx*px*pz + 2*cx*dz*px*pz +
2*cz*dy*py*pz + 2*cy*dz*py*pz - 2*cx*dx*pz**2 - 2*cy*dy*pz**2 +
2*cy**2*dx*qx + 2*cz**2*dx*qx - 2*cx*cy*dy*qx - 2*cx*cz*dz*qx +
2*cy*dy*px*qx + 2*cz*dz*px*qx - 4*cy*dx*py*qx + 2*cx*dy*py*qx -
2*dy*px*py*qx + 2*dx*py**2*qx - 4*cz*dx*pz*qx + 2*cx*dz*pz*qx -
2*dz*px*pz*qx + 2*dx*pz**2*qx - 2*cx*cy*dx*qy + 2*cx**2*dy*qy +
2*cz**2*dy*qy - 2*cy*cz*dz*qy + 2*cy*dx*px*qy - 4*cx*dy*px*qy +
2*dy*px**2*qy + 2*cx*dx*py*qy + 2*cz*dz*py*qy - 2*dx*px*py*qy -
4*cz*dy*pz*qy + 2*cy*dz*pz*qy - 2*dz*py*pz*qy + 2*dy*pz**2*qy -
2*cx*cz*dx*qz - 2*cy*cz*dy*qz + 2*cx**2*dz*qz + 2*cy**2*dz*qz +
2*cz*dx*px*qz - 4*cx*dz*px*qz + 2*dz*px**2*qz + 2*cz*dy*py*qz -
4*cy*dz*py*qz + 2*dz*py**2*qz + 2*cx*dx*pz*qz + 2*cy*dy*pz*qz -
2*dx*px*pz*qz - 2*dy*py*pz*qz + 2*dx*px*r**2 + 2*dy*py*r**2 +
2*dz*pz*r**2 - 2*dx*qx*r**2 - 2*dy*qy*r**2 - 2*dz*qz*r**2)**2 -
4*(cy**2*dx**2 + cz**2*dx**2 - 2*cx*cy*dx*dy + cx**2*dy**2 +
cz**2*dy**2 - 2*cx*cz*dx*dz - 2*cy*cz*dy*dz + cx**2*dz**2 +
cy**2*dz**2 + 2*cy*dx*dy*px - 2*cx*dy**2*px + 2*cz*dx*dz*px -
2*cx*dz**2*px + dy**2*px**2 + dz**2*px**2 - 2*cy*dx**2*py +
2*cx*dx*dy*py + 2*cz*dy*dz*py - 2*cy*dz**2*py - 2*dx*dy*px*py +
dx**2*py**2 + dz**2*py**2 - 2*cz*dx**2*pz - 2*cz*dy**2*pz +
2*cx*dx*dz*pz + 2*cy*dy*dz*pz - 2*dx*dz*px*pz - 2*dy*dz*py*pz +
dx**2*pz**2 + dy**2*pz**2 - dx**2*r**2 - dy**2*r**2 - dz**2*r**2)*
(cy**2*px**2 + cz**2*px**2 - 2*cx*cy*px*py + cx**2*py**2 +
cz**2*py**2 - 2*cx*cz*px*pz - 2*cy*cz*py*pz + cx**2*pz**2 +
cy**2*pz**2 - 2*cy**2*px*qx - 2*cz**2*px*qx + 2*cx*cy*py*qx +
2*cy*px*py*qx - 2*cx*py**2*qx + 2*cx*cz*pz*qx + 2*cz*px*pz*qx -
2*cx*pz**2*qx + cy**2*qx**2 + cz**2*qx**2 - 2*cy*py*qx**2 +
py**2*qx**2 - 2*cz*pz*qx**2 + pz**2*qx**2 + 2*cx*cy*px*qy -
2*cy*px**2*qy - 2*cx**2*py*qy - 2*cz**2*py*qy + 2*cx*px*py*qy +
2*cy*cz*pz*qy + 2*cz*py*pz*qy - 2*cy*pz**2*qy - 2*cx*cy*qx*qy +
2*cy*px*qx*qy + 2*cx*py*qx*qy - 2*px*py*qx*qy + cx**2*qy**2 +
cz**2*qy**2 - 2*cx*px*qy**2 + px**2*qy**2 - 2*cz*pz*qy**2 +
pz**2*qy**2 + 2*cx*cz*px*qz - 2*cz*px**2*qz + 2*cy*cz*py*qz -
2*cz*py**2*qz - 2*cx**2*pz*qz - 2*cy**2*pz*qz + 2*cx*px*pz*qz +
2*cy*py*pz*qz - 2*cx*cz*qx*qz + 2*cz*px*qx*qz + 2*cx*pz*qx*qz -
2*px*pz*qx*qz - 2*cy*cz*qy*qz + 2*cz*py*qy*qz + 2*cy*pz*qy*qz -
2*py*pz*qy*qz + cx**2*qz**2 + cy**2*qz**2 - 2*cx*px*qz**2 +
px**2*qz**2 - 2*cy*py*qz**2 + py**2*qz**2 - px**2*r**2 -
py**2*r**2 - pz**2*r**2 + 2*px*qx*r**2 - qx**2*r**2 +
2*py*qy*r**2 - qy**2*r**2 + 2*pz*qz*r**2 - qz**2*r**2)))
/
(2*(cy**2*dx**2 + cz**2*dx**2 - 2*cx*cy*dx*dy + cx**2*dy**2 +
cz**2*dy**2 - 2*cx*cz*dx*dz - 2*cy*cz*dy*dz + cx**2*dz**2 +
cy**2*dz**2 + 2*cy*dx*dy*px - 2*cx*dy**2*px + 2*cz*dx*dz*px -
2*cx*dz**2*px + dy**2*px**2 + dz**2*px**2 - 2*cy*dx**2*py +
2*cx*dx*dy*py + 2*cz*dy*dz*py - 2*cy*dz**2*py - 2*dx*dy*px*py +
dx**2*py**2 + dz**2*py**2 - 2*cz*dx**2*pz - 2*cz*dy**2*pz +
2*cx*dx*dz*pz + 2*cy*dy*dz*pz - 2*dx*dz*px*pz - 2*dy*dz*py*pz +
dx**2*pz**2 + dy**2*pz**2 - dx**2*r**2 - dy**2*r**2 - dz**2*r**2))
</code></pre>
<p>One problem is that the formula actually isn't defined at $r$, which can be worked around by evaluating the function at some $r-\epsilon$. Maybe it's possible to rewrite the equation so that this limit problem isn't an issue, but I will not touch that. :P</p>
<p>I would insert the LaTeX formula in my post, but that would probably break something... I tried to make an image of the formula but my tools failed to create the resolution needed to get a crisp image (>30k wide image). In lieu of that <a href="http://web.student.chalmers.se/~algmyr/upload/math.pdf">here is a pdf version</a> of the beautiful formula and even that required some work since LaTeX really doesn't like super wide equations.</p>
<p>Edit: Like I expected there are nicer solutions when you decide to not just hammer the problem with mathematica. <a href="/users/255162/tanmay28">@tanmay28</a>'s solution <a href="https://www.codechef.com/viewsolution/18811243">18811243</a> is a great example. Although I think most of my unwieldy expression is just expansions of cross products.</p>algmyrSun, 17 Jun 2018 14:12:28 +0530https://discuss.codechef.com/questions/129842/vsn-has-a-closed-form-solutionclosedformmonstrosityjune18vsnvisionGood Permutations Video Solutionhttps://discuss.codechef.com/questions/130142/good-permutations-video-solution<p>Video solution: <a href="https://youtu.be/mEUVVsifKbQ">https://youtu.be/mEUVVsifKbQ</a></p>code_reportWed, 20 Jun 2018 10:14:19 +0530https://discuss.codechef.com/questions/130142/good-permutations-video-solutioncook-offgoodpermjune18ARCTR - Editorialhttps://discuss.codechef.com/questions/128889/arctr-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/ARCTR">Practice</a></p>
<p><a href="https://www.codechef.com/JUNE18A/problems/ARCTR">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/barenuz">Igor Barenblat</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>MEDIUM-HARD</p>
<h1>Prerequisites</h1>
<p>Dynamic Convex-Hull Trick, Heavy-Light Decomposition</p>
<h1>Problem</h1>
<p>You are given a tree with $N$ nodes. $M$ speedsters travel on the tree. The $i^{th}$ speedster starts at time $t_i$ from vertex $u_i$ and travels towards $v_i$ at a constant speed of $s_i$. For every vertex, we need to find the first time, any speedster visited it. In case, it was not visited by any speedster, report the answer as -1.</p>
<h1>Explanation</h1>
<p>For simplicity, let us assume that the tree is rooted at node $1$ and the depth of all vertices from the root is calculated. The depth is basically the distance of the vertex from the root of the tree i.e. $1$.</p>
<p>Let us first write the equation for time taken by speedster $i$ reach a vertex $x$. If the vertex doesn't lie on the path from $u_i$ to $v_i$ then it is not visited by speedster $i$, or the time taken is INFINITY (a large constant). For all the other vertices on the directed path from $u_i$ to $v_i$, the time taken is given by:</p>
<p>$$\text{Time taken} = t_i + \frac{\text{Distance from vertex }u_i}{s_i}$$</p>
<p>$$\text{Distance between x and y} = \text{Depth[x]} + \text{Depth[y]} - 2 * \text{Depth[lca(x, y)]}$$</p>
<p>where $lca(x, y)$ is the lowest common ancestor of vertices $x$ and $y$.</p>
<p>We can now modify the equation for the time taken to reach any vertex on the path from $u_i$ to $v_i$ as follows:</p>
<p>Let the lowest common ancestor of $u_i$ and $v_i$ be $lca$. Calculate the final time at which we reach vertex $v_i$. Let us denote this by $t_f$. We now split the path from $u_i$ to $v_i$ into 2 parts: one from $u_i$ to $lca$ and from $lca$ to $v_i$. NIte that these paths are directed. The image below shows how to calculate the time at any vertex $x$ and $y$ on the 2 different paths.</p>
<p></p><center><img height="300" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-11_at_2.47.43_PM.png" width="400"></center><p></p>
<p>From the above figure, for a node $x$ on path from $u_i$ to $lca$, the time to reach it is:</p>
<p>$$\text{Time taken to reach x} = t_i + \frac{(Depth[u] - Depth[x])}{s_i} = \big(t_i + \frac{Depth[u]}{s_i}\big) - \frac{1}{s_i} * Depth[x]$$</p>
<p>Similarly, for a node $y$ on path from $lca$ to $v_i$, the time to reach it is:</p>
<p>$$\text{Time taken to reach y} = t_f - \frac{(Depth[v] - Depth[y])}{s_i} = \big(t_f - \frac{Depth[v]}{s_i}\big) - \frac{1}{s_i} * Depth[y]$$</p>
<p>If we observe carefully, both the above equations look the form $Y = MX + C$, where the first bracket part is $C$, time to be calculated is $Y$, $\frac{1}{s_i}$ is the slope ($M$) and the depth of the node is $X$.</p>
<p>The problem asks us to find minimum time at which every node is visited by any speedster, and the above equations clearly show that time to reach it only depends on the depth of the node and pair $(constant, slope)$ which is known beforehand for every speedster. Thus, this indicates the final solution will use the Dynamic convex-hull trick (Dynamic variant as the slopes are not guaranteed to be in increasing/decreasing order). If you don't know about it or its use case, you can read it <a href="https://wcipeg.com/wiki/Convex_hull_trick#Fully_dynamic_variant">here</a></p>
<p>So, let us first try to solve a simple version of the problem where the tree is a bamboo(a straight path). This basically rules out the tree of the problem and reduces it to updates and queries of the following form on an array:</p>
<ol>
<li>
<p>Update: Add a line $(M, C)$ denoting $Y = MX + C$ to every index in range $[l, r]$.</p>
</li>
<li>
<p>Query: Find the minimum value at any index $l$ for a given value of $X = w$.</p>
</li>
</ol>
<p>We have range updates and point queries. So, we will use segment trees for the solution. In each node of the segment tree, we will keep the lines (represented by $(M, C)$) and for querying, we will just use the convex-hull trick to evaluate the minimum at node efficiently. Below is the pseudo-code for the segment-tree:</p>
<pre><code>
def init(t, i, j):
if i == j:
seg[t].clear() # remove all the lines
return
mid = (i+j)/2
init(2*t, i, mid)
init(2*t, mid+1, j)
def update(t, i, j, l, r, M, C):
if i > r or j < l:
return
if l <= i and j <= r:
# within required range
seg[t].add_line({M, C})
return
mid = (i+j)/2
update(2*t, i, mid, l, r, M, C)
update(2*t+1, mid+1, j, l, r, M, C)
def query(t, i, j, l, r, X):
if l <= i and j <= r:
return seg[t].evaluate_minimum(X)
mid = (i+j)/2
if i <= mid:
if j <= mid:
return query(2*t, i, mid, l, r, X)
else:
a = query(2*t, i, mid, l, r, X)
b = query(2*t+1, mid+1, j, l, r, X)
return min(a, b)
else:
return query(2*t+1, mid+1, j, l, r, X)
</code>
</pre>
<p>The time complexity of the above operations on segment tree is $O(\log{N} * \log{M})$ for both update and query. This is because each update and query will visit at most $O(\log{N})$ nodes and operation on every node (addition of a line or querying for minimum) is $O(\log{M})$. For a good reference code to the Dynamic convex hull, you can look up <a href="https://github.com/niklasb/contest-algos/blob/master/convex_hull/dynamic.cpp">this</a>.</p>
<p>Back to the tree problem. We see that we can easily handle queries on an array and the queries on the tree as basically those on a path. Voila, we can simply use <a href="https://blog.anudeep2011.com/heavy-light-decomposition/">Heavy light Decomposition</a> or any other data structure you are suitable with (<a href="http://codeforces.com/blog/entry/18369">Euler Path</a> or <a href="https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree">Centroid Decomposition</a>). Thus, we efficiently solve the problem.</p>
<p>The overall time-complexity of the above approach using heavy-light decomposition will be $O({\log}^{2}{N} * \log{M})$ per update and query as it divides the path between the vertices $u$ and $v$ into $O(\log{N})$ path each of which is a straight path and can be solved using the segment tree mentioned above.</p>
<p>You can look at the author's implementation for more details.</p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h1>Time Complexity</h1>
<p>$O((N + M) * {\log}^{2}{N} * \log{M})$</p>
<h1>Space Complexity</h1>
<p>$O(N + M)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="https://ideone.com/3fcEa0">here</a>.</p>likecsMon, 11 Jun 2018 16:05:15 +0530https://discuss.codechef.com/questions/128889/arctr-editorialeditorialbarenuzlikecsmedium-hardconvex-hull-trickhldjune18VSN - Editorialhttps://discuss.codechef.com/questions/128583/vsn-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/VSN">Practice</a></p>
<p><a href="https://www.codechef.com/JUNE18A/problems/VSN">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/nots0fast">Rahim Mammadli</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>EASY-MEDIUM</p>
<h1>Prerequisites</h1>
<p>Cross Product, Binary Search</p>
<h1>Problem</h1>
<p>Given a stationary point $P$ and a point $Q$ moving in straight line, indicate the time when $Q$ is visible from $P$, given that there am opaque sphere between them.</p>
<h1>Explanation</h1>
<p>We will try to find the solution in 2-D and then extend the idea to 3-D as well.</p>
<p></p><center><img align="middle" height="200" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-05_at_4.16.36_PM.png" width="300"></center>
<center><img align="middle" height="200" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-05_at_4.20.27_PM.png" width="300"></center><p></p>
<p>From the above figure, the first idea which can be clearly concluded is that, once point $Q$ becomes visible from $P$, it will remain visible forever. Before that, it will always remain invisible. This, the function (whether $Q$ is visible $P$ at given time $t$) follows the idea that it is false initially and after a certain point, it always remains true. This hints that we can binary search on the answer and just need to check whether the point $Q$ is visible from $P$ at given time $t$ or not. For more ideas on "Binary search" on such type of problem, refer to this <a href="https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/">awesome tutorial on topcoder</a>. Hence, solution template looks like:</p>
<pre><code>
double low = 0, high = 10^18
for i in [1, 100]:
double mid = (low + high) / 2
if visible(P, Q, C, r, mid):
high = mid
else:
low = mid
double ans = (low + high) / 2
</code>
</pre>
<p></p><center><img align="middle" height="100" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-05_at_10.43.19_PM_rYxPI3h.png" width="200"></center><p></p>
<p>So, given a particular time $t$, we can first calculate the position of point $Q$. Join $P$ and $Q$ by a straight line. If the line doesn't pass through the circle, the point $Q$ is visible from $P$ else it is not visible. To check if a given line passes through the circle or not, it is enough to check that the perpendicular distance of the line from the centre, $C$, of the circle is greater than the radius, $r$, of the circle. For this, we first complete the triangle $PCQ$ and let the perpendicular distance of $PQ$ from $C$ be denoted by $CO$. Using the formula,</p>
<p>$$\text{Area of triangle} = \frac{1}{2} * \text{Base} * \text{Height} = \frac{1}{2} * CO * PQ$$</p>
<p>Since the area of the triangle can be found given 3 points in 2-D, and $PQ$ is the Euclidean distance between $P$ and $Q$, we can find the value of $CO$ efficiently. Finally, we just need to compare it to $r$, the radius of the circle.</p>
<p>For extending the solution in 3-D, the idea is same and we just need to find the area of a triangle in 3-D. For details, one can refer <a href="https://math.stackexchange.com/questions/128991/how-to-calculate-area-of-3d-triangle/128999#128999">here</a>. It can be clearly seen that the above formula holds for the 2-D case as well.</p>
<p>$$\text{Area of triangle in 2/3-D} = \frac{|CP X CQ|}{2}$$</p>
<p>where $CP$ and $CQ$ are <a href="https://en.wikipedia.org/wiki/Euclidean_vector">vectors</a>, $a X b$ denotes <a href="https://en.wikipedia.org/wiki/Cross_product">cross product of vectors</a> and $|a|$ denotes the <a href="https://www.khanacademy.org/math/precalculus/vectors-precalc/component-form-of-vectors/a/vector-magnitude-and-direction-review">magnitude of vector</a>.</p>
<p>Thus, to find the length of $CO$, we have</p>
<p>$$|CO| = \frac{2 * \text{Area of triangle PCQ}}{|PQ|} = \frac{|CP X CQ|}{|PQ|}$$</p>
<p>For more details, you may refer to the editorialist solution which exactly follows the above idea.</p>
<h3>Extra Ideas/Caveats</h3>
<p>The binary search implementation mentioned in the editorial is different from the one mentioned in Topcoder tutorial. Though both will give AC here, the one in Topcoder needs one to correctly set the <b>Epsilon</b> value for termination condition and sometimes can lead to wrong answers due to precision issues. The editorialist just prefers the above style to implement binary and ternary search involving doubles as calculation of epsilon is not required.</p>
<p><b>Also, for details regarding the exact number of iterations or complexity analysis for binary search problem on doubles, refer to <a href="http://codeforces.com/blog/entry/49189">this blog</a> on codeforces.</b> </p>
<h3>Note from the author</h3>
<p>Finding the distance of a point from a line in 3-D is a generally common problem and also contains some edge cases where the point may not lie within the line segment region. But given the constraints of the problems, there are no edge cases but we should be aware of it in general.</p>
<p></p><center><img align="middle" height="150" src="https://discuss.codechef.com/upfiles/Screen_Shot_2018-06-05_at_10.49.18_PM_iKwOvTO.png" width="500"></center><p></p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h1>Time Complexity</h1>
<p>$O(LogN)$ per test case (around 100 iterations for binary search).</p>
<h1>Space Complexity</h1>
<p>$O(1)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="https://ideone.com/PTrTyB">here</a>.</p>
<p>Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/JUNE18/tester/VSN.cpp">here</a>.</p>
<p>Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/JUNE18/editorialist/VSN.cpp">here</a>.</p>likecsWed, 06 Jun 2018 01:17:53 +0530https://discuss.codechef.com/questions/128583/vsn-editorialnots0fastjune18cross-productgeometrylikecseditorialbinary-searcheasy-mediumEditorial of BINSHFFLhttps://discuss.codechef.com/questions/132876/editorial-of-binshffl<p>Please update BINSHFFL with its editorial, I am eagerly waiting for it.</p>thesmartguyWed, 01 Aug 2018 02:16:43 +0530https://discuss.codechef.com/questions/132876/editorial-of-binshfflbinshffljune18Maths for LOChttps://discuss.codechef.com/questions/131691/maths-for-loc<p>Hello all. I am a school student. I know basic maths(And some imp. coding theorem like fermat's little theorem). The maths required for LOC is a bit of high level for me.</p>
<p>I would be grateful if u all can suggest some tutorials or books for maths for CP.</p>
<p>Thanks in advance.Happy coding:)</p>krishyadav007Tue, 17 Jul 2018 22:36:28 +0530https://discuss.codechef.com/questions/131691/maths-for-locloc18locjune18WAREHOUS - Editorialhttps://discuss.codechef.com/questions/129097/warehous-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/WAREHOUS">Practice</a></p>
<p><a href="https://www.codechef.com/JUNE18A/problems/WAREHOUS">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/pieguy">David Stolp</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>Challenge Problem</p>
<h1>Prerequisites</h1>
<p>BFS, Optimisations</p>
<h1>Problem</h1>
<p>You are given a grid and the order in which some items are coming. You need to place the items on the grid first and then remove them from the grid in the order $(1, 2, 3, ...)$. There are steps mentioned in the problem statement which can be used to move inside the grid, pick up an item or drop an item. You aim is to output a string containing the steps you will take and the objective is to minimise the length of this string.</p>
<h1>Explanation</h1>
<h3>Trivial solution</h3>
<p>As we need to remove the items in the order $(1, 2, 3, ....)$, we can just place the items in the clockwise or counter-clockwise direction of the grid. So, the grid may look like</p>
<pre> 0 1 2 3 4
9 8 7 6 5
10 11 12 13 14
.....
</pre>
<p>or</p>
<pre> 0 5 6 11
1 4 7 10
2 3 8 9
....
</pre>
<h3>Optimised Solution</h3>
<p>One of the main ideas is that there's no need to write a separate solver for the pick-up phase versus the drop-off phase. Once you have an algorithm for the drop-off phase, you can run the same algorithm but with the reverse pick-up order, and then do a sort of reversal on the result to get a sequence of instructions for filling the warehouse. Then it's a matter of assigning shipment locations so that most shipments have a direct path to the entrance in both phases.</p>
<p>For designing the algorithm for drop off phase, some sort of BFS/DFS on the grid will be helpful as it will help us to find the shortest path from given cell to the initial one. This problem can be treated as finding the shortest path from cell $(r, c)$ to cell $(0, 0)$ where some cells are blocked in between as some items are placed there. Some optimisations like changing the items in adjacent cells while finding the path can be helpful and optimise the solution further.</p>
<p>Another idea was to decide on how the grid should look like in the beginning. Apart from trivial clockwise and counter-clockwise ones shown above, spiral placement of items in the grid and ones used by author and gorre_morre can be other options.</p>
<p>Author's grid placement idea can be found in this solution below. Gorre_morre's grid placement idea can be found in his solution <a href="https://www.codechef.com/viewsolution/18866322">here</a></p>
<p>If your placement and drop-off phase algorithm is efficient enough, you can even try multiple iterations of it using some random grids and optimise your code further. Even more, changing some random locations and swapping some in the optimal grid you find after some iterations can boost your score. Below is a pseudo-code for it.</p>
<pre><code>
# Assume solve_grid returns string containing the required steps
def update_ans(s, length, ans):
if len(s) < length:
length = len(s)
ans = s
overall_timer = 0
length = 10**18
ans = ""
s = solve_clockwise()
update_ans()
s = solve_counter_clockwise()
update_ans()
s = solve_spiral()
update_ans()
# Other grid you want to try
TLE = 5.0 - 0.1
TLE_CUT = 2.0
timer = 0
while timer < TLE_CUT:
# generate random grid
s = solve_random_grid()
update_ans()
timer = 0
while timer < TLE_CUT:
# Swap some random poisitons in optimal grid so far
s = solve_improved_grid()
update_ans()
while overall_timer < TLE:
# Maybe try some more iterations of random grid or random swapping
print ans
</code>
</pre>
<p>You can look at the author's implementation for more details.</p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h1>Solution Links</h1>
<p>Setter's optimised solution can be found <a href="https://ideone.com/tzPq4b">here</a>.</p>
<p>Setter's trivial solution can be found <a href="https://ideone.com/1cHaks">here</a>.</p>likecsTue, 12 Jun 2018 09:11:57 +0530https://discuss.codechef.com/questions/129097/warehous-editorialjune18pieguychallengebfslikecseditorialSolution for VSN giving TLE in python 3 using the editorial approachhttps://discuss.codechef.com/questions/129780/solution-for-vsn-giving-tle-in-python-3-using-the-editorial-approach<p>I used the same approach as mentioned in the editorial using python 3.
I am getting TLE for 6 out of 7 tasks.</p>
<p>The link for the code is:
</p><li> <a href="https://ideone.com/IZ6ikK">https://ideone.com/IZ6ikK</a> </li><p></p>
<p>Could anyone please check and see whats wrong with my code.
I have been trying from many days but not able to understand why I am getting TLE.
It will be of great help. Thanks!!</p>zymbioSat, 16 Jun 2018 17:50:29 +0530https://discuss.codechef.com/questions/129780/solution-for-vsn-giving-tle-in-python-3-using-the-editorial-approachsolutionapproachjune18tleeditorialTWOFL RunTime Error in Javahttps://discuss.codechef.com/questions/129543/twofl-runtime-error-in-java<p>So when I was trying to do <strong>TWOFL</strong> question I don't know I was getting <strong>RunTimeError</strong> for some of the cases and only in subtasks 2 and 3. So I wonder whether this is because of big values. Then somehow in my program I made all value as 1 and traversed it for n=1000 and m=1000. Clearly on my PC I got an error of <strong>StackOverFlow</strong>. I thought may be my program is going in an infinite recursion so I tried more and couldn't find why is this happening. Then I thought of looking at one of the accepted codes in CPP and changing it into Java. Still it was giving <strong>RunTimeError</strong> on same cases. Then I looked at others code of Java and many were getting the same error and hence I was sure that this is only with Java who is doing in <strong>recursive</strong> fashion.</p>
<p>And finally I found this:<br>
<a href="http://codeforces.com/blog/entry/21472">http://codeforces.com/blog/entry/21472</a><br>
<a href="http://codeforces.com/blog/entry/166">http://codeforces.com/blog/entry/166</a></p>
<p>I hope this will help you.</p>
<p>Thanks</p>vjvjain0Thu, 14 Jun 2018 17:12:55 +0530https://discuss.codechef.com/questions/129543/twofl-runtime-error-in-javarecursiongraphsjavalong-contestjune18TLE in Sheokand and String(SHKSTR)https://discuss.codechef.com/questions/129103/tle-in-sheokand-and-stringshkstr<p>can anyone help me in this problem , i am getting TLE in task 3 . I checked up the editorial and the approach seems almost similar. can anyone help? <br>
here is the <a href="https://www.codechef.com/viewsolution/18869759">link</a> to my submission. </p>
<p>Note - In the structure Node , mn is the minimum index of the string passing through it, and x is the index of the string ending at that leaf .<br>
so mn is ids[0] and x is leaf_id if you co-relate solution with editor.</p>yogeshk972Tue, 12 Jun 2018 10:27:38 +0530https://discuss.codechef.com/questions/129103/tle-in-sheokand-and-stringshkstrtriestlec++11june18PLUSEQ - Editorialhttps://discuss.codechef.com/questions/129447/pluseq-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/PLUSEQ">Practice</a></p>
<p><a href="https://www.codechef.com/JUNE18A/problems/PLUSEQ">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/iloveksh">Stacy Hong</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>HARD</p>
<h1>Prerequisites</h1>
<p>Branch and Bound, Dynamic Programming, Big Integers, Hashing, DFS/Recursion</p>
<h1>Problem</h1>
<p>You are given a string $S$ and integer $N$. So need to place some '+' symbols in the strings $S$ so that the value of the expression equals $N$.</p>
<h1>Explanation</h1>
<h2>Subtask 1: N < 1000000</h2>
<p>A simple knapsack like dynamic programming is sufficient to pass this subtask. The dp state is as follows:</p>
<p>$$dp[i][j] = \text{1 if first 'i' characters of S can be partitioned such that the sum is 'j' else 0}$$</p>
<p>A recursive pseudo-code for the above logic is given below:</p>
<pre><code>
def solve(int idx, int remain):
if idx == len(s):
return remain == 0
if dp[idx][remain] != -1:
return dp[idx][remain]
dp[idx][remain] = 0
num = 0
for i in [idx, len(s) - 1]:
num = num * 10 + s[i] - '0'
if (num > remain):
break
if (solve(i + 1, remain - num)):
PLUS[i] = 1;
return dp[idx][remain] = 1
return dp[idx][remain];
solve(0, N) # N = integer value of string s in input
for i in [0, len(s) - 1]:
if i and PLUS[i]:
print '+'
print s[i]
</code>
</pre>
<p>The above code works in time complexity $O(|S| * N)$ where $|S|$ is the length of string $S$ and $N$ is the given integer. The space complexity is also same. Note that Codechef servers allow programs using such large memory (around 1G) to pass but you can you bitset or other equivalent structures to reduce the memory of your program too. See the linked solution below for subtask 1 for more details.</p>
<p>The solution for this subtask also exists using hashing and dynamic programming.</p>
<h2>Subtask 2: N < |S|</h2>
<p>Adding 2 numbers of sizes $x$ and $y$ leads to final result having size at most $max(x, y) + 1$. This is easy to prove. The size will be $max(x, y)$ if there is no carry-over in the end otherwise it will increase by 1. Extending the above logic to addition of $m$ number, we can conclude that if the numbers have lengths $x_1, x_2, \cdots, x_m$, then the length of final result is bounded by $(max(x_1 + x_2 + \cdots + x_m) + m - 1)$. You can easily prove it using induction.</p>
<p>Note that number of ways to partition the string $S$ into different expression is exponential. But using the above observation, you can the conclude the following fact:</p>
<p>Given a string $S$ and integer $N$, having the length as $n$, there is very less number way to achieve the target $N$ if $n$ is comparable to $|S|$. This is because most of the partitions will either have the maximum number in them as too low. Equivalently, if the number of partitions we put in $S$ is large, then achieving a larger target $N$ is not possible. This hints that for sufficiently large integers, the greedy technique of choosing a larger size partition and checking if the remaining part can add up to desired $N$ will run very fast in practice as the number of iterations will not be large. For example: $S = 114390211, N = 43915$</p>
<p>Considering greedily large size partition of $S$ such that their value is less than $N$, we have the following numbers: [11439, 14390, 43902, 39021]. (Note that the size of this selected numbers can be at most (|S| - n + 1).) Let us greedily start with $43902$. The remaining parts of $S$ are $(11, 11)$ and the required sum now is $(43915 - 43902) = 13$. Note that there are 2 ways to achieve it $(11 + 1 + 1) \text{ or } (1 + 1 + 11)$. As you can see, the number of iterations were less. The example is just a short one to make to understand how greedy recursion might behave for larger test cases.</p>
<p>But the other case where the integer $N$ is small but $|S|$ is very large, there can be large number of ways to achieve the desired result. For this, we have already seen that a dynamic programming solution already exists (Subtask 1). Trying the above greedy approach can be very bad in this case, a simple example being $(S = 99999999999, N = 108)$.</p>
<p>With some of the above ideas, we design a simple branch and bound based algorithm for the problem:</p>
<pre><code>
range_tried = [0 for i in [1, len(S) - 1]]
# Find all range in S such that their value is less than N and sort
# them in decreasing order of their value. Let it be called "RANGES"
def recurse(range_idx, remain):
if remain < 0:
return false
if remain < LIMIT: # LIMIT ~ 100000
use dp based subtask_1 solution
else:
for i in [range_idx, len(RANGES) - 1]:
if conflict(current_range, range_tried):
# If current range we are trying conflicts with one
# already tried in recursion before.
continue
X = value of integer for RANGES[i]
# Update range_tried
if recurse(range_idx, remain - X):
return True
# Update range_tried to old value
return False
</code>
</pre>
<p>Note the above is a simple solution based on the initial observations. But do we need to really check for all possible ranges? Can we decide greedily at some point that given range can never result in an answer as $N$, i.e. Say we have selected some ranges, can we say that with the remaining ones we can never achieve the target $N$ without checking all possible partitions or greedily checking large number ranges.</p>
<p>Actually, given initial choice of our ranges, we can bound the maximum number we can achieve with the remaining ones. A simple check which ignores the digits of remaining parts of $S$ and considers all of them to be $9$ and finds the maximum value possible is a good starting point. If this value is already less than $N$, then we can simple prune our solution. Even stronger checks based on actual values of digits in string $S$ can lead to better pruning. So, the loop in the above code modifies as follows:</p>
<pre><code>
for i in [range_idx, len(RANGES) - 1]:
if conflict(current_range, range_tried):
# If current range we are trying conflicts with one
# already tried in recursion before.
continue
MAX_POSSIBLE = get_max(ranges_set)
if MAX_POSSIBLE < N:
# As we iterate in decreasing order of numbers, the
# MAX_POSSIBLE can only decrease as 'i' increases
break
X = value of integer for RANGES[i]
# Update range_tried
if recurse(range_idx, remain - X):
return True
# Update range_tried to old value
</code>
</pre>
<p>Another thing we can do is to remove the early exit of recursion where a check is based on "remain < 0". This can be easily done by directly starting from ranges such that value of considered numbers is always less than "remain". This is again helpful as after greedily choosing a large size partition, it is possible in most case the other large size partitions should be ignored in further recursion either due to conflicts in common ranges or "remain" decreasing too fast to become less than $0$. For this, a simple binary search can help us to find the first index in "RANGES" from where we should begin our search. This is possible as we had initially stored our ranges in decreasing order of the value of integers they represent.</p>
<p>With the above ideas, the recursive solution based on branch and bound works quite fast in practice. A small analysis of the time complexity is as follows:</p>
<ol>
<li>
<p>$N < 100000$: Assuming we set LIMIT to this value in above pseudo-code. A dynamic programming based solution is run with complexity $O(|S| * N)$. Again to optimise this, we can use recursive version instead of iterative version. This is because will work in exactly the above complexity but in recursive solution, most of the states will be unvisited due to our initial choices of the ranges. This will significantly reduce the constant factor in your code.</p>
</li>
<li>
<p>For most of the other cases, as $N$ becomes larger i.e. size $n$ reaches closer to $|S|$, the possible solutions reduce significantly as explained before.</p>
</li>
</ol>
<p><b>A more detailed analysis of time complexity is will available soon.</b></p>
<h3>Ashmelev solution (Fastest in the contest): Branch and Bound with strong bound checking</h3>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>The solution is based on the following two ideas:</p>
<ol>
<li>Let's consider all possible partitions of S. Of course, it is extremely slow, but if we iterate from big substrings to small, the required sum (N) will be decreased fastly. I used recursion to find all possible partitions: function</li>
</ol>
<p>int go(int pos, string cur, int c, int csum)</p>
<p>where "pos" - number of the last taken substring (all substrings were sorted in decreasing order), "cur" - remaining necessary value (initially - N), "c" and "csum" - some useful variables.
The same function - "goSmall" - used for small numbers, where "cur" fits long long.</p>
<ol>
<li>This recursion is very slow still, it is necessary to add an additional check whether the solution may exist and exit the recursion in the bad case. I implemented function "tooBig" (and for small numbers - "tooBigSmall" :) ) that checks whether remaining number "cur" is too big and cannot be the sum of the remaining substrings, including that we may only use substrings starting from "pos". This function should be quite smart to make the recursion algorithm really fast. I used DP approach to find the largest possible number we may obtain from the remaining substrings - "getans2" calculates this number approximately for string "cur" and "getans3" calculates this number exactly for small (long long) "cur".</li>
</ol>
</div></div>
<h3>Tips for Big integer library (mostly for C++ users)</h3>
<p>Languages like python and java already have big integer library implemented in them. But C++ users need to implement the same for their usage in this problem. A small tip is to store the numbers as groups instead of single digits. For example: $S = 123456789123456789$. Below are 2 possible ways to store $S$:</p>
<p>$$S = 1|2|3|4|5|6|7|8|9|1|2|3|4|5|6|7|8|9$$</p>
<p>$$S = 123456|789123|456789$$</p>
<p>This helps to perform operations on base different than 10 and reduces the constant factor of your program. Generally, the base is chosen as ${10}^{9}$ so that all possible operations like $(+, -, * , /)$ fit inside the datatypes provided by the language. You can see setter's library for example.</p>
<h1>Time Complexity</h1>
<p>To be described in detail later.</p>
<h1>Space Complexity</h1>
<p>To be described in detail later.</p>
<h1>Solution Links</h1>
<p>The solution for subtask 1 can be found <a href="https://ideone.com/5rU7XN">here</a></p>
<p>Setter's solution can be found <a href="https://ideone.com/24We1O">here</a></p>
<p>Ashmelev's solution can be found <a href="https://pastebin.com/JdhBWa7c">here</a></p>likecsThu, 14 Jun 2018 03:24:42 +0530https://discuss.codechef.com/questions/129447/pluseq-editorialbignumeditorialdynamic-programminghardboundilovekshbranchjune18Why was my solution giving a WA first, then RE afterwards for NMNX?https://discuss.codechef.com/questions/131814/why-was-my-solution-giving-a-wa-first-then-re-afterwards-for-nmnx<p>I was following the logic of using combinatorics for this problem. My first approach was giving me a TLE because I was finding out a lot of coefficients beforehand. However, this new approach works fine as per my understanding. Can you all help me find my mistake?</p>
<p><a href="https://www.codechef.com/JULY18B/problems/NMNMX">Question</a></p>
<p><a href="https://www.codechef.com/viewsolution/19243735">Solution</a></p>major21Thu, 19 Jul 2018 10:50:32 +0530https://discuss.codechef.com/questions/131814/why-was-my-solution-giving-a-wa-first-then-re-afterwards-for-nmnxruntime-errorpypyjune18python3long-contestBUILDIT - Editorialhttps://discuss.codechef.com/questions/128857/buildit-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/BUILDIT">Practice</a></p>
<p><a href="https://www.codechef.com/JUNE18A/problems/BUILDIT">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/teja349">Teja Vardhan Reddy</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>MEDIUM-HARD</p>
<h1>Prerequisites</h1>
<p>Matrix Multiplication, Recurrences, Linearity of Expectation, Probabilities</p>
<h1>Problem</h1>
<p>You are given a circular which is equally divided into $H$ parts. There are $N$ building placed on the circle at some points, not necessarily distinct. You can start from any point and start shooting within a range of $X$. All building within the range collapse. You need to find the expected number of buildings which collapses when the probability of starting from any point is given by the following probability distribution:</p>
<p>$$a_i \text{is given for} 1 ≤ i ≤ K$$</p>
<p>$$a_i = \sum_{j=1}^{j=K} c_j\cdot a_{i-j} \quad \forall\,i:\;K \lt i \le h\,.$$</p>
<h1>Explanation</h1>
<h2>Subtask 1: N ≤ 1000, H ≤ 10000, K ≤ 10</h2>
<p>A simple brute force solution which first finds the probability of starting at each point and then simply iterates through each point and finds the number of buildings which are collapsed will work within the required constraints.</p>
<p>The time complexity of the above approach will be $O(H * K + N * H)$ as $X = H$ in the worst case. The first part is for the pre-computation and the next part if for finding the desired number of buildings which are collapsed. The space complexity is $O(H)$.</p>
<h2>Subtask 2: N ≤ 50000, H ≤ 1000000, K ≤ 10</h2>
<p>All the further subtasks require the knowledge of <a href="https://brilliant.org/wiki/linearity-of-expectation/">linearity of expectation</a> and <a href="https://www.cs.princeton.edu/courses/archive/fall02/cs341/lec22.pdf">indicator random variables</a>.</p>
<p>Let us define the indicator random variable $Y_i$. It equals $1$ if there is a building at position $i$ else $0$. Using this definition, the expected number of building which collapse is:</p>
<p>$$\text{Expected buildings} = \sum_{i=1}^{i=N} {a_i * \sum_{j=i}^{j=i+X} Y_j}$$</p>
<p>where the second sum is taken in a circular manner.</p>
<p>Using linearity of expectation (or rearrangement of terms), we can rewrite the above expression as:</p>
<p>$$\text{Expected buildings} = \sum_{i=1}^{i=N} {Y_i * \sum_{j=i-X}^{j=i} a[i]}$$</p>
<p>where the second sum is again taken in a circular manner.</p>
<p>Since $Y_i$ is defined to be $1$ for all points where buildings are present, we can see that outer sum runs for $O(N)$ times in worst case. For the inner sum, we can just maintain a prefix sum for array $a$ and thus find the required sum in $O(1)$.</p>
<p>Using this approach, the time complexity becomes $O(H * K + H + N)$ which is enough to pass this subtask. The space complexity is $O(H)$.</p>
<p>You can see editorialist approach for ${1}^{st}$ two subtasks below.</p>
<h2>Full Solution Approaches</h2>
<h3>Author/Tester Solution: Matrix multiplcation for recurrence solving</h3>
<p>The last approach was bad as it required us to calculate the probability of starting at each point which is not possible as $H$ is very large. If carefully observed, the way future $a_i$ are generated is given by a recurrence relation. Don't confuse by seeing the convolution form in it. :(</p>
<p>In case you don't know how to solve recurrence using matrix multiplication, I suggest you go through <a href="http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html">this blog</a> before.</p>
<p>In the last approach, we needed to calculate the prefix sum of some given range, for the recurrence relation, in an efficient manner. We can extend our matrix from $K * K$ for normal recurrence to include one extra row which will calculate the prefix sum. Below the idea with a recurrence containing 3 terms. We can generalise it later.</p>
<p>Let recurrence be $a_m = c_1 * a_{m-1} + c_2 * a_{m-2} + c_3 * a_{m-3}$. As per blog the matrix is given by</p>
<p>$$
\begin{bmatrix}
c_1 & c_2 & c_3 \\ 1 & 0 & 0 \\ 0 & 1 & 0
\end{bmatrix}
\begin{bmatrix}
a_{m-1} \\ a_{m-2} \\ a_{m-3}
\end{bmatrix}
=
\begin{bmatrix}
a_m \\ a_{m-1} \\ a_{m-2}
\end{bmatrix}
$$</p>
<p>To extend it to contain prefix sum as well, the matrix will look like:</p>
<p>$$
\begin{bmatrix}
c_1 & c_2 & c_3 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ c1 & c2 & c3 & 1
\end{bmatrix}
\begin{bmatrix}
a_{m-1} \\ a_{m-2} \\ a_{m-3} \\ \sum_{i=1}^{i=m-1} a_i
\end{bmatrix}
=
\begin{bmatrix}
a_m \\ a_{m-1} \\ a_{m-2} \\ \sum_{i=1}^{i=m} a_i
\end{bmatrix}
$$</p>
<p>Got the idea, we basically store the initial prefix sum as the last value and add the current value to the prefix sum to extend it further. This can be easily extended to higher order recurrences as well.</p>
<p>Using the above idea naively, we can solve the problem in $O(N * K^3 * \log{H})$, where for every building we use matrix multiplication to calculate the prefix sums. This is enough to pass the ${3}^{rd}$ subtask but not the last one.</p>
<p>To solve the last subtask, we need to look at one important detail of matrix multiplication. Given matrices of sizes $(a, b)$ and $(b, c)$, the complexity for their multiplication is $O(a * b * c)$. We are used to using square size matrices, so we say the complexity is always cubic. In recurrences, the last step involves multiplying the recurrent matrix, $(K, K)$ with the base matrix, $(K, 1)$ which takes $O(K^2)$ complexity instead of $O(K^3)$. This gives us a neat optimisation as follows:</p>
<p>$${R}^{n} * B = R^{i_1} * ( \cdots * ({R}^{i_{\log{H}}} * B))$$</p>
<p>where $R$ is the recurrent matrix ($(K+1, K+1)$ matrix which is described above), $B$ is the base matrix ($(K+1, 1)$ matrix which is described above) and $n = 2^{i_1} + 2^{i_2} + \cdots + 2^{i_{\log{H}}}$.</p>
<p>An example of above equation is:</p>
<p>$${R}^{11} * B = R^1 * (R^2 * (R^8 * B))$$</p>
<p>Note that the above step now needs $O(K^2 * \log{H})$ complexity, reducing a factor $K$ from previous one. But we need to precompute the $2^w$ powers of the recurrent matrix. This can be done in $O(K^3 * \log{H})$.</p>
<p>Using the above ideas of precomputation and matrix multiplication, the complexity is $O(K^3 \log{H} + N * K^2 * \log{H})$. This will easily pass all the subtasks.</p>
<p>For more details, you can refer to the author's or tester's solution below.</p>
<h3>Editorialist Solution: GP Sum of a matrix (Bad constant factor)</h3>
<p>The ideas of precomputation and matrix multiplication described above hold in the editorialist solution too.</p>
<p>The solution uses the following idea for finding the prefix sums or recurrence:</p>
<p>$$a_1 + a_2 + \cdots + a_m = R^0 * B + R^1 * B + \cdots + R^{(m-1)} * B = (R^0 + R^1 + \cdots + R^{(m-1)}) * B$$</p>
<p>So, we need to find the GP (<a href="https://en.wikipedia.org/wiki/Geometric_progression">Geometrix progression</a>) sum of a matrix. This is a known problem. If you don't know about it, you can read similar problem <a href="https://www.hackerrank.com/contests/mathemagic-bits/challenges/gp-on-fibonacci-matrix/problem">here</a>. But the only problem with this approach is the large constant factor involved. The matrix used to calculate the GP sum of a matrix is twice the size of given matrix, i.e. the matrix used will have size $(2k, 2k)$. Hence, a constant factor of $2^2 = 4$ is added to the complexity of the solution which is very hard to deal with. But with some neat observations like some parts of the matrix always retaining particular values, we can reduce the constant factor in the solution too.</p>
<p>I understand the above is a very brief idea of the solution, but in case you have any problem, you can read through the solution and ask any doubts you have in the comment section below.</p>
<p>The time complexity of the approach will be $O(4 * K^3 * \log{H} + 2 * N * K^2 * \log{H})$. The space complexity will be $O(4 * K^2)$.</p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h3>Extra Tip: Reduce constant factor in modular matrix multiplication</h3>
<p>Below is the general code used to calculate matrix multiplication in the modular field:</p>
<pre><code>
for i in [1, n]:
for j in [1, n]:
for k in [1, n]:
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod
</code>
</pre>
<p>It can be easily seen that above code uses $O(N^3)$ mod operations. It should be remembered that mod operations are costly operations as compared to simple operations like addition, subtraction, multiplication etc. We observe the following identity:</p>
<p>$$X \% \text{mod} = (X \% mod^2) \% \text{mod}$$</p>
<p>Above can be easily proved using $X = q * mod + r$. Using this fact, we can reduce the number of mod operations to $O(N^2)$ in matrix multiplication. Below is the pseudo-code for it:</p>
<pre><code>
mod2 = mod * mod
for i in [1, n]:
for j in [1, n]:
c[i][j] = 0
for k in [1, n]:
c[i][j] += a[i][k] * b[k][j] # Take care of overflows in interger multiplication.
if c[i][j] >= mod2:
c[i][j] -= mod2
c[i][j] %= mod
</code>
</pre>
<p>Note that above trick reduces the running time by approximately 0.8-0.9 seconds. Though it is not required for the complete solution, knowing it can always help and might be useful somewhere else.</p>
<h1>Time Complexity</h1>
<p>$O(K^3 \log{H} + N * K^2 * \log{H})$</p>
<h1>Space Complexity</h1>
<p>$O(K^3)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/JUNE18/setter/BUILDIT.cpp">here</a>.</p>
<p>Editorialist's solution for subtask 1 and 2 can be found <a href="https://github.com/likecs/Codechef-June-18-/blob/master/expected_building_sub_1_2.cpp">here</a>.</p>
<p>Editorialist's solution can be found <a href="https://github.com/likecs/Codechef-June-18-/blob/master/expected_building_full.cpp">here</a>.</p>likecsSun, 10 Jun 2018 23:24:34 +0530https://discuss.codechef.com/questions/128857/buildit-editorialjune18medium-hardmatrix-exporecurrenceslikecseditorialteja349