Little Elephant and Median CodeChef Solution

Problem -Little Elephant and Median 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.

Little Elephant and Median CodeChef Solution in C++14

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>

#include <cassert>
#include <limits>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(auto it= (o).begin(); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define inrep int t;cin>>t; while(t--)
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii > vpii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll > vpll;
typedef vector<string> vs;
typedef long double ld;

template<typename T> ostream& operator<< ( ostream &o,vector<T> v ) {
    if ( v.size() >0 )
        o<<v[0];
    for ( unsigned   i=1; i<v.size(); i++ )
        o<<" "<<v[i];
    return o<<endl;
}
template<typename U,typename V> ostream& operator<< ( ostream &o,pair<U,V> p ) {
    return o<<"("<<p.first<<", "<<p.second<<") ";
}
template<typename T> istream& operator>> ( istream &in,vector<T> &v ) {

    for ( unsigned   i=0; i<v.size(); i++ )
        in>>v[i];
    return in;
}
void apply ( int ma,int n, vi &vals ) {
    int lst=0;
//     cout<<ma<<endl;
    rep ( i,n ) {
        bool cur=ma & ( 1<<i );
        if ( !lst ) {
            int cnt1=cur;
            int cnt0=!cur;
            int ma2=ma | ( 1<<i );
            reu ( j,i+1,n ) {
                if ( ma& ( 1<<j ) ) cnt1++;
                else cnt0++;
                ma2=ma2| ( 1<<j );
                if ( cnt0 &&  cnt1>=cnt0 ) {
//                     cout<<mp ( i,j ) <<": "<<ma2<<endl;
                    vals.push_back ( ma2 );
                }
            }
        }
        lst=cur;
    }
}
int main() {
    ios_base::sync_with_stdio ( false );
    inrep {
        int n;
        cin>>n;
        vi a ( n );
        cin>>a;
        int amax=*max_element ( all ( a ) );
        int mask=0;
        rep ( i,n ) if ( a[i]==amax ) mask|=1<<i;
        vi st={mask};
        int cnt=__builtin_popcount ( mask );
        if ( cnt==n ) {
            cout<<0<<'\n';
            continue;

        }
        int d=0;
        int fnd=0;
        while ( 1 ) {
            vi nst;
            for ( int j: st ) {
                int cnt=__builtin_popcount ( j );
                if ( cnt>=n-cnt ) {
                    fnd=d+1;
                    break;
                }

                apply ( j,n,nst );
            }
//             cout<<nst<<endl;
            if ( fnd ) break;
            swap ( st,nst );
            d++;
        }
        cout<<fnd<<'\n';

    }
}

Little Elephant and Median CodeChef Solution in C

#include<stdio.h>
#include<stdlib.h>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
int a[32],b[32];
int main()
{
   int t;
   scanf("%d",&t);
   while(t--)
   {
       int n;
       scanf("%d",&n);
       int i;int max_num=-1;
       for(i=0;i<n;i++)
       {
           scanf("%d",&a[i]);
           max_num=max(max_num,a[i]);
 
       }
       int cnt=0,cnt1=0;
       for(i=0;i<n;i++)
       b[i]=a[n-(i+1)];
     while(1)
      {
        int l,h,mmax=0,j,k;
          int i;
          for(i=0;i<n;i++)
          if(a[i]!=max_num)
          break;
          if(i==n) break;
          cnt++;
          for(i=0;i<n;i++)
          {
              for(j=i+1;j<n;j++)
              {
                  int c=0;
                  for(k=i;k<=j;k++)
                  {
                      if(a[k]==max_num)
                      c++;
                  }
                  int num_elements=j-i+1;
                  if(c>=(num_elements+1)/2 && num_elements>mmax)
                  {
                      mmax=num_elements;
                      l=i;
                      h=j;
                  }
              }
          }
         // printf("%d %d\n",l,h);
          for(i=l;i<=h;i++)
          a[i]=max_num;
      }
 
      while(1)
      {
        int l,h,mmax=0,j,k;
          int i;
          for(i=0;i<n;i++)
          if(b[i]!=max_num)
          break;
          if(i==n) break;
          cnt1++;
          for(i=0;i<n;i++)
          {
              for(j=i+1;j<n;j++)
              {
                  int c=0;
                  for(k=i;k<=j;k++)
                  {
                      if(b[k]==max_num)
                      c++;
                  }
                  int num_elements=j-i+1;
                  if(c>=(num_elements+1)/2 && num_elements>mmax)
                  {
                      mmax=num_elements;
                      l=i;
                      h=j;
                  }
              }
          }
         // printf("%d %d\n",l,h);
          for(i=l;i<=h;i++)
          b[i]=max_num;
      }
      printf("%d\n",min(cnt,cnt1));
   }
}
 

Little Elephant and Median 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.InputMismatchException;
import java.util.PriorityQueue;

public class Main {	
	static class State implements Comparable<State>{
		int done = 0, max = 0, it = 0;
		@Override
		public int compareTo(State o) {
			if(this.it<o.it || (this.it==o.it && this.max>=o.max))
				return -1;
			return 1;
		}
	}
	
	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		OutputWriter out = new OutputWriter(System.out);
		int t=in.readInt();
		while(t --> 0){
			int n = in.readInt();
			int max = 0;
			int[] nums = new int[n];
			for(int i=0;i<n;i++){
				nums[i]=in.readInt();
				if(nums[i] > max)
					max = nums[i];
			}
			int start=-1,end=-1;
			State state = new State();
			for(int i=0;i<n;i++){
				if(nums[i]==max){
					state.done |= 1<<i;
					state.max++;
					if(start==-1)
						start=i;
					end = i;
				}
			}
			if((end-start)<state.max*2){
				while(state.max < n){
					state.max*=2;
					state.it++;
				}
			}else{
				PriorityQueue<State> pq = new PriorityQueue<State>();
				state.it++;
				state.max*=2;
				while(state.max < n){
					int maxtot = state.max;
					boolean isDone=false;
					while(!isDone){
						for(int i=0;i<=n-maxtot;i++){
							int subtot = 0;
							for(int j=0;j<maxtot;j++){
								if((state.done & (1<<(i+j))) > 0)
									subtot++;
								else
									subtot--;
							}
							if(subtot==0){
								if(maxtot%2>0)
									throw new RuntimeException("o_O maxtot div by 2");
								isDone=true;
								State next = new State();
								next.max = state.max+maxtot;
								next.it = state.it+1;
								next.done = state.done;
								for(int j=i;j<i+maxtot;j++){
									next.done |= 1<<j;
								}
								pq.add(next);
							}
						}
						maxtot=(maxtot==2?1:maxtot-2);
					}
					state = pq.poll();
				}
			}
			out.printLine(state.it);
		}
		out.close();
	}

	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		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 boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

	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();}
	}
}

Little Elephant and Median CodeChef Solution in PYTH

#!/usr/bin/env python

def process(N, A):
    C = 0
    M = max(A)
    w = N
    while w and A.count(M) != N:
        o = 0
        P = []
        while o+w <= N:
            if A[o:o+w].count(M) >= w / 2.:
               Anew = list(A)
               for k in xrange(o,o+w): Anew[k] = M
               P.append(Anew)
            o += 1
        if P:
           return 1 + min(map(lambda p: process(N, p), P))
        w -= 1
    return C

def main():
    T = int(raw_input().strip())
    for t in xrange(T):
        N = int(raw_input().strip())
        A = map(int, raw_input().strip().split()[:N])
        print process(N, A)

main()

Little Elephant and Median CodeChef Solution in C#

using System;
using System.Collections.Generic;

namespace NewFindMedianProgram
{
    public class Program
    {
        public static void Main()
        {
            var noOfTestCases = Convert.ToInt32(Console.ReadLine());
            for (var i = 0; i < noOfTestCases; i++)
            {
                var listOfMaxNumberIndex = new List<int>();
                var noOfIntInArray = Convert.ToInt32(Console.ReadLine());
                var maxNumber = 0;
                var readLine = Console.ReadLine();
                if (readLine == null) continue;
                var inputArray = readLine.Split(' ');
                var noOfOperation = 0;
                for (var j = 0; j < noOfIntInArray; j++)
                {
                    var number = Convert.ToInt32(inputArray[j]);
                    if (number < maxNumber)
                        continue;
                    if (number == maxNumber)
                    {
                        listOfMaxNumberIndex.Add(j);
                        continue;
                    }
                    if (number > maxNumber)
                    {
                        maxNumber = number;
                        listOfMaxNumberIndex = new List<int> {j};
                    }
                }

                while (listOfMaxNumberIndex.Count < noOfIntInArray)
                {
                    noOfOperation++;
                    listOfMaxNumberIndex.Sort();
                    CalculateAndUpdateMaxNumberIndex(listOfMaxNumberIndex, noOfIntInArray);
                }
                Console.WriteLine(noOfOperation);
            }
        }

