PROBLEM LINK:
DIFFICULTY:
Easy
PREREQUISITES:
Double-ended Queue
PROBLEM:
There was a mischievous magician named Donovan who was known for his mysterious music. He has the ability to hypnotize anyone with his music and make them follow him.
One day he decided to annoy people of the Hamelin city by hypnotizing their children. Any child who comes in contact with Donovan gets hypnotized and starts following him along with other already hypnotized children. All children move in line, following Donovan’s steps, with the recently hypnotized child being the first child in the line. Refer to Sample Inputs for better understanding.
Afraid of this mischievous magician, the people of Hamelin went to Moofre, a wise and kind magician. Seeing people’s problems, he used his magic to prevent Donovan from escaping Hamelin. He magically connected the opposite parts of the city. So, if Donovan tried to cross the city border then he along with hypnotized children will magically reappear on the other side of the city. And also, Moofre figured out the weakness of Donovan magic that if while playing the music he collides with a hypnotized child, all the children between Donovan and that child will come to consciousness.
The city is represented by an m*n grid. The asterisks(∗) represent children’s location. Donovan’s starting position is given to you and assumes he is facing to the right direction and no child was hypnotized initially. He can move straight, left, or right one unit at a time. If he comes across a ∗
then the child at that location gets hypnotized and starts following him with other hypnotized children behind.
Note: No child is present at Donovan’s starting position.
You have been given the path, taken by Donovan in the form of a string.
For example: LRSLRSLRSLRS
Here,
L means move left
R means move right
S means move straight
You need to find out the number of children who got free from Donovan’s magic when he collided for the first time. If there is no collision then 0 would be the number of children.
QUICK EXPLANATION:
We can maintain a double-ended queue in which we will keep the order of occupied positions. Use a data structure which allows insertion, deletion and searching to check whether we hit a child that is following us. Retrieve the order by popping elements from the queue.
EXPLANATION:
This problem is actually just like developing a Nokia snake game, except that you don’t take the input interactively, but rather as a string. First let us split the problem in two major case groups:
- Magician hits a child at some move in the string
- Magician hits no child after finishing the journey
Let us handle the first case and if it doesn’t occur, for latter we can simply print 0.
Consider every character of string as a point in time. This means that at every time unit, we should move our magician one unit to some adjacent field. We can keep two variables x_{dir} and y_{dir} which will tell us how the magician should move at each step. Initially let x_{dir} = 0 and y_{dir} = 1, this means we are moving to the right.
In cases of S_i being 'L' or 'R', where S_i denotes the i_{th} character of input string, we need to change the direction. This can be handled by a bunch of if statements, but there’s a much simpler way to handle it, which I will give you.
We can store moving directions as an array of 4 states, each describing movement in four directions - right, down, left, and up. Thus, when we face sumbol 'R', we can simply move one position to the right in the direcion array, or left in the dace of 'L'. Here’s what I mean by that:
x_{dir} = [0, -1, 0, 1]
y_{dir} = [1, 0, -1, 0]
So at each 'R' we encounter, we set current direction index dir = (dir + 1) mod 4.
Similarly, at each 'L' we set current direction index dir = ((dir - 1) + 4) mod 4
Now with this out of our way, let’s look at how we can utilize double-ended queue to handle picking up children. We know that double-ended queue allows us to manipulate both the front and the end of queue, so we can store the last child at the end of our queue and the magician at its front, with other children in between.
This is useful because at every move i_{th} child takes the position of the {(i-1)}_{th} child for every 1 < i \leq length, and 1_{st} child taking the position of magician. Of course, magician moves to the newly encountered {(x, y)}.
This allows us to handle position updates without traversing all the kids’ positions, but rather just inserting and erasing elements at front/back.
Here are the only two cases we need to handle:
- Magician encounters a child at (x, y) \implies push the new position to the front, this is because every child will take the position of the person in front of it, including the new child which occupies the last position in the current queue in the next step, the only differnece is in the position of the magician
- Magician does not encounter a child at (x, y) \implies push the new position to the front and pop the last position from the back, everyone takes a step forward, which is the same as removing the last child and adding the new position to the front (similar to the other case).
There is just one case where moving to the new position is impossible and that is when it will be occupied by one of our children that follow us in the next step. This little detail seems like it requires a while lot of modifying to get right, but actually a data structure which allows insertion, deletion and searching is all we need. This could be a balanced binary tree for example, but there’s a simple solution of using set, which I opted for.
All we need to do is maintain a set of occupied fileds and dynamically update them at every move. It’s same as adding\removing positions to the queue, except that we perform it on our set of positions.
So how do we actually handle collisions? All we need to do is after every move, check whether the new position matches one of currently occupied squares, which translates to finding whether a position exists in our structure or not. If it’s the latter, we don’t do anything, but in the other case we need to print our answer.
Since queue stores our elements in correct order from front to back, we can pop the elements from the front and count the number of children until front becomes the collided position. That’s it! Simple, right? 
SOLUTIONS:
Alternate Editorialist's Solution:
#include <bits/stdc++.h>
using namespace std;
int dir;
int x, y;
string s;
int n, m;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
deque<pair<int, int>> dq;
string ar[2005];
set<pair<int, int>> st;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> x >> y;
cin >> s;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> ar[i];
}
dq.push_front(make_pair(x, y));
st.insert(make_pair(x, y));
for (int i = 0; i < s.length(); i++) {
if (s[i] == 'L') dir--;
if (s[i] == 'R') dir++;
dir += 4; dir %= 4;
x += dx[dir];
y += dy[dir];
x %= n; y %= m;
if (ar[x][y] == '*') {
if (st.find(make_pair(x, y)) != st.end()) {
int res = 0;
while (dq.front() != make_pair(x, y)) {
res++;
dq.pop_front();
}
cout << res << '\n';
return 0;
}
dq.push_front(make_pair(x, y));
st.insert(make_pair(x, y));
} else {
st.erase(dq.back());
dq.pop_back();
if (st.find(make_pair(x, y)) != st.end()) {
int res = 0;
while (dq.front() != make_pair(x, y)) {
res++;
dq.pop_front();
}
cout << res << '\n';
return 0;
}
dq.push_front(make_pair(x, y));
st.insert(make_pair(x, y));
}
}
cout << 0 << '\n';
return 0;
}