CrossingTheRiver
TCO12 Round 3B · 2012-03-27 · by vexorian
TCO12 Round 3B · 2012-03-27 · by vexorian · Dynamic Programming
Problem Statement
Problem Statement
NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.
You start on the left side of a river. The river is waterWidth units wide and infinitely deep. The land on the right side of the river is (landWidth+1) units wide. On the far right side of this land there is an infinitely tall ladder of width 1 unit.
You own many blocks specified by theint[] , blockHeight. The i-th block has a width of 1 unit and a height of blockHeight[i] units. You have observed that all of the blocks have the curious property that when placed in water they float vertically with exactly depth units below the surface of the water (see image below). Blocks on land or in the water must be placed vertically. A side of the block that is 1 unit wide must touch the ground or be submerged in water. You can not place blocks to the left of the river. You also can not place blocks on top of other blocks.
Your objective is to cross the river and reach the ladder. After placing the blocks, you have three allowed movements: You can move to the right if height of the top of the next block (or the height of the land if there is no block there) is the same as your current height. You can also climb to the right if the height of the next block is exactly one unit above your current height. Finally, the ladder can always be reached no matter at what height you are when standing immediately to its left. It would be too dangerous to move down to a block or the land that lies at a lower height. Also, the water is too cold and you cannot swim.
If it is possible to place the available blocks such that you can reach the ladder then return theString "POSSIBLE" (quotes for clarity). If it is not possible then return the String "IMPOSSIBLE".
You start on the left side of a river. The river is waterWidth units wide and infinitely deep. The land on the right side of the river is (landWidth+1) units wide. On the far right side of this land there is an infinitely tall ladder of width 1 unit.
You own many blocks specified by the
Your objective is to cross the river and reach the ladder. After placing the blocks, you have three allowed movements: You can move to the right if height of the top of the next block (or the height of the land if there is no block there) is the same as your current height. You can also climb to the right if the height of the next block is exactly one unit above your current height. Finally, the ladder can always be reached no matter at what height you are when standing immediately to its left. It would be too dangerous to move down to a block or the land that lies at a lower height. Also, the water is too cold and you cannot swim.
If it is possible to place the available blocks such that you can reach the ladder then return the
Constraints
- waterWidth will be between 1 and 50, inclusive.
- landWidth will be between 1 and 50, inclusive.
- blockHeight will contain between waterWidth and 50 elements, inclusive.
- depth will be between 2 and 100, inclusive.
- Each element of blockHeight will be between depth and 100, inclusive.
Examples
0)
3
3
{3,4,4,5,5, 6}
2
Returns: "POSSIBLE"
The following image describes a possible solution:
1)
3
3
{3,4,4,5,6, 6}
2
Returns: "IMPOSSIBLE"
2)
5
2
{4,4,4,4,4}
4
Returns: "POSSIBLE"
It is not always necessary to place blocks on the land.
3)
25
25
{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49}
2
Returns: "POSSIBLE"
4)
15
15
{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29}
2
Returns: "POSSIBLE"
6)
5
5
{5,5,5,5,5,5, 2,3,4,4,6, 7, 3, 2}
2
Returns: "POSSIBLE"
A possible solution is described by the image in the problem statement.
8)
1
1
{5,3,4}
2
Returns: "IMPOSSIBLE"
Remember that it is not possible to place a block on the starting position.
Submissions are judged against all 149 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CrossingTheRiver with a public method string isItEvenPossible(int waterWidth, int landWidth, vector<int> blockHeight, int depth) · 149 test cases · 2 s / 256 MB per case