Here is something rare. A question where the question setter does an oopsie in the testcases.
The solution to the intended question:
First of all to make our lives easier, let's sort the array containing the indices of cities containing space stations.
Let us think of this example (0 is a city without space station, 1 is with)
00001001000001000
We should find the number of zeroes between two 1's (let that be n) and then, by induction one can prove that the longest distance to a space station in that set of zeroes is ceil( (n - 1)/2 ). We will have to find the maximum among all such groups of zeroes between two 1's.
But what about the ends? The ends have to be dealt differently. For the ends, the number of zeroes from that end to the nearest one is equal to the largest distance. So we do that by comparing the maximum value we obtained before with the number of zeroes between the left end and the first 1, and the number of zeroes after the last 1 and the right end. The maximum out of these three will be the answer.
Type, type, type... hit submit! What happens? 4 testcases did not pass. Wrong Answer, it says. But then you spend some Hackos to look at the testcase after racking your brains for an hour, and you see this:
6 6
0 1 2 4 3 5
Wait, what? The question mentions that the cities are indexed 1 based! So the question is not perfect. The setter apparently forgot to make the testcases 1 based. After taking that into account, it works.
The solution to the intended question:
First of all to make our lives easier, let's sort the array containing the indices of cities containing space stations.
Let us think of this example (0 is a city without space station, 1 is with)
00001001000001000
We should find the number of zeroes between two 1's (let that be n) and then, by induction one can prove that the longest distance to a space station in that set of zeroes is ceil( (n - 1)/2 ). We will have to find the maximum among all such groups of zeroes between two 1's.
But what about the ends? The ends have to be dealt differently. For the ends, the number of zeroes from that end to the nearest one is equal to the largest distance. So we do that by comparing the maximum value we obtained before with the number of zeroes between the left end and the first 1, and the number of zeroes after the last 1 and the right end. The maximum out of these three will be the answer.
Type, type, type... hit submit! What happens? 4 testcases did not pass. Wrong Answer, it says. But then you spend some Hackos to look at the testcase after racking your brains for an hour, and you see this:
6 6
0 1 2 4 3 5
Wait, what? The question mentions that the cities are indexed 1 based! So the question is not perfect. The setter apparently forgot to make the testcases 1 based. After taking that into account, it works.
No comments:
Post a Comment