Hi Sergii, I wondered about the same thing. I sent them this analysis:
Minimum Cost Required: N-1, as you would have to put each number in order, so
each individual number will have a cost of 1:
1 2: Cost of 1, N=2: minimum cost: N-1
1 2 3: Cost of 2, N=3: minimum cost: N-1
1 2 .. N-1 N: Cost of N: minimum cost: N-1
This means that any cost of less than N-1 is IMPOSSIBLE.
Maximum cost possible:
Maximum cost possible is to have a reversal at each step:
For N=1, there is one step to place the 1:
1
For N=2, there is only one step with a maximum cost of 2 (the other possibility
is the minimum variant as discussed above):
2 1 -> 1 2, for a cost of 2
For N=3, there is two steps with maximum reversal:
. . 1 -> 1 .., will reverse for a cost of 3:
For the .. to have a maximum value, you would take the maximum cost of N=2,
which was 2, but starting at 2, instead of 1:
2 3 1 -> R3 (C3): 1 3 2 -> R3 (C2) 1 2 3, for a total cost of 5.
By continuing this pattern, you will see that for any N, the cost C will be:
N + N-1 + N-2 + … + 3 + 2, or the sum of 2 to N. The formula for the sum of 1
to N is: N * (N-1) / 2, and if we subtract one we get N * (N+1) / 2 – 1:
So:
1: 1 * 2 / 2 - 1 = 0, 2: 2 * 3 / 2 – 1: 2, 3: 3 * 4 / 2 – 1: 5 etc
This also shows how to construct a maximum cost solution in O(N) time:
Place the 1 at position N: this will cause a maximum sized reversal of N at the
first step.
For the 2 to cause a reversal of cost N-1, it will have to be in position N-1
after the reversal of the 1. It therefore has to be at position 1. For the 3 to
cause a reversal of N-2 after the reversal of the 2, it has to be at position
N-2, the 4 will have to be at position 2 etc.
In other words, a maximum cost solution will look like:
2 4 6 .. N N-1 .. 5 3 1
To demonstrate:
2 4 6 .. N N-1 .. 5 3 1
1 3 5 .. N-1 N .. 6 4 2: cost N
1 2 4 6 .. N N-1 .. 3: cost N-1
1 2 3 … N-1 N … 6 4: cost N-2
..
1 2 3 4 5 6.. N N-1: cost 2
1 2 3 4 5 6 .. N-1 N
So, to construct a maximum cost solution, you will need O(N) steps: first put
all even numbers in ascending order until you reach N, then do the same for the
odd numbers starting at the end and working your way to the middle. Note that
this is also true if you were to shift the numbers by adding a constant to each
of those:
2+S 4+S .. N+S N+S-1 .. 3+S 1+S
As this is the maximum cost, anything over this amount will be IMPOSSIBLE.
Define the following functions for convenience:
MinC(N): the minimum cost of a N number placement.
MaxC(N): the maximum cost of a N number placement
There are now these cases to consider.
C < MinC(N): IMPOSSIBLE
C > MaxC(N): IMPOSSIBLE
C= MinC(N): Create an array of numbers from 1 to N in ascending order.
C = MaxC(N): Create the array of numbers as explained above, which is O(N)
(every place and every number are put in place exactly once, with only O(1)
operations)
C > MaxC(N-1):
To achieve this, you could create a maximum solution for N-1 numbers (starting
at 2), and have one reversal extra by placing the 1 at the (N-1-C) position:
Example: N=4, C=7: MaxC(4) = 4 * 5 / 2 – 1 = 9.
MaxC(N-1)=5: C > MaxC(N-1)
The MaxC(N-1) solution for N=3, starting at 2:
3 4 2. We now have to find a place for the 1 at a position with a cost of
N-C-1: 9-7-1 = 1
This is the case when we put it at the first position:
1 3 4 2
1 3 4 2 C: 1
1 2 4 3 C: 3
1 2 3 4: 2
Total cost: 6
By putting it at position 2, the cost would be 7, position 3: the cost would be
8, position 4: the cost would be 9. However, because there is an additional
reversal step, everything before the 1 needs to be in reverse, so the reversal
step would recreate the maximum cost solution.
The cost for creating the maximum cost solution is O(N-1) even if you have the
additional requirement of keeping room for the 1, and putting everything in
reverse. The placement of the 1 is O(1), so the total cost of creating this
C-cost placement is still O(1).
C < MaxC(N-1)
This is slightly trickier. We know that there must be a solution, because it is
between the valid range of MinC(N) and MaxC(N).
However, we can observe that if we put a 1 in the first position, and we know
by induction that we can solve this recursively by having the 1 followed by the
solution for Solution(N-1) starting at 2, and that this solution is O(N-1), the
algorithm will still be O(N).
The algorithm needed will therefore need to contain 3 elements:
Solution(N,C):
Calculate MinC(N), MaxC(N)
Shift = 0.
If (C < MinC(N)) -> IMPOSSIBLE
If (C > MaxC(N)) -> IMPOSSIBLE
While (C < MaxC(N-1)) :
Put (1+Shift) at position Shift, Shift += 1
N -= 1, C -= 1
If (C == MaxC(N))
// create a maximum solution starting at ‘Shift’
… according to spec above
If (C > MaxC(N)) {
// put the 1 (+Shift) at position (Shift+N-C-1)
// create a maximum solution of N-1, but for everything less than the position
of the 1,
// start at that position minus 1 and work backwards instead of forwards
// everything after the 1 stays where it would have stayed otherwise
}
The total cost of this algorithm is O(N), as all operations are O(1) and every
number is handled exactly once.
Also note that there is no recursion required, just three distinct phases:
- the minimum steps of cost 1
- the positioning of the surplus reversal (C - MaxC(N))
- the maximum solution, keeping in mind that you have to work backwards instead
of forwards when there is a surplus reversal and you are filling the positions
to the left of the reversal position.
Regards,
Ronald van Loon
On 06/04/2021 22:28:23, Sergii Olshanetskyi <[email protected]>
wrote:
The analysis for the problem suggest O(N^2) as the best solution.
However, it can be solved in O(N).
The idea is to break the expected array into two parts of size X and Y:
1) X are the numbers can be put at first position without any permutations
[ 1 2 3 4 ..... ]
2) Y are the number that have to be at specific positions to get the needed
complexity
[ 12 3 4.... 9 11 10 8]
It is possible to create the most costly solution for N digits, by putting each
number at the worst position. For instance, the most costly solution for N = 5
would be: 2 4 5 3 1.
My approach is to use Y numbers to generate the expected cost, and numbers X
are just printed as they are.
My submission worked. I also tested in locally on N = 10^6.
I am curious why didn't the Google Code Jam team mentioned O(N) solution in the
analysis section?..
--
-- You received this message because you are subscribed to the Google Groups
Code Jam group. To post to this group, send email to
[email protected]. To unsubscribe from this group, send email to
[email protected]. For more options, visit this group at
https://groups.google.com/d/forum/google-code?hl=en
[https://groups.google.com/d/forum/google-code?hl=en]
---
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected]
[mailto:[email protected]].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/4e97cc70-490c-413e-8803-4d73286153f7n%40googlegroups.com
[https://groups.google.com/d/msgid/google-code/4e97cc70-490c-413e-8803-4d73286153f7n%40googlegroups.com?utm_medium=email&utm_source=footer].
--
-- You received this message because you are subscribed to the Google Groups
Code Jam group. To post to this group, send email to
[email protected]. To unsubscribe from this group, send email to
[email protected]. For more options, visit this group at
https://groups.google.com/d/forum/google-code?hl=en
---
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/Mailbird-77f68ad0-89a1-4208-98d8-709231b7b488%40gmail.com.
