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// Thank God!
#include <bits/stdc++.h>
using namespace std;
// Aliases for simple data types
using ll = long long;
using dd = long double;
using mpi = map<int, int>;
using mpl = map<ll, ll>;
using ull = unsigned long long;
// Constant definitions
#define PI 3.14159265358979323
#define E 2.7182818284590
#define all(x) x.begin(), x.end()
// BIG NUMBERS (MODULAR)
const ll MOD1 = 998244353;
const ll MOD2 = (ll)1e9 + 7;
// simplified aliases for vectors,pairs
template <class T>
using v = vector<T>;
template <class T>
using p = pair<T, T>;
// overloaded instream operators
template <class T1, class T2>
istream &operator>>(istream &in, pair<T1, T2> &p)
{
in >> p.first >> p.second;
return in;
}
template <class T>
istream &operator>>(istream &in, v<T> &v)
{
for (auto &x : v)
in >> x;
return in;
}
// MULTITEST TOGGLE
const bool test = true;
// INTERACTIVE TOGGLE
const bool interactive = false;
/*-------------------------------------------------------------------------------*/
const int MAXN = 1e5 + 4;
v<v<int>> adj(MAXN);
// dp[u][0] represents NO music
// dp[u][1] represents MUSIC
v<v<ll>> dp(MAXN, v<ll>(2));
string status;
void dfs(int node, int prev)
{
if (status[node] == 'P')
{
dp[node][0] = 1e18; // need to party
}
else if (status[node] == 'S')
{
dp[node][1] = 1e18; // need to sleep
}
for (auto &x : adj[node])
{
if (x != prev)
{
dfs(x, node);
if (status[node] != 'P')
{
dp[node][0] += min(dp[x][0], dp[x][1] + 1);
}
if (status[node] != 'S')
{
dp[node][1] += min(dp[x][1], dp[x][0] + 1);
}
}
}
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
adj[i].clear();
dp[i].clear();
dp[i].push_back(0);
dp[i].push_back(0);
}
int x;
for (int i = 2; i <= n; i++)
{
cin >> x;
adj[i].push_back(x);
adj[x].push_back(i);
}
cin >> status;
status = "." + status;
dfs(1, -1);
cout << min(dp[1][0], dp[1][1]) << "\n";
}
int main()
{
/*Command Line
g++ forkiespad.cpp -o forkiespad
forkiespad.exe
*/
// file input
if (interactive)
{
freopen("input.txt", "r", stdin);
}
ios::sync_with_stdio(false);
cin.tie(0);
// testcases
int t;
if (test)
{
cin >> t;
}
else
t = 1;
while (t--)
{
solve();
}
}
/*
-try out more cases
-attack the problem creatively/at different angles
-what am i missing?
-CHECK YOUR CODE
-pay attention to BOUNDS
-errors - out of bounds, edge case(n=0, n=1?), integer overflow, etc.
-WHEN IN DOUBT, USE LONG LONG
-check the for loops
-watch out for division errors (use double and ll when needed)
*/
// Thank God!
Link to submission: https://mirror.codeforces.com/contest/1926/submission/248174404
