Toph: XORs

Problem link: XORs

Solution:

We will be given some integers. We are asked to output the cumulative xor sum of all possible pair from those integers; where pair (a[i] ^ a[j]) and 1 <= i, j <= n [i, j = index]

Given the array 1 2 2 4 5, we have to perform our operation like below->

For 1, take all possible pairs:

• (1, 2) = 1 ^ 2 = 3
• (1, 2) = 1 ^ 2 = 3
• (1, 4) = 1 ^ 4 = 5
• (1, 5) = 1 ^ 5 = 4

For 2, take all possible pairs:

• (2, 2) = 2 ^ 2 = 0
• (2, 4) = 2 ^ 4 = 6
• (2, 5) = 2 ^ 5 = 7

For 2, take all possible pairs:

• (2, 4) = 2 ^ 4 = 6
• (2, 5) = 2 ^ 5 = 7

For 4, take all possible pairs

• (4, 5) = 4 ^ 5 = 1

So, we get values: 3, 3, 5, 4, 0, 6, 7, 6, 7, 1 and out output would be
3 ^ 3 ^ 5 ^ 4 ^ 0 ^ 6 ^ 7 ^ 6 ^ 7 ^ 1 = 0

So, how can we solve this? If we try to use bruteforce approach, complexity would be so much and we will surely get TLE in the process.

Let's consider the previous array 1 2 2 4 5, here for 1 we have exactly 4 pairs, for 2(first) we have 3 pairs, for 2(second) we have 2 pairs... for 5 we have no pair. Can you see the pattern here? Well let's talk about it, why the number of pair is important for us.

We know, if we xor an integer odd number of times, it becomes 0 (zero) and for even number of times, it becomes the integer itself. For the 4 pairs of 1, we get the following result by xoring all of the pair for 1 like this: (1^2)^(1^2)^(1^4)^(1^5). We can see, as we have xored odd number of one (1), [1 ^ 1 ^ 1 ^ 1]. We can conclude that it will finally be zero (0). So we don't need this in our calculation. What we need is that the xor of (2^2^4^5). Similarly for 2(first) we get 3 pairs, as we are xoring two 2's, and two is even, so we have to xor 2 with the result. So it will look something like this: 2^(2^4^5).
For second 2, we get (4^5).
For 4, we have one pair (zero xor, as zero is even, we need to xor with 4), Finally we get: (4^5).
For 5, we have no pair, so we don't need to do anything.

I hope now you understand why we need the number of pair. We can get the number of pair simply by (n - index_of_the_element). And for each element, we need the cumulative xor of all the element from index+1 to n of that particular index. We can pre calculate the cumulative xor of all the elements in an array. Remember, we need to pre calculate in reverse order for our purpose.

Dev Skill: Another Bigmod Problem

Problem link: Another Bigmod Problem

In this problem, we are given three integers A, B, C; we need to calculate A^B % C.

Solution: We can calculate it by using modular arithmetic. We know

• (a * b) % c = ( (a % c) * (b % c) ) %c 
• (a + b) % c = ( (a % c) + (b % c) ) %c 
• a^b = a * a^(b-1)

So with this we can write this following code to calculate A^B % C

This algorithm is called classical bigmod algorithm. But in this problem, we still have problem. Look at line 9 : x = ( x * x ) % c;

Here, since c can be as large as 10^18, the value of x can be (10^18 - 1 ). When we multiply x with x, it will overflow. For example, try with input a = 10^18 - 1, b = 2, c = 10^18.

So how do we calculate ( x * x ) % c, without overflowing? We use the same divide and conquer approach like above. But this time we will use addition instead of multiplication. It's called bigmultiplication, we will write the function as following:

So finally our full code would look like this:

কম্বিনেশন ( Combination )

কোন বড় গ্রুপ থেকে কিছু সংখ্যক জিনিস নিয়ে ছোট ছোট গ্রুপে ভাগ করাই হল কম্বিনেশন। এখানে পারমুটেশন এর মত অর্ডার এর কোন প্রভাব থাকেনা। যেমনঃ ৩ টি জিনিস থেকে আমরা ২ টি জিনিস নিতে পারি এভাবেঃ
(১, ২), (১,৩), (২,৩) = মোট ৩ ভাবে, এটিই কম্বিনেশন।

অর্থাৎ, n টি জিনিস থেকে r টি জিনিস কতভাবে নিতে পারি সেটিই হল n,k এর কম্বিনেশন। (এখানে k<=n)

বাইনোমিয়াল কো-এফিশিয়েন্ট ( Binomial Coefficient )

বাইনোমিয়াল কোএফিশিয়েন্ট হল অর্ডার বিবেচনা না করে ভিন্ন ভিন্ন সম্ভাবনাকে নেয়া। শুনতে কঠিন লাগলেও ব্যাপারটি আসলে কিছুইনা। আমরা n জিনিস থেকে k জিনিস নিবো, অর্ডার বিবেচনা না করে। এটিকে কতভাবে নেয়া যাবে, এটিই বাইনোমিয়াল কোএফিশিয়েন্ট, অর্থাৎ কম্বিনেশন। 

আমরা কিছু সিরিজ এর এক্সপানশন দেখিঃ

(x + y)⁰ = 1
(x + y)¹ = x + y

(x + y)² = x² + 2xy + y²

(x + y)³ = x³ + 3x²y + 3xy² + y³

(x + y)⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴

এসব সিরিজ কে আমরা এভাবে লিখতে পারি কমন ফর্মেঃ 

আমরা কম্বিনেশন এর জন্য বাইনোমিয়াল কোএফিশিয়েন্ট ব্যবহার করবো, তবে তাকে মনোমিয়াল ফর্মে নিয়ে।
( মনোমিয়াল or monomial হল এমন পলিনোমিয়াল যার শুধুমাত্র একটি টার্ম আছে )। কাজেই আমাদের বাইনোমিয়াল এর রূপ হবে এরকমঃ (1 + x) ⁿ
আমরা এই ফর্মকে এক্সপানশন করলে প্রতি পাওয়ার অনুসারে প্রতি টার্ম এর একটি করে কো-এফিশিয়েন্ট পাবো। আমাদের কাজ হবে ঐ কো-এফিশিয়েন্ট নিয়ে কাজ করা। যেমন আমরা কিছু কো-এফিশিয়েন্ট দেখিঃ

আমরা n = 4 নিয়ে দেখিঃ

(1 + x)⁴ = x⁴ + 4x³ + 6x² + 4x + 1
এখন কো-এফিশিয়েন্টগুলি হবেঃ 1  4  6  4  1
এভাবে পাওয়ার অনুযায়ী এক্সপানশন করতে থাকলে আমরা একটি সুন্দর ত্রিভুজ এর মত ডিজাইন পাই, এটি সবার প্রথম খেয়াল করেছেন প্যাসকেল (Pascal). এজন্য একে প্যাসকেলের ত্রিভুজ বলা হয়। প্যাসকেল এর শর্তানুযায়ী আমরা কম্বিনেশন এভাবে দেখতে পারিঃ

(x + y)ⁿ = (nC0)(xⁿy⁰) + (nC1)(x^n-11y¹) + (nC2)(x^n-22y²) + ... + (nCn)(x⁰yⁿ);  [nCk = combnation of k element from n or n choose k]

আমরা যেহেতু বুঝতে পারলাম বাইনোমিয়াল কো-এফিশিয়েন্ট আসলে কি জিনিস, এখন আমরা কিছু অ্যালগরিদম দেখবো কিভাবে এই বাইনোমিয়াল বের করা যায়ঃ

১। ফ্যাক্টরিয়াল ( Factorial )

আমরা সরাসরি nCk ফর্মুলা ব্যবহার করে nCk বের করতে পারি।
ফর্মুলাঃ nCk  =  [ n! ] / [  k! * (n-k)! ]

কিন্তু এভাবে আমরা সর্বোচ্চ ২১-২২ ফ্যাক্টরিয়াল পর্যন্ত হিসাবে করতে পারবো। এর চেয়ে বেশি আমরা সি++ এ করতে গেলে আমাদের বিগ-ইন্টিজার লাইব্রেরি ব্যবহার করতে হবে। তবে পাইথন এ আমরা হিসাব করতে পারবো এবং এই হিসাবের কমপ্লেক্সিটি হল O(n).
আমরা বড় বড় কম্বিনেশন এর জন্য, nCk mod m এরকম কিছু একটা করে রেজাল্ট একটি নির্দিষ্ট লিমিটের মাঝে রাখতে পারি।

২। রিকার্সন ( Recursion )

nCk বের করার রিকার্সন ফর্মুলা হলঃ nCk (i,k) = nCk (i-1,k-1) + nCk (i-1,k);

আমাদের টাইম এবং স্পেস কমপ্লেক্সিটি হবেঃ O(n*k) for nCk

আমরা একে একটু মডিফাই করে স্পেস কমপ্লেক্সিটি কমিয়ে আনতে পারি। আমরা আগের সারি চেক করবো, কারন আমাদের ঐ সারিগুলো আসলে দরকার হবেনা পরে আর।

৩। কম্বিনেশন এর বিস্তার ( Expansion of Combination )

আমরা জানি, nCk  =  [ n! ] / [  k! * (n-k)! ], অর্থাৎ

               [ n(n-1)(n-2) ... (n-k+1) ] [ (n-k) ... (1) ]

-------------------------------------------------------------------------

                  [ (n-k) ... (1) ] [ k(k-1)(k-2) .... (1) ]

আমরা লব এবং হর থেকে [ (n-k) ... (1) ] টার্ম কেটে ফেলতে পারি, তাহলে আমাদের ফাইনাল টার্ম হবেঃ

 n       (n-1)      (n-2)      (n-k+1)

---  *  ------  *  ------  *  ----------

 k       (k-1)      (k-2)          (1)

আমরা একে এভাবে লিখতে পারিঃ

nCk (n,k) = 1                                             ; if k == 0

                     else  (n/k) * nCk (n-1, k-1)

৪। প্রাইম এর পাওয়ার ( Power of Prime )

আমরা ফ্যাক্টরিয়াল এর কোন প্রাইম এর পাওয়ার বের করতে পারি এভাবেঃ

P_prime = floor[ n/prime ] + floor[ n/prime² ] + .....

এখানে n = factorial, prime = the prime whose power in n-factorial we are calculating
আমরা nCk এর মাঝে p প্রাইম এর পাওয়ার বের করবো এভাবেঃ
power = fact(n, p) - fact(r, p) - fact(n-r, p)
এরপরে আমরা p^power করবো সকল প্রাইম, p এর জন্য যারা n থেকে ছোট।

৫। চাইনিজ রিমেইন্ডার থিওরেম  ( Chinese Remainder Theorem )

যদি আমাদের এরকম বের করতে বলা হয়ঃ nCk mod m where m is not prime , সেক্ষেত্রে আমরা m কে প্রাইম এ ফ্যাক্টরাইজ করার পরে CRT(Chinese Remainder Theorem) ব্যবহার করে মান বের করবো।

Toph: Range Product

Problem link: Range Product

Solution:

Given N and K, we have to find how many integers of K subarray has maximum product which starting index of the subarray is minimum. Also all the integers will be power of 2.
So, at first we will store the power of all the integers in an array. Then we will simply use brute force to check for maximum subarray summation (As we took only power, so we will check for summation here).

Why we took the power? Why we didn't simply multiply? As the multiplication's value will be far greater than long long in C++ data type, we simply can't do that. Also in the problem description there is no mention about modulo operator, so we definitely can't multiply. So we took out the power of 2's and add them to get our maximum muliplication subarray.

