Taulukko

Note: input/Datatahti_taulukko.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

/**
 *
 * @author DevBonBon
 */
public class Datatahti_taulukko {
    
    public static int triNumber(int n) {
        return (n * (n + 1)) / 2;
    }

    public static class Pair<K, V> {

        private final K key;
        private final V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        @Override
        public String toString() {
            return "Pair{" + "key=" + key + ", value=" + value + '}';
        }
    }

    public static class SetFinder implements Runnable {

        private final int[] ints;
        private final int startIndex;
        private final int endIndex;
        private final int maxDifferent;
        //
//        private final AtomicInteger result;
        private final List<Pair<Integer, Integer>> results;
        private final AtomicBoolean done;

        public SetFinder(int[] ints, int startIndex, int endIndex, int maxDifferent) {
            this.ints = ints;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
            this.maxDifferent = maxDifferent;

//            this.result = new AtomicInteger(0);
            this.results = new ArrayList<>();
            this.done = new AtomicBoolean(false);
        }

        public List<Pair<Integer, Integer>> getResult() {
            return this.results;
        }

        public boolean isDone() {
            return this.done.get();
        }

        @Override
        public void run() {
            boolean endReached = false;

            //NOTE: reformat so we can get rid of booleans and if's and... ugly
            //This doean't account for overlaps!!!
            for (int i = startIndex; i < endIndex; i++) {
                //We'll go with clear for now
                HashSet<Integer> intsSeen = new HashSet<>(maxDifferent);
                for (int j = i; j < ints.length; j++) {
                    if (endReached) {
                        break;
                    }
                    intsSeen.add(ints[j]);
                    if (intsSeen.size() > maxDifferent || j == ints.length - 1) {
                        if (j == ints.length - 1) {
                            endReached = true;
                            this.results.add(new Pair(i, j));
                            break;
                        } else {
                            this.results.add(new Pair(i, j - 1));
                            break;
                        }
                    }
                }
            }
            this.done.lazySet(true);
        }
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        //I read that split is actually "slow" (only hundreds of milliseconds slower, when iterating
        //hundreds of thousands of times) so lets try something different
        //First inputline
        String fl = input.nextLine();
        //Get the size of the table and max different ints in any subset
        int size = Integer.parseInt(fl.substring(0, fl.indexOf(" ", 1)));
        int maxDifferent = Integer.parseInt(fl.substring(fl.indexOf(" ", 1) + 1, fl.length()));
        //NOTE: Came up with something better
        String tableString = input.nextLine();

        //Convert tableString into an int array
        //Instead of using an int array, we should use have 2 infos at each index, the number, and how many times it has been visited
        int pow[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
        int[] tableInts = new int[size];
        int length = tableString.length();
        int index = length - 1;
        int spot = tableInts.length - 1;
        int number = 0;
        //Iterates through all characters from the back and adds them together
        while (index >= 0) {
            char c = tableString.charAt(index);
            if (c != ' ') {
                switch (c) {
                    case '0':
                        break;
                    default:
                        number += (c - '0') * pow[length - index - 1];
                        break;
                }
            } else {
                tableInts[spot] = number;
                number = 0;
                //Get ready for next iteration
                length = index;
                spot--;
            }
            index--;
        }
        //Also get the last number
        tableInts[spot] = number;

        //So let's be greedy, who needs efficiency anyway...
        //I've got some ideas, but I'm currious to see how this goes
        //NOTE: could move the creation and such inside the string conversion above
        long result = 0;
        //The amount of threads we want to create and the size of the chunks we're dividing the array into
        int threads;
        //I figured this is more readable than nested if's
        switch (size) {
            case 1:
            case 2:
            case 3:
                threads = 1;
                break;
            case 4:
            case 5:
            case 6:
            case 7:
                threads = 4;
                break;
            default:
                threads = 8;
                break;
        }
        int chunkSize = ((size - 1) + threads - 1) / threads; // divide by threads rounded up.

        SetFinder finders[] = new SetFinder[threads];
        boolean findersDone[] = new boolean[threads];

        for (int i = 0; i < threads; i++) {
            int start = i * chunkSize;
            int end = Math.min(start + chunkSize, size - 1);
            //Create and start the threads and mark their task as incomplete
            finders[i] = new SetFinder(tableInts, start, end, maxDifferent);
            finders[i].run();

            findersDone[i] = false;
        }

        //Check all threads and get their results
        int allDone = 0;
        while (allDone < threads) {
            for (int i = 0; i < threads; i++) {
                if (!findersDone[i] && finders[i].isDone()) {
                    findersDone[i] = true;
                    for (Pair<Integer, Integer> p : finders[i].getResult()) {
                        result += triNumber(p.getValue() - p.getKey() + 1);
                    }
                    allDone++;
                }
            }
        }

        System.out.println(result);
    }
}

Test 1

Group: 1

Verdict: WRONG ANSWER

Test 2

Group: 1

Verdict: WRONG ANSWER

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 1

Verdict: WRONG ANSWER

Test 7

Group: 1

Verdict: WRONG ANSWER

Test 8

Group: 1

Verdict: WRONG ANSWER

Test 9

Group: 1

Verdict: WRONG ANSWER

Test 10

Group: 1

Verdict: WRONG ANSWER

Test 11

Group: 1

Verdict: WRONG ANSWER

Test 12

Group: 1

Verdict: WRONG ANSWER

Test 13

Group: 1

Verdict: WRONG ANSWER

Test 14

Group: 1

Verdict: WRONG ANSWER

Test 15

Group: 2

Verdict: WRONG ANSWER

Test 16

Group: 2

Verdict: WRONG ANSWER

Test 17

Group: 2

Verdict: WRONG ANSWER

Test 18

Group: 2

Verdict: WRONG ANSWER

Test 19

Group: 2

Verdict: WRONG ANSWER

Test 20

Group: 2

Verdict: WRONG ANSWER

Test 21

Group: 2

Verdict: WRONG ANSWER

Test 22

Group: 2

Verdict: WRONG ANSWER

Test 23

Group: 2

Verdict: WRONG ANSWER

Test 24

Group: 2

Verdict: WRONG ANSWER

Test 25

Group: 2

Verdict: WRONG ANSWER

Test 26

Group: 2

Verdict: WRONG ANSWER

Test 27

Group: 2

Verdict: WRONG ANSWER

Test 28

Group: 2

Verdict: WRONG ANSWER

Test 29

Group: 3

Verdict: WRONG ANSWER

Test 30

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 31

Group: 3

Verdict: WRONG ANSWER

Test 32

Group: 3

Verdict: WRONG ANSWER

Test 33

Group: 3

Verdict: WRONG ANSWER

Test 34

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 37

Group: 4

Verdict: WRONG ANSWER

Test 38

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 4

Verdict: WRONG ANSWER

Test 40

Group: 4

Verdict: WRONG ANSWER

Test 41

Group: 4

Verdict: WRONG ANSWER

Test 42

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 43

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 44

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 45

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 46

Group: 4

Verdict: WRONG ANSWER

Test 47

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 48

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 49

Group: 4

Verdict: WRONG ANSWER

Test 50

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 51

Group: 4

Verdict: WRONG ANSWER

Test 52

Group: 4

Verdict: TIME LIMIT EXCEEDED