(SPOJ) Semente - Solution 1

Link to the problem: http://br.spoj.com/problems/SEMENT14/

The solution below uses a queue structure to keep all the spots that were not considered yet. Inside this queue, we keep the information about what spot will be visited and what day this visit will occur.


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

class solucao {
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        String line = br.readLine();
        String[] s = line.split(" ");
        int numBlocks = Integer.parseInt(s[0]);
        int numDrops = Integer.parseInt(s[1]);
       
        line = br.readLine();
        s = line.split(" ");
       
        int lastDay = 0;
        Queue<Info> queue = new ArrayDeque<>();
        HashSet<Integer> dropsPosition = new HashSet<>();
        for (int i = 0; i < numDrops; i++) {
            queue.add(new Info(Integer.parseInt(s[i]), 0));
            dropsPosition.add(Integer.parseInt(s[i]));
        }
       
       
        while (dropsPosition.size() < numBlocks) {
            Info info = queue.poll();
            int pos = info.pos;
            int day = info.day;
            if (pos-1 > 0 && !dropsPosition.contains(pos-1)) {
                queue.add(new Info(pos-1, day+1));
                dropsPosition.add(pos-1);
            }
            if (pos+1 <= numBlocks && !dropsPosition.contains(pos+1)) {
                queue.add(new Info(pos+1, day+1));
                dropsPosition.add(pos+1);
            }
           
            lastDay = day+1;
        }
       
        bw.write(lastDay+"\n");
           
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        solucao m = new solucao();
        m.process();
       
        System.exit(0);
    }
}

class Info {
    int pos;
    int day;
   
    public Info(int p, int d) {
        pos = p;
        day = d;
    }
}