[Timus] 1126 Magnetic Storms

Problem statement is here: http://acm.timus.ru/problem.aspx?space=1&num=1126

There are two ways to solve the problem that I could think of:

1. Use of max heap which is slow and will probably cause time limit exceeded.

2. Two queue solution. In this, two queues are created each having max size equal to M. The first queue keeps track of M last seen data and another queue which keeps the max value in the first queue (Before proceeding further think how you could do that.). The trick is to keep the max element in the first position, so whenever you see a new number discard all the lesser ones seen so far since now the new number is clearly the winner.

 

public void solve(int testNumber, InputReader in, OutputWriter out) {
    Queue<Integer> input = new LinkedList<>();
    Deque<Integer> maxInWindow = new LinkedList<>();

    int M = in.nextInt();

    while (true) {
        int n = in.nextInt();
        if (n == -1) {
            break;
        }
        // maxInWindow always have the max element in the first position.
        while (!maxInWindow.isEmpty() && maxInWindow.peekLast() < n) {
            maxInWindow.pollLast();
        }
        maxInWindow.offerLast(n);
        input.add(n);
        if (input.size() == M) {
            int tmp = input.poll();
            out.println(maxInWindow.peekFirst());
            if (maxInWindow.peekFirst()
                    .equals(tmp)) {
                maxInWindow.pollFirst();
            }
        }
    }
}