304 North Cardinal St.
Dorchester Center, MA 02124

# Partition It CodeChef Solution

## Partition It CodeChef Solution in C++17

``````#include<bits/stdc++.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define nl "\n"
#define ff first
#define ss second
#define pb push_back
#define PI 3.141592653589793238462
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#define debug(x)  cerr << #x <<" "; _print(x); cerr << endl;
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]\n";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
void _init_(){
fastio();
#ifndef ONLINE_JUDGE
freopen("Error.txt", "w", stderr);
freopen("inputf.in", "r", stdin);
freopen("outputf.in", "w", stdout);
#endif // ONLINE_JUDGE
}
void solve() {
ll t;
cin >> t;
vector<ll> v(1e5 + 50, 0);
vector<ll> primes;
for (ll i = 2; i < 1e5 + 50; i++) {
if (v[i]) continue;
for (ll j = i * i; j < 1e5 + 50; j += i) {
v[j] = 1;
}
}
for (int i = 2; i <= 1e5 + 50; i++) {
if (!v[i]) {
primes.push_back(i);
}
}
while (t--) {
ll n, k;
cin >> n >> k;
ll korz = k;
k = min(k, n - k);
ll psz = primes.size();
auto minmax = upper_bound(primes.begin(), primes.end(), n) - primes.begin();
minmax--;
vector<ll> ans = {1};
ll target = k - 1;
while (target-- && minmax >= 0 && primes[minmax] * 2 > n) {
ans.push_back(primes[minmax--]);
}
if (k != korz) {
set<ll> st;
for (int i = 1;  i <= n; i++) {
st.insert(i);
}
for (auto c : ans) {
st.erase(c);
}
ans.clear();
for (auto c : st) {
ans.push_back(c);
}
}
if (ans.size() == korz) {
cout << "YES" << nl;
for (auto c : ans)
cout << c << " ";
cout << nl;
}
else
cout << "NO" << nl;
}
}
int main(){
_init_();
int t = 1;
int tc = 1;
while (t--) {
solve();
}
return 0;
}``````

## Partition It CodeChef Solution in C++14

``````#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long

using namespace std;

int f[100006], prime[10006], cnt = 0;
bool GroupA[100006];

void sieve(int n) {
for(int i = 2; i <= n; ++i) {
if (f[i] == 0) f[i] = prime[++cnt] = i;
for(int j = 1; j <= cnt && prime[j] <= f[i] && prime[j] * i <= n; ++j)
f[prime[j] * i] = prime[j];
}
}

int main() {
ios_base::sync_with_stdio(0); cin.tie(NULL);

sieve(100000);

int tests = 0; cin >> tests;
while (tests--) {
int n, k; cin >> n >> k;

if (k > n / 2) k = n - k, mask = 1;

int l = upper_bound(prime + 1, prime + cnt + 1, n / 2) - prime;
int r = upper_bound(prime + 1, prime + cnt + 1, n) - prime;

if (k <= r - l + 1) {
cout << "Yes\n";

for(int i = 1; i <= n; ++i) GroupA[i] = false;

GroupA[1] = true; int cnt = k - 1;
for(int i = l; i < r && cnt > 0; ++i) GroupA[prime[i]] = true, --cnt;

for(int i = 1; i <= n && k > 0; ++i)
if (GroupA[i]) {
cout << i << ' ';
--k;
}
} else {
k = n - k;
for(int i = 1; i <= n && k > 0; ++i)
if (!GroupA[i]) {
cout << i << ' ';
--k;
}
}

cout << '\n';
} else cout << "No\n";
}

return 0;
}``````

## Partition It CodeChef Solution in PYTH 3

``````
def sieve(n):
s = {}
for i in range(2, n+1):
if s.get(i) is None:
s[i] = 0
if s[i] == 0:
for j in range(i*i, n+1, i):
if s.get(j) is None:
s[j] = 1
else:
s[j] += 1
return s
for _ in range(int(input())):
# n = int(input())
n, _k = map(int, input().split(" "))

