for E: I solved it using inclusion-exclusion principle Submission

I solved it using inclusion-exclusion principle.Submission

no it is Ayush.Ayush will start removing leaf node and Ashish will be the last person to remove third last leaf node after that only two leaf nodes(x and some node v) remain from which Ayush can remove x and he wins.

its not always the case that you have to travel cycle atleast once

how are you taking care of these cases

)(

(

)

you have to get length of cycle in component containing 1

we should only consider monotonically increasing sequence

it's not increasing nor decreasing... however if you notice function is increasing in intervals of b. eg. from x = 0,1,2,..b — 1 f(x) is increasing at x = b f(x) again drops and starts increasing same as for previous x

delayed due to inadequacy in problem

what about if we can get max answer with arr[i — 1]

may be!!!! designing transition can be different

since we know already how many elements we have to take i.e N/2 so instead of using N^2 dynamic programming solution we can do it in O(N) by maintaining at each i that we have taken i/2 elements upto now and have maximum possible sum till now, since at each i we have two possiblity either pick that element or don't pick it.

We have two cases to handle when i is odd and i is even

1. when i is odd and we want to pick ith element we can build a current state from (i — 2)th and (i -3)rd state because we know we have already calculated answer for (i/2) — 1 element up to (i — 2) and (i — 3) so that after adding total elements become i/2.

And if we don't pick ith element we have to construct answer so that total element chosen is i/2 and sum is maximum we can construct answer by taking arr[i — 1] and help from states (i — 1),(i — 2),(i — 3) (for arr[i — 1] only these are possibility can you see why???) and also by using arr[i — 2] and help from state (i — 3) (for arr[i — 2] only this is possible). You don't have to consider other elements and states because you cannot build current state having i/2 elements.

1. Similarly for even but possiblity for even i's are less than that of odd i's you can think about it.

we can maintain dp[i][j], j = {0,1}

Initially dp[2][1] = arr[2] and dp[2][0] = arr[1] (Base Case)

1. dp[i][1] denotes maximum sum when we are at i and we are picking ith element and floor(i / 2) elements(subset of 1...i such that adjacent element are not picked).

2. dp[i][0] denotes maximum sum when we are at i and we are NOT picking ith element and floor(i / 2) elements (subset of 1...(i — 1) such that adjacent element are not picked)

With some work we can fill dp upto n.

Our final answer will be max(dp[n][1],dp[n][0]) My Submission

sieve is not really needed here just make a set of smallest prime divisor of all numbers it will(number of sets) be less than equal to 11.

55555(n-1 times)8(1 time) also works.