SplitArrayWithSameAverage [source code]
public class SplitArrayWithSameAverage {
static
/******************************************************************************/
class Solution {
public boolean splitArraySameAverage(int[] A) {
int sum = 0;
for (int num : A)
sum += num;
for (int k = 1; k <= A.length / 2; k++) {
double subsum = (double) sum * k / A.length;
if (!isInteger (subsum))
continue;
if (findSubsetSum (A, k, 0, (int) subsum))
return true;
}
return false;
}
boolean findSubsetSum (int[] nums, int pos, int start, int sum) {
boolean success = false;
if (pos == 0) {
success = sum == 0;
} else {
for (int i = start; i < nums.length; i++) {
if (findSubsetSum (nums, pos - 1, i + 1, sum - nums[i]))
return true;
}
}
return success;
}
boolean isInteger (double d) {
return d == (int) d;
}
}
/******************************************************************************/
public static void main(String[] args) {
SplitArrayWithSameAverage.Solution tester = new SplitArrayWithSameAverage.Solution();
int[][] inputs = {
{1,2,3,4,5,6,7,8}, {1},
{3,1},{0},
{1817,3082,8735,9101,2576,3473,9941,5336,8452,2584,2518,3196,1421,8460,6863,6956,3668,17}, {0},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int[] A = inputs[2 * i];
boolean ans = inputs[2 * i + 1][0] != 0, output = tester.splitArraySameAverage (A);
System.out.printf ("%s\n%s, expected: %b\n",
Printer.array (A), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
这题先思考一下穷搜怎么搜? 因为A的长度并不大, 所以大概就是一个划分成两个subset, 然后...
发现这个居然是geeks4geeks的原题:
https://www.geeksforgeeks.org/divide-array-two-sub-arrays-averages-equal/
没意思了; 不过也看出来geeks4geeks这个网站的厉害之处了;
不对, 题目不一样, geeks4geeks这个题目是连续的分段的split, 这个题目要求的是不连续的, 难很多了;
https://www.geeksforgeeks.org/dynamic-programming-set-18-partition-problem/
这题有点类似, 不过好像简单一些;
想不到好办, 直接DFS搜算了;
写了一个naive的DFS, 果然是直接被TLE了;
看到这个, 感觉也并不是很对的样子: https://stackoverflow.com/questions/8914961/how-do-you-partition-an-array-into-2-parts-such-that-the-two-parts-have-equal-av
这个是TLE的嗲吗, 想不到什么好的prune方法:
boolean dfs (int[] nums, int idx, int picked_sum, int picked_cnt, int all_sum) {
// This pruning does not work
// if (!isInteger ((double) all_sum * picked_cnt / nums.length)) {
// return false;
// }
if (idx == nums.length)
return false;
if (checkEqualAvg (picked_sum, picked_cnt, all_sum, nums.length)) {
return true;
}
boolean success = dfs (nums, idx + 1, picked_sum + nums[idx], picked_cnt + 1, all_sum);
if (success)
return true;
return dfs (nums, idx + 1, picked_sum, picked_cnt, all_sum);
}
boolean checkEqualAvg (int picked_sum, int picked_cnt, int all_sum, int all_cnt) {
return (double) picked_sum / picked_cnt == (double) (all_sum - picked_sum) / (all_cnt - picked_cnt);
}
按照那个StackOverflow的做法实现了一下:
class Solution {
public boolean splitArraySameAverage(int[] A) {
int sum = 0;
for (int num : A)
sum += num;
for (int k = 1; k <= A.length - 1; k++) {
double subsum = (double) sum * k / A.length;
if (!isInteger (subsum))
continue;
if (findSubsetSum (A, k, new boolean[A.length], (int) subsum))
return true;
}
return false;
}
boolean findSubsetSum (int[] nums, int pos, boolean[] used, int sum) {
if (sum < 0)
return false;
if (pos == 0) {
return sum == 0;
}
for (int i = 0; i < nums.length; i++) {
if (used[i])
continue;
used[i] = true;
if (findSubsetSum (nums, pos - 1, used, sum - nums[i]))
return true;
used[i] = false;
}
return false;
}
boolean isInteger (double d) {
return d == (int) d;
}
}
结果在test3直接死循环了; GG;
看了contest居然有人直接用这个思路做出来的, 很奇怪我的这个几乎一样的写法为什么不行?
直接暴力debug看看;
好像算法本身没有什么问题, 就是慢;
重新看了一下contest那个人的代码:
class Solution {
public boolean splitArraySameAverage(int[] A) {
int sum = 0, len = A.length;
for(int i = 0; i < A.length; i++) {
sum += A[i];
}
for(int i = 1; i <= len / 2; i++) {
if(sum * i % len != 0)
continue;
if(checkSum(A, sum * i / len, i, 0, 0, 0))
return true;
}
return false;
}
private boolean checkSum(int[] A, int sum, int num, int start, int curSum, int curCount) {
if (curCount == num)
return curSum == sum;
for(int i = start; i < A.length; i++) {
if(curSum + A[i] <= sum) {
if(checkSum(A, sum, num, i + 1, curSum + A[i], curCount + 1))
return true;
}
}
return false;
}
}
看了一下, 他这个其实不是backtrack那样的穷搜, 而是一个有点greedy的做法? 每当用preleaf的思路判断到一个A[i]可以加到curSum里面去, 他就直接加进去了;
好像知道了, 他这个并不是duplicate, 他这个start其实是一个去重的作用, 比如我在这个level(pos)选择了[1], 那么下一个pos就只能从[2..]开始选, 因为比如第一个pos选[1], 下一个pos选[2], 跟第一个pos选[2], 下一个pos选[1], 是一样的!
所以这个题目还是有点难度的; 没有想到这一点; 以前也总结过, 去重并不是仅仅让算法显得更聪明(不需要借助于set), 实际上对于时间效率也有极大的影响(可以prune search tree的大小);
为什么我没有想到这个问题呢? 当时其实我这个算法AC不过的时候, 有去想怎么prune, 但是确实就是没有想到这个方面去; 不对, 我当时想prune的不是这个算法, 是那个element based的暴搜;
不过还是有点懊悔, 为什么我没有想到这个去重问题; 我的想法其实还是挺简单的, 就用used来控制, 之前也讲过, 这个是肯定不会错的; 不过好像不会错有些时候并不足够; 那么, 什么时候要意识到这个暴搜过程当中的去重的必要性呢?
也许是一个固定记忆代码? 毕竟这里实际上就是一个combination那道题的思路; 不过我其实也不记得那道题的代码了; 感觉这种经典提醒的代码还是要熟悉, combination, permutation, next permutation(之前见过一次, 是很好用的暴搜utility), reverse list之类的;
UNFINISHED
uwi: 他这个写的比较复杂了, 看了一下editorial和discuss最优解, 都很简练;
这一次contest他做的非常快, 这个解法看起来非常复杂但是实际上他只用了9分钟, 算是比较夸张的了;
class Solution {
public boolean splitArraySameAverage(int[] a) {
int n = a.length;
int s = 0;
for(int v : a){
s += v;
}
int m = (300001>>>6)+1;
long[][] dp = new long[n+1][m];
dp[0][0] = 1;
for(int i = 0;i < n;i++){
for(int j = i;j >= 0;j--){
or(dp[j], 0, 300000-a[i], dp[j+1], a[i]);
}
}
for(int i = 1;i <= n-1;i++){
if((long)s * i % n == 0){
int b = s*i / n;
if(dp[i][b>>>6]<<~b<0)return true;
}
}
return false;
}
public void or(long[] from, int fl, int fr, long[] to, int tl)
{
if(!(fl >= 0 && fl < from.length<<6))throw new RuntimeException();
if(!(fr >= 0 && fr <= from.length<<6))throw new RuntimeException();
if(!(tl >= 0 && tl < to.length<<6))throw new RuntimeException();
if(!(tl+(fr-fl) >= 0 && tl+(fr-fl) <= to.length<<6))throw new RuntimeException();
if(fl >= fr)return;
int tr = tl+(fr-fl);
for(int l1 = fl, l2 = Math.min(fr, (fl>>>6)+1<<6), r1 = tl, r2 = Math.min(tr, (tl>>>6)+1<<6);l1 < fr;){
if(l2-l1 <= r2-r1){
long f = from[l2-1>>>6]<<-l2>>>-l2+l1;
to[l2-l1+r1-1>>>6] |= f<<r1;
r1 += l2-l1;
l1 = l2;
l2 = Math.min(fr, (l1>>>6)+1<<6);
if(r2 - r1 == 0){
r2 = Math.min(tr, (r1>>>6)+1<<6);
}
}else{
long f = from[r2-r1+l1-1>>>6]<<-(r2-r1+l1)>>>-(r2-r1+l1)+l1;
to[r2-1>>>6] |= f<<r1;
l1 += r2-r1;
r1 = r2;
r2 = Math.min(tr, (r1>>>6)+1<<6);
if(l2 - l1 == 0){
l2 = Math.min(fr, (l1>>>6)+1<<6);
}
}
}
}
}
这个算法太潦草了, 不太想看了;
下面一个中国人的解法:
class Solution {
public boolean splitArraySameAverage(int[] A) {
int sum = 0, len = A.length;
for(int i = 0; i < A.length; i++) {
sum += A[i];
}
double aver = sum / (double)len;
for(int i = 1; i <= len / 2; i++) {
if(sum * i % len != 0)
continue;
if(checkSum(A, sum * i / len, i, 0, 0, 0))
return true;
}
return false;
}
private boolean checkSum(int[] A, int sum, int num, int start, int curSum, int curCount) {
if(curCount == num && sum == curSum)
return true;
if(curCount == num)
return false;
for(int i = start; i < A.length; i++) {
if(curSum + A[i] <= sum) {
if(checkSum(A, sum, num, i + 1, curSum + A[i], curCount + 1))
return true;
}
}
return false;
}
}
感觉正常了一点;
这个好像就是我StackOverflow上面看到的那个做法啊; 奇怪了为什么他这个可以AC;
node里面的处理, 是一个position based的做法, 然后不用backtrack, 直接preleaf判断;
另外len的范围稍微prune了一下;
他的这个start实际上就是充当一个类似我的used的效果;
if(curCount == num && sum == curSum)
return true;
if(curCount == num)
return false;
这个也是可以简写:
if (curCount == num)
return sum == curSum;
这个写法基本就跟我的非常类似的了;
Problem Description
In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)
Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.
Example :
Input:
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.
Note:
- The length of A will be in the range [1, 30].
- A[i] will be in the range of [0, 10000].
Difficulty:Hard
Total Accepted:2.6K
Total Submissions:13.1K
Contributor:awice