Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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.
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!
