Connection Status:
Competition Arena > TigerRiverCrossing

TigerRiverCrossing

SRM 823 · 2022-02-01 · by misof

SRM 823 · 2022-02-01 · by misof · Brute Force, Simple Search, Iteration
Class Name: TigerRiverCrossing
Return Type: String[]
Method Name: addRocks
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

To celebrate the Lunar New Year that starts the Year of the Tiger, the problems in this set feature tigers.


Tigers used to cross a local river. However, a recent flood took away some stones that were sticking out from the river, so now it might be impossible for the tigers to cross.

You are given the String[] river containing a rectangular map of the section of the river where the tigers want to cross it. The character '=' represents water, the character 'O' (uppercase oh) represents a rock in the river. The river flows left to right (i.e., eastwards).

To the north and south of the river there is a sufficient amount of solid ground everywhere. This isn't shown on the map, but you can imagine it as additional rows full of 'O' characters both before and after the rows shown in river.


A tiger always crosses the river orthogonally to its course (i.e., going straight up or down on our map). The tiger must cross the river in a sequence of jumps. Each jump must land on a rock. All jumps in the sequence must have exactly the same length. The length of that jump cannot exceed maxL: the maximum length tigers are physically able to jump.

The tiger can choose where it starts the first jump arbitrarily. In particular, it does not have to start on a rock that is adjacent to the river.


You want to place additional rocks into the river in a way that will allow tigers to cross the river. Rocks are heavy, so you want to minimize the number of extra rocks you need to add. Find and return any one optimal solution: a String[] obtained from the String[] river by changing some '='s into 'O's.

Notes

  • Any solution that adds the minimum number of stones will be accepted.
  • Note that all existing stones ('O's) must remain in their places, even if your path for tigers doesn't use them.

Constraints

  • river will contain between 1 and 50 elements, inclusive.
  • Each element of river will contain between 1 and 50 characters, inclusive.
  • All elements of river will contain the same number of characters.
  • Each character in river will be '=' or 'O'.
  • maxL will be between 1 and 50, inclusive.
Examples
0)
{"===============",
 "========O======",
 "===============",
 "========O======",
 "=O=============",
 "========O======",
 "===============",
 "========O======",
 "===============",
 "========O======"}
2
Returns: {"===============", "========O======", "===============", "========O======", "=O=============", "========O======", "===============", "========O======", "===============", "========O======" }

The tigers still have a sequence of rocks that allows them to cross this river. We don't need to add any new rocks.

1)
{"===============",
 "========O======",
 "===============",
 "========O======",
 "=O=============",
 "========O======",
 "===============",
 "========O======",
 "===============",
 "========O======"}
1
Returns: {"========O======", "========O======", "========O======", "========O======", "=O======O======", "========O======", "========O======", "========O======", "========O======", "========O======" }

The same map as before but now we have tigers that are only capable of jumps of length 1. The optimal solution is to fill in the entire column 8 (0-based index) with rocks.

2)
{"===============",
 "========O======",
 "===============",
 "========O======",
 "=O=============",
 "===============",
 "===============",
 "========O======",
 "===============",
 "========O======"}
3
Returns: {"===============", "========O======", "===============", "========O======", "=O=============", "========O======", "===============", "========O======", "===============", "========O======" }

This is also similar to Example 0, but now one rock is missing and the tigers are capable of jumps of length 3. Jumps of length 3 don't help, the optimal solution is still to fill in the rock that is missing from Example 0. Tigers then can use a sequence of jumps of length 2 to cross the river.

3)
{"===============",
 "========O======",
 "===============",
 "========O======",
 "=O=============",
 "===============",
 "===============",
 "========O======",
 "===============",
 "========O======"}
4
Returns: {"===============", "========O======", "===============", "========O======", "=O=============", "===============", "===============", "========O======", "===============", "========O======" }

Tigers capable of jumps of length 4 can cross this river without needing any extra stones.

4)
{"===============",
 "===============",
 "========O======",
 "===============",
 "==============="}
5
Returns: {"===============", "===============", "========O======", "===============", "===============" }
5)
{"===============",
 "===============",
 "===============",
 "===============",
 "==============="}
5
Returns: {"===============", "===============", "O==============", "===============", "===============" }

A single stone anywhere in the river will do.

6)
{"===============",
 "===============",
 "===============",
 "===============",
 "==============="}
7
Returns: {"===============", "===============", "===============", "===============", "===============" }

Here the tigers are capable of jumping across the whole river in a single leap, so they don't need our help.

111)
{"===============",
 "===============",
 "====O==========",
 "===============",
 "====O==========",
 "===============",
 "===============",
 "====O==========",
 "==============="}
3
Returns: {"===============", "====O==========", "====O==========", "===============", "====O==========", "===============", "===============", "====O==========", "===============" }

Remember that tigers cannot change their jump length while crossing the river. (If they could, they could cross this river by alternating jumps of length 2 and 3, but as they cannot do so, we need to give them at least one extra stone.)

Submissions are judged against all 116 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TigerRiverCrossing with a public method vector<string> addRocks(vector<string> river, int maxL) · 116 test cases · 2 s / 256 MB per case

Submitting as anonymous