Hi there,

I am trying to solve this problem : http://codeforces.net/contest/302/problem/C, however even on reading the editorial I am not able to get how to solve it.

Editorial link.

Editorial says that it can be solved using dfs but I am not even able to figure out the graph in the problem.

Further, most of solutions I have read are doing this :

if((n is odd) || (n is even and #negatives is even)) ans= sum of absolute values of all numbers

else ans=sum of absolute values of all numbers-2*(abs(element with minimum absolute value)) ``

Can you please help me in understanding how this is working and how to apply dfs in this ?

Thanks in advance.

Hi there, I came across this dp solution for subset sum problem which uses O(sum) space rather than O(n*sum). The array is filled in a reverse manner i.e. starting from sum.

But I am not able to understand it properly,I know what is happening but not able to make clear sense out of it. Can someone please explain, how its working.

bool is_subset_sum(vector<int>& v,int sum)
{
int n=v.size();
vector<int>dp(sum+1,0);
dp[0]=1; //sum =0 is always attainable.

for(int i=0;i<n;i++)for(int j=sum;j>=v[i];j--)
     dp[j]|=dp[j-v[i]];

return dp[sum];

}

Hi there,

I am not able to solve div-2 1000 problem of yesterday's srm 644. Please ,provide some hint to the direction in which I can proceed.

================================================================================================ TreeCutting Problem Statement

Wolf Sothe has an undirected tree with N vertices, numbered 0 through N-1. You are given the description of the tree as a int[] par with N-1 elements. For each valid i, the tree contains the edge between vertices (i+1) and par[i]. (Note that for your convenience par[i] is always smaller than i+1.)

Some of the vertices contain a positive integer, others are empty. You are given a int[] num with N elements. For each valid i, num[i] is either the number written in vertex i, or -1 if vertex i is empty.

Sothe can modify the tree by cutting some of its edges. Sothe's goal is to reach a configuration with the following properties: Each connected component contains exactly one vertex with an integer. The number of vertices in each component is equal to the only integer in that component.

Return "POSSIBLE" (quotes for clarity) if Sothe can reach some configuration with the desired properties by cutting zero or more edges. Otherwise, return "IMPOSSIBLE". Note that the return value is case-sensitive. Definition

Class TreeCutting Method can Parameters vector , vector Returns string Method signature string can(vector par, vector num) (be sure your method is public) Limits

Time limit (s) 2.000 Memory limit (MB) 256 Constraints

N will be between 1 and 50, inclusive. par will contain exactly N-1 elements. For each i, the i-th element of par will be between 0 and i, inclusive. num will contain exactly N elements. Each element in num will be either -1 or between 1 and N, inclusive. Test cases

par { 0, 1, 2, 2, 2 } num { 2, -1, -1, 4, -1, -1 } Returns "POSSIBLE" This is a tree with 6 vertices. The edges are 1-0, 2-1, 3-2, 4-2, and 5-2. Vertex 0 contains the integer 2, vertex 3 contains the integer 4, and all other vertices are empty.

Sothe can reach his goal by cutting the edge 1-2. This will produce two components. In one component we have the vertices {0,1}. One of them contains the number 2 (which is also the size of this component) and the other is empty. In the other component we have the vertices {2,3,4,5}. One of them contains the number 4 (which is also the size of this component) and the other three are empty. par { 0, 1, 2, 2, 2 } num { 3, -1, -1, 3, -1, -1 } Returns "IMPOSSIBLE" par { 0, 1, 2, 2, 2 } num { 2, -1, -1, 3, -1, -1 } Returns "IMPOSSIBLE" The tree has 6 vertices but in any valid final configuration the components must have 2+3 = 5 vertices, which is impossible. par { 0, 1, 2, 2, 1, 5, 2, 6, 6 } num { -1, -1, 2, -1, 1, 3, -1, 1, 1, 2 } Returns "POSSIBLE" par { 0, 1, 2, 2, 1, 5, 2, 6, 6 } num { -1, -1, 2, -1, 1, -1, 3, 1, 1, 2 } Returns "IMPOSSIBLE" par { 0, 0, 0, 0, 1, 1, 2, 3, 3, 3, 4, 4, 4, 5, 9, 9, 14, 14, 14, 16, 20 } num { -1, 3, -1, -1, -1, -1, -1, 1, 1, -1, -1, -1, 3, 1, -1, 1, 8, -1, -1, 4, -1, -1 } Returns "POSSIBLE" par { 0, 0, 0, 0, 1, 1, 2, 3, 3, 3, 4, 4, 4, 5, 9, 9, 14, 14, 14, 16, 20 } num { -1, 2, -1, -1, -1, -1, -1, 1, 1, -1, -1, -1, 3, 1, -1, 1, 9, -1, -1, 4, -1, -1 } Returns "IMPOSSIBLE" par { 0, 0, 1, 1 } num { -1, -1, 5, -1, -1 } Returns "POSSIBLE" No cutting necessary.

==========================================================================================

.