Join Us
Can you please explain your approach
Entering edit mode
// FOR COMPUTER LABS QUESTIONS
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll dp[100001][2][2];
ll solve(ll ind,ll flag,ll pc,string &s){
if(ind==s.length()) {
if(flag) return 0;
else return 1e9;
}
if(dp[ind][flag][pc]!=-1) return dp[ind][flag][pc];
ll ans = 1e9;
if(flag){
if(pc==0){
if(s[ind]=='.'){
ans = min(1+solve(ind+1,1,1,s),solve(ind+1,1,0,s));
}
else{
ans = solve(ind+1,0,0,s);
}
}
else{
if(s[ind]=='.'){
ans = min(1+solve(ind+1,1,1,s),solve(ind+1,1,0,s)); }
else{
ans = solve(ind+1,1,0,s);
}
}
}
else{
if(pc==0){
if(s[ind]=='.'){
ans = 1+solve(ind+1,1,1,s);
}
else{
ans = 1e9;
}
}
}
return dp[ind][flag][pc] = ans;
}
int main() {
ll n;
cin>>n;
string s;
cin>>s;
memset(dp,-1,sizeof(dp));
ll ans =solve(0,1,0,s);
if(ans<1e9) cout<<ans<<endl;
else cout<<-1<<endl;
return 0;
}
Entering edit mode
Ques - 1
#include <bits/stdc++.h>
using namespace std;
int DFS(int idx, vector<int> &sum, int total_sum, vector<int> adj[], int &res, int parent){
for(auto it: adj[idx]){
if(it!=parent){
DFS(it, sum, total_sum , adj, res,idx);
sum[idx] += sum[it];
}
}
if(idx!=0)
res = min( res , abs(total_sum - 2*sum[idx]) );
return res;
}
int getMinSubtreeSumDifference(int vertex[],
int edges[][2], int N, int M) {
vector<int> adj[N];
vector<int> sum(N,0);
for(int i=0;i< M;i++){
adj[edges[i][0]].push_back(edges[i][1]);
adj[edges[i][1]].push_back(edges[i][0]);
}
int total_sum=0;
for(int i=0;i<N;i++){
total_sum += vertex[i];
sum[i] = vertex[i];
}
int res=INT_MAX;
return DFS(0,sum,total_sum,adj,res,-1);
}
int main()
{
int vertex[] = {4, 2, 1, 6, 3, 5, 2};
int edges[][2] = {{0, 1}, {0, 2}, {0, 3},
{2, 4}, {2, 5}, {3, 6}};
int N = sizeof(vertex) / sizeof(vertex[0]);
int M = sizeof(edges) / sizeof(edges[0]);
cout << getMinSubtreeSumDifference(vertex, edges, N, M);
return 0;
}
Loading Similar Posts
SIMPLE DFS SOLUTION
Just store the value of all the subtrees using dfs and then return the minimum value of abs(total_sum - 2 * sum_of_subtree[i])
int n, k;
vector<vector<int>> adj;
vector<int> val, summ;
int dfs1(int ind){
summ[ind] = val[ind];
for(auto x: adj[ind]){
if(!summ[x])
summ[ind]+=dfs1(x);
}
return summ[ind];
}
void solve(){
cin>>n;
adj.clear(); val.clear(); summ.clear();
adj.resize(n+1); val.resize(n+1); summ.resize(n+1);
for(int i=0; i<n-1; i++){
int p, q;
cin>>p>>q;
adj[p].push_back(q);
adj[q].push_back(p);
}
for(int i=1; i<=n; i++)
cin>>val[i];
int ans = 1e9;
dfs1(1);
for(int i=2; i<=n; i++){
ans = min(ans, abs(summ[1] - 2* summ[i]));
}
cout<<ans<<endl;
}
int n,k;cin>>n>>k;
vi mand(k);
for(int i = 0;i<k;i++)cin>>mand[i];
int x;
vi adj[n];
for(int i = 0;i<n;i++){
cin>>x;
int y;
while(x--){
cin>>y;
y--;
adj[i].pb(y);
}
}
queue<int>Q;
for(int i = 0;i<k;i++){
mand[i]--;
Q.push(mand[i]);
}
int ans = 0;
vi vis(n,-1);
while(!Q.empty()){
int node = Q.front();
Q.pop();
vis[node] = 1;
ans++;
for(auto it:adj[node]){
if(vis[it] == -1)
Q.push(it);
}
}
cout<<ans<<"\n";