304 North Cardinal St.
Dorchester Center, MA 02124

# Two k-Convex Polygons CodeChef Solution

## Two k-Convex Polygons CodeChef Solution in C++14

``````
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N =1e3 + 50;
pair<ll,int> A[N];
ll pre[N];
int taken[N];
bool check(int idx , ll s1 , ll s2 , int l1, int l2){
if(l1 == 0 && l2 == 0){
if(s1 < 0 && s2 < 0) return true;
else return false;
}
else if(l1 == 0){
s2 -= A[idx].first;
--l2;
taken[idx] = 1;
if(check(idx+1 , s1 , s2 , l1 , l2)) return true;
return false;
}
else if(l2 == 0){
s1 -= A[idx].first;
--l1;
taken[idx] = 0;
if(check(idx+1 , s1 , s2, l1 , l2)) return true;
return false;
}
else{
s1 -= A[idx].first;
--l1;
taken[idx] = 0;
if(check(idx+1 , s1, s2 , l1 , l2)) return true;
s1 += A[idx].first;
++l1;
s2 -= A[idx].first;
--l2;
taken[idx] = 1;
if(check(idx+1 , s1 , s2 , l1, l2)) return true;
return false;
}
}

int main(){
ll n , k;  cin >> n >> k;
for(int i = 1;i <= n ; ++i) cin >> A[i].first , A[i].second = i;
sort(A+1 , A+n+1);
reverse(A+1 , A+n+1);
for(int i = 1;i <= n; ++i) pre[i] =pre[i-1] +  A[i].first;
for(int i = 1;i <= n ; ++i){
for(int j = i+k;j <= n-k+1 ; ++j){
if(A[i].first < pre[i+k-1]-pre[i] && A[j].first < pre[j+k-1]-pre[j]){
cout << "Yes" << endl;
for(int z = i ; z <= i+k-1 ; ++z)
cout << A[z].second << ' ';
for(int z = j ; z <= j+k-1 ; ++z)
cout << A[z].second << ' ';
cout << endl;
return 0;
}
}
}
for(int i = 1;i <= n-2*k+1 ; ++i){
for(int j = i+1; j <= min(n-k+1,i+k-1) ; ++j){
ll lft = A[i].first - pre[j-1] + pre[i];
ll rht = A[j].first;
//cout << i << ' ' << j << ' ' << lft << ' ' << rht << endl;
if(check(j+1 , lft , rht , k - (j-i) , k-1)){
cout << "Yes" << endl;
for(int z = i; z < j ;++z)
cout << A[z].second << ' ';
for(int z = j+1; z <= i+2*k-1 ; ++z)
if(taken[z] == 0) cout << A[z].second << ' ';
cout << A[j].second << ' ';
for(int z = j+1;z <= i+2*k-1 ; ++z)
if(taken[z] == 1) cout << A[z].second << ' ';
cout << endl;
return 0;
///
}
}
}
cout << "No" << endl;
return 0;
}``````

## Two k-Convex Polygons CodeChef Solution in C

``````#include<stdio.h>
void quicksort(long long int x[],int y[],int first,int last){
int pivot,j,i,temp1;
long long int temp;

if(first<last){
pivot=first;
i=first;
j=last;

while(i<j){
while(x[i]<=x[pivot]&&i<last)
i++;
while(x[j]>x[pivot])
j--;
if(i<j){
temp=x[i];
x[i]=x[j];
x[j]=temp;

temp1=y[i];
y[i]=y[j];
y[j]=temp1;
}
}

temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;

temp1=y[pivot];
y[pivot]=y[j];
y[j]=temp1;
quicksort(x,y,first,j-1);
quicksort(x,y,j+1,last);

}
}

int main()
{
int n,k,p,poly_count=0,y,z,k_diff,k_count,i,j,v,count=0,flag=0,temp_count;
scanf("%d%d",&n,&k);
int b[n],res[k],res1[k],btemp[n];
long long int a[n],sum=0,diff,temp[n];
for(i=0;i<n;i++){
scanf("%lld",&a[i]);
b[i]=i+1;
}
quicksort(a,b,0,n-1);
p=k-1;
for(i=p;i<n;i++)
{
sum=0;
for(j=i-1,count=1;count<k;j--,count++)
sum=sum+a[j];

if(sum>a[i])
{
poly_count=1;
res[0]=b[i];
k_count=1;
k_diff=k-k_count;
diff=a[i];
while(k!=k_count)
{
for(y=0;y<i;y++)
{
sum=0;
for(v=y,count=1;count<=k_diff;v++,count++)
{
sum=sum+a[v];
}
if(sum>diff)
{res[k_count]=b[v-1];k_count++;k_diff=k-k_count;diff=diff-a[v-1];break;}
}
}//while
}

if(poly_count==1)break;
// p++;
}
if(poly_count==1)
{

temp_count=0;
for(i=0;i<n;i++)
{
flag=0;
for(j=0;j<k;j++)
{
if(b[i]==res[j]){flag=1;break;}
}
if(flag==0){temp[temp_count]=a[i];btemp[temp_count]=b[i];temp_count++;}
}
p=k-1;
for(i=p;i<temp_count;i++)
{
sum=0;
for(j=i-1,count=1;count<k;j--,count++)
sum=sum+temp[j];

if(sum>temp[i])
{
poly_count=2;
for(z=i,count=1;count<=k;z--,count++)res1[count-1]=btemp[z];
break;
}
}
}
if(poly_count==2)
{
printf("Yes\n");
for(i=0;i<k;i++)
printf("%d ",res[i]);
for(i=0;i<k;i++)
printf("%d ",res1[i]);
}
else
printf("No");
/* for(i=0;i<temp_count;i++)
printf("%d------%d\n",temp[i],btemp[i]);*/
return 0;
}``````