s = sieve(n)
s1 = []
s2 = [1]
for k, v in s.items():
if v == 0 and k*2 > n:
s2.append(k)
else:
s1.append(k)
if _k <= len(s2):
print("yes")
print(" ".join(list(map(str, s2[:_k]))))
elif _k >= len(s1):
print("yes")
s1 += s2[:_k]
print(" ".join(list(map(str, s1[:_k]))))
else:
print("no")``````

## Partition It CodeChef Solution in C

``````#include <stdio.h>

#include <stdlib.h>

long root(long n)
{
long low=1;
long high=n;
long mid;
long value=1;
while(low<=high)
{
mid=(low+high)/2;
if((mid*mid)<=n)
{
low=mid+1;

}
else
{
high=mid-1;
}
}
if((mid*mid)<=n)
{
return mid;
}
else
{
return mid-1;
}
}

int main()
{
long n=100000;

long p[n+1];
long i,j;

for(i=0; i<=n; i++)
{
p[i]=0;
}
for(i=2; i<=n; i++)
{

for(j=2; j<=root(i); j++)
{
if((i%j)==0)
{
p[i]=1;
break;
}
}
}

long t;
scanf("%ld",&t);
while(t--)
{
long k;
scanf("%ld %ld",&n,&k);
long a[n+1];
for(i=1; i<=n; i++)
{
a[i]=0;
}
for(i=2; i<=n; i=i+2)
{
a[i]=1;
}
for(i=3; i<=n; i++)
{
if(p[i]==0 && i*2<=n)
{
for(j=i; j<=n; j=j+i)
{
a[j]=1;
}
}
}
long s1=0;
long s2=0;
for(i=1; i<=n; i++)
{
if(a[i]==1)
{
s1++;
}
else
{
s2++;
}
}

if(k>=s1 && k<=n)
{
printf("YES\n");

for(i=1; i<=n; i++)
{
if(a[i]==1)
{
printf("%ld ",i);
}
}
k=k-s1;

for(i=1; (i<=n && k>0); i++)
{
if(a[i]==0)
{
printf("%ld ",i);
k--;
}
}

printf("\n");
}
else if(k<=s2 && k>=0)
{
printf("YES\n");

for(i=1; (i<=n && k>0); i++)
{
if(a[i]==0)
{
printf("%ld ",i);
k--;
}
}
printf("\n");

}
else
{
printf("NO\n");
}

}

}``````

## Partition It CodeChef Solution in JAVA

``````// package practice;

import java.util.*;

class Codechef {
public static void main(String[] args) {

Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0) {
int n=sc.nextInt();
int k=sc.nextInt();
int dp[]=new int [n+1];
for(int i=1;i<=n;i++) {
dp[i]=-1;
}
dp[1]=0; // can be in any set.
int together=0;
int single=1;
for(int i=2;i<=n;i++) {
if(i%2==0 && dp[i]==-1) {
dp[i]=1;
together++;
}
else if(dp[i]==-1) {
int z=2*i;
int flag=-1;
while(z<=n) {
flag=1;
if(dp[z]==-1) {
//                				  System.out.println(z);
together++;
}
dp[z]=1;
z+=i;
}
if(flag==1) {
dp[i]=1;
together++;
}
else{
dp[i]=0;
single++;
}
}
}
//                  System.out.println(together+" "+single);
if(k<=single) {
System.out.println("YES");
for(int i=1;i<=n;i++) {
if(k!=0 && dp[i]==0){
System.out.print(i+" ");
k--;
}
}
System.out.println();
}
else if(k>=together) {
System.out.println("YES");
k-=together;
for(int i=1;i<=n;i++) {
if(k!=0 && dp[i]==0){
System.out.print(i+" ");
k--;
}
else if(dp[i]==1) {
System.out.print(i+" ");
}
}
System.out.println();
}
else{
System.out.println("NO");
}
}
}
}``````

## Partition It CodeChef Solution in PYPY 3

``````import sys

