Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Partition It CodeChef Solution
Problem -Partition It CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
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;
int mask = 0;
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;
if (mask == 0) {
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
input = sys.stdin.buffer.readline
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:
A.add(p)
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')
answer = ' '.join(map(str, B))
sys.stdout.write(f'{answer}\r\n')
elif len(A) >= K:
answer = A[:K]
sys.stdout.write('YES\r\n')
answer = ' '.join(map(str, answer))
sys.stdout.write(f'{answer}\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):
S.add(primes[p])
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
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
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() {
reader := bufio.NewReader(os.Stdin)
var buf bytes.Buffer
tc := readNum(reader)
for tc > 0 {
tc--
n, k := readTwoNums(reader)
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.
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!
