Find Kth Element In Ascending Order And Delete It, Perform Q-Queries

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

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

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

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

Lazy Propagation Segment Tree (Codechef : FlipCoin Problem)

Ramesh Chandra

2-D Sub Matrix Sum Query With Point Update Using BIT

Ramesh Chandra

3-D Sub Matrix Sum Query With Point Update Using BIT