Bishops

Problem Statement:

                        আমাদের একটি বিশপ এর current position দিয়ে দেয়া হয়েছে (r1,c1)। এবং আমাদের destination position (r2,c2) ও দেয়া হয়েছে। বিশপটি একটি ইনফিনিট সাইজ chess board এ আসে।আমাদের বলতে হবে বিশপটি তার destination এ পোষাইতে পাড়বে কি না? আর পোষাইতে পাড়লে মিনিমাম কত move এ পোষাইতে পাড়বে।

Solution:

এ প্রব্লেম আমি বহুদিন আগে দেখেছি LOJ এ। কিন্তু অত দিন কোন solution মাথায় আসে নাই।

আজকে same প্রবলেম পাইলাম সিএস আচাডেমীতে। 

লাস্ট দাবা খেলেছি প্রায় ৬ মাস আগে। কিন্তু আজকে প্রব্লেমটা পরতেগিয়ে মাথায় একটা কথা আসল।

কোন বিশপ যদি কাল ঘরে থাকে তাহলে সে কখন সাদায় জেতে পারে না আবার বিশপ যদি সাদা ঘরে থাকে তাহলে সে কখন কাল জেতে পারে না।

এটা যখই মাথায় আসল তখনি বুঝে গেলাম destination এ পোষাইতে পাড়বে কি না তার solution পেয়ে গেসি।

আমি destination এ পোষাইতে পাড়ব যদি same color  হয় current position ও destination position।

এখন এটা check কিভাবে করব?

একটা ২ *৩ board আঁকলাম।

এখনে লক্ষ করলে দেখা যায় যে কোন cell এর r%2==c%2 হলে cellটি  white cell হবে। তা না হলে black cell হবে। 

আমরা পোষাইতে পাড়বে কি না তা পেয়ে গেসি। কিন্তু minimum move আমাদের লাগবে।

তখন আমি একটা ছবি আঁকলাম।

জিনিশটা লক্ষ করার মত হল আমরা যে রঙ এর ঘরে আছি বোর্ডে সেই রঙ এর অন্য কোন ঘর যেতে মাক্সিমাম ২টা move লাগবে। আর ঘরটি current cell er diagonal যদি হয় তাহলে আমরা ১ move এ যেতে পারি।

current cell (3,2) , destination cell (1,4) এ ২ cell diagonal তা হাতে একে দেখলেই বুঝা যায়। যেহেতু diagonal cell তাই ১ টা move চলে যেতে পারব।

current cell (3,2) , destination cell (3,4) এ ২ cell diagonal না। আমরা একটা move দিয়ে (2,3) cell এ চলে যেতে পারব , আর আরেকটা মভে দিয়ে destination cell (3,4) এ চলে যেতে পারব। সব non-diagonal same color cell এ আমরা একই ভাবে ২টা move এ পোষাইতে পারব।

এটাই আমাদের solution :v :v :v ।

এ question পরেছিলাম ১-১.৫ বছর আগে। এ ৩ লাইন এর observation আস্তে লাগে গেছে ১- ১.৫ বছর। জীবন বরই সুন্দর  :D ।

DP & Recursion Lower Bound

DON'T KNOW:
Longest Run on a Snowboard
Wedding shopping       [DONE]
Cutting Sticks         [FAILED]
Unidirectional TSP
Getting in Line       [FAILED]
Distinct Subsequences
Longest Palindrome   [DONE]
Collecting Beepers
Optimal Array Multiplication Sequence
Maximum Sum
The Twin Towers
23 out of 5
Take the Land
Stacking Boxes
History Grading
Strategic Defense Initiative
Largest Submatrix

Non Classical (The Easier Ones):
Homer Simpson
How do you add? [DONE]

0-1 Knapsack (Subset Sum):
10819 - Trouble of 13-Dots [DONE]
990 - Diving for Gold
10261 - Ferry Loading
11003 - Boxes

Coin Change (CC):
166 - Making Change
11517 - Exact Change
10313 - Pay the Price
10306 - e-Coins

Longest Increasing Sub-sequence (LIS):
111 - History Grading
10131 - Is Bigger Smarter?
Testing the CATCHER
481 - What Goes Up
497 - Strategic Defense Initiative
10534 - Wavio Sequence
437 - The Tower of Babylon

Longest Common Sub-sequence (LCS):
Longest Common Sub-sequence
Compromise
Vacation

