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.
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?
