Let dp[i] be the answer if we are currently on i-th pile and didn't take anything from, then we can either move to next pile, or start taking from this one. If we take from this one we can get only dp[i+1] or v[i]-dp[i+1], but we can force v[i]-dp[i+1] for other player only in case of odd c[i]. So if c[i] is odd dp[i] = max(dp[i+1],v[i]-dp[i+1]), otherwise dp[i]=dp[i+1].

This is how i solved C: Firstly, we want to maximize lcm(a, b) and minimize gcd(a, b). So lcm(a, b) should be a*b and gcd(a, b) = 1. Now for two numbers a and b, where a + b = n, their product a*b will be maximum if a = b = n/2.

• If n is odd, then a = n/2 and_ b = n/2 + 1_.
• If n is even, then we can't take a = b = n/2 since both of them will be equal. So we will search for the nearest odd number on the left and on the right side of n/2. If n%4 == 0, then a = n/2 -1 and_ b = n/2 + 1,_ else a = n/2 — 2 and b = n/2 + 2.

Prime gap is how I came up with it.

Odd case is more straightforward:

n1 = N/2, n2 = N/2 + 1;

cout << lcm(n1, n2) — __gcd(n1, n2) << endl;

In the even case either taking the numbers closest to each other with a gap of 2 or 4 will be best (depending on if that gap will create even numbers or not):

n1 = N/2 -1, n2 = N/2 + 1;

ll ans = lcm(n1, n2) — __gcd(n1, n2);

if(n1-1 >= 1 && n2+1 <= N) { n1--, n2++; }

ans = max(ans, lcm(n1, n2) — __gcd(n1, n2));

cout << ans << endl;

Can you please tell the approach in Throw and Take. I could solve it till here. We only have to consider one coin for each pile having odd number of coins and from that new set of coins we have to play the game and find the value of (coinsA — coinsB). Right?

How to solve this..some people applied dp but I am not exactly sure how to apply dp here. Can you please tell your approach.

I understand this condition is necessary but I am unable to understand why this is sufficient.

Firstly, notice that the condition basically says that each integer $$$i$$$ ($$$1 \leq i \leq n$$$) should lie in at most $$$k-1$$$ segments of the set. This is a necessary and sufficient condition.

I first consider this method of "building" permutations. Basically, in a permutation, for each element you can make an edge to the next element. And make an edge from the last element to zero, to denote the end of the permutation. We will try to build this graph representation of the permutation.

Now, think of the subgraph of such a graph if you only consider the nodes $$$[0, i]$$$. This will look like a directed graph with $$$m$$$ chains, with exactly one chain ending at zero. We will basically build the final graph, by adding nodes to the graph one by one, from $$$1$$$ to $$$n$$$. When we add node $$$i$$$, we only have to decide if it has any outgoing or incoming edges to lower numbered nodes. We can see that depending on our choice, the number of chains will increase by $$$1$$$, decrease by $$$1$$$, or remain same. Try to see how the number of ways to cause each of these changes only depends on the initial number of chains $$$m$$$. We must make sure that we never attach a outgoing edge to the node $$$0$$$, as it's supposed to denote the end. Notice that depending on our choice of how we add $$$i$$$ to the graph, and the previous number of chains $$$m$$$, we can exactly determine the number of segments of the final permutation, in which $$$i$$$ will lie. This will allow us to not consider choices in which this exceeds $$$k-1$$$.

As the number of chains $$$m$$$ in the subgraph $$$[0, i-1]$$$, is the only important data we need, I denote $$$\text{dp}[i][m]$$$ as the number of ways to proceed to build a good permutation, given we have already built the subgraph with nodes $$$[0, i-1]$$$, which has $$$m$$$ chains. Try to form the $$$O(1)$$$ transition. The final answer is simply $$$\text{dp}[1][1]$$$.

Code