Basic Number Theory Tutorial in Bangla by ইকরাম মাহমুদ

Tutorial Link - progkriya

Love for programming

Number of common divisors of 2 numbers

Problem link: COMDIV - Number of common divisors

For this we need to know
                         CommonDivisor(a,b) = NumberOf Divisor(gcd(a,b)) proof

Find the number of divisors: Time Complexity O(sqrt(n))

tutorial for finding the number of divisors : progkriya

Solution:

Codeforces problem B Two Buttons analysis

Problem Type : BFS , math , greedy , shortest path

Problem link: Two Buttons

this was a very interesting for me.

This problem asks us what is the minimum steps we need to reach from one given number to another given number by multiplying by 2 or  subtracting 1

i have found 2 ways to solve this problem 
       1) using bfs (hard way)
       2) simple mathematics

The hard way:

let us try to analyze 2 given test cases 

1)  4 ->6  minimum steps: 2
2) 10 ->1 minimum steps: 9

let us make a graph using the 2 test cases

UVA 383 - Shipping Routes analysis

Problem Type : Single-Source Shortest Paths On Unweighted Graph  (BFS/DFS)

Its a basic SSSP problem.

"The cost of a shipment is equal to the size of the shipment times the number of shipping legs required times $100."

we just have to do a bfs or dfs from given source if we have't done bfs or dfs on the source before.We can get the cost of the shipment using the above statement using the cost of the destination :D

UVA 260 - Il Gioco dell'X analysis

Problem Type : Finding Connected Components (BFS/DFS)

Let us try to understand the problem

"The game ‘Il Gioco dell’ X’ is played on a N by N board (N ≥ 2). The object of both players, say Black and White, is to join opposite sides of the board by placing in turn their pawns on the board in such a way that a path is made from one side to the other by adjacent (neighboring) pawns of their own color."

Though the statement is not very clear how Black and White will win but we can get the idea from the given picture

Sifat Shishir's Blog: UVA 11254 : Consecutive Integers

Sifat Shishir's Blog: UVA 11254 : Consecutive Integers: Prob link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=22...

Another thing on Quora

Depth-first search Implementation

1 thing i always remember about dfs is "Using dfs We go to the depth of a node and then we come back"

I learned dfs from my friend and from this blog shafaetsplanet . In shafaetsplanet the algorithm is explained very easily.


Algorithm :


Basic DFS Traversal of a Graph:


Here starting node is 0.

Some good beginner problems

IMPLEMENTATION:

01.Beautiful Year (L1)
Solution

02.Queue at the School (L1)
Solution

03.Lights Out (L1)
Solution

04.Arrival of the General (L1)
Solution

05.Twins (L1)
Solution

06.Effective Approach (L2)
Solution

07.Even Odds (L2)
Solution

08. Airport (L2)
Solution

EASY GREEDY:

01.Dragons (L2)
Solution

Problems on Data structures

Some Problems on Data structures

Disjoint set:

459 - Graph Connectivity (UVA)
Solution

793 - Network Connections (UVA)

Solution

10583 - Ubiquitous Religions (UVA)
Solution

10685 - Nature (UVA)
Solution

11503 - Virtual Friends (UVA)

Solution

Some Graph Problems

Here are some Graph problems i have solved over time 

Flood Fill/Finding Connected Components using dfs/bfs:

784 - Maze Exploration (UVA)

Solution

10946 - You want what filled? (UVA)
Solution

572 - Oil Deposits (UVA)
Solution

439 - Knight Moves (UVA)
Solution

10653 - Bombs! NO they are Mines!! (UVA)
Solution

352 - The Seasonal War (UVA)
Solution

871 - Counting Cells in a Blob (UVA)
Solution

10336 - Rank the Languages (UVA)
Solution

260 - Il Gioco dell'X (UVA)
Solution

785 - Grid Colouring

Solution

BFS:

336 - A Node Too Far (UVA)
Solution

11730 - Number Transformation (UVA)
Solution

762 - We Ship Cheap (UVA)
Solution

10009 - All Roads Lead Where? (UVA)
Solution

11463 - Commandos (UVA)
Solution

DFS:

615 - Is It A Tree? (UVA)
Solution

11504 - Dominos 2 (UVA)
Solution

280 - Vertex (UVA)
Solution

10452 - Marcus (UVA)
Solution

11770 - Lighting Away (UVA)
Solution

PT07Y - Is it a tree (SPOJ)
Solution

Tropological sort:

10305 - Ordering Tasks (UVA)
Solution

11060 - Beverages (UVA)
Solution

Strongly connected component:

247 - Calling Circles (UVA)
Solution

CAPCITY - Capital City (SPOJ)
Solution

11504 - Dominos
Solution

11838 - Come and Go
Solution

Graph coloring:

A Bug’s Life (SPOJ)
Solution

10004 - Bicoloring
Solution

MST:

908 - Re-connecting Computer Sites
Solution

11631 - Dark roads
Solution

11747 - Heavy Cycle Edges
Solution

10034 - Freckles
Solution

11733 - Airports
Solution

1174 - IP-TV
Solution

11710 - Expensive subway
Solution

11857 - Driving Range
Solution

10048 - Audiophobia (mst+bfs)
Solution

544 - Heavy Cargo
Solution

10099 - Tourist Guide
Solution

10147 - Highways
Solution

10397 - Connect the Campus
Solution

10600 - ACM Contest and Blackout
Solution

11228 - Transportation system.
Solution

11733 - Airports
Solution

11857 - Driving Range

Solution

Dijkstra:

10986 - Sending email
Solution

929 - Number Maze
Solution

bellman ford:

558 - Wormholes
Solution