CEOI '18 P3 - Lottery

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.4s
Memory limit: 32M

Problem types

For a long long time you have been a big fan of Bytelotto. For around the same time, the members of your family have been telling you that all such games are a waste of money. You are sure that it is because of their lack of skill! You have a brilliant plan and everyone will see you winning the game soon.

There are many types of games. You are interested in one of them: Bitlotto. The choice was simple, as it is the easiest offered type of game: on each day exactly one number is drawn at random. You took notes the results of draws in n consecutive days and obtained a sequence a_1, a_2, \dots , a_n. You are sure that there is some pattern in this sequence, especially in intervals of l consecutive days. Your family still does not believe you, so the only way to convince them is to use solid math.

There are n-l+ 1 intervals of days of length l. The i^{th} interval starts at position i, so it contains elements a_i, a_{i+1}, \ldots , a_{i+l-1}. The distance between two intervals is the number of mismatches on their corresponding positions. In other words, for the x^{th} and the y^{th} interval it is the number of positions i (0 \le i < l) such that a_{x+i} and a_{y+i} are different. Finally, we define two intervals to be k-similar if their distance is at most k.

There is a fixed sequence and an integer l. You are given q queries. In every query, you are given an integer k_j and for each of the n - l + 1 intervals you must find the number of intervals of the same length that are k_j -similar to this interval (not counting this interval itself).


The first line of the standard input contains two space-separated integers n and l (1 \le l \le n \le 10\,000), the number of days and the length of the analysed intervals. The second line contains n space-separated integers a_1, a_2, \ldots , a_n (1 \le a_i \le 10^9), where a_i is the number that was drawn on the i^{th} day.

The third line contains an integer q (1 \le q \le 100), the number of queries. Each of the next q lines contains an integer k_j (0 \le k_j \le l), the similarity parameter for the j^{th} query.


Print q lines. The j^{th} line should contain n - l + 1 space-separated integers that are the answer to the j^{th} query. The i^{th} number in a line should be the number of other intervals that are k_j -similar to the i^{th} interval.


The test set is divided into the following subtasks with additional constraints. Tests in each of the subtasks consist of one or more separate test groups. Each test group may contain one or more test cases.

Subtask Constraints Points
1 n \le 300 25
2 n \le 2000 20
3 q = 1, k_1 = 0 20
4 q = 1 15
5 \text { no additional constraints } 20

Sample Input

6 2
1 2 1 3 2 1

Sample Output

2 1 1 1 1
4 4 4 4 4

Explanation for Sample Output

In the example above there are five intervals of length 2:

  • the first interval contains the numbers 1\ 2
  • the second contains 2\ 1
  • the third contains 1\ 3
  • the fourth contains 3\ 2
  • the fifth contains 2\ 1

There are two queries.

The first query has k = 1. The first and the third interval — 1\ 2 and 1\ 3 — differ only on the second position, so the distance between them is 1. Similarly, the first and fourth interval — 1\ 2 and 3\ 2 — differ only on the first position, so the distance is 1. These are the only two intervals that are 1-similar to the first interval, so the first printed number is 2.

In the second query we are given k = 2. All pairs of intervals are 2-similar.


There are no comments at the moment.