5
\$\begingroup\$

Challenge

Given an array of positive integers and a threshold, the algorithm should output a set of consecutive-element-groupings (subarrays) such that each group/subarray has a sum greater than the threshold.

Rules

The solution should honor two additional criteria:

  • be of highest cardinality of the groups (i.e. highest number of groups)
  • having the maximum group-sum be as lowest as possible.

Mathematical Description:

  • input array \$L = [l_1, l_2, ..., l_n]\$
  • threshold \$T\$

output groups/subarrays \$G = [g_1, g_2, ..., g_m]\$ where:

  • \$m \leq n\$
  • \$\bigcap\limits_{i=1}^m{g_i}=\varnothing\$
  • \$\bigcup\limits_{i=1}^m{g_i}=L\$
  • if we denote the sum of elements in a group as \$s_{g_i} = \sum\limits_{l \in g_i}l\$, then all groups have sum greater than threshold \$T\$. In other words: \$\underset{g \in G}{\operatorname{min}}{\{s_g\}} \ge T\$
  • if cardinality \$|g_i|=k\$, then \$g_i=[l_j, ..., l_{j+k-1}]\$ for an arbitrary \$j\$ (i.e. all elements are consecutive).
  • optimal solution has highest cardinality: \$|G_{opt}| \ge \max\left(|G| \right),\,\,\forall G\$
  • optimal solution \$G_{opt}\$ has lowest maximum group-sum: \$\underset{g \in G_{opt}}{\operatorname{max}}{\{s_g\}} \le \underset{g \in G}{\operatorname{max}}{\{s_g\}}, \,\,\, \forall G\$

Assumption

for simplicity, we assume such a solution exists by having: \$\sum\limits_{i=1}^n l_i \ge T\$

Example:

Example input:

L = [1, 4, 12, 6, 20, 10, 11, 3, 13, 12, 4, 4, 5] 
T = 12

Example output:

G = {
  '1': [1, 4, 12, 6],
  '2': [20], 
  '3': [10, 11], 
  '4': [3, 13], 
  '5': [12], 
  '6': [4, 4, 5]
}

Winning Criteria:

  1. Fastest algorithm wins (computational complexity in \$O\$ notation).
  2. Additionally, there might be situations where an element \$l_i >\!\!> T\$ is really big, and thus it becomes its own group; causing the maximum subarray sum to be always a constant \$l_i\$ for many potential solutions \$G\$.
    Therefore, if two potential solutions \$G_A\$ and \$G_B\$ exists, the winning algorithm is the one which results in output that has the smallest max-subarray-sum amongst the non-intersecting groups.
    In other words: if we denote \$G_{A \cap B}=\{g_i: \,\, g_i \in G_A \cap G_B\}\$, then optimum grouping, \$G_{opt}\$, is the one that has:

$$\underset{g \in \mathbf{G_{opt}} - G_{A \cap B}}{\operatorname{max}}{\{s_g\}} = \min\left( \underset{g \in \mathbf{G_A} - G_{A \cap B}}{\operatorname{max}}{\{s_g\}}\, , \,\,\underset{g \in \mathbf{G_{B}} - G_{A \cap B}}{\operatorname{max}}{\{s_g\}} \right)$$

\$\endgroup\$
4
  • \$\begingroup\$ Thanks @Arnauld for letting me know the rules, I make the change now. \$\endgroup\$ Sep 15, 2019 at 20:03
  • \$\begingroup\$ Shouldn't the example result be [[1, 4, 12, 6], [20], [10, 11], [3, 13], [12], [4, 4, 5]] ? This has six entries too, but the maximal sum is lower at 23 (rather than 26). \$\endgroup\$ Sep 15, 2019 at 20:11
  • \$\begingroup\$ @JonathanAllan, corrected it. Thanks for pointing it out. \$\endgroup\$ Sep 15, 2019 at 20:24
  • \$\begingroup\$ made the change @Arnauld \$\endgroup\$ Sep 15, 2019 at 20:34

2 Answers 2