Bitmask DP:
(LOJ) Marriage Ceremonies (bitmask dp)
Free Candies (bitmask dp)
Forming Quiz Teams

Basic recursion:
524 - Prime Ring Problem [DONE]
750 - 8 Queens Chess Problem
729 - The Hamming Distance Problem
167 - The Sultan's Successors
574 - Sum It Up [DONE]
10098 - Generating Fast
10063 - Knuth's Permutation
193 - Graph Coloring

Count all numbers up to A that have sum of digits equal to S

1 <= A < 10^15
1 <= S <= 135
আমরা যদি A পর্যন্ত সকল সংখ্যা generate করি এবং sum এর সমান কিনা তা check করি তাহলেই আমরা আমাদের answer পেয়ে যাব।

000

001

.

.

188

189

.

.

244

245

.

.

257

258

আমাদের কে প্রথমে জানতে হবে ডিজিট সংখ্যা কয়টি। এখানে আমরা ৩ ডিজিট এর সংখ্যা ধরেছি A।

আমরা ৩ ডিজিট এর সকল সংখ্যা generate করতে পারব। কিন্তু A এর উপরের সংখ্যা generate করে আমাদের কোন লাভ হবে না। তাই A পর্যন্ত limit দিয়ে  ৩ ডিজিট এর সংখ্যা generate করব।

আমরা আগেই n ডিজিট এর সকল সংখ্যা কিভাবে generate করা যায় তা দেখেছি এখানে।

এখন আমরা দেখবো A পর্যন্ত limit কিভাবে সেট করা যায়।

আমরা একটা recursive function লেখতে পারি। যার প্যারামিটার হবে 3ta  current_digit_no  ,sum_left , limit ।

আমরা এভাবে চিন্তা করতে পারি A = 2(0 তম ডিজিট ) 5 (1 তম ডিজিট) 6 (2 তম ডিজিট) 8 (3  তম ডিজিট)।

function er limit parameter আমাদের বলবে আমরা যে ডিজিট এ আসছি তার limit পর্যন্ত নিতে পারব না সব সংখ্যা নিতে পারব।

০ তম ডিজিট এর জন্য আমরা highest ২ পর্যন্ত generate করতে পারব, আমরা যদি ০ তম ডিজিট এ ২ নিয়ে আগাই তাহলে ১ তম ডিজিট এ ৫ পর্যন্ত genetare করতে পারব, আবার আমরা যদি ০ তম ডিজিট এ ০/১ নিয়ে আগাই তাহলে ১ তম ডিজিট এ ০-৯ পর্যন্ত  সব গুল ডিজিট নিয়ে আগাইতে পারব। পরের ডিজিট এর জন্য same কাজ হবে।

আমরা limit এর ২টা value ঠিক করব।

যখন limit == 0 তখন প্রতিবার ০ - ৯ এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব আর limit 0 পাথাব।

আর যখন limit == 1 তখন ঐ ডিজিট এর highest_limit বের করব। প্রতিবার ০ ঠেকে  highest_limit এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব। সংখ্যাটা highest_limit এর চে ছোট হলে limit = 0 পাঠাব আর highest_limit এর সমান হলে limit = 1 পাঠাব।

BaseCase:

যদি current_digit_no যদি n হয়ে যায় আর sum_left ০ হয়ে যায় তার মানে আমরা এমন একটা n ডিজিট বিশিষ্ট সংখ্যা পায়ে গেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান। তাই আমরা ১ return করব।

যদি current_digit_no যদি n হয়ে যায় আর sum_left ০ না হয় তার মানে আমরা যে সংখ্যা generate করেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান না। তাই আমরা ০ return করব।

dynamic programming:

function টার recursive tree আঁকলে দেখবো যে এখানে overlapping subproblem পাওয়া যাবে। তাই যদি আমরা memorization করতে পারি। 

UseFull Links:

• Count of numbers between A and B (inclusive) that have sum of digits equal to S StackOverFlow
• Counting problems from A to B (CodeForces)

Problem: 

• Sum of Digits

Given n & sum find all the n digit numbers with sum of digit as sum with no leading zero

1 <= n <=20
1<= sum <= 500000

