Questions Tagged With mediumhttps://discuss.codechef.com/tags/medium/?type=rss&user=panikquestions tagged <span class="tag">medium</span>enFri, 11 Jan 2019 18:20:52 +0530Editorial for ENG5 - PELT2019https://discuss.codechef.com/questions/143582/editorial-for-eng5-pelt2019<p>Problem setter: <a href="https://www.codechef.com/users/aditya10_">aditya10_</a></p>
<p>DIFFICULTY:
Medium </p>
<p>PREREQUISITES:
Dynamic Programming, Bit Masking</p>
<p>EXPLANATION:
We will take a mask of the number of items M. 1 at ith index represent that item of type i is included. Mask at any time represents the type of items which are ordered continuously from the left. We will find the cost of adding every type of item which was not there in the mask ie the bits which were unset.<br>
Cost of adding an item of type X means the number of items to select such that item of type X occurs in succession. The item of type X here is added after the type of items which have already been placed continuously i.e. the bits which were set in the mask.<br>
Dp array stores the cost of each mask.<br>
The above can be represented as:<br></p>
<p><img alt="code" src="https://discuss.codechef.com/upfiles/Capture_1xkltz8.PNG"><br></p>
<p>Now How to find the cost of adding a type of item X?<br>
Let the total number of items be tot which are set in the mask. And the number of items of type x be c. Now the cost will be the number of items which are not of type x in the range
[tot+1,tot+x]. </p>
<p>For this we will maintain an array which stores the frequency of each type of item. And a pref array pref[N+1][M+1]. pref[idx][x] represent the number of items of type x upto index idx.<br></p>
<p><img alt="code2" src="https://discuss.codechef.com/upfiles/Capture1_TRPZSCD.PNG"></p>
<p>Author’s Solution: <a href="https://ideone.com/25foEK">click here</a></p>
<p>Tester’s Solution: <a href="https://ideone.com/25foEK">click here</a></p>panikFri, 11 Jan 2019 18:16:20 +0530https://discuss.codechef.com/questions/143582/editorial-for-eng5-pelt2019aditya10_mediumpelt2019bitmaskingdp+bitmaskeng5Editorial for MISSME - PELT2019https://discuss.codechef.com/questions/143584/editorial-for-missme-pelt2019<p>Problem Setter: <a href="https://www.codechef.com/users/panik">panik</a></p>
<p>Difficulty: Medium</p>
<p>Prerequisites: DP on Trees, DFS</p>
<p>Explanation:
This is a DP on trees question. In this, we need to optimally traverse the tree by keeping track of different paths using DP as repetition occurs.
we need a DP array of dimension DP[N][K] where K maximum value of J possible and N is no. of nodes. As we need to skip nodes according to the given conditions we would need 2 DFS functions, one to skip J level of nodes(where J is the penalty of that node if selected) and one for normal traversal and DP table filling. To fill the DP we use a top-down approach since the data structure in use is a tree so linear traversal is not possible.</p>
<p>So we start from the tree root, now we have the option of selecting it or not. If we select it then the state of its next selected node would be its current state xor value, and if not selected we would directly go to its children and pass its current state as it is and calculate the max value from them.</p>
<p>Author’s Solution: <a href="https://ideone.com/Z2sSm3">click here</a> (the code is well commented for your understanding)</p>
<p>Tester’s Solution: <a href="https://ideone.com/AZnhpN">click here</a> (using only 1 dfs function by the help of flag variable)</p>panikFri, 11 Jan 2019 18:20:52 +0530https://discuss.codechef.com/questions/143584/editorial-for-missme-pelt2019mediumpelt2019dp+treesmissmedfspanik