40 Mathematics Quotes

গনিতবিদ, দার্শনিকরা গনিত এর বিভিন্ন বিষয় নিজেরা যেভাবে চিন্তা করতেন, সেভাবে তারা গনিত নিয়ে কিছু কথা বলে
গেছেন।এখানে এরকম ৪০ টি উক্তি দেয়া হল, যা টাইম অফ ইউক্লিড ( Time of Euclid ) ্থেকে সংগ্রীহিত।
1. Mathematics is the door and key to the sciences. — Roger Bacon

2. Mathematics – the unshaken Foundation of Sciences, and the plentiful Fountain of Advantage to human affairs.  — Isaac Barrow

3. Mathematics is the art of giving the same name to different things.– Henri Poincaré

4. Mathematics is like checkers in being suitable for the young, not too difficult, amusing, and without peril to the state. — Plato

5. Mathematics is not a careful march down a well-cleared highway, but a journey into a strange wilderness, where the explorers often get lost. Rigour should be a signal to the historian that the maps have been made, and the real explorers have gone elsewhere. –– W. S. A

6. Mathematics is not only real, but it is the only reality. — Martin Gardner

7. Mathematics Is an Edifice, Not a Toolbox

8. Mathematics serves as a handmaiden for the explanation of the quantitative situations in other subjects, such as economics. – H. F. Fehr

9. Mathematics is a hard thing to love. It has the unfortunate habit, like a rude dog, of turning its most unfavourable side towards you when you first make contact with it. — David Whiteland

10. Mathematics makes a nice distinction between the usually synonymous terms “elementary” and “simple”, with “elementary” taken to mean that not very much mathematical knowledge is needed to read the work and “simple” to mean that not very much mathematical ability is needed to understand it. – Julian Havel

11. Mathematics is concerned with “all possible worlds. — D.M. Armstrong

12. But mathematics is the sister, as well as the servant, of the arts and is touched by the same madness and genius. — Marston Morse

13. Mathematics, however, is, as it were, its own explanation; this, although it may seem hard to accept, is nevertheless true, for the recognition that a fact is so is the cause upon which we base the proof. — Girolamo Cardano

14.   . . mathematics is not just another language . . . it is a language plus logic. Mathematics is a tool for reasoning. — Richard Feynman

15. Mathematics is pure language – the language of science. It is unique among languages in its ability to provide precise expression for every thought or concept that can be formulated in its terms. — A Adler.

16. Mathematics compares the most diverse phenomena and discovers the secret analogies that unite them. — Joseph Fourier

17. Mathematics is an independent world created out of pure intelligence.  — William Woods Worth

18. Mathematics is the science which uses easy words for hard ideas. — Edward Kasner and James R. Newman

19. Mathematics is a body of knowledge, but it contains no truths.  — Morris Kline

20. Mathematics is the science which draws necessary conclusions. — Benjamin Pierce

21. Mathematics is the queen of science. — Carl Friedrich Gauss

22. Mathematics is no more computation than typing is literature.– John Allen Paulos

23. Mathematics, as much as music or any other art, is one of the means by which we rise to a complete self-consciousness. The significance of mathematics resides precisely in the fact that it is an art; by informing us of the nature of our own minds it informs us of much that depends on our minds.– John William Navin Sullivan

24. Mathematics is the science of what is clear by itself. — Carl Jacobi

25. Mathematics is a game played according to certain rules with meaningless marks on paper. — David Hilbert

26. Mathematics is as much an aspect of culture as it is a collection of algorithms. —  Carl Boyer

27. Mathematics is the supreme judge; from its decisions there is no appeal.–Tobias Dantzig

28. Mathematics is the language with which God wrote the universe. — Galileo

29. Mathematics is a great motivator for all humans.. Because its career starts with zero and it never end (infinity).

30. Mathematics is often erroneously referred to as the science of common sense. — Newman & Kasner

31. Mathematics is the cheapest science. Unlike physics or chemistry, it does not require any expensive equipment. All one needs for mathematics is a pencil and paper.

32. Mathematics is, as it were, a sensuous logic, and relates to philosophy as do the arts, music, and plastic art to poetry. —  K. Shegel

33. Mathematics is a more powerful instrument of knowledge than any other that has been bequeathed to us by human agency.  — Descartes

34. Mathematics is an art of human understanding. — William Thurston

35. Mathematics is not a contemplative but a creative subject; no one can draw much consolation from it when he has lost the power or the desire to create; and that is apt to happen to a mathematician rather soon. It is a pity, but in that case he does not matter a great deal anyhow, and it would be silly to bother about him. — G.H. Hardy

36. Mathematics is on the artistic side a creation of new rhythms, orders, designs, harmonies, and on the knowledge side, is a systematic study of various rhythms, orders.– William L. Schaaf

37. Mathematics is the science of definiteness, the necessary vocabulary of those who know. — W. J. White

38. Mathematics is not a book confined within a cover and bound between brazen clasps, whose contents it needs only patience to ransack; it is not a mine, whose treasures may take long to reduce into possession, but which fill only a limited number of veins and lodes; it is not a soil, whose fertility can be exhausted by the yield of successive harvests; it is not a continent or an ocean, whose area can be mapped out and its contour defined: it is limitless as that space which it finds too narrow for its aspirations; its possibilities are as infinite as the worlds which are forever crowding in and multiplying upon the astronomer’s gaze. — J. Sylvester

39. Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true. — Bertrand Russell

40. Mathematics is concerned only with the enumeration and comparison of relations. — Carl Friedrich Gauss

Sources: Brainy Quote, Oklahom State U Website, Peter Cameron’s Blog, David Pleacher’s Website, Quote Garden

Cool Magic Square Trick

Today I will talk about a very exciting and cool trick regarding magic square. Once you learn this trick, everybody will definitely acknowledge you as a great math magician ;)
Let's get started then,

