Would this be a good Div. 2 A?

Правка en1, от 123gjweq2, 2024-10-17 07:29:11

Hello everyone. I came up with this problem today (I'm not sure if it is original, but I really hope it is), and I am just wondering if it would be a good div. 2 A.

Problem statement:

You are given an array $$$a$$$ of distinct elements, and, because you like hygienic things, you want to sort it in ascending order. Unfortunately, you can't run a normal sorting algorithm on the array. In fact, you can only perform one type of operation that goes like this:

  • You can reorder the array in any way you want. But one constraint must be satisfied: the reordered array must be different from what it was before. For example, the array $$$[1, 2, 3]$$$ can be reordered to $$$[1, 3, 2]$$$, but it cannot be reordered to $$$[1, 2, 3]$$$. Note that, in a string of operations, you can return to previous states of the array. For example, $$$[1, 2, 3] \implies [1, 3, 2] \implies [1, 2, 3]$$$ is valid.

Because sorting the array was too easy for you, you decide to challenge yourself by answering $$$n + 1$$$ queries. The $$$i^{th}$$$ query asks the question: can you sort the array $$$a$$$ in exactly $$$i - 1$$$ operations? Note that the queries are $$$1$$$-indexed.

Input:

The first line of each test contains one integer: $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$, which denotes the length of the array. The next line contains $$$n$$$ space-separated integers $$$a_1, a_2, \cdots a_n$$$ $$$(1 \le a_i \le 10^9)$$$. All $$$a_i$$$ are pairwise distinct.

Output:

For each test, output $$$n + 1$$$ space-separated integers, the $$$i^{th}$$$ integer being the answer to the $$$i^{th}$$$ query. If the answer to the $$$i^{th}$$$ query is true, the $$$i^{th}$$$ integer is $$$1$$$. Otherwise, it is $$$0$$$.

For example, the answer to the array $$$1\,2\,3$$$ would be $$$1\,0\,1\,1$$$, because you cannot sort the array using $$$1$$$ operation, but you can sort it using $$$0, 2, 3$$$ operations.


Solution

I'd also appreciate some feedback if you have the time. If you saw this as a Div. 2 A, would you consider it a bad/average/good problem?

bad

average

good

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский 123gjweq2 2024-10-17 07:29:11 3184 Initial revision (published)