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)

Basic Dp On Tree

   

 Problem: 

    Given a tree with n nodes we have to    find the number of nodes under each sub-tree

 The root is 1.

 Solution:

  

  we can solve this with dynamic programming

       

1. Determine the bottom nodes of the tree (with no children)
2. Assign "weight" 1 to each of the bottom nodes
3. Build your way up the tree calculating the "weight" of each node (for example a node with 2 children has "weight" 3)
4. That's your answer....

    Related Problem:

     Even-Tree

                Cut The Tree

Degree Of Node

    

    The degree of a vertex V in a graph is defined as the number of graph edges that touches the vertex V.

     

    In a graph,

        the total sum of all degree of

       vertex = 2 * E    [E = number of edge]

    For a Tree,

        the total sum of all degree of

       vertex = 2 * E

              = 2 * (n-1)

 So if the sum of all degree of 

  vertex = 2*(n-1) then it must be a tree

    Related Problem:

         Monk at the Graph Factory

    

Counting Triangles Problem

1307 - Counting Triangles

                এ প্রবলেম এ আমাদের কাছে কিছু লাঠির length দিয়ে দিয়েছে। এ length দিয়ে আমারা কত ভাবে একটি valid triangle বানাতে পারি তা বের করতে হবে। একটি valid triangle মানে তার ক্ষেত্রফল ০ এর সমান বা কম হতে পারে না।

                আমরা জানি triangle একটি তখনি valid  হয় যখন তার ক্ষুদ্রতম দুই বাহুর সমষ্টি বিহতম বাহুরচে বড় হয়।

                একটি triangle এর তিন বাহুর যদি a,b,c হয় ও c > a এবং c > v হয়।

                তার মানে triangle  valid হবে যদি a + b > c হয়। এর জন্য আমারা বাহু গুল কে length অনুজাই sort করে compare করতে পারি।


                

oshomapto

Greatest Common Divisor

Greatest common divisor:
       দুটি সংখ্যা a ও b যদি non-zero হয় তাহলে তাদের gcd হল largest common divisor a ও b হয়।যদি a এবং b non-zero হয় তাহলে,
                      1 ≤ gcd(a, b) ≤ min(|a|)


Gcd function এর কিছু elementary property:

gcd(a, 0)= |a|

gcd(a, ka)=|a|

gcd(0, 0)=0

gcd(an, bn)=n*gcd(a, b) where n ≥ 0

যদি n|ab এবং gcd(a, n)= 1 তাহলে n|b

যদি gcd(a, p) = 1 এবং gcd(b, p) = 1 হয় তাহলে gcd(ab, p) = 1

Euclidian algorithm:
    Euclid algorithm এর যে principal এর উপর কাজ করে তাহলো

       Gcd(a, b) = gcd (b, a%b)

         Base case হল: gcd(a, 0) = a

Algorithm implementation:

আমরা এটি প্রমান করতে পারি। কিন্তু এটি প্রমান করার আগে প্রথমে division theorem সম্পর্কে idea নিতে হবে।

Division theorem:
          যদি a একটি পূর্ণ সংখ্যা ও b একটি ধনাতম্ক পূর্ণ সংখ্যা হয় তাহলে আমরা এমন ২টি unique পূর্ণ সংখ্যা পাব k এবং r যেখানে,
                    a = k*b+r
            যেখানে k = a/b = ভাগফল
                       r = a mod b
     আমরা b|a লিখতে পারি যদি এবং কেবল যদি a mod b = 0 হয়।

Euclid algorithm এর প্রমানঃ

   ধরি, g = gcd(a, b)

         a = k*b+r [k হল k=a/b অধনাত্মক সংখ্যা ও r হল ভাগশেষ।]
যেহেতু g, a কে ভাগ করতে পারে তার মানে g, k*b+r নিঃশেষে ভাগ করতে পারে।

যেহেতু g, b কে নিঃশেষে ভাগ করতে পারে g, k*b কেও নিঃশেষে ভাগ করতে পারে।তার ফলে g r কেও ভাগ করতে পারে, তা না হলে k*b+r, b দ্বারা ভাগ করা যাবে না।

তাহলে আমরা প্রমান করলাম যে, g, b এবং r কে নিঃশেষে ভাগ করতে পারে।

          এখন ধরি,
             g’ = gcd(b, r)

     যেহেতু g’, b ও r উভয় কে নিঃশেষে ভাগ করতে পারে ত্রার মানে এটি k*b+r কে নিঃশেষে ভাগ করতে পারবে।

    তার মানে, g’,a কে নিঃশেষে ভাগ করতে পারবে।

আমরা contradiction এর মাধ্যমে প্রমান করতে 
             পারি যে, g = g’

অর্থাৎ gcd(a, b)= gcd(b, r) = gcd(b, a%b)


 কিছু Property of GCD function:


1) Communicative Law : GCD(a,b) = GCD(b,a)

2) Associative Law : GCD(a,GCD(b,c)) = GCD(GCD(a,b),c) 

3)  GCD(a,b,c) = GCD(GCD(a,b),c) 


Things to remember:

1) GCD(4,-2) returns -2 but correct answer should be 2 . To get the correct value we need to send the absolute value of the inputs to the algorithm or use the absolute value of the return value.

.2) GCD(0,0)=0 but the algo will try to do 0%0 for that we might 

get RTE. We need to take care of this manually.

Common Divisors

Common divisor: 

         যদি  d, a এর একটি divisor হয় এবং d যদি b এর ও একটি divisor হয় তাহলে আমরা বলতে পারি যে d হল a এবং b এর common divisor।

         6 এর divisor হল 1, 2, 3, 6
         12 এর divisor হল 1, 2, 3, 4, 6, 12

         Common divisor (6, 12) = 1, 2, 3, 6

কিছু দরকারি তথ্য common divisor এরঃ

        1)   d | a এবং d | b implies  d | (a+b) এবং d | (a-b)
                         
        আরও সাধারনভাবে বলা যায় যে, d | a এবং d | b implies d | (ax+by) [সকল x এবং y এর জন্য] এবং যদি  a|b তবে,|a|≤|b| অথবা b=0

        2)  Number of Common Divisor(a, b) = Number Of Divisor (gcd(a, b))

             প্রমানঃ

             GCD(24, 30) = 6
             অর্থাৎ 24 এবং 30 এর মধ্যে এমন কোনো common divisor      নেই যা 6 এর চেয়ে বড়। 6 এর divisor হল 1, 2, 3, and 6।  24, 30     এর জন্য 6 এর চেয়ে ছোট বা সমান কোনো সংখ্যা নেই যা 24, 30     কে ভাগ করতে পারে এবং{1, 2, 3, 6} এর সেটে এ পরে না।

Problem : COMDIV - Number of common divisors

Editorial : Editorial Link

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

LINK

List of algorithmic problems uva

Topological Sorts using indegree (Kahn's algorithm)

Tutorial - Kahn's Algorithm for Topological Sorting
             
                Shafaetsplanet

                Tutorial


ALGORITHM:


The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges, asymptotically, ${\displaystyle O(\left|{V}\right|+\left|{E}\right|)}$.

Implementation: