I'm writing this while there's a tornado warning at Purdue but I refuse to die until I reach orange↵
↵
Wanted to share an idea that comes up reasonably often in my opinion. Essentially, you can take advantage of some property of the minimum or maximum of an array or some other structure to construct/calculate the answer starting from there.↵
↵
[2129B/2130D](https://codeforces.me/contest/2130/problem/D) — Difficulty: 1600↵
↵
<spoiler summary="Hint 1">↵
For the index $j$ where $p_j = 1$, you must set $a_j$ to $1$ or $2n-1$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
In other words, $a_j$ will either be the minimum or maximum of the entire array.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
So $a_j$ will be part of an inversion with every element to the left, or every element to the right.↵
</spoiler>↵
↵
<spoiler summary="Answer">↵
For the index $j$ where $p_j = 1$, greedily set $a_j$ to $1$ or $2n-1$ depending on whether there would be less inversions to the left or to the right.↵
↵
Then for the index $k$ where $p_k = 2$, do the same thing again. Although be careful counting because you should ignore index $j$ since it was already counted.↵
↵
Repeat until you have constructed the answer. This works in $O(n^2)$ and should pass, or you can speed up to $O(n \log n)$ by counting with std::set or something like that.↵
</spoiler>↵
↵
[2067D](https://codeforces.me/contest/2067/problem/D) — Difficulty: 1900↵
↵
<spoiler summary="Hint 1">↵
Min/max abuse!↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Minimum $x_i$ and maximum $x_j$.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Let $m$ equal the number of unique values in $x_i$. The length of the longest path in the graph (if it's a graph) cannot exceed $m-1$. (Why?)↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
$x_j - x_i$ is at least $m-1$. (Why?)↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
Do you see what to query first yet?↵
</spoiler>↵
↵
<spoiler summary="Hint 6">↵
Query $x_i$ and $x_j$ first. If you:↵
↵
- get $< m-1$, then you definitely have a graph↵
- get $> m-1$, then you definitely have points in the plane↵
- get $m-1$, then you could have either, but you have 1 query left.↵
</spoiler>↵
↵
<spoiler summary="Hint 7">↵
If we have a graph, and $i \rightarrow j$ has length $m-1$, what does this say about $j \rightarrow i$?↵
</spoiler>↵
↵
<spoiler summary="Answer">↵
For the first query see above.↵
↵
For the second query we'll query $x_j$ and $x_i$ (same as the first time but in the reversed order).↵
↵
If we have a graph, we either:↵
↵
- $i, j$ not connected: we'll get 0.↵
- $i, j$ are connected in a cycle, in which case we have to get 1, because the path $i \rightarrow ... \rightarrow j$ visits every vertex. If there was another vertex between $j$ and $i$, that would be a contradiction, since there would now be a shorter path from $i$ to $j$.↵
↵
Otherwise, we'll get a number $\ge m-1$ for the distance.↵
</spoiler>↵
↵
↵
[1852B/1853D](https://codeforces.me/contest/1853/problem/D) — Difficulty: 1800 on CF, 2000 on CList, definitely feels more like a 2000 to me↵
↵
<spoiler summary="Hint 1">↵
The statement seems pretty diabolical. Let's try to do _something_: maybe sort $a$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If you sort $a$, then the resulting array $b$ should also be sorted.↵
↵
Because if $b_i \le b_j$, then if an index works for $i$, it will also work for $j$, so $a_i \le b_i$.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Think about min/max abuse. Specifically, min/max abuse on the array $b$ you're constructing.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
There must be a **unique** absolute-value min/max. For example, if $-n$ is in $b$, then the problem conditions prevent $n$ from being in $b$.↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
The unique absolute-value min/max either↵
↵
- has $a_i = n$, because it's too positive for anything to make it $< 0$;↵
- or has $a_i = 0$, because it's too negative for anything to make it $> 0$.↵
</spoiler>↵
↵
<spoiler summary="Hint 6">↵
So we can place either $-n$ at the left, or $n$ at the right.↵
</spoiler>↵
↵
<spoiler summary="Answer">↵
For each step, we'll either place $-n$ at the left if $a_l = 0$, or $n$ at the right if $a_r = n$. Note that if both $a_l = 0, a_r = n$, then that's a contradiction.↵
↵
Continue for $n-1$. Note that all the higher positive numbers we placed before are guaranteed to work with us, and all the lower negative numbers we placed are guaranteed to not. So other than that the subproblem is independent.↵
↵
_Note: don't look at my accepted submission, check the official one instead. I used a slightly different method of filling it in at the time._↵
</spoiler>↵
↵
[2234E](https://codeforces.me/contest/2234/problem/E) (just 2 contests ago!) — Difficulty: 2100↵
↵
<spoiler summary="Hint 1">↵
First try to find any polynomial time solution.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
$1$ has to be in the permutation $p$ somewhere.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
If $1$ is placed at position $i \in [1...n]$, then $a_i = (i) \cdot (n-i+1)$.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Additionally, if there are multiple valid locations to place the $1$, that's a contradiction. (Why?)↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
Now that you know the location of $1$, solve the left and right half.↵
</spoiler>↵
↵
<spoiler summary="Hint 6">↵
The left and right half are independent because crossing the minimum $1$ forces the subarray minimum to be less than $p_i$.↵
</spoiler>↵
↵
<spoiler summary="Answer">↵
Recursively solve the left and right half. Then merge the answers (assuming the current size is $n$ and the minimum occurs at index $i$:↵
↵
$$ans_{full} = ans_{left} \cdot ans_{right} \cdot \binom{n-1}{i-1}.$$↵
↵
We multiply by the choose because you can choose any distribution of the $n-1$ remaining numbers across the left and right half.↵
↵
Also check for contradictions if any $a_i$ is too large (exceeds what would be possible even if it was a minimum).↵
↵
Then optimizing to $n \log n$ involves searching for the $a_i$ location from outside to inside. See the official editorial for more details.↵
↵
[Here is my somewhat crappy code](https://codeforces.me/contest/2234/submission/377712996)↵
</spoiler>↵
↵
**How do I get better at spotting this?**↵
↵
Probably just practice! You'll start to remember to think about it more often and start seeing the patterns like this one.
↵
Wanted to share an idea that comes up reasonably often in my opinion. Essentially, you can take advantage of some property of the minimum or maximum of an array or some other structure to construct/calculate the answer starting from there.↵
↵
[2129B/2130D](https://codeforces.me/contest/2130/problem/D) — Difficulty: 1600↵
↵
<spoiler summary="Hint 1">↵
For the index $j$ where $p_j = 1$, you must set $a_j$ to $1$ or $2n-1$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
In other words, $a_j$ will either be the minimum or maximum of the entire array.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
So $a_j$ will be part of an inversion with every element to the left, or every element to the right.↵
</spoiler>↵
↵
<spoiler summary="Answer">↵
For the index $j$ where $p_j = 1$, greedily set $a_j$ to $1$ or $2n-1$ depending on whether there would be less inversions to the left or to the right.↵
↵
Then for the index $k$ where $p_k = 2$, do the same thing again. Although be careful counting because you should ignore index $j$ since it was already counted.↵
↵
Repeat until you have constructed the answer. This works in $O(n^2)$ and should pass, or you can speed up to $O(n \log n)$ by counting with std::set or something like that.↵
</spoiler>↵
↵
[2067D](https://codeforces.me/contest/2067/problem/D) — Difficulty: 1900↵
↵
<spoiler summary="Hint 1">↵
Min/max abuse!↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Minimum $x_i$ and maximum $x_j$.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Let $m$ equal the number of unique values in $x_i$. The length of the longest path in the graph (if it's a graph) cannot exceed $m-1$. (Why?)↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
$x_j - x_i$ is at least $m-1$. (Why?)↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
Do you see what to query first yet?↵
</spoiler>↵
↵
<spoiler summary="Hint 6">↵
Query $x_i$ and $x_j$ first. If you:↵
↵
- get $< m-1$, then you definitely have a graph↵
- get $> m-1$, then you definitely have points in the plane↵
- get $m-1$, then you could have either, but you have 1 query left.↵
</spoiler>↵
↵
<spoiler summary="Hint 7">↵
If we have a graph, and $i \rightarrow j$ has length $m-1$, what does this say about $j \rightarrow i$?↵
</spoiler>↵
↵
<spoiler summary="Answer">↵
For the first query see above.↵
↵
For the second query we'll query $x_j$ and $x_i$ (same as the first time but in the reversed order).↵
↵
If we have a graph, we either:↵
↵
- $i, j$ not connected: we'll get 0.↵
- $i, j$ are connected in a cycle, in which case we have to get 1, because the path $i \rightarrow ... \rightarrow j$ visits every vertex. If there was another vertex between $j$ and $i$, that would be a contradiction, since there would now be a shorter path from $i$ to $j$.↵
↵
Otherwise, we'll get a number $\ge m-1$ for the distance.↵
</spoiler>↵
↵
↵
[1852B/1853D](https://codeforces.me/contest/1853/problem/D) — Difficulty: 1800 on CF, 2000 on CList, definitely feels more like a 2000 to me↵
↵
<spoiler summary="Hint 1">↵
The statement seems pretty diabolical. Let's try to do _something_: maybe sort $a$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
If you sort $a$, then the resulting array $b$ should also be sorted.↵
↵
Because if $b_i \le b_j$, then if an index works for $i$, it will also work for $j$, so $a_i \le b_i$.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Think about min/max abuse. Specifically, min/max abuse on the array $b$ you're constructing.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
There must be a **unique** absolute-value min/max. For example, if $-n$ is in $b$, then the problem conditions prevent $n$ from being in $b$.↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
The unique absolute-value min/max either↵
↵
- has $a_i = n$, because it's too positive for anything to make it $< 0$;↵
- or has $a_i = 0$, because it's too negative for anything to make it $> 0$.↵
</spoiler>↵
↵
<spoiler summary="Hint 6">↵
So we can place either $-n$ at the left, or $n$ at the right.↵
</spoiler>↵
↵
<spoiler summary="Answer">↵
For each step, we'll either place $-n$ at the left if $a_l = 0$, or $n$ at the right if $a_r = n$. Note that if both $a_l = 0, a_r = n$, then that's a contradiction.↵
↵
Continue for $n-1$. Note that all the higher positive numbers we placed before are guaranteed to work with us, and all the lower negative numbers we placed are guaranteed to not. So other than that the subproblem is independent.↵
↵
_Note: don't look at my accepted submission, check the official one instead. I used a slightly different method of filling it in at the time._↵
</spoiler>↵
↵
[2234E](https://codeforces.me/contest/2234/problem/E) (just 2 contests ago!) — Difficulty: 2100↵
↵
<spoiler summary="Hint 1">↵
First try to find any polynomial time solution.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
$1$ has to be in the permutation $p$ somewhere.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
If $1$ is placed at position $i \in [1...n]$, then $a_i = (i) \cdot (n-i+1)$.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Additionally, if there are multiple valid locations to place the $1$, that's a contradiction. (Why?)↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
Now that you know the location of $1$, solve the left and right half.↵
</spoiler>↵
↵
<spoiler summary="Hint 6">↵
The left and right half are independent because crossing the minimum $1$ forces the subarray minimum to be less than $p_i$.↵
</spoiler>↵
↵
<spoiler summary="Answer">↵
Recursively solve the left and right half. Then merge the answers (assuming the current size is $n$ and the minimum occurs at index $i$:↵
↵
$$ans_{full} = ans_{left} \cdot ans_{right} \cdot \binom{n-1}{i-1}.$$↵
↵
We multiply by the choose because you can choose any distribution of the $n-1$ remaining numbers across the left and right half.↵
↵
Also check for contradictions if any $a_i$ is too large (exceeds what would be possible even if it was a minimum).↵
↵
Then optimizing to $n \log n$ involves searching for the $a_i$ location from outside to inside. See the official editorial for more details.↵
↵
[Here is my somewhat crappy code](https://codeforces.me/contest/2234/submission/377712996)↵
</spoiler>↵
↵
**How do I get better at spotting this?**↵
↵
Probably just practice! You'll start to remember to think about it more often and start seeing the patterns like this one.
