GAME THEORY IN COMPETITIVE PROGRAMMING

Game Theory in Competitive Programming Series: Part 2

Part 2 of Game Theory in CP — Game With Array (Codeforces)

Shivamjha

Published in

Intellectually Yours

5 min readOct 14, 2020

Welcome to part 2 of this series, in case you have missed part 1, here is the link: https://medium.com/intellectually-yours/game-theory-in-competitive-programming-series-part-1-7be1d8d6d159

Today we would be discussing the problem, Game with Array on codeforces: https://codeforces.com/problemset/problem/1355/D.

THE PROBLEM STATEMENT

Petya and Vasya are competing with each other in a new interesting game as they always do.

At the beginning of the game Petya has to come up with an array of N positive integers. Sum of all elements in his array should be equal to S. Then Petya has to select an integer K such that 0≤K≤S.

In order to win, Vasya has to find a non-empty subarray in Petya’s array such that the sum of all selected elements equals to either K or S−K. Otherwise Vasya loses.

You are given integers N and S. You should determine if Petya can win, considering Vasya plays optimally. If Petya can win, help him to do that.

Input:

The first line contains two integers N and S (1≤N≤S≤10^6) — the required length of the array and the required sum of its elements.

Output:

If Petya can win, print “YES” (without quotes) in the first line. Then print Petya’s array in the second line. The array should contain N positive integers with sum equal to S. In the third line print K. If there are many correct answers, you can print any of them.

If Petya can’t win, print “NO” (without quotes).

You can print each letter in any register (lowercase or uppercase).

Examples

Input:

1 4

Output

YES
4
2

Input

3 4

Output

NO

Input

3 8

Output

YES
2 1 5
4

It is strongly recommended to first try this question on your own and then only move forward

HINT 1:

First try to generalize your array with some numbers such that you can always construct an array with sum of elements equal to S and length equal to N.

HINT 2:

After that try to find out whether there exists an integer K such that the sum of no subarray equals K or S-K.

Full Solution:

As N (length of the array) and S (sum of elements of the array) are of the order of 10⁶, and there are multiple such queries, we can’t generate a completely different sequence every time as that would be very slow and memory inefficient.

So, let’s first come up with a strategy to fill the elements of the array such that they have sum equal to S.

Notice in the constraints it is given that S>=N, and all the elements of the array should be positive:- which simply means that each element of the array is guaranteed to be greater than equal to 1. So, except for the last element, let’s put all the elements to be equal to 1. The sum of these N-1 elements is simply N-1, therefore we can say that the last element of the array has to be equal to S-(N-1), which is nothing but S-N+1.

Here, all the elements except the last element are equal to 1 and the last element is equal to S-N+1 because we have to satisfy the condition that the sum of all elements should be equal to S.

A few examples of our constructed array;

N=5, S=10

1 1 1 1 6

N=8, S=8

1 1 1 1 1 1 1 1

N=6, S=100

1 1 1 1 1 95

Now that we have created our array for any N and any S, we move on to the next part of the solution which is to find whether there exists an integer K such that the sum of no subarray equals to K or S-K.

For simplicity, let the last element of the array be denoted by ‘x’ from now on, we already know the value of x, which is x=S-N+1.

Let’s find out all the subarray sums that exist in our array. As N-1 elements are already 1, it is fairly easy to calculate the subarrays.

Let’s first find out all the subarrays which don’t include the last element. Here all the subarray sums are within the range [1 to N-1]. If we take the largest subarray consisting of elements from 1 to N-1 we get a sum equal to N-1. All other subarray sums would be less than this sum obtained as they would be inside of this subarray.

We can now say that K is not included in the range [1 to N-1].

Now we take the case where the last element is included in the subarray sums. Let’s find out what all subarrays we can now come up with. The answer is simply from [x to S]. Imagine like this: the largest sum subarray is the whole array whose sum is S and the lowest sum subarray is just x (if we take only the last element). Thus it can be proved that all the other subarrays which include the last element will have sum in the range [x to S] as they would completely lie inside the largest subarray.

Now we can say that K is not included in the range [x to S].

Here we can see the K should neither be included in the range [x to S] nor in the range [1 to N-1].

Also by the constraints, K should not exceed S. Thus we can say that for a solution to exist, these ranges must be non-overlapping and there must exist an integer between these two ranges which is included in none of the range.

Let’s visualize this:

For a solution to exist,

[ 1, 2, 3………., N-3, N-2, N-1] .…K…. [x , x+1 , x+2 , x+3………..S-2,S-1,S ]

We should see that for a solution to exist, there should be a minimum gap of 2 between x and N-1 because we also have to fit in a positive integer K between these two ranges. One may argue that simply x > N-1 should be sufficient but here we cannot guarantee whether or not there exists some integer between N-1 and x. What if N-1 and x are consecutive integers. That’s why the extra condition of minimum gap=2. Therefore solving this: x — (N-1)>=2, replacing x by S-N+1, we get, S-N+1-N+1>=2.

Which implies S>=2*N.

Finally, we have come to the answer, if S>=2*N, there will always be a solution and that K can be equal to anything between N to x-1. For the sake of simplicity, we can put K to be just greater than N-1 which is N.

However, if S<2*N, there simply does not exist a solution.

IMPLEMENTATION

C++ code for reference: https://codeforces.com/contest/1355/submission/94718302

Java code: https://codeforces.com/contest/1355/submission/95481920

Note: As this is a constructive problem, multiple solutions are valid for this question.

That’s all for today! Stay tuned for Part 3 of Game Theory in CP.