A real world problem revisited

★★★★★

1 votes

Hard

Details

Problem

This problem will be interesting for those who love to play cricket but others shall also try. I have been experiencing this problem since the start of my cricket journey but never had thought that one day I will have some simulation to solve it :D

In a cricket match when it comes to bowling you need to be very clever in case of field placement. Even if you are clever enough but the real challenge comes when field placement needs to be changed just because the batsman is now left handed instead of right handed or vice versa and in many other cases you can think of. So the challenge here is what should be the minimum movement of players in the field so that the required field placement is achieved.

ASSUMPTIONS: Cricket field is a 2D plane where the distance between two points is Manhattan Distance (Refer to the below link in case of clarification) and the bowling takes place from one end only.At the end of each over the bowler goes to the new bowler's place and this movement is assumed negligible.A bowler can be given overs consecutively.Two players may be present at same positions.There will be negligible movement of players for the first over.

https://xlinux.nist.gov/dads/HTML/manhattanDistance.html

INPUT FORMAT

First line contains two space separated integers N,M i.e no of players fielding in the field(including bowler and the wicket keeper) and no of overs respectively.

Each of the next N lines contains field placement of i^thbowler for right handed batsman given by 2*(N-2) integers (excluding i^th bowler and the wicket keeper) i.e x_i1 y_i1 x_i2 y_i2......... x_i(N-2) y_i(N-2)

Each of the next N lines contains field placement of i^thbowler for left handed batsman given by 2*(N-2) integers (excluding i^th bowler and the wicket keeper) i.e x_i1 y_i1 x_i2 y_i2......... x_i(N-2) y_i(N-2)

Each of the next M lines contains two integers A_i,B_i i.e the A_i^thbowler will bowl i^thover and the batsman on strike is of type B_i where B_i=0 means Right handed and B_i=1 means Left Handed

OUTPUT FORMAT

For each over you need to print the minimum movement of players needed to satisfy the required bowler in a newline.

CONSTRAINTS

N=30
1<=M<=10⁶
0<=x_ij,y_ij<=10¹⁰
1<=A_i<=N
0<=B_i<=1

SUBTASK 1 (Real World) (50 Points)

N=11

SUBTASK 2 (God Level) (50 Points)

ORIGNIAL CONSTRAINTS

Problem Setter-Reshab Gupta

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

This input is only for clarification purpose.
There are 4 players playing and it's a 3 overs match.
In the first over ,the field will be set according to the 3^rd bowler preference for the right handed batsman.The movement of players should be assumed negligible for the first over so the answer is 0
After the first over completes the 3^rd bowler will go to the 4^th bowler's position.Now the field will be set according to the 4^th bowler preference for the right handed batsman and the minimum movement of players to do so is 9.
The 3^rd bowler throws 4^th over also but the batsman on strike is left handed,so the minimum movement to do to satisfy him is 12