Hello World (1926G Solution)

Правка en9, от dlucoding813, 2024-02-25 03:00:24

Hi everyone!

I'm not sure that I'll be posting here very often, but I'll be mainly outlining interesting solutions to hard problems or just noting something worthwhile to think about for competitive programming.

Although I recently promoted to the Silver division in USACO, I managed to fail horribly in solving graph problems. Before I was promoted, I also saw this issue from past Codeforces contests, especially in problem C (see 1830A - Copil Copac Draws Trees).

A recent example is 1926G - Vlad and Trouble at MIT, which I couldn't manage to solve in-contest. After trying to upsolve it and looking at the main solution, I still didn't get how dynamic programming portion over the three types of water functioned. After a very long time searching up other solutions, I suddenly got inspired to do dp over whether music was played or not at a particular node.

I wrote down all of the details of the dp because being a newbie, I do not see the solution very clearly.

Solution

Denote a p-node as a node that represents a partying student. Define s-node and c-node similarly for sleepy and indifferent students.

Note that in the optimal configuration, each node either hears music or doesn't hear music. Now, we cannot have a p-node that hears music nor an s-node that hears music. For each c-node, we can have any state we wish.

Typically, in many graph problems (especially those involving TREES), these "state" observations inspire a dynamic programming solution, rather than a greedy one I stupidly try to look for. Let $$$dp[u][0]$$$ denote the minimal number of walls needed to construct a valid solution for the subtree containing $$$u$$$ if node $$$u$$$ doesn't hear music, and $$$dp[u][1]$$$ if node $$$u$$$ does.

Say $$$u$$$ is a p-node. Then, $$$dp[u][0]=\infty$$$ because it has to hear music. Let $$$adj$$$ be the set of all of the children of $$$u$$$. Then, $$$dp[u][1]=\sum_{v \in adj} \min(dp[v][1], dp[v][0]+1).$$$ We are required to add one for $$$dp[v][0]$$$ because we will need to construct a single wall between a non-music and a music node.

Similarly, for s-nodes, $$$dp[u][1]=\infty$$$ and $$$dp[u][0]=\sum_{v \in adj} \min(dp[v][0], dp[v][1]+1)$$$.

For c-nodes, we combine the two summations developed above to calculate $$$dp[u][1], dp[u][0]$$$.

Now the answer is just $$$\min(dp[1][0], dp[1][1])$$$. Hooray!

My solution

Link to submission: https://codeforces.me/contest/1926/submission/248174404

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский dlucoding813 2024-02-25 03:00:24 0 (published)
en8 Английский dlucoding813 2024-02-25 03:00:02 3 Tiny change: 'k to submition: <url>' -> 'k to submission: <url>'
en7 Английский dlucoding813 2024-02-25 02:59:43 88
en6 Английский dlucoding813 2024-02-25 02:59:07 3302
en5 Английский dlucoding813 2024-02-25 02:54:30 483 Tiny change: 'this up)\n**Soluti' -> 'this up)\n\n**Soluti'
en4 Английский dlucoding813 2024-02-25 02:50:12 1270
en3 Английский dlucoding813 2024-02-25 02:40:47 530
en2 Английский dlucoding813 2024-02-25 02:34:30 21 Tiny change: '$$\sum_{i=0}' -> '$$\displaystyle \sum_{i=0}'
en1 Английский dlucoding813 2024-02-25 02:33:27 73 Initial revision (saved to drafts)