First choose a participant. Ask him/her to select a 2 digit number between 22 and 99. Suppose he choses the number 50. Now I will construct a 4x4 magic square with different unique numbers and make him/her believe that I'm the greatest math magician :D
I will now take a pen and paper, draw a 4x4 grid and fill up the grid with some random numbers like this:

Well see, every number is random and unique. If you calculate the sum of every column or every row, even the diagonals, you will see the sum is 50 ! And that is your chosen number. If you take the sum of the numbers of the 4 corners, it will be 50 ( 30+7+4+9 = 50 ).
if you take any 4 square inside the grid, the summation of numbers there will be 50. Don't believe? Check yourself :P

Ok, but the trick doesn't end here actually. If you take any 9 square (3x3) and take the summation of 4 corners for that square, the sum will also be 50 !

Check the red colored tiles and see the magic yourself. Cool , right? And I can do this all
day with different numbers ;)
And even this is also possible:

The red and blue tiles sum is also 50! Well there are 28 different combinations where we can get the desired value.
Okay, let's reveal the trick behind the scene. First think of your magic square like this in your mind:

These four blocks are our magic blocks that will determine the outcome. Remember this by heart and randomly place numbers to other 12 blocks to confuse your partner. But you aren't doing it randomly, are you? ;) The greater the magician, the innocent he looks, so you have to be really smart and innocent to pull this off :P
Well, just fill the 12 blocks like this each and everytime:

You can remember this through some practice of course. Well it is essential for every magician to practice, so it's alright for you to do so. Look we didn't fill up the A, B, C, D blocks. We only placed the numbers from 1 to 12 here. And remember, everytime these 12 numbers have to be placed like this exactly. Now we will fill up the 4 magic blocks with four different magic numbers. How we will generate these magic numbers? Here is the answer:

A : Subtract 20 from the given number. The number given was 50. So I get 50 - 20 = 30 for the block A.
B : Subtract 1 from A, so we get 30 - 1 = 29.
C : Add 2 with A, so we get 30 + 2 = 32 for C.
D : Add 1 with A, so we get 30 + 1 = 31 for D.

Thank you for reading this. Hope you enjoyed all.

Magic Square Part - 2

আগের পর্ব ঃ part - 1

জোড় সংখ্যক গ্রিডের ম্যাজিক স্কয়ার সমাধান ( Solving Even-Numbered Magic Square )

প্রথমে আমরা সহজভাবে দেখি। আমরা এখন যেটি দেখবো সেটি হল ডাবল-জোড় সংখ্যক গ্রিড এর জন্য। ডাবল-জোড় কি? ( Doubly Even ) ডাবল-জোড় হল, যে জোড় গ্রিড ভাঙলে আবার জোড় গ্রিড পাওয়া যায়। যেমন ঃ ৪, ৮, ১৬... আবার, ৬, ১২, ১৪... এসব হবে সিঙ্গেল-জোড় গ্রিড এর মেথড এ। আমরা পরে আলোচনা করবো এটি নিয়ে। আপাতত ডাবল-জোড় দেখি।
প্রথমেই আমরা ম্যাজিক কন্সটেন্ট বের করি। ধরি গ্রিড 4x4,
সুতরাং, [  4 * ( 4² + 1 ) ] / 2 = [ 4 * 17 ] / 2 = 34

প্রথম ধাপ ঃ গ্রিড এর ৪ টি কোনাতে আমরা N/4 সাইজের ঘর মার্ক করে রাখবো।
4x4 এর জন্য মার্ক করা ঘরের সাইজ ঃ 1x1
8x8 এর জন্য মার্ক করা ঘরের সাইজ ঃ 2x2
12x12 এর জন্য মার্ক করা ঘরের সাইজ ঃ 3x3

দ্বিতীয় ধাপঃ এবার আমরা মাঝাখানের ঘরগুলি, যেগুলি চার কোনার সাথে কানেক্টেড আছে, তাদের মার্ক করবো এভাবেঃ

তৃতীয় ধাপঃ এবার আমরা মার্ক করা ঘরগুলিতে সংখ্যা বসাতে থাকবো। যে যেই ঘরে বসবে ( ১ থেকে শুরু করে ) তাকে সেই ঘরে বসিয়ে দিবো এভাবে ঃ

চতুর্থ ধাপঃ এবার আমরা যেসব ঘর মার্ক করা নেই, সেগুলোতে বাকি সংখ্যাগুলি বসিয়ে দিবো রিভার্স অর্ডার এঃ

আমরা হিসাব করে দেখবো যে, সকল সারি, কলাম, কর্ণ বরাবর যোগফল ৩৪ হচ্ছে ( ম্যাজিক কন্সটেন্ট )।
একটি ৮x৮ এর জন্য দেখা যাক -->

এখানে ম্যাজিক কন্সটেন্ট ঃ ২৬০
এবার আমরা দেখবো সিঙ্গেল-জোড় সংখ্যার জন্য। ( Single-Even ) সিঙ্গেল-জোড় হল এমন সংখ্যার গ্রিড যা ২ দিয়ে বিভাজ্য কিন্তু ৪ দিয়ে নয়। প্রথম সিংগেল-জোড় হল ৬x৬, কারন ২x২ ম্যাজিক স্কয়ার সম্ভব নয়।আমরা এখন এরকম গ্রিড এর জন্য দেখবো কিভাবে মানগুলি বসাতে হবে।
ম্যাজিক কন্সটেন্ট, c = [  6*( 6*6+1 ) ] / 2 = 222/2 = 111

প্রথমে আমরা ৬x৬ গ্রিড টিকে এভাবে চারভাগে চাগ করবো। এবার আমরা এই চার ব্লকে আমাদের নাম্বারগুলি বসাবো এভাবেঃ A ব্লকের রেঞ্জ হবে ১-৯, B ব্লকের রেঞ্জ হবে ১৯-২৭, C হবে ২৮-৩৬ এবং D হবে ১০-১৮। এরপরে আমরা ৩x৩ যেভাবে সল্ভ করেছি, সেইভাবে মানগুলি বসাবো।

