Magician of Hamelin(CC023) - Editorial

editorial
,
1

Contest Name:

CODICTION 2.0

PROBLEM LINK:

Problem
Contest

Author: Mradul Rathore
Tester: Murtaza Ali, Nehal Jain, Vishal Rochlani
Editorialist: Mradul Rathore

DIFFICULTY:

MEDIUM

PREREQUISITES:

Queue

PROBLEM:

Find the number of children who got free from Donovan’s magic when he collided for the first time. If there is no collision then print 0.

EXPLANATION:

This problem is similar to the snake game. Consider Donovan as the head of Snake and children as its prey. Each time he hypnotizes one child, a child joins the queue of other hypnotized children, or equivalently, the length of the snake gets incremented by one.

We maintain a queue to keep track of cells on which Donovan and children are currently, and to get the position of the first cell in the queue.

For example, if Donovan visited cells in the order 1->2->3->4 then the content of the queue will be coordinates of the cell (front)1, 2, 3, and 4(rear);

Also, we need to use a “visited” array that we will use to check whether the next cell that we are visiting is occupied or not. This array will be very useful in detecting a collision if any.

Using the “direction” matrix we update the x and y (coordinates of Donovan) according to the path string. Since the opposite parts of the city are connected, we need to handle the cases when Donovan reaches the boundary of the city.

Code 
 if(x == r) x = 0;
 else if(x == -1) x = r-1;
 if(y == c) y = 0;
 else if(y == -1) y = c-1;

Since the direction of Donovan is important for Donovan’s movement, we’ll need to keep track of its direction. We do so by using a “dir” variable and the same “direction” matrix where elements at index 0 => when S is encountered.

Index 1 => when R is encountered.

Index 2 => when L is encountered.

We update “dir” as follows:

Code 
if(s[i] == 'S') {
            x += dirc[dir][0][0]; 
            y += dirc[dir][0][1];
}
else if(s[i] == 'R') {
            x += dirc[dir][1][0];
            y += dirc[dir][1][1];
            dir = (dir + 1) % 4;
}
else {
            x += dirc[dir][2][0];
            y += dirc[dir][2][1];
            dir = (4 + (dir - 1)) % 4;
}

You can check for its correctness by considering different cases.

The collision occurs when Donovan visits an already visited cell and that cell is not the first element of the queue. If it was the first element of the queue, then on moving forward, the child at that cell will move to the next cell, and thereby no collision will occur. We check for this condition using the queue and “visited” array.

The algorithm stops when either we have traversed the whole “path” string or there is a collision.

If there is a collision then we simply need to remove all the cells till the coordinates of the collided cell. And the “size(queue) - 1” will be the number of children who got free from Donovan’s magic.

COMPLEXITY

Time complexity: O(len(path))

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std; 

int dirc[4][3][2] = {{{-1, 0}, {0, 1}, {0, -1}}, {{0, 1}, {1, 0}, {-1, 0}}, 
                {{1, 0}, {0, -1}, {0, 1}}, {{0, -1}, {-1, 0}, {1, 0}}}; 
// up(0), right(1), down(2), left(3) with S(0), R(1), L(2)

int main() {

    int x, y;
    cin>>x>>y;
    
    string s;
    cin>>s;
    
    int r, c;
    cin>>r>>c;
    
    vector<string> g(r);
    
    for(int i = 0; i < r; i++) cin>>g[i];

    vector<vector<bool>> visited(r, vector<bool> (c, false));
    visited[x][y] = true;
    
    queue<vector<int>> q;
    q.push({x, y});
    
    int dir = 1;
    bool game_over = false;
    
    for(int i = 0; i < s.length(); i++) {
        if(s[i] == 'S') {
            x += dirc[dir][0][0]; 
            y += dirc[dir][0][1];
        } else if(s[i] == 'R') {
            x += dirc[dir][1][0];
            y += dirc[dir][1][1];
            dir = (dir + 1) % 4;
        } else {
            x += dirc[dir][2][0];
            y += dirc[dir][2][1];
            dir = (4 + (dir - 1)) % 4;
        } 
        
        if(x == r) x = 0;
        else if(x == -1) x = r-1;
        
        if(y == c) y = 0;
        else if(y == -1) y = c-1;
        
        if(visited[x][y]) {
            if(q.front() == vector<int>({x, y})) q.pop(), q.push({x, y});
            else {
                game_over = true;
                break;
            }
        } else {
            visited[x][y] = true;
            q.push({x, y});
            if(g[x][y] == '*') g[x][y] = '-';
            else {
                auto k = q.front();
                q.pop();
                visited[k[0]][k[1]] = false;
            }
        }
    } 
    
    if(game_over) {
        while(q.front() != vector<int>({x, y})) q.pop();
        cout<<q.size()-1<<'\n';
    } else cout<<0<<'\n';

return 0;
}

Feel free to post your queries in the comment box.

2 Likes