2
\$\begingroup\$

Java (JDK), 1248 bytes

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class TestCG{
	public static void main(String [] args) {
		int [] input = new int[] {1,4,12,6,20,10,11,3,13,12,4,4,5};
		int threshold = 12;
		List<List<Integer>> groups = new ArrayList<>();
		
		int currentGroupSum = 0;
		int previousGroupSum = 0;
		
		int maxGroupSum = 0;
		int boundaryValue = 0;
		List<Integer> currentGroup =  new ArrayList<>();
		
		for(int i=0; i<input.length; i++) {
			currentGroup.add(input[i]);
			currentGroupSum+=input[i];
			
			if(currentGroupSum>=threshold) {
				if(i<input.length-1) {
					boundaryValue = input[i+1];
				}
				
				if(currentGroupSum>maxGroupSum) {
					maxGroupSum = currentGroupSum;
				}
				
                if(currentGroupSum > previousGroupSum && (currentGroupSum - boundaryValue)>=threshold) {
                  
                	groups.get(groups.size()-1).add(boundaryValue);
                	currentGroup.remove(0);
                }
				
				previousGroupSum = currentGroupSum;
				
				
				currentGroupSum = 0;
				groups.add(currentGroup);
				currentGroup = new ArrayList<>();
			}
		}
		System.out.println(groups.size());	
		
		for(List<Integer> group : groups) {
			System.out.println(group);
		}
	}

}

Try it online!

Complexity O(n)

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to CG&CC! This doesn't seem to specify the language it's written in (I'm assuming Java, or some relative thereof?) or its complexity (which is relevant because the winning criterion for this challenge is lowest complexity). You should probably edit your answer to state both of those things, and while you're at it also provide a link to an online interpreter for your code, such as Try It Online!. \$\endgroup\$ Sep 19, 2019 at 8:05
  • 1
    \$\begingroup\$ Apologies as it was my first submission, have included online link. \$\endgroup\$
    – Pranav83
    Sep 19, 2019 at 23:21
0
\$\begingroup\$

Prolog: \$ O(n^2) \$, 785 bytes

:- use_module(library(clpz)).
:- use_module(library(lists)).

sum(Ls, S) :-
    sum_(Ls, 0, S).

sum_([], S, S).
sum_([L|Ls], S0, S) :-
    S1 #= L + S0,
    sum_(Ls, S1, S).

solve([], _, _, []).
solve(Ls, T, M, Ms) :-
    T > 0,
    solve_(Ls, T, M, [], Ms1),
    reverse(Ms1, Ms).

solve_([], _, _, Ms, Ms).
solve_(Ls, T, M, Ms0, Ms) :-
    append(As, Bs, Ls),
    As = [_|_],
    sum(As, S),
    S #>= T,
    S #=< M,
    solve_(Bs, T, M, [As|Ms0], Ms).

solution(Ls, T, Ms, M) :-
    solution_(Ls, T, Ms, sup, M).

solution_(Ls, T, Ms, M0, M) :-
    M1 in 0..M0,
    solve(Ls, T, M1, _),
    !,
    clpz:fd_get(M1, from_to(n(M2), _), _),
    M3 #= M2 - 1,
    (   solution_(Ls, T, Ms, M3, M), !
    ;   end_(Ls, T, Ms, M2, M)
    ).
end_(Ls, T, Ms, M, M) :- solve(Ls, T, M, Ms).

To run it:

?- solution([1, 4, 12, 6, 20, 10, 11, 3, 13, 12, 4, 4, 5], 12, Ms, M).
   Ms = [[1,4,12,6],[20],[10,11],[3,13],[12],[4,4,5]], M = 23.
?- 
\$\endgroup\$
2
  • 1
    \$\begingroup\$ What is the complexity of the algorithm? It is necessary for scoring. \$\endgroup\$
    – Wheat Wizard
    May 29, 2020 at 20:52
  • \$\begingroup\$ Yes, it is but I can't compute it yet. \$\endgroup\$ May 29, 2020 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.