This problem originates from some contest for school children. Thanks to our colleague Vadim Tukaev for bringing it to our attention.
There is a small city with all houses arranged in a single. Houses themselves are of a form of towers of various height:
###
### ###
### ### ### \ /
### ### ### ### --0--
### ### ### ### ### / \
### ### ### ### ### ###
-------------------------------------long distance-------
1 2 3 4 5 6 E
In this schematic we see house #1 of 5 storeys, house #2 of 2 storeys etc.
Far-far away to the right there is a small nuclear power plant E. It suffers some failure and there are
rumors it emits dangerous radiation. Really, rumors are exaggerated, as usually, but people in general are
not well aware of what amounts of radiation are dangerous and at what distance.
So people are alarmed. However they are told by mayor that:
Citizens of most houses become content with these explanations and started calculating, which house is
the most important (i.e. "hides" more buildings than others). In our example house #6 hides only #5,
while #4 hides #3 and #1. Meanwhile #2 is not hidden by #4 but rather by #3 (e.g. if #4 and
all to the right of it are demolished, nevertheless #2 is still safe thanks to #3).
Here is the problem at last
We really don't know the heights of the buildings. But we are given "a profile" of a city. Profile is an array of values, giving for every house, how many other buildings it "hides". For our example profile is:
0 0 1 2 0 1
And we want to "restore" the model of the city from its profile - i.e. to find out the possible heights
of houses. We know that no houses are of the same height. Anyway there could be several solutions.
In our schematic houses #3 and #6 can be swapped for example. You are free to choose any you like.
Example:
input data:
0 0 1 2 0 1
answer:
4 1 3 6 2 5
P.S. As the amount of data is not too great, you may also solve this with pencil and paper - though of course we encourage writing some code to automate the calculations :)