        private static void CalculateAndUpdateMaxNumberIndex(List<int> listOfMaxNumberIndex, int noOfIntInArray)
        {
            var countOfMaxElements = listOfMaxNumberIndex.Count;
            var medianCheck = noOfIntInArray/2 + 1;
            var median = noOfIntInArray - medianCheck + 1;
            var noOfMaxElementsIncluded = 0;
            var listOfCompatibleIndex = new List<IndexList>();
            if(countOfMaxElements >= median)
            {
                for (var i = 0; i < noOfIntInArray; i++)
                {
                    if(!listOfMaxNumberIndex.Contains(i))
                        listOfMaxNumberIndex.Add(i);
                }
                return;
            }
            for (var i = 0; i < countOfMaxElements; i++)
            {
                for (var j = countOfMaxElements - 1; j >= i; j--)
                {
                    var noOfElementsIncluded = listOfMaxNumberIndex[j] - listOfMaxNumberIndex[i] + 1;
                    var noOfMaxElements = j - i + 1;
                    var elementThatCanBeIncluded = noOfMaxElements*2;
                    //var medianOfIncludedCheck = noOfElementsIncluded/2 + 1;
                    //var medianOfIncluded = noOfElementsIncluded - medianOfIncludedCheck;
                    if(elementThatCanBeIncluded >= noOfElementsIncluded)
                    {
                        if (noOfMaxElementsIncluded > elementThatCanBeIncluded)
                            continue;
                        var currentIndexListElement = new IndexList
                                                          {
                                                              startIndex = listOfMaxNumberIndex[i],
                                                              endIndex = listOfMaxNumberIndex[j],
                                                              diffToLeft = -1,
                                                              diffToRight = -1,
                                                              noOfMaximumElements = noOfMaxElements
                                                          };
                        if (i - 1 >= 0)
                        {
                            currentIndexListElement.diffToLeft = listOfMaxNumberIndex[i] - listOfMaxNumberIndex[i - 1];
                        }
                        if (j + 1 < countOfMaxElements)
                        {
                            currentIndexListElement.diffToRight = listOfMaxNumberIndex[j + 1] -
                                                                  listOfMaxNumberIndex[j];
                        }
                        if (elementThatCanBeIncluded > noOfMaxElementsIncluded)
                        {
                            noOfMaxElementsIncluded = elementThatCanBeIncluded;
                            listOfCompatibleIndex = new List<IndexList>();
                        }
                        listOfCompatibleIndex.Add(currentIndexListElement);
                    }

                }
            }
            var left = false;
            var finalIndexListToUse = new IndexList();
            var minDiffOfAll = noOfIntInArray;
            if (listOfCompatibleIndex.Count == 1)
                ReplaceList(noOfIntInArray, listOfCompatibleIndex[0], listOfMaxNumberIndex);
            else
            {
                foreach (var indexList in listOfCompatibleIndex)
                {
                    var minDiffForThisIndexList = noOfIntInArray;
                    var leftForThisIndexList = false;
                    if (indexList.diffToLeft != -1)
                    {
                        minDiffForThisIndexList = indexList.diffToLeft;
                        leftForThisIndexList = true;
                    }
                    if (indexList.diffToRight != -1 && indexList.diffToRight < minDiffForThisIndexList)
                    {
                        minDiffForThisIndexList = indexList.diffToRight;
                    }
                    if(minDiffForThisIndexList < minDiffOfAll)
                    {
                        minDiffOfAll = minDiffForThisIndexList;
                        left = leftForThisIndexList;
                        finalIndexListToUse = indexList;
                    }
                }
                ReplaceList(noOfIntInArray, finalIndexListToUse, listOfMaxNumberIndex, left);
            }
        }

        private static void ReplaceList(int noOfIntInArray, IndexList indexList, List<int> listOfMaxNumberIndex, bool left)
        {
            var noOfMaxElements = indexList.noOfMaximumElements;
            var maxNoOfElementsToConverted = noOfMaxElements * 2;
            if(maxNoOfElementsToConverted >= noOfIntInArray)
            {
                for (var i = 0; i < noOfIntInArray; i++)
                {
                    if(!listOfMaxNumberIndex.Contains(i))
                        listOfMaxNumberIndex.Add(i);
                }
                return;
            }
            if(!left)
            {
                for (var i = 0; i < maxNoOfElementsToConverted; i++)
                {
                    if(!listOfMaxNumberIndex.Contains(indexList.startIndex + i))
                        listOfMaxNumberIndex.Add(indexList.startIndex + i);
                }
                return;
            }
            for (var i = maxNoOfElementsToConverted; i > 0; i--)
            {
                if(!listOfMaxNumberIndex.Contains(indexList.endIndex - i))
                    listOfMaxNumberIndex.Add(indexList.endIndex - i);
            }
        }

        private static void ReplaceList(int noOfIntInArray, IndexList indexList, List<int> listOfMaxNumberIndex)
        {
            var noOfMaxElements = indexList.noOfMaximumElements;
            var maxNoOfElementsToConverted = noOfMaxElements * 2;
            if (maxNoOfElementsToConverted >= noOfIntInArray)
            {
                for (var i = 0; i < noOfIntInArray; i++)
                {
                    if (!listOfMaxNumberIndex.Contains(i))
                        listOfMaxNumberIndex.Add(i);
                }
                return;
            }
            var left = false;
            var startIndex = indexList.startIndex;
            var endIndex = indexList.endIndex;
            var diffRight = noOfIntInArray - endIndex - 1;
            if (indexList.diffToLeft == -1 && indexList.diffToRight == -1)
            {
                left = startIndex > diffRight;
            }
            else
            {
                var minDiffForThisIndexList = 0;
                var leftForThisIndexList = false;
                if (indexList.diffToLeft != -1)
                {
                    minDiffForThisIndexList = indexList.diffToLeft;
                    leftForThisIndexList = true;
                }
                if (indexList.diffToRight != -1 && indexList.diffToRight < minDiffForThisIndexList)
                {
                    leftForThisIndexList = false;
                }
                left = leftForThisIndexList;
            }
            if(left)
            {
                if (endIndex - maxNoOfElementsToConverted < 0)
                {
                    for (var i = 0; i < maxNoOfElementsToConverted; i++)
                    {
                        if (!listOfMaxNumberIndex.Contains(i))
                            listOfMaxNumberIndex.Add(i);
                    }
                }
                else
                {
                    for (var i = 0; i < maxNoOfElementsToConverted; i++)
                    {
                        if(!listOfMaxNumberIndex.Contains(endIndex - i))
                            listOfMaxNumberIndex.Add(endIndex - i);
                    }
                }
            }
            else
            {
                if (startIndex + maxNoOfElementsToConverted > noOfIntInArray - 1)
                {
                    for (var i = 0; i < maxNoOfElementsToConverted; i++)
                    {
                        if (!listOfMaxNumberIndex.Contains(noOfIntInArray- 1 - i))
                            listOfMaxNumberIndex.Add(noOfIntInArray - i - 1);
                    }
                }
                else
                {
                    for (var i = 0; i < maxNoOfElementsToConverted; i++)
                    {
                        if (!listOfMaxNumberIndex.Contains(startIndex + i))
                            listOfMaxNumberIndex.Add(startIndex + i);
                    }
                }
            }
        }

        public class IndexList
        {
            public int startIndex;
            public int endIndex;
            public int diffToLeft = -1;
            public int diffToRight = -1;
            public int noOfMaximumElements;
        }
    }
}

Little Elephant and Median CodeChef Solution in GO

package main

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

func main() {
	reader := bufio.NewReader(os.Stdin)

	tc := readNum(reader)

	var buf bytes.Buffer

	for tc > 0 {
		tc--
		n := readNum(reader)
		A := readNNums(reader, n)
		res := solve(n, A)
		buf.WriteString(fmt.Sprintf("%d\n", res))
	}

	fmt.Print(buf.String())
}

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, A []int) int {

	mem := make(map[int]int)

	var dfs func(mask int) int

	dfs = func(mask int) int {
		var c1, c0 int
		for i := 0; i < n; i++ {
			if mask&(1<<uint(i)) > 0 {
				c1++
			} else {
				c0++
			}
		}
		if c0 == 0 {
			return 0
		}
		if c1 >= c0 {
			return 1
		}
		if v, found := mem[mask]; found {
			return v
		}
		var res int = n
		for i := 0; i < n; i++ {
			var a, b int
			next := mask
			to := -1
			for j := i; j < n; j++ {
				if mask&(1<<uint(j)) > 0 {
					a++
				} else {
					b++
					next |= 1 << uint(j)
				}
				if a >= b && next != mask {
					to = next
				}
			}
			if to > 0 {
				res = min(res, dfs(to)+1)
			}
		}
		mem[mask] = res
		return mem[mask]
	}

	mx := A[0]
	for i := 1; i < n; i++ {
		mx = max(mx, A[i])
	}

	var mask int
	for i := 0; i < n; i++ {
		if A[i] == mx {
			mask |= 1 << uint(i)
		}
	}

	return dfs(mask)
}

func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}
Little Elephant and Median CodeChef Solution Review:

In our experience, we suggest you solve this Little Elephant and Median 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 Little Elephant and Median CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Little Elephant and Median 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

Leave a Reply

Your email address will not be published. Required fields are marked *