Find Kth Element which has at least one divisor < 50

To find the k'th number whose at least one prime divisor is less than 50.

Prerequisite
Inclusion-Exclusion Principle

Solution
we just need to count how many number having at least one prime divisor less than 50.

We are trying to solve this question for smaller constraints
To find the k'th number who has at least one prime divisor is less than 5.
only prime numbers : {2,3}

counting divisor till X
count_div = X/2 + X/3 - X/(2*3)

So basically we need to add divisor of each element and subtract divisor of both once as they are added twice(once with 2 and once with 3)

So this Idea can be extended to any number of primes using Inclusion-Exclusion Principle.

P = p1*p2*....*pn

if n is odd
count_div += X/P
else
count_div -= X/P

For more clarification see the code.


Problem Link




Ramesh Chandra

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