এবার আমরা প্রতি ব্লকের জন্য মানগুলি বসাবো। প্রতি ব্লকের ১, ১০, ১৯, ২৭ এগুলোকে ১ ধরে আমরা আমাদের ৩x৩ ম্যাজিক স্কয়ার কমপ্লিট করবো। মান বসানোর সময় আমরা শুধুমাত্র ৩x৩ গ্রিডই বিবেচনা করবো।

আমাদের কাজ এখনও শেষ হয়নি। সিঙ্গেল-জোড় এর ক্ষেত্রে এই পার্টটি গুরুত্বপুর্ণ। আমরা কয়েকটি ঘর মার্ক করবো এবং কিছু ঘরের সাথে এক্সচেঞ্জ করবো এভাবেঃ

মার্ক করা ঘরগুলি আমরা এক্সচেঞ্জ করবো, তাহলেই আমাদের কাজ শেষ।

এভাবে সবসময়, A এবং C ব্লকের মাঝে এক্সচেঞ্জ করতে হবে।
৬ এর থেকে বড় গ্রিড এর জন্য আমাদের A,C ছাড়াও B,D এর মাঝেও এক্সট্রা এক্সচেঞ্জ করতে হবে সেইম ১-১ মেথড এ, নিচের ছবিটি দেখলে আশা করি বুঝা যাবে ঃ

১৪x১৪ ঃ এক্সচেঞ্জ এর আগে।

১৪x১৪ ঃ এক্সচেঞ্জ এর পরে।

এবার একটি মজার ট্রিক ঃ magic square trick

Magic Square Part - 1

ম্যাজিক স্কয়ার কি? ( What is Magic Square? )

একটি  N x N ২ডি গ্রিড এ 1 থেকে N পর্যন্ত সংখাগুলোকে প্রতিটি কেবলমাত্র একবার ব্যবহার করে এমনভাবে সাজাতে হবে, যাতে ঐ গ্রিড এর প্রতিটি সারি, কলাম এবং কর্ণ গুলির যোগফল সমান হয়। এখন এরকম অনেকরকম সাজানো যেতে পারে, আমাদের এমন একটি স্টেট বের করতে হবে, যেটায় এই যোগফল সবচেয়ে কম হয়।

ম্যাজিক কন্সটেন্ট ( Magic Constant )

ম্যাজিক কন্সটেন্ট হল সেই সর্বনিম্ন সংখ্যা যেটা আমাদের গ্রিড এর জন্য বের করতে হবে। এখন গ্রিড N x N হলে,
ম্যাজিক কন্সটেন্ট, c = N * [ ( N² + 1 ) / 2 ]
সুতরাং, N = 3 হলে, c = 3 * [  ( 9 + 1 ) / 2 ] = 3 * [ 10 / 2 ] = 3 * 5 = 15
কাজেই সব সারি, কলাম, কর্ণ এর যোগফল অবশ্যই ১৫ হতে হবে।

বেজোড় সংখ্যক গ্রিডের ম্যাজিক স্কয়ার সমাধান ( Solving Odd-Numbered Magic Square )

 প্রথম ধাপ ঃ গ্রিড এর প্রথম সারির একদম মাঝের কলামে ১ বসাই।

আমরা একটি 3 x 3 গ্রিড এর জন্য করবো। 7 x 7 এর জন্য 4th কলামে আমরা 1 বসাবো, এরকমভাবে।
বেজোড় সারি-কলামের ক্ষেত্রে আমরা সবসময় এভাবে শুরু করবো।

দ্বিতীয় ধাপঃ আমরা সবসময় sequencially ১ থেকে n পর্যন্ত বসাবো। এখন, ১ বসানোর পরে আমরা একবার কলাম, একবার সারি, এভাবে ধাপে ধাপে সিরিয়ালি বসাবো। নিচের উদাহরন দেখলে বিষয়টা বুঝা যাবেঃ

২ আমরা এভাবে বসাবো। ১ এর ঠিক পরের কলাম এবং সবার শেষের সারিতে ২ বসবে। এরপরে আমরা বাকি সংখ্যাগুলি ২ এর পরের কলাম, এবং আগের সারিতে, এভাবে বসাবো। অর্থাৎ আমরা নিচ থেকে উপরে উঠবো। এখন কথা হচ্ছে, ২ এর পরে আর কলাম নেই, এটা একটি ব্যাতিক্রম। এরকম ৩ ধরনের ক্ষেত্র আছে, যেগুলি একটু খেয়াল করলে আমরা সহজে হ্যান্ডেল করতে পারবো।

প্রথম ব্যাতিক্রমঃ আমরা এখন হিসাব অনুযায়ী ৩ নং কলাম এবং ২ নং সারিতে যাবো। কিন্তু আমাদের এটি গ্রিড এর বাইরে, কাজেই আমাদের ঐ সারিতে থাকবো ঠিকই, কিন্তু ডান দিকে না গিয়ে আমরা একদম সবচেয়ে বামদিকের ঘরে বসাবো।

 ছবি দেখে আমরা বুঝতে পারবো ব্যাপারটা। ৩ এর জন্য ঘর গ্রিড এ নাই, কাজেই আমরা ২ নং সারিতে থাকবো ঠিকই, কিন্তু, একদম বামে চলে যাবো, আসলে ব্যাপারটা ঠিক বামে না, আমাদের যে দিকে যাবার কথা, তার বিপরীত দিকে যাবো। কাজেই কলাম ১ এ চলে আসলাম।

