Оптимизация времени выполнения

Question

Задача:

Дано число N (N <= 1 000 000).

Необходимо:

Разбить его на набор 1...N;

Проверить, возможно ли набор представить в виде двух наборов так, чтобы сумма каждого набора была равна N/2.

Например:

N = 11

Вывод:
[[1,2,4,5,6,7,8], [3,9,10,11]]

И там и там 33. Мой код не работает с большими числами. Своими клешнями я написал что-то большое и плохо пахнущее:

import java.util.*;
import java.util.ArrayList;
import java.util.List;

public class CreateTwoSetsOfEqualSum {
    public static List<List<Integer>> createTwoSetsOfEqualSum(int n) {    
        List<List<Integer>> sets = new ArrayList<>();
        
        int tmp = 0;
        int sum1 = 0;
        
        List<Integer> list = new ArrayList<>();
        List<Integer> res1 = new ArrayList<>();
        List<Integer> res2 = new ArrayList<>();
        
        for(int i=1; i<=n; i++){
            tmp += i;
            list.add(i);
        }
        
        if(tmp % 2 > 0){
            sets.add(new ArrayList<>());
            sets.add(new ArrayList<>());
            return sets;
        } else {
              
              tmp /= 2;
              int i = list.size()-1;
              
              while(sum1 < tmp && i>0){
                  
                  if(sum1+list.get(i) < tmp){
                      res1.add(list.get(i));
                      sum1 += list.get(i);
                  } else {
                        while(sum1 != tmp){
                            
                            if(sum1+list.get(i)==tmp){
                                
                                sum1 += list.get(i);
                                res1.add(list.get(i));
                                
                                break;
                            
                            } else {
                                  
                                  i--;
                              }
                        }
                        i--;
                    }
                    
                    for(int a=0; a<res1.size(); a++){
                    
                        for(int j=0; j<list.size(); j++){
                            
                            if(res1.get(a)==list.get(j)){
                                
                                list.remove(list.get(j));
                            }
                        }
                    }
                    
                    Collections.reverse(res1);
                    
                    sets.add(new ArrayList<>());
                    sets.add(new ArrayList<>());
                    
                    for(int l : res1){
                        sets.get(0).add(l);
                    }
                    
                    for(int l : list){
                        sets.get(1).add(l);
                    }
                    
                    return sets;
            }
        }
    }
}

int tmp, int sum1 не вписываются т.к. 2^31-1 и т. д. ... long - время выполнения 16000ms

Как то так:

Test Results:
SolutionTest
randomTests()
STDERR
Execution Timed Out (16000 ms)

Тесты:

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertTrue;

class SolutionTest {
    @Test
    void fixedTests() {
        for (int i = 1; i <= 10; i++) {
            final ResultMessage verification =  Preloaded.validateTwoSetsOfEqualSum(i, CreateTwoSetsOfEqualSum.createTwoSetsOfEqualSum(i));
            final boolean result = verification.result;
            final String message = verification.message;
            assertTrue(result,  "i = " + i + " Result: " + message);
        }
    }
}

Наверное, надо не заниматься мазохизмом, а вносить числа сразу в подсписки.

Подскажите что-нибудь умное)

Answer 1

Решение довольно простое. Болше кода на вывод решения ушло.

    public static void main(String[] args) {
        for (int i = 1; i < 100; i++) {
            System.out.println("N = " + i);
            Set<Integer> toMove1;
            Set<Integer> toMove2;
            boolean impossible;
            switch (i % 4) {
                case 0:
                    impossible = false;
                    if (i / 4 % 2 == 0) {
                        toMove1 = Set.of();
                        toMove2 = Set.of(i / 4);
                    } else {
                        toMove1 = Set.of(1);
                        toMove2 = Set.of(i / 4 + 1);
                    }
                    break;
                case 1, 2:
                    impossible = true;
                    System.out.println("impossible");
                    toMove1 = Set.of();
                    toMove2 = Set.of();
                    break;
                case 3:
                    impossible = false;

                    if (i / 4 % 2 == 0) {
                        toMove1 = Set.of(i / 4 + 1);
                        toMove2 = Set.of();
                    } else {
                        toMove1 = Set.of(i / 4, i / 4 + 2);
                        toMove2 = Set.of(i / 4 + 1);

                    }
                    break;
                default:
                    throw new RuntimeException();
            }
            List<Integer> g1 = Stream.concat(
                            toMove2.stream(),
                            odd(i).filter(j -> !toMove1.contains(j)))
                    .toList();
            List<Integer> g2 = Stream.concat(
                    toMove1.stream(),
                    even(i).filter(j -> !toMove2.contains(j))
            ).toList();
            int sumG1 = g1.stream().mapToInt(Integer::intValue).sum();
            System.out.println("sum g1 = " + sumG1 + " g1 = " + g1);
            int sumG2 = g2.stream().mapToInt(Integer::intValue).sum();
            System.out.println("sum g2 = " + sumG2 + " g2 = " + g2);
            if (sumG1 != sumG2 && !impossible) {
                System.out.println("ERROR");
            }
        }
    }

    private static Stream<Integer> even(int i) {
        return IntStream.range(1, i + 1)
                .filter(j -> j % 2 == 0)
                .boxed();
    }

    private static Stream<Integer> odd(int i) {
        return IntStream.range(1, i + 1)
                .filter(j -> j % 2 == 1)
                .boxed();
    }

Answer 2

Первый вариант:

Сумма от 1 до N S=(N^2+N)/2. Должна быть чётная. Обозначим полусумму как M=S/2.
Верхняя граница первого подмножества K=INT(0.5+SQRT(0.25+(N^2+N)/2)). То есть первое подмножество от 1 до K, а второе от K+1 до N.
Из первого подмножества нужно забрать во второе число X=(K^2+K)/2-M.

Второй вариант:

// это не Java, если что
int M = N + 1, lim = (N >> 1) + (N & 1);
for (int i = 1; i < lim; i += 2) {
  set1.Add(i); set1.Add(M - i);
  set2.Add(i + 1); set2.Add(N - i);
}

БЛОГ НА HUSL

Оптимизация времени выполнения

Ответы (2 шт):