## Two k-Convex Polygons CodeChef Solution in JAVA

``````import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.TreeMap;
import java.util.TreeSet;

class TKCONVEX
{
public static void main(String[] args)
{
OutputWriter out	=	new OutputWriter(System.out);

long[] sticks = new long[n];
for(int i = 0 ; i < n ; i++)
sticks[i] = sticksi[i];

Arrays.sort(sticks);
int[] indexlookup	=	indexlookup(sticks,sticksi);
Pair p1	=	findPolygon(sticks,k);

if(p1 == null)
{
out.printLine("No");
out.close();
return;
}

long[] sticksnew 		= new long[n-k];
int[] sticknewindexs	= new int[n-k];
int j = 0;
int p = 0;
int[] pointers = p1.sides;

for(int i = 0 ; i < sticks.length ; i++)
{
if(!(( p < pointers.length && pointers[p] == i && p++ > -1) || p1.base == i))
{
sticksnew[j++] = sticks[i];
sticknewindexs[j-1] = i;
}
}

Pair p2 = findPolygon(sticksnew, k);
if(p2 == null)
{
out.printLine("No");
out.close();
return;
}

out.printLine("Yes");
for(int i = 0 ;i < p1.sides.length ; i++)
{
out.print((indexlookup[p1.sides[i]]+1)+" ");
}
out.print((indexlookup[p1.base]+1) + " ");

for(int i = 0 ;i < p2.sides.length ; i++)
{
out.print((indexlookup[sticknewindexs[p2.sides[i]]]+1)+ " ");
}

out.print((indexlookup[sticknewindexs[p2.base]]+1) + " ");

out.close();
}

private static int[] indexlookup(long[] sticks, int[] sticksi)
{
TreeMap<Integer, TreeSet<Integer>> tree	=	new TreeMap<Integer, TreeSet<Integer>>();
for(int i = 0 ; i < sticksi.length ; i++)
{
if(tree.get(sticksi[i]) == null)
tree.put(sticksi[i], new TreeSet<Integer>());

}

int[] index	=	new int[sticks.length];
for(int i = 0 ; i < index.length ; i++)
{
index[i] = tree.get((int)sticks[i]).pollFirst();
}

return index;
}

private static Pair findPolygon(long[] sticks, int k)
{
int n = sticks.length;
int stickpointer = k-1;

while(stickpointer < n)
{
int[] pointers	=	new int[k-1];
long sum = 0;
for(int i = stickpointer-1 ; i >= stickpointer-k+1 ; i--)
{
pointers[i+k-stickpointer-1] = i;
sum += sticks[i];
}

int pointer = 0;
int lastpointer = -1;	//value of last pointer
while(sum > sticks[stickpointer] && pointer < k-1)
{
int temppointer = pointers[pointer] - 1;
if(
temppointer >= 0 &&
temppointer != lastpointer &&
sum - sticks[pointers[pointer]] + sticks[temppointer] > sticks[stickpointer])
{
sum = sum - sticks[pointers[pointer] ] + sticks[temppointer];
pointers[pointer] = temppointer;
}
else
{
pointer++;
lastpointer = pointers[pointer-1];
}
}

if(pointer == k-1)
{
return new Pair(pointers, stickpointer);
}

//update ]\stickpointer
stickpointer++;
}

return null;
}

static class Pair
{
int[] sides;
int base;

public Pair(int[] sides, int base)
{
this.sides = sides;
this.base = base;
}

@Override
public String toString()
{
return Arrays.toString(sides) + " , " + base;
}
}

private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;

this.stream = stream;
}

if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}

while (isSpaceChar(c))
int sgn = 1;
if (c == '-') {
sgn = -1;
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

while (isSpaceChar(c))
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
} while (!isSpaceChar(c));
return res.toString();
}

public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public String next() {
}

public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}

static class OutputWriter {
private final PrintWriter writer;

public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
outputStream)));
}

public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}

public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}

public void printLine(Object... objects) {
print(objects);
writer.println();
}

public void close() {
writer.close();
}

public void flush() {
writer.flush();
}

}

static class IOUtils {

int[] array = new int[size];
for (int i = 0; i < size; i++)
return array;
}

}
}``````

## Two k-Convex Polygons CodeChef Solution in PYTH

``````import sys
from collections import defaultdict

n, k = map(int, raw_input().split())
a = map(int, raw_input().split());

