Pintu and Fruits CHPINTU

Original Problem Link: CHPINTU

Solution Author Name: Hritik Seth linkedin link

Prequisutes: Basics of array/list indexing and mathematics.

Explaination: Well the problem was quite easy.It only check your basics in any programming language. It was based on the concept of count array/list. We only have to count the minimum number of basket cost required for the fruits. So I firstly subtracted 1 from every type of fruit and stored it in a list so that basket of type 0 can be included while calculating then I store total cost of the corresponding basket at the corresponding index. After the cost is stored (index being the basket type), I finally find the the basket type with minimal cost in the list and printed it.

XOR Engine

Original Problem Link: ENGXOR

Solution Author Name: Himanshu Shukla

Prequisutes: Observation

Explaination: Observation
1. (EVEN number of bits NUMBER) XOR (ODD number of bits NUMBER) = (ODD number of bits NUMBER)
2. (ODD number of bits NUMBER) XOR (ODD number of bits NUMBER) = (EVEN number of bits NUMBER)
3. (EVEN number of bits NUMBER) XOR (EVEN number of bits NUMBER) = (EVEN number of bits NUMBER)

Get initial count of even bit numbers(x) and odd bit numbers(y) present in array.
When a query P comes check whether P is even bit number or odd bit number, if P is even bit number print x and y else print y and x.

ADA BISHOP 2

Original Problem Link: ADASHOP2

Solution Author Name: Himanshu Shukla

Prequisutes: Basic Graph Traversal Algorithm, Observation

Explaination: Well I have seen many programmers hardcoding solution. Solution I am going to present is quite general and works even with N X N chessboard with some modification to solution presented below. Solution presented below is based on graph traversal algorithm called DFS(Depth First Search).

Construct a graph which is not going to change with testcases, (u,v) where u = (a,b), v = (c,d) is an undirected edge in graph if u and v represents black cell and bishop can move from u to v and from v to u beforehand. This can be constructed in O(N X N) time for general N X N chessboard.
Whenever a query src = (r,c) comes keep a counter rem(here initially rem = 32), perform a DFS considering src as root and keep on pushing cells in ans array till rem becomes 0.
Finally print the ans array.
Main observation here is number of cell visited will not become greater than 64 each cell is visited atmost twice and number of black cell is 32 so number of cell visited is always less than equal to 64 (loose upper bound).

Lasers Everywhere LAZER

Original Problem Link: LAZER

Solution Author Name: Mohammed Shahraaz Hussain

Prequisutes: Range Query Tree(Segment Tree or Fenwick Tree), Line Sweep Algorithm intuition

Explaination: We can imagine Problem to be some set of adjacent towers and wires connecting adjacent towers. Each tower has different height.

When ever a query is asked you can assume that a light is to be shot from x1 to x2 at height h. Which is pretty straight forward.
While processing a query what must be done? here we must be quite strategic. here we need to process the queries offline.

now we need to think of lines as some structure. for each line we define a start point, end point. Starting point is the point on with higher y cordinate and end is the one with lower y cordinate. if a line is horizontal we consider the left point as start point and right point as end point.

Guess where we are headed! Split the line. Start point and end Point.

Now we need to define some points as events points. These is where we do some computaion for our queries. here start point, end point and queries are the event points.

Now decide how to process the event points. In the mean while we will define our event point staructre. First Observation We need to process the event points from Top to Bottom by height. If the events have same height we need to process start points first, then queries and finally the end points.

When a start point is detected we add 1 at the left idx of the line. When a end point is detected we substract 1 from left idx of the line. when a query is detected we do a range query on the left idx and right idx-1 of the query(Finally store then by their query idx). If range query is done slowly we will fail. So we need to use Segment Tree or Fenwick Tree(Link to refernce in the roadmap section).

Chef and DAG

Original Problem Link: CHEFDAG

Solution Author Name: Written By: Himanshu Shukla Credit: William Lin

Prequisutes: Minimum Path Cover on DAG, Maximum Bipartite Matching, Maximum Flow

Resources

Link : Minimum Path Cover on DAG

Solution

Original Commented Code: tmwilliamlin's Solution