n টা ডিজিট এর প্রতিটায় ০ - ৯ ১ বার বসিয়ে আমরা মোট n^10 টা সংখ্যা generate করতে পারি। কিন্তু আমাদের বলা হয়েছে যে generate করা সংখ্যাটার প্রথম ডিজিট ০ হতে পারবে না। তাহলে আমরা প্রথম ডিজিটটাকে আলাদা ভাবে handle করব।

আমরা একটা recursive function লেখতে পারি। যার প্যারামিটার হবে n এর কত গুল ডিজিট বাকি আর আমার sum কত টুকু বাকি।

আমরা প্রতিবার ০ - ৯ এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব।

BaseCase:

যদি num_of_digit_left যদি ০ হয়ে যায় আর sum_left ০ হয়ে যায় তার মানে আমরা এমন একটা n ডিজিট বিশিষ্ট সংখ্যা পায়ে গেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান। তাই আমরা ১ return করব।

যদি num_of_digit_left যদি ০ হয়ে যায় আর sum_left ০ না হয় তার মানে আমরা যে সংখ্যা generate করেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান না। তাই আমরা ০ return করব।

প্রথম ডিজিটটাকে আলাদা ভাবে handle:

যেহেতু প্রথম ডিজিট ০ হতে পারবে না তাই আমরা প্রথম ডিজিটটাতে ০ ছাড়া বাকি ৯ টা  সংখ্যার  সবগুলো সংখ্যা নিয়ে একবার  আগাবো।

dynamic programming:

আমরা যদি n = ৫ আর sum যে কোন সংখ্যা দিয়ে function টার recursive tree আঁকলে দেখবো যে এখানে overlapping subproblem পাওয়া যাবে। তাই যদি আমরা memorization করতে পারি। (20*500000 =  < 10^8 যা ম্যাক্সিমাম কোন  array এর সাইজ)

ToDo List June 2K17

(UVA) Corporative Network (dsu)
(UVA) Fibonacci Sum (don't know)

(UVA)10539 - Almost Prime Numbers (number theory) [DONE]
(UVA) 13153 - Number of Connected Components (number theory + bfs/dfs/dsu) [DONE Finally]

DP:
(UVA) 10943 - How do you add? (Non Classical DP (The Easier Ones) [DONE]
(UVA) Matches (Mediam dp) [DONE]
(UVA) Zeros and Ones (Mediam dp) [DONE]

Bitmask DP:
(LOJ) Marriage Ceremonies (bitmask dp)
(UVA) Free Candies (bitmask dp)

Permutation:
(UVA) 10063 - Knuth's Permutation (permutation)
(UVA) 10098 - Generating Fast (permutation)

DIGIT DP:
(SPOJ) LUCIFER - LUCIFER Number (Digit dp) [DONE]
(SPOJ) RAONE - Ra-One Numbers (Digit dp)
(SPOJ) GONE - G-One Numbers (Digit dp)
(SPOJ) NUMTSN - 369 Numbers (Digit dp)
(SPOJ) LOTGAME - New Lottery Game (Digit dp)
(LOJ) Fast Bit Calculations (Digit dp) [DONE]
(LOJ) Investigation (Digit dp) [DONE]
(LOJ) How Many Zeroes (Digit dp) [DONE]
(LOJ) Palindromic Numbers (Digit dp)

        বাংলায় প্রোগ্রামিং রিসোর্সসমূহ

LINK

List of algorithmic problems uva

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

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

Light OJ 1074 - Extended Traffic

Problem link - 1074 - Extended Traffic

In this problem we have to compute minimum earning from node 1. At first we have to do a dfs to see if destination is reachable from 1.Every node that can be reached with negative earning , all its adjacent nodes can be reached with negative earning too.

If a node if not reachable from 1 or or the earning is less than 3 then we have to print '?' else we have to print ta earning from 1. We can use bellman ford algorithm from this problem as there are negative earnings.

let us analyze some test cases:

1

5

6 7 8 9 10

6

1 2

2 3

3 4

1 5

5 4

4 5

2

4

5

here node 4 (D) can be reached with earning 3 and node 5(E) can be reached with earning 4

Light OJ 1041 - Road Construction

Problem link -  1041 - Road Construction

In this problem we are given m roads with this roads we have to create a mst. If there are n cities and if we can select n-1 edges from  all edges when running mst then we can say we have a solution as we got a tree :-)

For mapping the cities we can use STL map.

Light OJ 1040 - Donation

Problem link - 1040 - Donation

Its a very basic mst problem.

let us try to analyze some test case

2

27 26

1 52