You are given N numbers and Q queries. There is only one query type, you have to print the Kth number when all the remaining numbers are arranged in ascending order. You have to remove that number from the list after a query.
Prerequisite
Balanced BST
Solution
Basic Idea is in-order traversal of BST gives us sorted array.
So we will traverse Balanced BST in in-order fashion and print the number and mark as deleted(put 0 at that place) after printing.
Now we just need to traverse the tree in in-order traversal based on Kth number and how many elements current node contains in left and right subtree.
what all information is required to store in BST Node.
* value : actual element value
* left_nodes : number of nodes in left
* right_nodes : number of nodes in right
for more clarification, See the code.
If anything is not clear in post, you can ask [me]
Problem Link
Ramesh Chandra
Tuesday, 28 March 2017
Find Kth Element In Ascending Order And Delete It, Perform Q-Queries
Sunday, 5 March 2017
Younger Brother[CODECHEF] : Grundy Number
GRUNDY NUMBER
The game consists of C boards. Each board i is a grid of dimension ni x mi.
Rules of the game:
- A coin is placed at (1,1) on every board initially.
- Each one takes a turn alternatively.
- In one turn, a player can choose any one board and move a coin from a cell (i,j) to one of the following cells:
(i+1,j) OR (i+2,j) OR (i,j+1) OR (i,j+2) OR (i+1,j+1) OR (i+2,j+2).
- A coin cannot be moved out of the board at any point during the game.
- A coin cannot be moved once it reaches the cell (n,m) where n and m are the dimensions of the board of that coin.
- A player MUST make one valid move.
Problem Link
faster Solution
Ramesh Chandra
Friday, 24 February 2017
Second Min And Second Max With Update Using Segment Tree
SEGMENT TREE
To perform following operation(<10^5) on given array(<10^5) :
U I V - Update the value present at I with value V
A L R - Find the sum between range L and R
M L R - Find the maximum number between L and R
m L R - Find the minimum number between L and R
S L R - Find second maximum value in between L and R
s L R - Find second mimimum value in between L and R
Ramesh Chandra
Tuesday, 21 February 2017
Maximum Coin Sum Set Of Non Adjacent Vertices In Tree
DYNAMIC PROGRAMMING
Given a tree T of N nodes, where each node i has Ci coins attached with it. You have to choose a subset of nodes such that no two adjacent nodes(i.e. nodes connected directly by an edge) are chosen and sum of coins attached with nodes in chosen subset is maximum.
Ramesh Chandra