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?
IMO the operation felt quite unnatural, and the casework was unnecessarily heavy.
Yes, it seems like it is pretty casework-heavy. Thank you for your feedback.
On the operation being unnatural, you could try having a story around the problem instead of using arbitrary terms like "hygienic"
For instance, perhaps you are a card dealer trying to rig the cards in a certain order and are tasked with shuffling it i-1 times, but the players will notice if you perform a false shuffle (one that leaves the order unchanged)
Different people prefer different things. I know some people who are somewhat against stories and would prefer a concise statement that corresponds to how they would end up parsing the problem, in which case the current statement would appeal to them more.
Cute problem. It feels quite okay to have as a Div. 2 A, but like others have pointed out, there is a little too much casework.
As a participant everyone would like to solve the simplest problems as quickly as possible, so it actually seems rather weird as well as annoying that we even have to classify cases just to solve a Div2 A. But I still voted "average" since its overall difficulty and involved algorithm is relatively appropriate for a Div2 A.
Here's a piece of advice: Try to remove implementation difficulty and heavy casework to make the problem more friendly(that is, the concise solution could be figured out the very instant you finish reading its statement). Therefore I think it would be good if the operation could be "choose an index i and set a[i] into a[i]+x" where x is a given positive integer(and you only need to output the minimum number of times you use the operation to sort the array), to transform it into a simple greedy problem.