pop1912's blog

Need help in CSES Two Sets
By pop1912, history, 4 years ago, In English

Hi, Can you help me in this CSES Two Sets problem?.

Statement:

Your task is to divide the numbers 1,2,…,n into two sets of equal sum.

Input

The only input line contains an integer n.

Output

Print "YES", if the division is possible, and "NO" otherwise.

After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.

Constraints 1≤n≤106

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

To be able to divide the set into two different sets of equal sum, n must be of the form 4k or 4k+3,

case [i] -> n = 4k put first n/4 numbers and last n/4 in first set, and remaining n/2 numbers in second set, for eg, n= 8 {1,2,7,8}, {3,4,5,6}

case [ii] -> n = 4k + 3

observation- 4n 4n+1 4n+2 4n+3, then 4n + 4n+3 == 4n + 1 + 4n + 2, therefore make partition accordingly.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    i think you might be slightly late

    → Reply
»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

You can initialise a matrix (let's say dp) where (i,j) element stores the number of ways of making the sum j using values from 1 to i. Then our relation becomes dp[i][j]=dp[i-1][j]+dp[i-1][j-i]. Of course, provided j>i.

Here's the code just in case:

https://cses.fi/paste/d377beb47794981f91183b/

Hope it helps :)

→ Reply