(UVA) Smallest Sub-Sequence - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2531

The solution below used a technique called Sliding Window to solve this problem.


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

class Main {
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numTests = Integer.parseInt(br.readLine());
        for (int test = 0; test < numTests; test++) {
            String line = br.readLine();
            String[] s = line.split(" ");
            int n = Integer.parseInt(s[0]);
            int m = Integer.parseInt(s[1]);
            int k = Integer.parseInt(s[2]);
           
            int[] array = new int[n];
            array[0] = 1;
            array[1] = 2;
            array[2] = 3;
            // construct the sequence
            for (int i = 3; i < n; i++) {
                array[i] = (array[i-1]+array[i-2]+array[i-3])%m + 1;
            }
           
            int[] amount = new int[k]; // how many times each desired number appeared
            HashSet<Integer> sequence1toK = new HashSet<>();
           
            int pointerLeft = 0;
            int bestAnswer = Integer.MAX_VALUE;
            for (int pointerRight = 0; pointerRight < n; pointerRight++) {
                if (array[pointerRight] > k) {
                    continue;
                }
               
                sequence1toK.add(array[pointerRight]);
                amount[array[pointerRight]-1]++;
                // if I have all the desired elements
                if (sequence1toK.size() == k) {
                    while (sequence1toK.size() == k) {
                        bestAnswer = Math.min(bestAnswer, (pointerRight-pointerLeft+1));
                        if (array[pointerLeft] > k) {
                            pointerLeft++;
                            continue;
                        }
                        amount[array[pointerLeft]-1]--;
                        if (amount[array[pointerLeft]-1] == 0) {
                            sequence1toK.remove(array[pointerLeft]);
                        }                   
                        pointerLeft++;
                    }
                }
            }
           
            String out = (bestAnswer == Integer.MAX_VALUE) ? "sequence nai\n" : bestAnswer+"\n";
            bw.write("Case " + (test+1) + ": " + out);
        }
                                                      
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução