Nikita and the Game

Problem Statement :

Nikita just came up with a new array game. The rules are as follows:

Initially, Nikita has an array of integers.

In each move, Nikita must partition the array into 2 non-empty contiguous parts such that the sum of the elements in the left partition is equal to the sum of the elements in the right partition. If Nikita can make such a move, she gets 1 point; otherwise, the game ends.

After each successful move, Nikita discards either the left partition or the right partition and continues playing by using the remaining partition as array arr.

Nikita loves this game and wants your help getting the best score possible. Given arr, can you find and print the maximum number of points she can score?

For example, Nikita starts with the array arr = [1,2,3,6]. She first splits it into a1 = [1,2,3] and a2 = [6], then discards a2. arr = a1->a1 = [1,2], a2 = [3]. Discard a2 leaving arr = [1,2]. This cannot be further split, so Nikita scored 2.

Function Description

Complete the arraySplitting function in the editor below. It should return an integer that reperesents the number of times Nikita can split the array.

arraySplitting has the following parameter(s):

arr: an array of integers
Input Format

The first line contains an integer t, the number of test cases.

Each of the next t pairs of lines is as follows:

The first line contains an integer n, the size of array arr.
The next line contains n space-separated integers arr[i].

Constraints

1 <= t<= 10
1 <= n <= 2^14
0 <= arr[i] <=10^9

Solution :

                            Solution in C :

In C++ :





//start of jonathanirvings' template v3.0.1 (BETA)

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <deque>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <time.h>
#include <bitset>
#include <list>
#include <assert.h>
#include <time.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#ifdef TESTING
  #define DEBUG fprintf(stderr,"====TESTING====\n")
  #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
  #define debug(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DEBUG 
  #define VALUE(x)
  #define debug(...)
#endif

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)

inline string IntToString(LL a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline LL StringToInt(string a){
  char x[100]; LL res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string GetString(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}

inline string lowercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

inline void OPEN (string s) {
  freopen ((s + ".in").c_str (), "r", stdin);
  freopen ((s + ".out").c_str (), "w", stdout);
}

//end of jonathanirvings' template v3.0.1 (BETA)

int data[17000];
int n;
int T;

int count(int L,int R)
{
  if (L == R) return 0;
  LL tot = 0;
  FORN(i,L,R) tot += data[i];
  if (tot % 2 == 1) return 0;
  LL now = 0;
  FORN(i,L,R)
  {
    now += data[i];
    if (now == tot/2)
    {
      return 1 + max(count(L,i),count(i+1,R));
    }
  }
  return 0;
}

int main()
{
  scanf("%d",&T);
  TC(T)
  {
    scanf("%d",&n);
    REP(i,n) scanf("%d",&data[i]);
    int risan = count(0,n-1);
    printf("%d\n",risan);
  }
  return 0;
}








In Java :






import java.util.*;
import java.io.*;

public class B
{
   public static void main(String[] args) throws Exception
   {
      FastScanner in = new FastScanner(System.in);
      PrintWriter out = new PrintWriter(System.out);
      int T = in.nextInt();
      while (T-->0) new B(in, out);
      out.close();
   }
   int N;
   int[] vs;
   int go(int i, int j)
   {
      long sum = 0;
      for (int x=i; x<=j; x++)
         sum += vs[x];
      if (sum % 2 != 0) return 0;
      sum /= 2;

      long ss = 0;
      for (int x=i; x<j; x++)
      {
         ss += vs[x];
         if (ss == sum)
            return 1 + Math.max(go(i, x), go(x+1, j));
      }
      return 0;
   }

   public B(FastScanner in, PrintWriter out)
   {
      N = in.nextInt();
      vs = new int[N];
      for (int i=0; i<N; i++)
         vs[i] = in.nextInt();

      long res = go(0, N-1);
      out.println(res);
   }
}

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

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

   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++];
   }

   boolean isSpaceChar(int c)
   {
      return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
   }
   
   boolean isEndline(int c)
   {
      return c=='\n'||c=='\r'||c==-1;
   }

   int nextInt()
   {
      return Integer.parseInt(next());
   }
   
   long nextLong()
   {
      return Long.parseLong(next());
   }

   double nextDouble()
   {
      return Double.parseDouble(next());
   }

   String next(){
      int c = read();
      while (isSpaceChar(c))
         c = read();
      StringBuilder res = new StringBuilder();
      do{
         res.appendCodePoint(c);
         c = read();
      }while(!isSpaceChar(c));
      return res.toString();
   }
   
   String nextLine(){
      int c = read();
      while (isEndline(c))
         c = read();
      StringBuilder res = new StringBuilder();
      do{
         res.appendCodePoint(c);
         c = read();
      }while(!isEndline(c));
      return res.toString();
   }
}








In C :





#include<stdio.h>
typedef long long unsigned U;
typedef unsigned u;
u A[222222];
u F(u l,u r,U s)
{
	u m=l-1,i,j;U x=0llu;
	for(;++m<=r;)
	{
		x+=A[m];
		if((x<<1)>s)break;
		if((x<<1)==s)
		{
			i=F(l,m,x);
			if(i<(j=F(m+1,r,x)))i=j;
			return i+1;
		}
	}
	return 0;
}
int main()
{
	u t,n,i;U s;
	for(scanf("%u",&t);t--;)
	{
		scanf("%u",&n);s=0llu;
		for(i=-1;++i<n;s+=A[i])scanf("%u",A+i);
		if(!s){printf("%u\n",n-1);continue;}
		printf("%u\n",F(0,n-1,s));
	}
	return 0;
}








In Python3 :





import math

def solve(a):
    s = sum(a)
    if s % 2:
        return 0
    s //= 2
    t = 0
    for i in range(len(a)):
        t += a[i]
        if t == s:
            #print(sum(a[:i + 1]), sum(a[i + 1:]))
            return 1 + max(solve(a[:i + 1]), solve(a[i + 1:]))
        if t > s:
            return 0
        
def solve0(n):
    return n - 1

t = int(input().strip())
for test in range(t):
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    if sum(a) == 0:
        print(solve0(n))
    else:
        print(solve(a))

View More Similar Problems

Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →

Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →

Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

View Solution →

Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

View Solution →

Super Maximum Cost Queries

Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and

View Solution →

Contacts

We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co

View Solution →

Our Effort to provide you the best solutions requires some appreciation

Please disable your adblocker and refresh

Nikita and the Game

Problem Statement :

Solution :

View More Similar Problems

Minimum Average Waiting Time

Merging Communities

Components in a graph

Kundu and Tree

Super Maximum Cost Queries

Contacts