You are not logged in. Please login at www.codechef.com to post your questions!

×

Editorial for MISSME - PELT2019

Problem Setter: panik

Difficulty: Medium

Prerequisites: DP on Trees, DFS

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.

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.

Author’s Solution: click here (the code is well commented for your understanding)

Tester’s Solution: click here (using only 1 dfs function by the help of flag variable)

asked 11 Jan, 18:20

panik's gravatar image

5★panik
1166
accept rate: 7%

edited 11 Jan, 18:49

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,556
×693
×50
×10
×6
×2

question asked: 11 Jan, 18:20

question was seen: 96 times

last updated: 11 Jan, 18:49