Roll the bar editorial?

Can anyone provide the editorial for ROLLBAR question of FEB Lunchtime.
Thank you…

1 Like

It’s pending for being posted by the admin

1 Like

Hints:

First, think about the basic problem where you can take only one step in any direction

Solution:
brute force would be costly

better solution would be to use bfs(breadth-first search) from the target cell

same ideas are used for solving this problem.

You should know bfs on grids before solving this problem(Practice similar problems to become familiar - Eg problem: L56LABY Problem - CodeChef)

Short Explanation of Solution:

We can define a point( this is basically the current state to be processed ) as:

struct point{

      int posx, posy ;

      int roll_direction ; // direction of roll (useful only if state = rolled)

      int state ; // standing or rolled over (i've used 0 or 1 respectively)

} ;

Assume you have to reach the cell (gx, gy)

There are 2 states possible at any moment:

  • you are standing on a cell (x, y)
  • you are lying flat on 2 cells

lying flat can be represented using (x,y) and direction arrow(converted to integers) instead of two coordinates
where (x, y) can be one of those cells(this is what i’ve chosen, there may be other ways to represent but i’ve chosen this one)

Initialize all distances to -1, dist[x][y] = -1 for all ( 0 < x < n && 0 < y < m) (other values such as INF can also be chosen)

We implement bfs from the target cell, initializing dist[gx][gy][roll_dir][0] = 0 (i have used 2 different distances for different states) and putting it in bfs queue, and for each point in bfs queue, put in queue the neighbouring cells(think on paper how to represent the neighbours as points) and increase their distance by 1 than previous cell(also check whether they are valid points or not).
You should be familiar with bfs on grid to understand it better

Repeat this process until queue becomes empty

At the end, display the distances

The implementation is a tough part though(atleast for me), have to think a lot carefully before implementing, took a lot of time for me.
There may be better approaches possible, look at codes of high rated coders

my solution code link: CodeChef: Practical coding for everyone

2 Likes

thank you so much @the_batman for help :slight_smile: