Two k-Convex Polygons CodeChef Solution

Problem -Two k-Convex Polygons 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.

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) 
	{
		InputReader in		=	new InputReader(System.in);
		OutputWriter out	=	new OutputWriter(System.out);
		
		int n = in.readInt();
		int k = in.readInt();
		int[] sticksi	=	IOUtils.readIntArray(in, n);
		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>());
			
			tree.get(sticksi[i]).add(i);
		}
		
		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;
		}
	}
	
	static class InputReader {

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

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

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

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

		public String readString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} 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() {
			return readString();
		}

		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 {

		public static int[] readIntArray(InputReader in, int size) {
			int[] array = new int[size];
			for (int i = 0; i < size; i++)
				array[i] = in.readInt();
			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() {
	reader := bufio.NewReader(os.Stdin)

	var buf bytes.Buffer

	n, k := readTwoNums(reader)
	A := readNNums(reader, n)
	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())
}

func readString(reader *bufio.Reader) string {
	s, _ := reader.ReadString('\n')
	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
}

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 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 {
					// already first >= 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

	// right adjust pattern
	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!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn