Matchsticks CodeChef Solution

Problem -Matchsticks 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.

<<Previous CodeChef Problem Next Codechef Problem>>

Matchsticks CodeChef Solution in C++17

#include<bits/stdc++.h>
using namespace std;
template<typename... T>
void see(T&... args) { ((cin >> args), ...);}
template<typename... T>
void put(T&&... args) { ((cout << args << " "), ...);}
template<typename... T>
void putl(T&&... args) { ((cout << args << " "), ...); cout<<'\n';}
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << "=" << a << ", "; err(++it, args...);}
// #define int long long
#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define vc vector
#define L cout<<'\n';
#define E cerr<<'\n';
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for (int i=a; i<b; ++i)
#define rev(i,a,b) for (int i=a; i>b; --i)
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define setpr(x) cout<<setprecision(x)<<fixed
#define sz size()
#define seea(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define seev(v,n) for(int i=0;i<n;i++){int x; cin>>x; v.push_back(x);}
#define sees(s,n) for(int i=0;i<n;i++){int x; cin>>x; s.insert(x);}
const ll inf = INT_MAX;
const ld ep = 0.0000001;
const ld pi = acos(-1.0);
const int M = 1e9 + 7;
const int N = 200020;
const ll modi = 500000004;
int spf[N];
ll Log2[N];
int main(){
    IOS
    Log2[1] = 0;
    rep(i,2,N){
        Log2[i] = Log2[i/2] + 1;
    }
    ll n,q;
    see(n);
    ll a1[n];
    seea(a1,0,n);
    see(q);
    ll mn[n][Log2[n]+1] = {0};
    ll mx[n][Log2[n]+1] = {0};
    rep(i,0,n) mn[i][0] = a1[i];
    rep(i,0,n) mx[i][0] = a1[i];
    rep(j,1,Log2[n]+1){
        rep(i,0,n - (1<<j) + 1){
            mn[i][j] = min(mn[i][j-1],mn[i + (1<<(j-1))][j-1])  ;
        }
    }
    rep(j,1,Log2[n]+1){
        rep(i,0,n - (1<<j) + 1){
            mx[i][j] = max(mx[i][j-1],mx[i + (1<<(j-1))][j-1]);
        }
    }
    int cnt = 0;
    while(q--){
        int a,b;
        see(a,b);
        int k = b - a + 1;
        k = Log2[k];
        double mx1,mx2 = 0,mx3 = 0,mx4;
        mx1 = max(mx[a][k],mx[b-(1<<k) + 1][k]);
        ll mn1 = min(mn[a][k],mn[b-(1<<k) + 1][k]);
        if(a!=0){
            k = Log2[a];
            mx2 = max(mx[0][k],mx[a - (1<<k) ][k]);
        }
        if(b!=n-1){ 
            k = Log2[n - b - 1];
            mx3 = max(mx[b+1][k],mx[n - (1<<k)][k]);
        }
        mx4 = max(mx3,mx2);
        double time = max((mx1+mn1)/2,mx4 + mn1);
        setpr(1)<<time<<endl;
    }

}

Matchsticks CodeChef Solution in C++14

#include <bits/stdc++.h>
#define ll long long
#define llinf LLONG_MAX
#define llminf LLONG_MIN
#define inf INT_MAX
#define minf INT_MIN
const long long mod = 1e9 + 7;

using namespace std;

int tree[2*100005];
int tmx[2*100005];

vector <int> v;

int n = 0;

void buildmin() {
    for (int i = 0;i<n;i++) {
        tree[i+n]=v[i];
    }
    for (int i = n-1;i>0;i--) {
        tree[i]=min(tree[2*i],tree[2*i+1]);
    }
}

int qmin(int l, int r) {
    l+=n; r+=n;
    int ans = inf;
    while (l<=r) {
        if (l%2==1) {
            ans=min(ans,tree[l++]);
        }
        if (r%2==0) {
            ans=min(ans,tree[r--]);
        }
        r/=2; l/=2;
    }
    return ans;
}

void buildmax() {
    for (int i = 0;i<n;i++) {
        tmx[n+i]=v[i];
    }
    for (int i = n-1;i>0;i--) {
        tmx[i]=max(tmx[2*i],tmx[2*i+1]);
    }
}

int qmax(int l, int r) {
    l+=n; r+=n;
    int ans = 0;
    while (l<=r) {
        if (l%2==1) {
            ans=max(ans,tmx[l++]);
        }
        if (r%2==0) {
            ans=max(ans,tmx[r--]);
        }
        r/=2; l/=2;
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout << setprecision(1) << fixed;
    cin >> n;
    v.resize(n,0);
    for (int i = 0;i<n;i++) {
        cin >> v[i];
    }
    buildmax();
    buildmin();
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int mn = qmin(l,r);
        int mx = qmax(l,r);
        int ot;
        if (l==0 and r==n-1) ot=0;
        else if (l==0) {
            ot=qmax(r+1,n-1);
        }
        else if (r==n-1) {
            ot=qmax(0,l-1);
        }
        else {
            ot=max(qmax(0,l-1),qmax(r+1,n-1));
        }
        double ans = max((double)ot,(double)(mx-mn)/2) + mn;
        cout << ans << "\n";
    }
}

Matchsticks CodeChef Solution in PYTH 3

# cook your dish here
import math
n = int(input())
arr=[int(x) for x in input().split()]
k = int(math.log2(n))

#max table
sp = [[0 for i in range(k+1)] for j in range(n)]

for j in range(k+1):
    i=0
    while i+(1<<j)-1<n:
        if j==0:
            sp[i][j]=arr[i]
        else:
            sp[i][j] = max(sp[i][j-1],sp[i+(1<<(j-1))][j-1])
        i+=1

#min table
sp1 = [[0 for i in range(k+1)] for j in range(n)]

for j in range(k+1):
    i=0
    while i+(1<<j)-1<n:
        if j==0:
            sp1[i][j]=arr[i]
        else:
            sp1[i][j] = min(sp1[i][j-1],sp1[i+(1<<(j-1))][j-1])
        i+=1
        
def query1(l,r):
    k = r-l+1
    msb = int(math.log2(k))
    return max(sp[l][msb],sp[r-(1<<msb)+1][msb])

def query(l,r):
    k = r-l+1
    msb = int(math.log2(k))
    ans = min(sp1[l][msb],sp1[r-(1<<msb)+1][msb]) 
    m = ans+(query1(l,r)-ans)/2
    if l-1>=0:
        m = max(m,ans+query1(0,l-1))
    if r+1<=n-1:
        m = max(m,ans+query1(r+1,n-1))
    return float(m)
        
    
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(query(l,r))

Matchsticks CodeChef Solution in C

#include<stdio.h>
void buildtree(long int n,long int b[],long int B[])
{
 long int i;
 for(i=n-1;i>0;i--)
 {
    b[i]=b[2*i]>b[2*i+1]?b[2*i+1]:b[2*i];
    B[i]=B[2*i+1]>B[2*i]?B[2*i+1]:B[2*i];
 }
};
long int querymin(long int l,long int r,long int b[])
{
  long int res=1000000000;
  for(;l<r;l>>=1,r>>=1)
  {
     if(l&1)
     {
       res=res>b[l]?b[l]:res;
       l++;
     }
     if(r&1)
     {
       r--;
       res=res>b[r]?b[r]:res;
     }
  }
  return res;
};

long int querymax(long int l,long int r,long int b[])
{
  long int res=0;
  for(;l<r;l>>=1,r>>=1)
  {
     if(l&1)
     {
       res=res<b[l]?b[l]:res;
       l++;
     }
     if(r&1)
     {
       r--;
       res=res<b[r]?b[r]:res;
     }
  }
  return res;
};
int main()
{
 long int n,q,i,l,r;
 scanf("%ld",&n);
 long int b[2*n],B[2*n];
 for(i=n;i<2*n;i++)
 {
  scanf("%ld",&b[i]);
  B[i]=b[i];
 }
 buildtree(n,b,B);
 scanf("%ld",&q);
 long int min,max1,max2;
 long int max;
 double m;
 for(i=0;i<q;i++)
 {
  scanf("%ld %ld",&l,&r);
  min=querymin(l+n,r+1+n,b);
  max=querymax(l+n,r+1+n,B);
  max1=querymax(n,l+n,B);
  max2=querymax(r+1+n,2*n,B);
  m=(max-min)/2.0;
  max1=max1>max2?max1:max2;
  m=m>max1?m:max1;
  m=m+min;
  printf("%.1lf\n",m);
 }
 return 0;
}

Matchsticks CodeChef Solution in JAVA

import java.io.*;
import java.text.*;
import java.util.*;
import java.util.function.*;

class CodeChef {

	public static void main(String[] args) throws java.lang.Exception {
		int N = Scan.readInt();
		int tab[] = Scan.readIntArray(N);
		NumberFormat formatter = new DecimalFormat("#0.0", DecimalFormatSymbols.getInstance(Locale.US));     
		SparseTableInt spiMin = new SparseTableInt(tab, Integer.MAX_VALUE, Math::min);
		SparseTableInt spiMax = new SparseTableInt(tab, Integer.MIN_VALUE, Math::max);

		Scan.loop(() -> {
			int L = Scan.readInt();
			int R = Scan.readInt();
			int toCenter = spiMin.get(L, R);
			int a = toCenter + spiMax.get(0, L-1);
			double b = toCenter + (spiMax.get(L, R) - toCenter) / 2.0;
			int c = toCenter + spiMax.get(R+1, N-1);
			Out.bufln(formatter.format(Math.max(Math.max(a, b), c)));
		});
		
		Out.flush();
	}
}

class Out {
	private static final boolean SYSTEM_OUT = true;
	private static final File OUTPUT_FILE = new File("input.txt");
	
	private static final PrintStream stream;
	private static StringBuilder sb = new StringBuilder();
	
	static {
		if (SYSTEM_OUT) stream = System.out;
		else try { stream = new PrintStream(OUTPUT_FILE); }
		catch (IOException ex) { throw new Error("Could not write " + OUTPUT_FILE.getAbsolutePath() + ".", ex); }
	}
	
	public static void print(Object o) { flush(); stream.print(o); }
	public static void println(Object o) { flush(); stream.println(o); }
	public static void buf(Object o) { sb.append(o); }
	public static void bufln(Object o) { sb.append(o + "\n"); }
	public static void flush() { stream.print(sb); sb = new StringBuilder(); }
}

class Scan {
	private static final boolean SYSTEM_IN = true;
	private static final File INPUT_FILE = new File("input.txt");
	
	private static final BufferedReader br;
	private static StringTokenizer st;
	
	static {
		if (SYSTEM_IN) br = new BufferedReader(new InputStreamReader(System.in));
		else try { br = new BufferedReader(new FileReader(INPUT_FILE)); }
		catch (IOException ex) { throw new Error("Could not read " + INPUT_FILE.getAbsolutePath() + ".", ex); }
	}

	public static String next() {
		while (st == null || !st.hasMoreElements())
			try { st = new StringTokenizer(br.readLine()); }
			catch (IOException ex) { throw new Error("Scan reached EOF."); }
		return st.nextToken();
	}
	
	public static String nextLine() {
		try { return st.hasMoreTokens() ? st.nextToken("\n") : br.readLine(); }
		catch (IOException e) { throw new Error("Scan reached EOF."); }
	}

	public static int readInt() { return Integer.parseInt(next()); }
	
	public static long readLong() { return Long.parseLong(next()); }
	
	public static double readDouble() { return Double.parseDouble(next()); }
	
	public static int[] readIntArray() {
		int size = readInt();
		int[] res = new int[size];
		for (int i = 0; i < size; i++) res[i] = readInt();
		return res;
	}
	
	public static long[] readLongArray() {
		int size = readInt();
		long[] res = new long[size];
		for (int i = 0; i < size; i++) res[i] = readLong();
		return res;
	}

	public static double[] readDoubleArray() {
		int size = readInt();
		double[] res = new double[size];
		for (int i = 0; i < size; i++) res[i] = readDouble();
		return res;
	}

	public static int[] readIntArray(int size) {
		int[] res = new int[size];
		for (int i = 0; i < size; i++) res[i] = readInt();
		return res;
	}
	
	public static long[] readLongArray(int size) {
		long[] res = new long[size];
		for (int i = 0; i < size; i++) res[i] = readLong();
		return res;
	}

	public static double[] readDoubleArray(int size) {
		double[] res = new double[size];
		for (int i = 0; i < size; i++) res[i] = readDouble();
		return res;
	}

	public static void loop(Runnable r) {
		int loops = readInt();
		for (int i = 0; i < loops; i++) r.run();
	}
	
	public static void loop0(Consumer<Integer> c) {
		int loops = readInt();
		for (int i = 0; i < loops; i++) c.accept(i);
	}

	public static void loop1(Consumer<Integer> c) {
		int loops = readInt();
		for (int i = 1; i <= loops; i++) c.accept(i);
	}
}

class SparseTableInt {
	
	private int defaultValue;
	private int[] tab;
	private int n;
	private BiFunction<Integer, Integer, Integer> func;
	
	public SparseTableInt(int[] vals, BiFunction<Integer, Integer, Integer> f) {
		this(vals, 0, f);
	}
	
	public SparseTableInt(int[] vals, int def, BiFunction<Integer, Integer, Integer> f) {
		defaultValue = def;
		func = f;
		n = vals.length;
		if (n == 0) return;
		int log = log2(n) + 1;
		tab = new int[n * log];
		System.arraycopy(vals, 0, tab, 0, n);
		int start = 0;
		int prevStart = 0;
		int end = 1;
		for (int i = 1; i < log; i++) {
			start += n;
			int limit = n - end;
			for (int j = 0; j < n; j++) {
				tab[start + j] = j < limit ? f.apply(tab[prevStart + j], tab[prevStart + j + end]) : tab[prevStart + j]; 
			}
			prevStart += n;
			end *= 2;
		}
	}
	
	public int get(int a, int b) {
		if (a > b) return defaultValue;
		if (a == b) return tab[a];
		int la = log2(b - a);
		return func.apply(tab[la * n + a], tab[la * n + b + 1 - (1<<la)]);
	}

	private static int log2(int i) { return 31 - Integer.numberOfLeadingZeros(i); }
}

Matchsticks CodeChef Solution in PYPY 3

import math

n=int(input())
arr=list(map(int,input().split()))

size=int(math.sqrt(n))+1


block_min=[1000000000]*size
for index in range(n):
    block_min[index//size] = min(block_min[index//size ],arr[index])
    
block_max=[-1]*size
for index in range(n):
    block_max[index//size] = max(block_max[index//size], arr[index])
     
def minimumFinder(l,r,size) :
    answer=1000000000
    index=l
    while (index <= r):
        if index % size == 0 and index+size-1 <= r:
            answer=min(answer, block_min[index//size])
            index+=size
        else:
            answer=min(answer, arr[index])
            index+=1
    return answer
    
def maximumFinder(l,r,size) :
    answer=-1  
    index=l
    while (index <= r):
        if index % size == 0 and index+size-1 <= r:
            answer=max(answer, block_max[index//size])
            index+=size
        else:
            answer=max(answer, arr[index])
            index+=1
    return answer
    
queries=int(input())

for _ in range (queries):
    l,r=map(int,input().split())
    minInRange=minimumFinder(l, r, size)
    maxInRange=maximumFinder(l, r, size)
    maxOutLeft =0
    maxOutRight=0
    if ((l-1)>= 0):
        maxOutLeft=maximumFinder(0,l-1, size)
    if ((r+1)<n):
        maxOutRight=maximumFinder(r+1, n-1, size)
    maxOutRange = max (maxOutRight,maxOutLeft)
   # print(maxOutRange,maxInRange,minInRange,maxOutRight,maxOutLeft)
    ans=minInRange+max(maxOutRange,(maxInRange-minInRange)/2)
    print(float (ans))

Matchsticks CodeChef Solution in PYTH

def buildS(sp,L,R):
	if L == R:
		Stree[sp] = A[L] 
	else:
		m = (L+R)/2 
		buildS(2*sp+1,L,m)
		buildS(2*sp+2,m+1,R) 
		Stree[sp] = min(Stree[2*sp+1],Stree[2*sp+2])
	# endif
# end fun
def buildB(sp,L,R):
	if L == R:
		Btree[sp] = A[L] 
	else:
		m = (L+R)/2 
		buildB(2*sp+1,L,m)
		buildB(2*sp+2,m+1,R) 
		Btree[sp] = max(Btree[2*sp+1],Btree[2*sp+2])
	# endif
# end fun
def getmin(sp,sl,sr,L,R):
	if (sl > R) or (sr < L) :
		res = 10**9
	else:
		if  (L <= sl) and (sr <= R):
			res = Stree[sp] 
		else:
			m = (sl+sr)/2
			res = min(getmin(2*sp+1,sl,m,L,R),getmin(2*sp+2,m+1,sr,L,R))
		# endif
	# endif
	return res
# end fun
def getmax(sp,sl,sr,L,R):
	if (sl > R) or (sr < L) :
		res = 0
	else:
		if  (L <= sl) and (sr <= R):
			res = Btree[sp] 
		else:
			m = (sl+sr)/2
			res = max(getmax(2*sp+1,sl,m,L,R),getmax(2*sp+2,m+1,sr,L,R))
		# endif
	# endif
	return res
# end fun
N = int(raw_input())
size = 1
while size < N:
	size = size*2
# endwhile 
size = size*2
Stree = [0 for x in range(size)] 
Btree = [0 for x in range(size)] 
st = raw_input().split()
A = []
for x in st:
	A.append(int(x))
# endfor x
buildS(0,0,N-1)
buildB(0,0,N-1)
Q = int(raw_input())
for k in range(Q):
	st = raw_input().split()
	L = int(st[0])
	R = int(st[1])
	mi = getmin(0,0,N-1,L,R)
	mx = getmax(0,0,N-1,L,R)
	mxL = 0
	mxR = 0
	if L > 0:
		mxL = getmax(0,0,N-1,0,L-1)
	# endif
	if R < N-1:
		mxR = getmax(0,0,N-1,R+1,N-1)
	# endif
	mLR = max(mxL,mxR)
	r = max(mi+mx,2*(mi+mLR))
	r = 1.0*r/2
	print r
# endfor k

Matchsticks CodeChef Solution in C#

using System;
using System.Collections.Specialized;
using System.Linq;
using System.Runtime.CompilerServices;
using Console = System.Console;

namespace CodeForces
{
  class Program
  {
    private static int[] tmax, tmin;

    static void build(int k, int l, int r, int[] matchsticks)
    {
      if (r - l == 1)
      {
        tmax[k] = tmin[k] = matchsticks[l];
        return;
      }

      int m = (l + r) / 2;
      int k1 = k * 2 + 1;
      int k2 = k * 2 + 2;
      build(k1, l, m, matchsticks);
      build(k2, m, r, matchsticks);
      tmax[k] = Math.Max(tmax[k1], tmax[k2]);
      tmin[k] = Math.Min(tmin[k1], tmin[k2]);
    }

    static int query(int k, int l, int r, int ql, int qr, bool max)
    {
      if (qr <= l || r <= ql)
      {
        return max ? 0 : Int32.MaxValue;
      }

      if (ql <= l && r <= qr)
      {
        return max ? tmax[k] : tmin[k];
      }

      int m = (l + r) / 2;
      int k1 = k * 2 + 1;
      int k2 = k * 2 + 2;
      int t1 = query(k1, l, m, ql, qr, max);
      int t2 = query(k2, m, r, ql, qr, max);
      return max ? Math.Max(t1, t2) : Math.Min(t1, t2);
    }

    static void Main(string[] args)
    {
      string testCasesString = Console.ReadLine();
      int n = Int32.Parse(testCasesString);
      string matchstickLine = Console.ReadLine();
      string[] matchstickLineSplit = matchstickLine.Split(' ');
      int[] matchsticks = new int[n];
      for (int i = 0; i < n; i++)
      {
        matchsticks[i] = Int32.Parse(matchstickLineSplit[i]);
      }
      int[] matchmod = new int[n];
      matchmod[0] = matchsticks[0];
      for (int i = 1; i < n; i++)
      {
        matchmod[i] = Math.Max(matchsticks[i], matchmod[i - 1]);
      }
      int[] matchmod2 = new int[n];
      matchmod2[n - 1] = matchsticks[n - 1];
      for (int i = n - 2; i >= 0; i--)
      {
        matchmod2[i] = Math.Max(matchsticks[i], matchmod2[i + 1]);
      }
      int nmod = 1;
      while (nmod < n)
      {
        nmod = nmod * 2;
      }

      tmax = new int[nmod * 2];
      tmin = new int[nmod * 2];
      build(0, 0, n, matchsticks);
      string queryCasesString = Console.ReadLine();
      int queryCount = Int32.Parse(queryCasesString);
      while (queryCount-- > 0)
      {
        string queryLine = Console.ReadLine();
        string[] queryLineSplit = queryLine.Split(' ');
        int l = Int32.Parse(queryLineSplit[0]);
        int r = Int32.Parse(queryLineSplit[1]) + 1;
        int tp = l > 0 ? matchmod[l - 1] : 0;
        int tq = r < n ? matchmod2[r] : 0;
        int t1 = query(0, 0, n, l, r, false);
        int t2 = query(0, 0, n, l, r, true);
        double answer = t1 + Math.Max(Math.Max(tp, tq), (t2 - t1) / 2.0);
        string result = string.Format("{0:0.0}", Math.Truncate(answer * 10) / 10);
        Console.WriteLine(result);
      }
    }
  }
}

Matchsticks CodeChef Solution in GO

package main

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

func main() {

	reader := bufio.NewReader(os.Stdin)

	n := readNum(reader)
	B := readNNums(reader, n)
	m := readNum(reader)
	Q := make([][]int, m)
	for i := 0; i < m; i++ {
		Q[i] = readNNums(reader, 2)
	}
	res := solve(n, B, Q)

	var buf bytes.Buffer

	for i := 0; i < m; i++ {
		buf.WriteString(fmt.Sprintf("%.1f\n", res[i]))
	}

	fmt.Print(buf.String())
}

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 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 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 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
}

const INF = 1 << 30

func solve(n int, B []int, Q [][]int) []float64 {

	set := func(arr []int, p int, v int, fn func(int, int) int) {
		p += n
		arr[p] = v
		for p > 1 {
			arr[p>>1] = fn(arr[p], arr[p^1])
			p >>= 1
		}
	}

	get := func(arr []int, l, r int, init_res int, fn func(int, int) int) int {
		res := init_res
		l += n
		r += n
		for l < r {
			if l&1 == 1 {
				res = fn(res, arr[l])
				l++
			}
			if r&1 == 1 {
				r--
				res = fn(res, arr[r])
			}
			l >>= 1
			r >>= 1
		}
		return res
	}

	dp := make([]int, 2*n)
	fp := make([]int, 2*n)

	for i := 0; i < 2*n; i++ {
		dp[i] = INF
		fp[i] = -INF
	}

	for i := 0; i < n; i++ {
		set(dp, i, B[i], min)
		set(fp, i, B[i], max)
	}

	res := make([]float64, len(Q))

	for i, cur := range Q {
		l, r := cur[0], cur[1]
		x := get(dp, l, r+1, INF, min)
		// first match stick burns outs
		var ans float64
		if l > 0 {
			ans = float64(get(fp, 0, l, 0, max)) + float64(x)
		}
		if r+1 < n {
			ans = math.Max(ans, float64(get(fp, r+1, n, 0, max)+x))
		}
		y := get(fp, l, r+1, 0, max)
		ans = math.Max(ans, float64(y-x)/2+float64(x))
		res[i] = ans
	}
	return res
}

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
}

Matchsticks CodeChef Solution Review:

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

Find on CodeChef

Conclusion:

I hope this Matchsticks 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