HackwithInfy 2nd Round DP Question help needed

Given a tree with N nodes we are required to seperate a connected component with exactly k nodes. You are given queries specifying this k. We need to find the minimum edges to be removed for each query.
First line specifies N.
Next N-1 lines specify edges.
Next line shows Q(number of queries).
Subsequent Q lines contain k for each query.

N <= 3000
Q <= 3000
K <= N

1 2
1 3
1 4
1 5


same discussion : https://codeforces.com/blog/entry/68398

Bro it’s not hack with infy round 2, it’s from infytq round 2 …
Ps have u got mail…
@aryanc403 @l_returns help… This same question is in my set too…

I have got the mail yesterday for a pre-placement interview for System Engineer Specialist. My Infytq Upgrade Test was on 7th August.

Same with me how many test cases u complete…

One complete(15/15) and for others 3 each.

can you give solution of this problem?

yes, i got mail from infosys… you won pre-placement interview for power programmer role.

anyone did you received the mail for the date of interview of power programmer.

I have the same question…I also not able to think about the solution that time…as problem looks easy but was not…It is one of the hardest problem I guess in the sets of round 2…Till now I’m not able to find the correct solution of this problem…:(:slightly_frowning_face:

Means 8 lakh… Package…so u did 32+ test cases

Same here…:pensive::pensive::pensive::pensive: (20 char)

How many questions needs to be solved to get PPI for Power programmar through Infytq round 2 and in how many days do we get the result?

at least 2 in less time.

Forgive me if this is wrong as I haven’t coded it myself, but the solution I think is:
Preprocess dp(u, sz) as minimum edges in subtree of u that needs removal so that the component including u have a size of sz. This can be processed in O(N ^ 2).
Then for each query run through all dp(u, k), if u is not root take dp + 1 as the answer, else take dp. Each query is O(N), so it’s O(NQ) for all queries.

1 Like