The Contest Contest 1 P4 - A Typical YAC Problem

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Josh lives on a street with N houses conveniently numbered from 1 to N from left to right, where Josh lives at house number S. Nils doesn't know what S is, but Josh tells him that he'll be going for a walk.

Starting from his house S, he will repeatedly travel along the street to adjacent houses, never going to the left of house 1 or to the right of house N. His walk ends back at his house S, though he can pass by his house multiple times during the walk. Let p be the list of house numbers that Josh visited on his walk, in order.

Nils also knows that Josh never visits more than K consecutive houses in a row. More formally, if a is a monotonic subarray of p, then |a| \le K. Note that an array is monotonic if the elements are either all strictly increasing or all strictly decreasing.

After going on his walk, he constructs an array f, where f_i is the number of times he visited house number i during his walk.

Confident that his address is hidden, Josh gives Nils f. Using this array, can you help Nils determine Josh's possible house numbers, or determine that the array is inconsistent?


3 \le N \le 10^6

3 \le K \le N

1 \le f_i \le 10^9

Subtask 1 [20%]

N \le 3 \times 10^3

K = N

Subtask 2 [20%]

K = N

Subtask 3 [30%]

N \le 3 \times 10^3

Subtask 4 [30%]

No additional constraints.

Input Specification

The first line contains two integers N and K.

The next line contains N integers f_1, \ldots, f_N.

Output Specification

First output a line containing an integer X, the number of possible house numbers S.

If X \ge 1, output X distinct integers, the possible house numbers on the next line in ascending order.

Sample Input 1

4 4
1 3 3 2

Sample Output 1

2 4

Explanation for Sample 1

A possible walk Josh could have taken is p=[2,1,2,3,4,3,4,3,2], which starts and ends at house 2. In this walk, the longest monotonic subarray is [1,2,3,4], which has a length of 4.

Another possible walk Josh could have taken is p=[4,3,2,1,2,3,2,3,4], which starts and ends at house 4.

Sample Input 2

5 3
2 2 2 2 1

Sample Output 2


Explanation for Sample 2

There are no possible paths that satisfy the given constraints. Even though p=[1,2,3,4,5,4,3,2,1] is a path that starts and ends at house 1, it does not satisfy the constraints since the monotonic subarray [1,2,3,4,5] has a length greater than K.


There are no comments at the moment.