দ্বিতীয় ব্যাতিক্রমঃ এখন আমাদের ৪ বসানোর জন্য আবার ঝামেলায় পরে গেলাম। আমাদের উপরের সারিতে এবং পরের কলামে যাওয়ার কথা, কিন্তু সেখানে আগে থেকেই ১ আমরা লিখে রেখেছি। এরকম অবস্থা হলে সেটি হল দ্বিতীয় ব্যাতিক্রম। এজন্য আমরা যেখানে বর্তমানে আছি, তার ঠিক নিচের সারিতে পরের মান বসাবো, এক্ষেত্রে কলাম একই থাকবে। অর্থাৎ ৪ কে আমরা ৩ এর নিচে বসাবো এভাবে ঃ

এখন আমরা দেখতে পাচ্ছি আমাদের মূল যেভাবে বসানোর কথা ছিল, আমরা সেরকম পথ পেয়ে গেছি :D । কাজেই আমরা ৪ থেকে উপরের সারি, পরের কলাম, এভাবে বাকি সংখ্যাগুলি বসাতে থাকবো যতক্ষন কোন ব্যাতিক্রম না পাই। অর্থাৎ ঃ

এখন আমরা ৭ বসানোর জন্য দেখি যে একটি ব্যাতিক্রম হয়ে গেছে। হিসাব অনুযায়ী গ্রিডের বাইরে চলে যায়, এখন আমাদের এটা ১ নং ব্যাতিক্রমের মধ্যে পরে, কিন্তু যেহেতু, ৬ এর নিচে খালি একটি ঘর আছে, কাজেই, এটি আসলে ২ নং ব্যাতিক্রম। তাই আমরা ৬ এর ঠিক নিচে ৭ কে বসাবো এভাবে ঃ

এখন আমরা খেয়াল করলে দেখবো এখানে আসলে ১ নং ব্যাতিক্রমটি হয়েছে, কারন ৭ এর নিচে ঘর ফাঁকা নেই, আবার গ্রিড এর বাইরেও চলে যাচ্ছে। তাই আমরা উপরের সারির সবচেয়ে বামদিকে পরের সংখ্যাকে বসাবো এভাবে ঃ

তৃতীয় ব্যাতিক্রমঃ এখন আমরা আসি ৩ নং ব্যাতিক্রম এ। এটি আসলে এমনিতেই বুঝা যায়, আমাদের হিসাবে এখন যাওয়ার কথা উপরে, কিন্তু গ্রিড এর বাইরে হওয়াতে আমরা দেখবো ৮ এর নিচে ফাঁকা ঘর আছে কিনা, ফাঁকা নেই, কাজেই হিসাব মত আমাদের সবচেয়ে বামের ঘরে ব্যাতিক্রম ১ অনুযায়ী মান বসানোর কথা, কিন্তু এটিও গ্রিড এর বাইরে  -_- । এটিই আমাদের ৩নং ব্যাতিক্রম। এক্ষেত্রে আমাদের ঠিক পরের কলামের নিচ থেকে যে ঘর ফাঁকা পাবো, সেখানে মান বসায়ে দিবো।

সারি, কলাম, কর্ণ সকল ক্ষেত্রে যোগফল ১৫ এসেছে, কাজেই আমাদের উদ্দেশ্য সফল। এভাবে আমরা যেকোন বেজোর সংখ্যক গ্রিড এর জন্য ম্যাজিক স্কয়ার বানাতে পারবো।
 ** ৭ এর জন্য আমরা একটি ম্যাজিক স্কয়ার দেখি ঃ
এক্ষেত্রে ম্যাজিক কন্সটেন্ট, c = 175

আমরা ঠিক 3x3 এর মত করে 7x7 গ্রিডটি সাজালাম। এখন সারি, কলাম, কর্ণ সব যোগ করে আমরা ১৭৫ পাবো :)
ইটারেশন গুলিতে বুঝতে সমস্যা হলে, হাতে কলমে এভাবে একটি করলেই আশা করি সবাই বুঝে যাবে।
এখন আমাদের লাগবে জোড় সংখ্যক গ্রিডের জন্য সমাধান। আমাদের প্রথমে ১ টি জিনিস দেখা লাগবে আগে, আমরা প্রথমে দেখবো যে গ্রিডটি কে ভাঙলে যে গ্রিড পাওয়া যায়, সেগুলি জোড় নাকি বেজোড়। ২ টির ভিন্নতার কারনে ভিন্ন ভিন্ন মান আসবে।
আমরা ২ টির জন্যই দেখবো এখানে ঃ part - 2

Even the Odds!

Contest link: Intra AUST Preliminary Fall - 17

Problem name: Even the Odds!

Required knowledge: Modular arithmetic, big multiplication.
Editorial: Firstly, try reading this Modular Arithmetic or you can google about modular arithmatic and it's properties. Now let's analyze the problem.

Given N and M, we need to find summation of first N even numbers modulo M and summation of first N odd numbers modulo M.
We can observe that the first N odd numbers summation can be found by calculating N * N and first N even numbers summation can be found by calculating N * (N+1).
let, N = 4,

Odd : 1 + 3 + 5 + 7 = 16 = 4 * 4
Even : 2 + 4 + 6 + 8 = 20 = 4 * 5
As the modulo M is really big we can't simply calculate ( (N % M) * ( (N+1)%M) )%M, because the N can be as large as 10¹⁸ - 1 and M can be 10¹⁸, then at the time of multiplying, it will overflow. How can we do this without overflow? We will simply use a divide and conquer technique to calculate N * N by adding N with N, N times, instead of multiplying them. Let N = 10¹⁸ - 1, M = 10¹⁸.


Now, from modular arithmatic we know that
- (a * b) % m = (( a%m ) * ( b%m ))%m
- (a + b) % m = (( a%m ) + ( b%m ))%m
Say, a = 10¹⁸ and b = 10 and m = 10¹⁸ - 1.
So, ( (10¹⁸ - 1) %10¹⁸ ) * (10¹⁸ - 1) %10¹⁸ ) ) % 10¹⁸= ( (10¹⁸ - 1) * (10¹⁸ - 1) ) % 10¹⁸ = 0 ; here (10¹⁸ - 1) * (10¹⁸ - 1) will cause overflow.
But,(((10¹⁸ - 1)%10¹⁸) + ((10¹⁸ - 1)%10¹⁸) + ....

We can easily add (10¹⁸ - 1 + 10¹⁸ - 1) and then mod it with 10¹⁸. We will do this 10¹⁸ times, and by using modulo operation each time, there won't be any overflow.
As 10¹⁸ is also a very big number, we can do this is O (log10(N)) times with folowing divide and conquer algorithm.


We will use this bigmul function to calculate ( a * b ) % c. We will simply add the number a, b times each with modulo operation. As the range is too big, we can't simply use loop, so we will use this recursion technique of calculating big multiplication in logN time.

Timus 1014 : Product of Digit

Prob link: Timus 1014: Product of Digit

প্রব্লেম এ চাওয়া হয়েছে যে , আমাকে একটা integer দেয়া হবে, আমাকে minimum এমন একটা integer বের করতে হবে যেখানে ঐ integer এর প্রত্যেক digit এর গুনফল ঐ integer এর সমান হয়।
test case চিন্তা করলে দেখা যায়, N = 10 ;
10 কে এভাবে লিখা যায়ঃ (2 * 5) , (5 * 2) .. দেখা যাচ্ছে যে আসলে 10 এর গুননীয়ক গুলা নিয়ে আমাদের চিন্তা করা লাগবে। দেখা যাচ্ছে  25 , 52 ,... 25 হচ্চে সবচেয়ে ছোট, তাই answre 25 for N = 10;

আমরা কিন্ত ( 1 * 10 ) এই combination টা নেইনাই , কারন 1,1,0 or 1,0,1 এর digit এর গুনফল N এর সমান হয়না।

এখন এটা solve করা যায় কিভাবে ? প্রশ্নে এ বলা হইছে digit এর গুনফল  N এর সমান হবে, এরমানে একটা জিনিস বলা যায় যে আমার উত্তর আসলে 0 to 9 digit এর কোন সংখ্যা হবে।
তাহলে loop এর code অনেকটা এরকম হবেঃ

for ( int digit = 9 ; digit > 1 ; digit -- )

{

         // rest of the code

}

তাহলে তো প্রব্লেম টা খুবই সহজ হয়ে গেলো। আমাদের দেখতে হবে যে 2 থেকে 9 এর মাঝে কোন কোন digit দিয়ে N কে mod করা যায়, মানে ভাগশেষ শুন্য হয়। যখনই কোন সংখ্যা দিয়ে N ভাগ যাবে ঐ সংখ্যা দিয়ে N কে ভাগ করতে থাকতে হবে যতক্ষন N  আর ভাগ না যায়।

 অর্থাৎ,

while ( N % digit ==0 )

আমাদের মূল কাজ হল N এর divisor digit গুলি বের করা,মানে যেসব digit দিয়ে N কে মড করা যায় এমন digit.

এখন যেহেতু আমাদের নতুন একটা integer বের করতে হবে, কাজেই কেবলমাত্র একবার N কে মড করার পরেই থেমে গেলে হবে না, যতক্ষন মড করা যায় করতে থাকতে হবে। কাজেই , while লিখা হয়েছে।
উদাহরন দিলে ব্যাপারটা বোঝা সহজ হবে ,
N = 50  >>  ans = 255
N = 120 >> ans = 358

( Digit নিয়ে কাজ করার এইটা একটা reason , অনেকে Digit না নিয়ে only sqrt ( N ) পর্যন্ত লুপ চালায়ে first যেটা দিয়ে ভাগ যায় সেই সংখ্যা আর  N /  ( সেই সংখ্যা ) ans print করে , যা ভুল ; 120 এর জন্য খেয়াল করলেই বুঝা যায়ঃ

for ( int digit = 2 ; digit <= 9 ; digit++ ){
if ( N % digit == 0 ) {
cout << digit << N / digit << endl ;

                    return 0;

           }

}

120 এর জন্য হবে 260 ,যেটা ভুল কারন  2 * 6 * 0 == 0  ( not 120 )

valid code:

for ( int digit = 9 ; digit > 1 ; digit-- ){
       while ( N % digit == 0 ){
       // rest of the calculation
       }
}
এখন হিসাবের জন্য N = ১০ ধরি,
---> 10 % 5 == 0
কাজেই এটি while লুপ এ ঢুকবে। লুপের ভিতর আমরা দেখি যে 5 একটি ভ্যালিড ডিজিট আমাদের ফাইনাল রেজাল্ট এর জন্য, তাই আমরা 5 কে আমাদের প্রথম ডিজিট হিসেবে নিয়ে একটি ভ্যারিয়েবল ( SUM ) এ সেইভ করে রাখবো।এখন SUM এর মান 5, কাজেই আমাদের এখন N কে 5 দিয়ে ভাগ করতে হবে, কেননা আমরা 5 কে আমাদের ডিজিট হিসেবে নিয়ে নিয়েছি।

কাজেই N = N / 5 = 2

এরপর আমরা আবার দেখবো N % 2 == 0, কাজেই আমরা আমদের পরের ডিজিট টিও পেয়ে গেলাম।

 ( আশা করি এতক্ষনে সবাই বুঝে গেছি আমরা কেন লুপ ৯ থেকে ২ পর্যন্ত চালিয়েছি। )

কাজেই আমাদের ফাইনাল রেজাল্ট হবে এরকমঃ
25  =  2 * 10 + 5 * 1 ( multiple করার ব্যাপারটা তোমরা নিজেরা try করে দেখো )
অর্থাৎ রেজাল্ট = 25।
120 এর জন্য :  3 * 100 + 5 * 10 + 8 * 1 = 358.

Critical test case:

N = 0 হলে আমাদের রেজাল্ট হবে 10, কারন 0 পজিটিভ, নেগেটিভ কোনটিই না এই প্রব্লেম এর জন্য। কাজেই 10 হচ্ছে প্রথম পজিটিভ রেজাল্ট।
N = 1 হলে রেজাল্ট হবে 1.
এখন N যদি প্রাইম নাম্বার হয়? এখানে একটি কন্ডিশন আছে, যা লুপ এর শেষে N কে চেক করে, আমরা এটি বুঝতে পারছি যে, লুপের শেষে N যদি 1 হয়, তাহলে আমাদের ফাইনাল অ্যান্সার হবে -1, কারন কোন ডিজিট ই N কে মড ( MOD ) করতে পারেনি। এটি আশা করি সবাই বুঝে গেছো।

ধন্যবাদ কষ্ট করে পড়ার জন্য।

UVA 11254: Consecutive Integers

Prob link: UVA 11254: Consecutive Integers

Problem টায় বলা হয়েছে আমাকে একটা integer দেয়া হবে, আমাকে ঐ integer টি আরো কতোগুলি consecutive integer এর summation এর মাধ্যমে বানানো যায় তা print করতে হবে।
Suppose 15 কে আমরা লিখতে পারি এভাবে ------>

15 = 1 + 2 + 3 + 4 + 5
15 = 4 + 5 + 6
15 = 7 + 8
15 = 15

দেখা যাচ্ছে যে এর মধ্যে প্রথম টির integer সংখ্যা বেশি, তাই আমাকে প্রথম টি ই print করা লাগবে।print করার জন্যে question এ যে format এর কথা বলা হয়েছে, সে অনুযায়ী print করলে আমাদের output হবে এরকম  :::
15 = 1 + ... + 5  ( অর্থাৎ আমাকে consecutive integers এর  first এবং last integer টা print করতে হবে )
যদি এমন integer হয়, যাকে কোন consecutive integer এর summation এ ফেলা যায় না, তখন কেবল ঐ integer টাই print হবে।
Ex : For N = 8  ans   ===   8 = 8 + ... + 8

Solve Technique:

আমরা sum of arithmetic progression সম্পর্কে নিশ্চই জানি।
যদি n তম integer পর্যন্ত summation বের করতে হয়, তাহলে সূত্র ঃ sum, Sn ( n terms ) = n / 2 + [ 2 * a + ( n - 1 ) * d ]
যেখানে , a = first term , n = last term , d = interval between numbers .
আমরা এই সূত্র ব্যবহার করে আমাদের উত্তর বের করবো।
যেহেতু আমাদের বলা আছে , consecutive integers, so আমাদের d এর মান হবে  one  ( 1 ) .
এখন আমাদের n জানা আছে, আমরা চাইলে brute force করে করতে পারি,  কিন্তু আমাদের range টাকে ( 10 ^ 9 ) মাথায় রাখতে হবে।
এতবড় জিনিস বারবার loop চালায়ে করলে TLE  ( Time Limit Exceeded ) খাওয়ার সম্ভাবনা অনেক বেশি, তাই আমরা আমাদের সূত্র ব্যবহার করে একটা ফরমুলা বানানোর চেষ্টা করবো যাতে আমাদের brute force এর time complexity কম হয়।
সূত্র টাকে আরেকভাবে লিখা যাক,  a = ( 2 * Sn + n - n * n ) / ( 2 * n )
হিসাবের সুবিধার জন্য আমরা এভাবে লিখলাম, এখন খেয়াল করে দেখো আমাদের জানা মান হল Sn , যা qs এ দেয়া থাকবে, আমাদের বের করতে হবে a এবং n । আমরা ২ টা কাজ করতে পারি, প্রতি a  এর জন্য লুপ চালায়ে n বের করতে পারি, অথবা উলটা কাজটাও করতে পারি।

এখন কথা হল লুপ চালাবো কতক্ষন ?
equation খেয়াল করলে দেখা যায় আমাদের R.H.S এ আছে 2 * Sn , আমরা square root of 2 * Sn থেকে 1 পর্যন্ত integer এর উপর লুপ চালায়ে n  এর মান বের করতে পারি এবং n  এর মান আমরা equation এ বসায়ে  a এর মান এর validity check করতে পারি।যখন ই আমরা valid একটা মান পাবো তখন আমাদের result এর a হবে
equation থেকে প্রাপ্ত মান এবং n হবে   a + ( যেই মান এর জন্য আমরা valid a পেলাম সেই মান) - 1 ।

Qs 1 : Why sqrt ( 2 * Sn )  ?

Ans : equation থেকে এটা easily observe করা যায়, n * n এই value টার আগে minus sign আছে, কাজেই, আমার  n এর মান sqrt ( 2 * Sn ) এর বেশি হলে negative integer আসবে , যা আসলে ভুল result দিবে।

Qs 2 : a এর validity check করবো কিভাবে ?

Ans : আমরা a = ( 2 * Sn + n - n * n ) / ( 2 * n )  এই সূত্র টা কাজে লাগাবো, sqrt ( 2 * Sn ) থেকে 1 পর্যন্ত লুপ চালায়ে আমরা প্রতি n এর জন্য  a এর মান এর validity দেখবো। a valid হবে তখনই যখন আমার equation এ n এবং Sn বসালে তা সত্য হবে।

a = ( 2 * Sn + n - n * n )  এটা থেকে আমরা একটা মান পাবো, এখন কখন এই মানটা সত্য? যখন a কে  ( 2 * n ) দিয়ে মড করলে মান শুন্য আসবে, কেবলমাত্র তখনই আমরা a এর একটা integer value পাবো এবং value টা হবে ( 2 * Sn + n - n * n ) / ( 2 * n ).