def prime_sieve(n):
"""returns a sieve of primes >= 5 and < n"""
flag = n % 6 == 2
sieve = bytearray((n // 3 + flag >> 3) + 1)
for i in range(1, int(n**0.5) // 3 + 1):
if not (sieve[i >> 3] >> (i & 7)) & 1:
k = (3 * i + 1) | 1
for j in range(k * k // 3, n // 3 + flag, 2 * k):
sieve[j >> 3] |= 1 << (j & 7)
for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):
sieve[j >> 3] |= 1 << (j & 7)
return sieve

def prime_list(n):
"""returns a list of primes <= n"""
res = []
if n > 1:
res.append(2)
if n > 2:
res.append(3)
if n > 4:
sieve = prime_sieve(n + 1)
res.extend(3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not (sieve[i >> 3] >> (i & 7)) & 1)
return res

def process(N, K):
primes = prime_list(N)
A = set([1])
B = []
for p in primes:
if 2*p > N:
for i in range(1, N+1):
if i not in A:
B.append(i)
A = list(A)
#  print(A, B)
"""
K or N-K
= len(A)+c, c <= len(B)
"""
if K >= len(B):
c = K-len(B)
for i in A[:c]:
B.append(i)
sys.stdout.write('YES\r\n')
elif len(A) >= K:
sys.stdout.write('YES\r\n')
else:
sys.stdout.write('NO\r\n')

T = int(input())
for i in range(T):
N, K = [int(x) for x in input().split()]
process(N, K)``````

## Partition It CodeChef Solution in PYTH

``````N = 10**5 # value of N required
def primesieve(N):
n = N+1
sieve = [True] * (n/2)
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i/2]:
sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
# endif
# endfor i
return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]
# end fun
primes = primesieve(N)
C = [0 for x in range(N+1)]
for p in primes:
C[p] = 1
# endfor p
for k in range(3,N+1):
C[k] += C[k-1]
# endfor k
t = int(raw_input())
for i in range(t):
st = raw_input().split()
N = int(st[0])
K = int(st[1])
d = min(K,N-K)
mx = C[N] - C[N/2] +1
if mx < d:
print 'No'
else:
print 'Yes'
if d == K:
st = '1 '
p = C[N/2]
for k in range(d-1):
st += str(primes[p]) + ' '
p += 1
# endfor k
print st
else:
S = set()
p = C[N/2]
for k in range(d-1):
p += 1
# endfor k
st = ''
for k in range(2,N+1):
if not (k in S):
st += str(k) + ' '
# endif
# endfor k
print st
# endif
# endif
# endfor i
``````

## Partition It CodeChef Solution in GO

``````package main

import (
"bufio"
"bytes"
"fmt"
"os"
)

func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}

return
}

a, b = res[0], res[1]
return
}

a, b, c = res[0], res[1], res[2]
return
}

res := make([]int, n)
x := 0
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
}
return res
}

func readUint64(bytes []byte, from int, val *uint64) int {
i := from

var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp

return i
}

func main() {
var buf bytes.Buffer
for tc > 0 {
tc--
res := solve(n, k)
if len(res) == 0 {
buf.WriteString("NO\n")
} else {
buf.WriteString("YES\n")
for i := 0; i < k; i++ {
buf.WriteString(fmt.Sprintf("%d ", res[i]))
}
buf.WriteByte('\n')
}
}

fmt.Print(buf.String())
}

const MAX_N = 100001

var lpf []int

func init() {
set := make([]bool, MAX_N)
lpf = make([]int, MAX_N)
for i := 2; i < MAX_N; i++ {
if !set[i] {
for j := i; j < MAX_N; j += i {
if lpf[j] == 0 {
lpf[j] = i
}
set[j] = true
}
}
}
}

func solve(n int, K int) []int {
A := make([]int, 0, n)
B := make([]int, 0, n)

A = append(A, 1)

for i := 2; i <= n/2; i++ {
B = append(B, i)
}
for i := n/2 + 1; i <= n; i++ {
if lpf[i] == i {
A = append(A, i)
} else {
B = append(B, i)
}
}

if K < n-len(A) && n-K < n-len(A) {
return nil
}
p := len(A)
for len(B) != K && K != p {
B = append(B, A[p-1])
p--
}
if len(B) == K {
return B
}
return A[:p]
}``````
##### Partition It CodeChef Solution Review:

In our experience, we suggest you solve this Partition It CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Partition ItCodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Partition It CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!