dic = defaultdict(list)
for i, v in enumerate(a):
dic[v].append(i + 1)
a.sort()
x, y = n+1, -1
for i in xrange(k - 1, n):
if sum(a[i - k + 1 : i + 1]) > 2 * max(a[i - k + 1 : i + 1]):
x = min(x, i)
y = max(y, i)

if x == y or x == n + 1 or y == -1 or y + 1 < 2 * k:
print "No"
sys.exit(0)

if x < y - k + 1:
print "Yes"
for i in a[x - k + 1: x + 1]:
print dic[i].pop(),
for i in a[y - k + 1: y + 1]:
print dic[i].pop(),
sys.exit(0)

b = a[y - 2 * k + 1 : y + 1]

for mask in xrange(1 << (2 * k)):
fm, fs = 0, 0
sm, ss = 0, 0
cnt = 0
for i in xrange(2 * k):
if (mask & (1 << i)) == 0:
cnt += 1
fs += b[i]
fm = max(fm, b[i])
else:
ss += b[i]
sm = max(sm, b[i])
if cnt == k and 2 * fm < fs and 2 * sm < ss:
x = []
y = []
for i in xrange(2 * k):
if (mask & (1 << i)) == 0:
x.append(dic[b[i]].pop())
else:
y.append(dic[b[i]].pop())
print "Yes"
for i in x:
print i,
for i in y:
print i,
sys.exit(0)``````

## Two k-Convex Polygons CodeChef Solution in GO

``````package main

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

func main() {

var buf bytes.Buffer

res := solve(n, k, A)
if len(res) > 0 {
buf.WriteString(fmt.Sprintf("Yes\n"))
for i := 0; i < len(res); i++ {
buf.WriteString(fmt.Sprintf("%d ", res[i]+1))
}
buf.WriteByte('\n')
} else {
buf.WriteString("No\n")
}

fmt.Print(buf.String())
}

for i := 0; i < len(s); i++ {
if s[i] == '\n' {
return s[:i]
}
}
return s
}

func normalize(s string) string {

for i := len(s); i > 0; i-- {
if s[i-1] >= 'a' && s[i-1] <= 'z' {
return s[:i]
}
}
return ""
}

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 solve(n int, k int, A []int) []int {
B := make([]Pair, n)

for i := 0; i < n; i++ {
B[i] = Pair{A[i], i}
}

sort.Sort(Pairs(B))

var sum int64
first := -1

res := make([]int, 2*k)

arr := make([]int, 2*k)

for i := 0; i <= n; i++ {
if i >= k {
// sum is s[i-k:i]
if 2*int64(B[i-1].first) < sum {
// a good choice
if first < 0 {
first = i - 1
for p := 0; p < k; p++ {
res[p] = B[i-k+p].second
}
} else if i-2*k >= 0 {
if i-k > first {
// two segments, one ending at first, another ending at first
for p := 0; p < k; p++ {
res[p+k] = B[i-k+p].second
}
return res
}
for p := 0; p < 2*k; p++ {
arr[p] = B[i-2*k+p].first
}
if x := check(arr); x > 0 {
// case two
var p int
for j := 0; j < 2*k; j++ {
if (x>>uint(j))&1 == 1 {
res[p] = B[i-2*k+j].second
p++
}
}
for j := 0; j < 2*k; j++ {
if (x>>uint(j))&1 == 0 {
res[p] = B[i-2*k+j].second
p++
}
}
return res
}
}
}
sum -= int64(B[i-k].first)
}
if i < n {
sum += int64(B[i].first)
}
}

return nil
}

type Pair struct {
first  int
second int
}

type Pairs []Pair

func (this Pairs) Len() int {
return len(this)
}

func (this Pairs) Less(i, j int) bool {
return this[i].first < this[j].first
}

func (this Pairs) Swap(i, j int) {
this[i], this[j] = this[j], this[i]
}

func check(arr []int) int {
n := len(arr)
if n == 0 {
return 0
}
// n <= 20
k := n / 2

x := (1 << uint(k)) - 1
end := 1 << uint(n)

for x < end {
var first int64
var second int64
var a, b int64
for i := 0; i < n; i++ {
if (x>>uint(i))&1 == 1 {
first += int64(arr[i])
a = int64(arr[i])
} else {
second += int64(arr[i])
b = int64(arr[i])
}
}
if 2*a < first && 2*b < second {
return x
}
x = nextNum(x)
}
return 0
}

func nextNum(x int) int {
// right most set bit
rightOne := x & -x

// reset the pattern and set next higher bit
// left part of x will be here
nextHigherOneBit := x + rightOne

// nextHigherOneBit is now part [D] of the above explanation.

// isolate the pattern
rightOnesPattern := x ^ nextHigherOneBit

rightOnesPattern = (rightOnesPattern) / rightOne

// correction factor
rightOnesPattern >>= 2

// rightOnesPattern is now part [A] of the above explanation.

// integrate new pattern (Add [D] and [A])
next := nextHigherOneBit | rightOnesPattern

return next
}``````
##### Two k-Convex Polygons CodeChef Solution Review:

In our experience, we suggest you solve this Two k-Convex Polygons 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 Two k-Convex Polygons CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Two k-Convex Polygons 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!