Wednesday, January 31, 2018

Toph: Arya and OR

Problem link: Arya and OR

Solution: 

Firstly, the maximum value we could get is the largest element of the array. So we will sort the array. Then our maximum value could get greater by doing OR ( | ) with other elements of the array. So in that case, what we will do is that, each time we will make bitwise OR with the largest element of the array with other elements in descending order. So, gradually, we will get values after everytime we OR them. If our current value is greater than our maximum value, then we will simply update the maximum value.

As there is a term "arbitrary group of numbers"
Arbitrary group should mean any group possible from the whole array, and in that case the bitwise or of the whole array is always the maximum answer

**ps: We don't even need sorting for this problem. Simply compute OR of all the numbers.

Code:

Codeforces Round #460 (Div. 2)


  • Supermarket
Find the minimum value of (a/b) for every n supermarkets. This will be considered as unit value of one kilo apple. Then simply multiply m with minimum(a/b) to get the answer.

  • Perfect Number
If we observe carefully, there is a pattern. From 19, every 9-th number should be a Perfect Number according to the statement. But we will also check their digit sum each time whether they match 10 or not. If they match 10, then we will increase our counter.

  • Seat Arrangements
First we will find how many different combination in row-wise. If we get '.' in any position of the grid, we will simply check next + k - 1  row for our answer. If row+k-1 >= n, there is no combination. Same thing goes for column as well. Else we will increase our counter.
The legendary hack case for this problem is this:

2 2 1
..
..

If we do according to our approach, there will be overlapping while counting row wise and column wise. So we need to check, if k == 1 or not. If k == 1, then the answer will be summation/2, as we counted each position twice.

Wednesday, January 24, 2018

A client server multichat program for network programming

This was like my 4th year's network programming lab's project. The main task is to create a server that will help some clients to make communication with each other, like any social media services like Facebook, Whatsapp, Messenger etc.

Software Used: XAMPP server, NetBeans IDE.

Codes, sql files are given in the folder. Create a database in XAMPP named multichat. Then import the sql file. These are the instructions for the program: 
  • 1. Type 'create User_name Password' to create an account 
  • 2. Type 'login User_name Password' to login your account
  • 3. Type 'logout' to logout from your account 
  • 4. Type 'joinchatroom Chat_room_name' to join a chatroom 
  • 5. Type 'leavechatroom' to leave from your current chatroom
  • 6. Type 'showchatroom' to show all available chat rooms 
  • 7. Type 'showuser' to show all logged in user available
  • 8. Type 'showfriend' to show your friend list 
  • 9. Type 'showrequest' to show your pending friend request 
  • 10. Type 'connect Friend_name' to send friend request to your friend
  • 11. Type 'yes Friend_name' to accept a friend request 
  • 12. Type 'no Friend_name' to reject a friend request 
  • 13. Type 'message Friend_name Message' to send private message to your friend 
  • 14. Type anything else besides these commands to chat with your friends :)
At first, run the Xampp and start apache and sql connection, then run the server.java in the server project and after that we can run client.java as many ( I set at most 50 user ) times to create new client that can communicate.

Snapshots of the project

Firstly we will create a user using ‘create’ command like this:

Be careful about spacing. Ok, now login part:


The username is incorrect. Same thing goes for incorrect password too.

Now we are logged in. All the other commands are similar like this. Commands: 
  • 1. create: creates an user account in the database. 
  • 2. login: login command requires three space separated strings. If not found three strings, then it will show invalid command in the console. If the user is already logged in, then it will also show already logged in. Else command will check username and password from client table in the database and the user will be online. 
  • 3. logout: logout will sign out the user from the program.
  • 4. joinchatroom: The user will be able to join a chat room using this command as follows:
**If there are already people in a chat room, and they are online; if then a person joins that chat room, every other members of that room (currently logged in) will receive a message to welcome the new user 
  • 5. leavechatroom: User can leave his chat room. User can enter another chat room using joinchatroom command. If he is already in a chat room, then he will automatically be removed from previous room. Basically, a user can be inside one chat room at a time.
  • 6. showchatroom: This will show how many chat rooms are currently available which has at least one member. If there is no member in a chat room, that room will be deleted.

  • 7. showuser: Show all currently logged in user.
  • 8. showfriend: It will show the user’s friend list.
  • 9. showrequest: This will show pending friend request. 
  • 10. connect: Send a friend request to a user. If user doesn’t exist in the database, then it will show incorrect user.

** Also case like: sending friend request to own self, sending request to user that already been sent etc are also handled, Try typing command like these to check.
 
Ok, now if Sifat logs in, then he will automatically see pending requests from different users.
  • 11. yes & no: If Sifat type yes aladin, then he and aladin will become friend. If types no aladin, then aladin’s request will be rejected and aladin will be notified via a message. If aladin is not online, then the message will be pending, else aladin will receive rejection instantly.
  • 12. message: Type message aladin to send aladin a private message.

As aladin doesn’t have friend named Sifat, so private message won’t be possible. So let’s make friends:

Now, both of them can share private message. Suppose, aladin sent a message to Sifat. If Sifat is online, he will receive the message. If Sifat is offline, the message will be stored as pending message. When Sifat will log in, he will then receive all the pending messages from different users.

**If user is not in any chat room, all of his messages will be global, an everyone who are logged in globally will receive that message(Broadcast). Private message between friends is Unicast and inside chat room, messages will be counted as multicast (only user in the chat room will receive messages).

You can find my project here: https://github.com/sifatshishir/Client-Server-Multichat

Tuesday, January 23, 2018

লংগেস্ট কমন সাব-সিকুয়েন্স (Longest Common Subsequence)

২ টি স্ট্রিং দেয়া থাকবে। এদের মাঝে ম্যাক্সিমাম কত দৈর্ঘ্যের সাব-সিকুয়েন্স আছে, এবং সিকুয়েন্সটি কি, এটা আমাদের বের করতে হবে।
সাব-সিকুয়েন্স হল এমন একটি সিকুয়েন্স, যা কিনা ২ টি স্ট্রিং এর মাঝে কমন ক্যারেক্টার নিয়ে তৈরী এবং, একটি ক্যারেক্টার এর ইনডেক্স এর চেয়ে পরের ক্যারেক্টার এর ইনডেক্স (একটি নির্দিষ্ট স্ট্রিং) অবশ্যই বড় হবে।
যেমনঃ
String X = "AAABCD"
String Y = "ABCDDA"
তাহলে, এদের মাঝে LCS হবেঃ "ABCD"
ধরি Z = "ABCD"
এখানে দেখা যাচ্ছে যে, A,B,C,D এর প্রত্যেকটি ক্যারেক্টার এর ইনডেক্স তার আগের ক্যারেক্টার থেকে বড় (X এবং Y উভয় স্ট্রিং এ)। আমরা মেইনলি ক্যারেক্টার এর অর্ডার মেইনটেইন করবো।

এপ্রোচঃ প্রথমে আমরা X এর i-তম prefix (ক্যারেক্টার, যা অন্য ক্যারেক্টার এর আগে বসাই) কে Xi দিয়ে প্রকাশ করি। তাহলে,
X1 = "A"
X3 = "AAA" etc..
এখন আমরা খেয়াল করি,

  • যদি, Xi == Yj হয়, (অর্থাৎ ২ টি স্ট্রিং এর ক্যারেক্টার মিলে গেছে), তাহলে, Zs = Xi = Yj হবে, এবং Zs-1, Xi-1 এবং Yj-1 এর একটি LCS হবে
  • যদি, Xi != Yj হয়, তাহলে Zs != Xi বলতে আমরা বুঝাবো, ্Z , Xi-1 এবং Yj এর একটি LCS
  • যদি, Xi != Yj হয়, তাহলে Zs != Yj বলতে আমরা বুঝাবো, ্Z , Xi এবং Yj-1 এর একটি LCS
তাহলে, যখন ক্যারেক্টার সমান হবে না, তখন আমরা ২ স্ট্রিং এর মাঝে ক্যালকুলেট করে ম্যাক্সিমাম মানকে নিবো।তাহলে আমাদের অ্যালগরিদম অনেকটা এরকমঃ

c[ i,j ] = 0; if i == 0 OR j == 0
              c[ i-1,j-1 ] + 1; if i,j > 0 AND Xi == Yj
              max ( c[ i,j-1 ], c[ i-1,j ] ); if i,j > 0 AND Xi != Yj

LCS ক্যালকুলেশন

ধরি, X = "ABCBDAB", Y = "BDCABA"
এখন আমরা একটি 8x7 সাইজ এর ২-ডি অ্যারে নিবো। 8 = X.size()+1, 7 = Y.size()+1
আমাদের অ্যারের [0,0] ইনডেক্স 0 ইনিশিয়ালাইজ করবো। এরপরে আমরা প্রতি সারি-কলামে ২ টি স্ট্রিং থেকে ভ্যালু মিলানোর চেষ্টা করবো। এবং আমাদের অ্যালগরিদম অনুযায়ী মান বসাবো। এখন খেয়াল করে দেখবো যে, ইনডেক্স ১ এর A(String X) এর সাথে ইনডেক্স ১ এর B (String Y) মিলেনি, কাজেই আমরা [1,1] ইনডেক্স এ 0 বসিয়ে দিলাম। এই 0 এসেছে, [1,0] এবং [0,1] ইনডেক্স এর ভ্যালুর মাঝের ম্যাক্সিমাম ভ্যালু। অর্থাৎ max ([1,0] এবং [0,1]) = 0।
এর মানে হল, X1 এবং Y1 এর মাঝে LCS এর দৈর্ঘ্য = 0. এভাবে আমরা টেবিল ফিল আপ করতে থাকি।
এখানে, 1(A) এর সাথে 4(A) মিলে গেছে, তাই আমরা [0,3] ঘরের ভ্যালু + ১ বসাবো। এভাবে আমরা বাকি ভ্যালুর জন্য ঘর ফিল আপ করলে এরকম একটি ফাইনাল টেবিল পাবো।

কাজেই, আমাদের LCS স্ট্রিং এর দৈর্ঘ্য হচ্ছে 4.
কোডঃ

এখন আমাদের কাজ হবে, এই যে LCS স্ট্রিং টির দৈর্ঘ্য পেলাম, একে প্রিন্ট করা। এর জন্য আমাদের পাথ বের করতে হবে। আমরা আমাদের ফাইনাল রেজাল্ট থেকে উপরে এবং বামে মুভ করতে থাকবো, যখন আমরা দেখবো যে Xi == Yj, তখন আমরা সেই ঘরের ভ্যালু প্রিন্ট করে দিবো। আমরা যদি পাথ ফাইন্ডিং এর জন্য টেবিল জেনারেট করি, দেখতে এরকম হবে ফাইনালিঃ
এই হচ্ছে আমাদের ফাইনাল পাথ টেবিল। আমরা নিচ থেকে উপরে সিকুয়েন্স অনুযায়ী উঠতে থাকবো। আমরা LCS বের করার সময়, যখন অ্যারেতে ভ্যালু আপডেট করতাম, ঐ সময়, আমরা আমাদের পাথ টেবিল ও আপডেট করে দিবো। Xi == Yj হলে আমরা টেবিলে স্টোর করবো m, তানাহলে, আমাদের চেক করতে হবে যে c[i-1,j] কি c[i,j-1] থেকে বড় অথবা সমান কিনা। এক্সদি বড় অথবা সমান হয়, তাহলে আমরা স্টোর করবো u (up), তানাহলে, আমরা l(left) স্টোর করবো। তাহলে আমাদের LCS স্ট্রিং: "BCBA" এরপরে আমরা নিচের কোড অনুযায়ী পাথ ক্যালকুলেট করবোঃ


এখানে char x[] হল X স্ট্রিং, আমরা এখানে ইচ্ছা করলে Y ও পাঠাতে পারতাম। যেহেতু, ২ স্ট্রিং এর মাঝের কমন স্ট্রিং বের করতে চাচ্ছি, কাজেই, আমাদের ২ টি স্ট্রিং চেক না করে একটির ইনডেক্স চেক করলেই কাজ হয়ে যাচ্ছে

প্র্যাকটিস প্রব্লেম (Practice Problems)






Monday, January 22, 2018

ম্যাট্রিক্স চেইন মালটিপ্লিকেশন (Matrix Chain Multiplication)

আমাদের কিছু ম্যাট্রিক্স দেয়া থাকবে।আমাদেরকে বের করতে হবে, এমন কোন অর্ডার এ ম্যাট্রিক্সগুলিকে গুন করলে তাদের cost মিনিমাম হবে।
ধরি আমাদের ২ টি ম্যাট্রিক্স দেয়া আছে A এবং B.
এখন A = [ P x Q ] ; এখানে P হল সারি (row), Q হল কলাম (column)
B = [ Q x R ]
এখন A*B করার পরে আমরা যে নতুন ম্যাট্রিক্স পাবো, তার ডাইমেনশন হবে = P x R
এখন আমাদের সবসময় লক্ষ্য রাখতে হবে যে ২ টি ম্যাট্রিক্স এর গুনের জন্য অবশ্যই প্রথম ম্যাট্রিক্স এর কলাম এবং দ্বিতীয় ম্যাট্রিক্স এর সারি সমান হতে হবে। এবং এক্ষেত্রে তাদের মাঝে গুনের জন্য টোটাল মালটিপ্লিকেশন লাগবে ঃ P*Q*R; [ ১ম ম্যাট্রিক্স এর সারি * ১ম ম্যাট্রিক্স এর কলাম * ২য় ম্যাট্রিক্স এর কলাম ]।
অর্থাৎ, cost = P*Q*R.

এবং আমাদের কাজ হচ্ছে একাধিক ম্যাট্রিক্স এভাবে লিনিয়ারলি গুন করা যাতে তাদের cost মিনিমাম হয়।
এখানে মূল ব্যাপার হল, আমরা যেভাবেই মালটিপ্লাই করিনা কেন, ফাইনাল রেজাল্ট সবসময় একই আসবে। অর্থাৎ গুন করার ক্ষেত্রে অর্ডার কোন প্রভাব ফেলেনা। তবে একেক অর্ডার এর জন্য একেকরকম cost আসবে। আমাদের কাজ হবে এমন অর্ডার বের করা যাতে cost মিনিমাম হয়।

ধরি, A [10 x 100 ] , B [ 100 x 5 ] , C [ 5 x 50 ], এই তিনটি ম্যাট্রিক্স। এখন আমরা ২ ভাবে এদের গুন করতে পারি।
  • ( A * B ) * C
  • A * ( B * C )
এখন ( A * B ) * C এর ক্ষেত্রে, প্রথমে,
( A * B ) এর জন্য cost, c1 = 10 * 100 * 5 = 5000; [ cost = P*Q*R ]
এখন ( A * B ) করার পরে আমরা যে নতুন ম্যাট্রিক্স পাবো, ধরি নতুন ম্যাট্রিক্সটি A' .
তাহলে A' এর ডাইমেনশন হবেঃ A' [ 10 x 5 ]; [ P x R ]
এখন, ( A' * C ) এর জন্য cost, c2 = 10 * 5 * 50 = 2500
সুতরাং, টোটাল cost, c = 5000 + 2500 = 7500

একইভাবে A * ( B * C ) এর জন্য টোটাল cost হবে 75000
কাজেই আমাদের জন্য প্রথম অর্ডার এ মালটিপ্লাই করলে cost মিনিমাম হবে।

অ্যালগরিদম (Algorithm)


আমরা আমাদের MCM (Matrix Chain Multiplication) বের করার জন্য যে ম্যাট্রিক্সগুলি দেয়া থাকবে, সেগুলি থেকে আমরা তাদের ডাইমেনশনকে একটু মডিফাই করে একটি অ্যারেতে সেভ রাখবো এমন ভাবে যাতে, প্রতিটির ইনডেক্স এ তাদের সারির (row) মানগুলি থাকবে। উদাহরন দিলে ব্যাপারটি পরিষ্কার হবে।
ধরি, আমাদের ৬ টি ম্যাট্রিক্স দেয়া আছে এভাবেঃ

A1 [ 30 x 35 ]
A2 [ 35 x 15 ]
A3 [ 15 x 5 ]
A4 [ 5 x 10 ]
A5 [ 10 x 20 ]
A6 [ 20 x 25 ]

এখন আমরা এদের সারি-কলামের মানগুলোকে একটি অ্যারে p তে এভাবে সাজায়ে রাখবোঃ
কাজেই আমরা যদি, A1 * A2 করতে চাই, তাহলে p অ্যারে থেকে আমরা p[0]*p[1]*p[2] করলেই মান পেয়ে যাবো।
তাহলে আমরা এখন একটি ফর্মুলা দাঁড়া করাতে পারি এভাবেঃ

m[i,j] = i হতে j পর্যন্ত ম্যাট্রিক্স গুন করতে মিনিমাম মালটিপ্লিকেশন।
তাহলে আমরা লিখতে পারিঃ

m[ i,j ] = { 0 if , i == j, else
                min { m[ i,k ] + m[ k+1,j ] + p[ k-1 ] * p[ k ] * p[ j ]  }; [k = 1 to j-1]

আমরা এই ফর্মুলা অনুযায়ী আমাদের MCM table জেনারেট করবো।

টেবিল জেনারেট (MCM table generate)


যেহেতু আমাদের ৬ টি ম্যাট্রিক্স, তাই আমরা 6 x 6 সাইজ এর একটি ২-ডি অ্যারে নিবো। এখন আমরা প্রতিবার, length 1 to 6 পর্যন্ত ম্যাট্রিক্স মালটিপ্লিকেশন এর অর্ডার বের করবো।
length = 1 হলে, m[i,j] = m[i,i] = m[j,j] = 0; m[i,j] হল, m ২-ডি অ্যারের i,j ইনডেক্স।
তাহলে, আমাদের টেবিল দেখতে এরকম হবে। এখানে আমরা cost গুলিকে হিসাব করবো।

length = 2 হলে,
m[1,2] = m[1,1] + m[2,2] + p[0]*p[1]*p[2] = 0+0+30*35*15 = 15750
m[2,3] = m[2,2] + m[3,3] + p[1]*p[2]*p[3] = 0+0+35*15*5 = 2625
m[3,4] = m[3,3] + m[4,4] + p[2]*p[3]*p[4] = 0+0+15*5*10 = 750
m[4.5] = m[4,4] + m[5,5] + p[3]*p[4]*p[5] = 0+0+5*10*20 = 1000
m[5,6] = m[5,5] + m[6,6] + p[4]*p[5]*p[6] = 0+0+10*20*25 = 5000
length = 3;
m[1,3] = m[1,1] + m[2,3] + p[0]*p[1]*p[3] = 0+2625+30*35*5 = 7875; k = 1
               m[1,2] + m[3,3] + p[0]*p[2]*p[3] = 15750+0+30*15*5 = 18000; k = 2
এখানে, ৩ দৈর্ঘ্যের জন্য, একবার (A1*A2)*A3, আরেকবার A1*(A2*A3) হিসাবে করে এদের মাঝে মিনিমামটি নিতে হবে। কাজেই m[1,3] = min (7875,18000) = 7875.
lenght = 3 এর জন্য আমরা k এর মান 1,2 ধরবো। এখন এভাবে length = 3 এর জন্য সকল ভ্যালু বসালে আমরা পাবোঃ
এখন length = 4 এর জন্য, k = 1,2,3 ধরে হবেঃ
m[1,4] = m[1,1] + m[2,4] + p[0]*p[1]*p[4] = 14875; k = 1
               m[1,2] + m[3,4] + p[0]*p[2]*p[4] = 21000; k = 2
               m[1,3] + m[4,4] + p[0]*p[3]*p[4] = 9375; k = 3
m[1,4] = min (14875,21000,9375) = 9375

এভাবে বাকি মান বসালে আমরা পাইঃ
length = 5;
m[1,5] = m[1,1] + m[2,5] + p[0]*p[1]*p[5] = 28125
               m[1,2] + m[3,5] + p[0]*p[2]*p[5] = 27250 
               m[1,3] + m[4,5] + p[0]*p[3]*p[5] = 11875; k = 3
               m[1,4] + m[5,5] + p[0]*p[4]*p[5] = 15375
m[1,5] = 11875, so-->


lenght = 6 -->
অর্থাৎ আমাদের ম্যাট্রিক্স মালটিপ্লিকেশন এর জন্য মিনিমাম cost = 15125. এখন আমরা যদি অর্ডার বের করতে চাই, যে কিভাবে আসলে আমরা মাল্টিপ্লিকেশনটি করলাম, এজন্য আমাদের আরো একটি 6x6 সাইজ এর অ্যারে লাগবে। এখানে আমরা প্রতিবার k এর কোন মানের জন্য মিনিমাম ভ্যালুটি নিচ্ছি, সেই k এর মান সেভ করে রাখবো।
যেমন আমরা length = 2 এর সময়, k = 1,2,3,4,5 পর্যন্ত নিয়েছিলাম। সেই অনুযায়ী মিনিমাম সাজালেঃ
আমরা এই অ্যারের নাম দিলাম s, এখানে আমরা k - partition এর নাম্বারগুলি সেভ রাখবো।
length = 3 এর জন্য, আমরা m[1,3] তে যেই মিনিমাম ভ্যালু রেখেছিলাম, সেটি ছিল k = 1 এর ভ্যালু। আমরা এরকম কিছু একটি পেয়েছিলাম-->

m[1,3] = m[1,1] + m[2,3] + p[0]*p[1]*p[3] = 0+2625+30*35*5 = 7875; k = 1
               m[1,2] + m[3,3] + p[0]*p[2]*p[3] = 15750+0+30*15*5 = 18000; k = 2

এখানে মিনিমাম ভ্যালু এর জন্য k = 1, কাজেই আমরা s[1,3] = 1 রাখবো। এভাবে length = 3,4,5,6 এর জন্য সাজালে আমাদের বাকি ঘরগুলি সাজায়ে আমরা ফাইনালি এরকম একটি ম্যাট্রিক্স পাবোঃ

অর্ডার প্রিন্ট (Order print)

আমরা এখন আমাদের ম্যাট্রিক্স এর মাল্টিপ্লিকেশন এর অর্ডারটি প্রিন্ট করবো। আমাদের অর্ডার ফাইন্ডিং এর অ্যালগরিদম ঃ



এভাবে আমরা পাবোঃ ( (A1) (A2 A3) ) ( (A4 A5) (A6) )
অর্থাৎ, এই অর্ডারে মাল্টিপ্লিকেশন চালালে আমরা মিনিমাম cost, এক্ষেত্রে 15215 পাবো।
MCM code:

প্র্যাকটিস প্রব্লেম (Practice Problems)



২ - পয়েন্টার টেকনিক (Two Pointer Technique)

কোন অ্যারেতে (সর্টেড) সাধারনত জোড়ায় জোড়ায় ভ্যালু খুঁজে বের করার একটি এফিশিয়েন্ট টেকনিক হল ২-পয়েন্টার। আমরা মূলত, কোন সর্টেড অ্যারেতে ২ বা তার বেশি জোড় বের করবো এমনভাবে, যেন তারা কোন কন্ডিশন মেনে চলে। যেমনঃ এমন ১ জোড়া ভ্যালু বের কর যাদের যোগফল X এর সমান হয়, অথবা বিয়োগফল, বা গুনফল ইত্যাদি।
প্রথমে একটি প্রবলেম নিয়ে আলোচনা করা যাক। আমাদের একটি সর্টেড (ছোট থেকে বড়) অ্যারে দেয়া আছে। এখান থেকে এমন একটি জোড়া বের করতে হবে, যাতে তাদের যোগফল X এর সমান হয়। এবং জোড়ার ২ টির ইন্ডেক্স একই হওয়া যাবেনা। আমরা কোড করলে অনেকটা এভাবে ২ টি লুপ চালায়ে করে ফেলবোঃ

এর কপ্লেক্সিটি O(n*(n-1)) যা অনেক বেশি। আমাদের আরও ভালো এপ্রোচ লাগবে। এখন দেখা যাক এই প্রব্লেমটার জন্য ২-পয়েন্টার কিভাবে কাজ করবেঃ

আমরা প্রথমে ২ টি পয়েন্টার সেট করবো। একটি হবে প্রথম ভ্যালুর জন্য, অপরটি হবে দ্বিতীয় ভ্যালুর জন্য। আমরা প্রত্যেকবার চেক করবো X এর সাথে ভ্যালু ২ টির যোগফল মিলে যাচ্ছে কিনা। যদি যোগফল X এর চেয়ে কম হয়, তাহলে আমরা প্রথম পয়েন্টারকে ডানদিকে বাড়াবো। যদি যোগফল X এর চেয়ে বেশি হয়, তাহলে আমরা দ্বিতীয় পয়েন্টারকে বামদিকে কমাবো। অনেকটা বাইনারি সার্চ এর মত কাজ করবে এই ২- পয়েন্টার। এবং আমাদের কন্ডিশন অনুযায়ী প্রথম এবং দ্বিতীয় ভ্যালুর ইনডেক্স সেইম হওয়া যাবেনা। ২ পয়েন্টার এর প্রথমটিকে আমরা 0 (এখানে অ্যারের প্রথম ইনডেক্স 0 ধরে ) এবং পরের পয়েন্টারকে আমরা অ্যারের শেষ ইনডেক্স দিয়ে ইনিশিয়ালাইজ করবো। কোডঃ

এর কমপ্লেক্সিটি হবে O(n)। এখন কিছু ভ্যারিয়েশন দেখা যাকঃ

১ম প্রব্লেম

২ টি সর্টেড অ্যারে(ভিন্ন ভিন্ন সাইজ) থেকে আমাদের এমন ২ টি এলেমেন্ট নিতে হবে (প্রত্যেক অ্যারে থেকে ১ টি), যাতে তাদের যোগফল X এর সমান বা ছোট (ম্যাক্সিমাম যোগফল, অর্থাৎ X এর কাছাকাছি হয়)।

আমরা প্রথম অ্যারেতে একটি পয়েন্টার এবং দ্বিতীয় অ্যারেতে আরেকটি পয়েন্টার সেট করবো। এখন প্রতিবার আমরা চেক করবো X এর সমান অথবা আমাদের ম্যাক্সিমাম সাম X এর কাছাকাছি কিনা, যদি না হয়, আমরা ইনডেক্স আপডেট করবো। এখন যদি সাম X এর চেয়ে কম হয়, তাহলে আমরা প্রথম অ্যারের ইনডেক্স বাড়াবো, নাহলে দ্বিতীয় অ্যারের ইনডেক্স বাড়াবো। এখানে প্রথম পয়েন্টারকে অ্যারের প্রথম ইনডেক্স এবং পরের পয়েন্টারকে অ্যারের শেষ ইনডেক্স দিয়ে ইনিশিয়ালাইজ করবো। কোডঃ


২য় প্রব্লেম

একটি ভিন্ন ভিন্ন (distinct) এলেমেন্ট এর অ্যারে থেকে এমন একটি ট্রিপলেট (তিন টি এলেমেনট এর জোড়া) বের করতে হবে, যাদের যোগফল শুন্য হবে।

২ জোড়ার জন্য আমরা যেভাবে করতাম, এটাও একইভাবে হবে, খালি এক্সট্রা একটি ভ্যালুর জন্য আমরা আগেই একটি ভ্যালু নিয়ে নিব। প্রথমে অ্যারেকে সর্ট করে ফেলবো। এরপরে আমরা আগের মতন যেভাবে জোড়া বের করতাম, একইভাবে এখানেও সেই কাজ করবো। এখানে আমরা একটি ইনডেক্স কে ফিক্সড করে, বাকি ইনডেক্স এর মাঝে ২ টি পয়েন্টার ঠিক আগের মতন করে সেট করবো। কোড দেখা যাকঃ


এখন এভাবে আমরা যেকোন একটি ট্রিপলেট পেলেই প্রোগ্রাম স্টপ করপে দিচ্ছি। যদি আমাদের বলা হয় যে এরকম যত ট্রিপলেট আছে তাদের দেখাও, তাহলে উপরের কোড এ সামান্য একটু পরিবর্তন করলেই আমরা সব ট্রিপলেট পেয়ে যাবো। আমরা লাইন ২১ এ রিটার্ন না করে, l++ এবং r-- করে দিবো। তাহলেই কাজ হয়ে যাচ্ছে।

৩য় প্রব্লেম

আমাদের যদি কোন ট্রিপলেট বের করতে বলে, যাদের যোগফল X এর সমান হবে, আমরা সেইম উপরের টেকনিক অনুযায়ী বের করে ফেলতে পারবো।

৪র্থ প্রব্লেম

এমন ট্রিপলেট বের কর, যাতে যেকোন ২ টির যোগফল, তৃতীয় টির সমান হবে।
এই সমস্যাটিও হুবহু আগের মতই কাজ করবে। আমরা প্রথমে একটি এলেমেন্টকে সেট করবো, এরপরে বাকি ২ টি এলেমেন্ট বের করবো যাতে তাদের সাম, সেট করা এলেমেন্ট এর সমান হয়। কোডঃ


২ - পয়েন্টারের প্রব্লেমগুলিতে আমরা ইনডেক্স কে একেকভাবে সেট করতে পারি, এটা আসলে যে কোড লিখছে তার উপর নির্ভর করে। তবে মূল আইডিয়া ঠিক থাকলে প্রব্লেম এর ফাইনাল আউটপুট সবসময় একই আসবে।

প্র্যাকটিস প্রব্লেম (Practice Problems)

Friday, January 19, 2018

C তে র‍্যান্ডম সংখ্যা জেনারেট (Producing Random Numbers in C)

আমরা প্রথমে srand() ফাংশন ব্যবহার করবো, যেটা randomizer কে seed করবে।মূল কথা হল, কম্পিউটার একটি র‍্যানডম নাম্বার তৈরী করবে এমন নাম্বার এর উপর ভিত্তি করে, যেটা srand() ফাংশন এর ভিতর seed হিসাবে দেয়া হবে।এখন আমরা যদি প্রতিবার একই সিড ভ্যালু দেই, তাহলে বারবার একই নাম্বার তৈরী হবে।তাই আমাদের আসলে এমন কিছু করা দরকার যাতে প্রতিবার আমাদের প্রোগ্রাম রান করলে সিড ভ্যালুটি একেকবার একেক রকম হয়। এজন্য আমরা time() ফাংশন ব্যবহার করবো।আমরা time() ফাংশন এর মাধ্যমে প্রতিবার আমাদের কম্পিউটার এর বর্তমান সময়কে সিড হিসেবে srand() এ পাস করবো এবং এর ফলে আমরা প্রতিবার প্রোগ্রাম রান করলে আলাদা আলাদা মান পাবো।




এখানে র‍্যানডম নাম্বার তৈরী হবে ঠিকি, কিন্তু আমরা যদি একটি নির্দিষ্ট রেঞ্জ এর মধ্যে নাম্বার চাই, তাহলে আমাদের
rand() কে মড ( modulus '%' ) করতে হবে। যেমন ঃ n % 3 = { 0 , 1 , 2 } এর মধ্যে যে কোন সংখ্যা হবে।
তাই আমরা যদি 0 থেকে n-1 পর্যন্ত সংখ্যার মধ্যে rand() করতে চাই, তাহলে rand() % n দিলেই কাজ হবে :)
0 থেকে n এর মধ্যে চাইলে, rand() % (n+1) or rand() % n + 1 দিলেই আমাদের কাজ শেষ।

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

Java MySQL DELETE (using Statement)

See also: MySQL XAMPP Connection for Java jdbc Program

Suppose we have folowing table:



Now we want to delete one record at a time by following:
  • Create a Java Connection to our MySQL database.
  • Create a SQL DELETE statement.
  • Then execute a Java Statement, using our SQL DELETE statement.
  • Close our Java MySQL database connection.
  • Finally catch any SQL exceptions using try-catch clause.


See also:
Reference

Java MySQL INSERT (using Statement)

See also: MySQL XAMPP Connection for Java jdbc Program

First suppose we have a table in out database named user. Or we can create a simple table like below:



Now we want to insert one record in this table. By following some steps we will do that.
  • Create a Java Connection to our MySQL database.
  • Create a SQL INSERT statement.
  • Then execute a Java Statement, using our SQL INSERT statement.
  • Close our Java MySQL database connection.
  • Finally catch any SQL exceptions using try-catch clause.


quey1 is passing direct values to the table. query2 is passing values through variables. Be careful about quote marks for executing queries.

See also:
Reference

Java MySQL SELECT (using Statement)

See also: MySQL XAMPP Connection for Java jdbc Program

Let's see the following table:



Now follow these steps:

  • Create a Java Connection to our MySQL database.
  • Define SQL SELECT statement.
  • Then execute the SELECT query, getting a Java ResultSet from that query
  • Now iterate over the ResultSet, getting the database fields (columns) from each row of data that is returned
  • Close our Java MySQL database connection.
  • Finally catch any SQL exceptions using try-catch clause.


See also:
Reference

MySQL XAMPP Connection for Java jdbc Program

First we will open our XAMPP server.





Then type localhost/phpmyadmin/ in the browser. After that we will create our database. After that, see below java code for setting up connection for the database.

Java Database Connectivity (JDBC) is an application programming interface (API) for the programming language Java, which defines how a client may access a database. It is Java based data access technology and used for Java database connectivity. It is part of the Java Standard Edition platform, from Oracle Corporation.




"jdbc:mysql://localhost:3306/newdatabase" ; here 3306 is the port number for XAMPP server and newdatabase is the name of our database.

Remember : First create the database, otherwise it won't connect simply by coding
These parts seem ok, but you will get error if you didn't add the appropriate library(ies) to the project using Netbeans's library facility. So, let's see how we can do that :
  • First Right-click on the project's root node in the Projects tab.
  • In the pop-up context menu, click on Properties (on the bottom of the menu).
  • Click on Libraries under Categories:. You should see the following screen:



  • Click on the Add Library...
  • Under Global Libraries click on MySQL JDBC Driver and then click the Add Library button. (If you don't have library named MySQL JDBC Driver, then simply download it from internet)
  • Finally Click on OK.
If you need a specific version of the driver, you can download it, and then after clicking on Add Library... you can click on Create... to add the downloaded version to your library repository. You'd then remove the default JDBC Driver from the project, and add the library containing the specific version.
Following these steps properly will be enough for you to access your database.
See also:
 Reference

Java UDP (Transfer Any Types & Size of File)

In my previous post, I wrote about how to transfer files from one location to another using UDP connection for client server model. There was a limitation of how much size of data can be passed. Now I will discuss about how to pass any types and size of data using UDP connection.

As the file is larger, we can't send the file simply by using DatagramPacket with the help of our byte array. So what we need to do is that we will first divide the full file into some chunks or small size of byte array, say 1024 bytes each. Then we will count how many byte array is required to transfer the file fully. Then we will use a loop to send all the chunks serially.






We created a DatagramSocket ds, DatagramPacket out, byte array snd of size 1024. We created a File f1 and gave the location of the file to be transfered. Now for getting how many packets are required to transfer the file fully, we divided the file by the length of our byte array. So no_of_pkt will hold how many packets are needed to be sent. We then simply send the value to the server to let the server know that, the next file it will receive, will have no_of_pkt number of packets that are to be transfered.






We created a FileInputStream ff to transfer the packets at a time to the server. Inside the loop, we just created byte array of size 1024 each time of sending a new packet. The server will gradually receive these packets one at a time.

Thread.sleep(10L): Pausing Execution with SleepThread.sleep causes the current thread to suspend execution for a specified period. This is an efficient means of making processor time available to the other threads of an application or other applications that might be running on a computer system. We need this as we have many packets to be send, we will consider each of the sending process as a new different thread.
The server will also receive packets with the same loop stated above and gradually write them in a new file.

Sometimes server can't write all the packets. Packets may loss at the time of transfering process. Client will send all the packets but because server can't get all the data ( approximately 10-20% loss ) we need to wrap our whole program in a try-catch for exception. As each time we are sending and receiving new FileStream, we need to check whether they contain data from the previous packet or not. If they have data from the previous packet, then these types of data loss occurs. We need to handle it accordingly. Simply nullifying the Stream before each packet ( both sending and receiving ) will help.

Java File Transfer Using UDP Connection

What is UDP ?

User Datagram Protocol (UDP) is part of the Internet Protocol suite used by programs running on different computers on a network. UDP is used to send short messages called datagrams but overall, it is an unreliable, connectionless protocol. Basically a client will throw something to the server. And then, the server may or may not take the file, do something to that file and then may or may not send the file to some client. Unlike TCP connection, UDP doesn't need to establish connection between server and client before handling any kind of transfer.

What we will do :
  1. Create two new project: one for Server, another for Client
  2. Server will show client specific file items in a specific directory
  3. Client will then request the server to download a file from that directory by inserting the file name
  4. Server will then find the file in the directory, make a copy of it in another desirable directory
  5. Close socket
Client Part:


First, we create a public class named UDPClient under UDPClient project. The port number is where (Server) we will send our data. Scanner will be used to take user input for the filename.
A DatagramSocket is the sending or receiving point for a packet delivery service. Each packet sent or received on a DatagramSocket is individually addressed and routed. Multiple packets sent from one machine to another may be routed differently, and may arrive in any order. We created a DatagramSocket named ds.

DatagramPacket is used to implement a connectionless packet delivery service. We created two DatagramPacket named outdata (for sending packet to server), indata(for receiving packet from server).

byte array is required to get the data from the packet as bytes. So we also created them.
Java InetAddress class represents an IP address. The java.net.InetAddress class provides methods to get the IP of any host name. We will get localhost for this purpose.


Now we know that server doesn't know anything about client unlike TCPconnection where firstly connection in established between server and client. So to get our server know about the client, we will send something to server from our client program. I sent address and port number ( it's not necessary, but i did it anyways :P ).
outdata is the DatagramPacket and it takes 4 parameters as input. Serially they are:

#Byte array where the data is stored
#Length of the byte array
#Address of the client
#Port number of the client


Now server knows client's port and address. So from the server (we will discuss it later), some specific file names from specific directory is sent to the client as packet and client will now receive that packet in indata, the DatagramPacket we declared earlier. For receiving a packet only byte array name and length is required, in which we will store our packet. Then converting into string, we simply print out the file names in the screen for the client to choose which file should be downloaded.


String fname will contain the user input file name and we will send it to the server via packet like we did at the first time.




Now after the server get the file name for download, server will send that as a packet and client will receive the file and write it in client's desired path.
public class BufferedWriter extends Writer. Writes text to a character-output stream, buffering characters so as to provide for the efficient writing of single characters, arrays, and strings. We used BufferedWriter to write out the file.
In java, FileOutputStream is a bytes stream class that's used to handle raw binary data. To write the data to file, you have to convert the data into bytes and save it to file.
An OutputStreamWriter is a bridge from character streams to byte streams: Characters written to it are encoded into bytes using a specified charset . ... Each invocation of a write() method causes the encoding converter to be invoked on the given character(s).
Finally we will close the socket.
See the sample code below for UDPClient. Next we will  talk about the server part.

Server Part:




Same as client code before, we declared DatagramSocket, Server needs the address and the port number of the client that is trying to connect with it. So we will get the address and port from the client's file using getAddress() and getPort() method.



Now we have just received the packet here and printed the result. With this server got the address and port number of the client ( So, later server can send packet to the address of the client willingly ).




Now, server will send the file names from the directory. String dirname contains the path of the directory. Then we created a File named f1 to get the files from dirname and then created an array direct[] to contain the list of all the files from f1. Then with some coding we got our file names and send it to the client as packet.



Now, server will get the file name for downloading from the client. String fname holds the file name to be downloaded. Then we check whether the file exists in the direct[] or not. If we find matching, then we preserve the index of the file. Then, File copy = new File(direct[idx].getAbsolutePath()); it will contain the path of the desired file. Then with the help of BufferedReader, we will write the file in String s, and then convert it to bytes for packeting, then we will send it to the client. Finally client will then rewrite the file in it's desired directory which we have already seen above.
Here is the code for UDPServer. Thank you for reading patiently.

Now, let's see how to transfer any size of file here.

Simple Project (Data Structure)

আমরা এখন একটি student management টাইপ সিস্টেম নিয়ে কথা বলবো। প্রোজেক্ট টি খুব ই সিম্পল। যাদের নূন্যতম ডাটা স্ট্রাকচার নিয়ে জ্ঞান আছে, তারা আশা করি খুব সহজে বুঝতে পারবে কোড এ কি করা হয়েছে। যেসব ফাংশন ব্যবহার করা হয়েছে তার কিছু নিচে বলা হলঃ
কোড ঃ 


struct info ডাটা টাইপ এ আমার যেসব ইনফরমেশন দরকার তা ভ্যারিয়েবল আকারে লিখে রাখলাম, এটা আসলে কোডার এর উপর নির্ভর করে যে কিকি টাইপ ডাটা নিয়ে প্রোগ্রাম টা কাজ করবে। এটা একটা স্ট্রাকচার টাইপ ডাটা টাইপ।
struct node টাইপ এর একটা ডাটা টাইপ এ নাম এবং সিজিপিএ ( CGPA ) রেখে কাজ করবো যাতে পরবর্তীতে আমরা CGPA এর উপর ভিত্তি করে নাম গুলো সর্টেড আকারে আউটপুট দেখাতে পারি।
cmp( node p, node q ) একটা compare টাইপ ফাংশন যার কাজ হচ্ছে স্ট্রাকচার এর ভিতরের ডাটাগুলো compare করে ঐ অনুযায়ী আউটপুট দেখানো।
void option() আমি আমার প্রোগ্রামটি রান করার সময় user দের কি show করবো তার একটা সিম্পল ডেমো।
void show_data(item *root) নতুন নতুন ডাটা ইনসার্ট এর সময় আমি লিংক লিস্ট আকারে ইনসার্ট করেছি, তাই একেকটা নোড ( স্ট্রাকচার ) এর যাযা ভ্যারিয়েবল এ যাযা ডাটা ছিল তা একবারে দেখানোর জন্য এই ফাংশন।
void show_all() যতগুলি ডাটা ইনসার্ট করা হয়েছে তা সিরিয়ালি সব দেখানো।
void inserting() ডাটা ইনসার্ট করা।
void deleting() ডাটা ডিলিট করা।
void updating() ডাটা আপডেট করা।
void searching() নামের উপর ভিত্তি করে ডাটা সার্চ করা। ( লিংক লিস্ট এর ব্যাসিক সার্চিং )।
void show_cgpa() এখানে নাম এবং CGPA লিংক লিস্ট থেকে struct node টাইপ একটি অ্যাারে calc [ ] এর মধ্যে রেখে STL এর sort ( ) ফাংশন ব্যবহার করে আউটপুট অ্যাারেটা কনসোল এ দেখানো হয়েছে।

Matrix Exponentiation

Where there is recurrence , there is Matrix Expo.

We use matrix expo to calculate very large number, terms of the recurrence where even DP can't help us to pre-calculate the result.

You are all requested to read this blog  Matrix Expo  for understanding the matrix exponentiation.
Here is a sample code for generating Fibonacci numbers.



Note: For different types of recurrence , the base matrix will change accordingly. We have to generate this base matrix carefully , else every other things are pretty much same.

Sample Input/Output (I/O) for Programming contest (for beginners)

Programming contest বা Online OJ তে প্রব্লেম সাবমিট করার জন্য কিছু নিয়ম আছে। তার কিছু এখানে তুলে ধরা হলঃ

১। Main function int main() দিয়ে শুরু করা ভালো, void main() ব্যবহার করার চেয়ে। কোনো কোনো কম্পাইলার error দেয় void main() ব্যবহার করলে। কাজেই যেহেতু আমরা জানি না আমাদের কোড কোন কম্পাইলার এ চালানো হবে, কাজেই void main() ব্যবহার না করাই ভালো। প্রতি প্রোগ্রাম শেষে return 0; লিখা ভালো অভ্যাস।

২। প্রগ্রামিং কন্টেস্ট এ শুধু #include<conio.h> ব্যবহার করা যাবেনা। কাজেই clrscr(), getch() এসব ব্যবহার করা যাবে না।
C তে কোড করলে C99 এ যেসব header file সাপোর্ট করে সেসব ব্যবহার করা যাবে, কিন্তু যেহেতু #include স্ট্যান্ডার্ড header file না, তাই এটা লিখা যাবে না। String reverse এর ক্ষেত্রে কেউ যদি strrev ব্যবহার করে তাহলেও CE ( Compilation Error ) হবে,কারন এটাও C99 স্ট্যান্ডার্ড header file এর ফাংশন না। এরকম আরও অনেক কিছু আছে, এসব প্রোগ্রাম করতে করতে শিখা হবে। আর একটা কথা হচ্ছে কোন key word এর নাম ভুলেও variable নাম হিসাবে ব্যবহার করা যাবেনা, এতে প্রোগ্রাম run ই করবে না।

৩। কন্টেস্টের প্রশ্নে ইনপুট নেয়ার ক্ষেত্রে যদি কতবার ইনপুট নিতে হবে তা না বলা থাকে তাহলে scanf ("%d", &a) এর বদলে while(scanf("%d",&a)!=EOF ) ব্যবহার করতে হবে।
exp: problem: find a+b.
solve:
#include
int main () {
int a, b, sum;
while (scanf ("%d %d", &a, &b) != EOF) {
sum = a + b;
printf ("%d", sum);
printf ("\n");
}
return 0;
}

৪। new line এর ব্যাপারে সতর্ক থাকতে হবে।ঠিকমত লাইন প্রিন্ট করতে নয়া পারলে PE ( Presentation Error ) দিবে এবং প্রব্লেম এর আউটপুট এ ঠিক যেভাবে প্রিন্ট করতে বলা হবে একদম সেভাবেই প্রিন্ট করতে হবে, একটা দাড়ি, কমা ও কমবেশি দেয়া যাবেনা।

৫। প্রগ্রামিং কন্টেস্ট এর প্রশ্নে sample ইনপুট আউটপুট দেয়া থাকে। কিন্তু ওটা দেখেও অনেক সময় কিভাবে আউটপুট দিতে হবে বোঝা যায়না। যেমনঃ

Problem Description: I have a very simple problem for you.
Given two integers A and B, your job is to calculate the Sum of A + B.

Input: The first line of the input contains an integer T(1<=100). Then T lines follow each having two integers A & B.

Output: For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case.
The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces in the equation.
Output a blank line between two test cases.

Sample Input:
2
1 2
3 10

Sample Output:
Case 1:
1 + 2 = 3
Case 2:
3 + 10 = 13

( এখানে Case 1: দেয়ার পরে কোন space না দিয়ে একটা new line ( '\n' ) দিতে হবে। পরবর্তী লাইন এ 1 + 2 = 3 দিতে হবে অবশ্যই অর্থ্যাত ঠিকমত space দিতে হবে যেভাবে আউটপুট এ চাওয়া হয়েছে। প্রত্যেকটা আউটপুট এর পরে একটা করে new line দেয়া লাগবে। যদি বলা থাকে পরপর test case এর মাঝে blank line or new line দিতে হবে, তাহলে আরও একটা new line প্রিন্ট করতে হবে। আর সবার শেষ test case এর জন্য কোন blank line or extra new line প্রিন্ট করা যাবেনা )
কোড ঃ

#include
int main () {
int tc, t;
scanf ("%d", &t);
for (tc = 1; tc <= t; tc++){
int a, b;
scanf ("%d %d", &a, &b);
printf ("Case %d:\n%d + %d= %d\n", tc, a, b, (a + b));
if (tc < t) printf ("\n");   // Output a blank line between two test cases
}
return 0;
}


কিছু verdict সম্পর্কে লিখা হল। এগুলা UVA থেকে কপি পেস্ট করা :)


Accepted (AC) (and the CPU time & memory used): OK! Your program is correct!. Note that during true contest perhaps only 1 CPU minute will be allowed If your program spends a reasonable time, it may be ok, but this depends on the judge power in comparison with the true contest computers.

Presentation Error (PE): Your program outputs are correct but are not presented in the correct way. Check for spaces, justify, line feeds...

Accepted (P.E.): Same as above, but the Presentation Error is intended only for contests. The 24-hours judge takes it only as a warning. Don't worry a lot, since many of our problems have the output specification not very fine.

Wrong Answer (WA): Correct solution not reached for the inputs. The inputs and outputs that we use to test the programs are not public (it is recommendable to get accustomed to a true contest dynamic.

Crash - Run time Error (RTE): Your program failed during the execution (segmentation fault, floating point exception...). The exact cause is reported to the user.

Time Limit Exceeded (TLE): Your program tried to run during too much time; this error don't allows you to know if your program would reach the correct solution to the problem.

Memory Limit Exceeded (MLE): Your program tried to use more memory than the judge default settings. If you are sure that such problem needs more memory, please contact us.

Output Limit Exceeded (OLE): Your program tried to write too much information. This usually occurs if it goes into a infinite loop.

Restricted Function (RF): Your source program tried to use a not allowed function (such as fork(), fopen(), ...)

Compile Error (CE): The compiler (gcc/g++/gpc) could not compile your ANSI program. Of course, warning messages are not error messages. The compiler output messages are reported you by E-Mail.

Submission Error (SE): You don't specified correctly the @JUDGE_ID fields (a incorrect User ID, number of problem...).

Can't Be Judged (CJ): The judge hasn't test input and outputs for the selected problem. While choosing a problem be careful to ensure that the judge will be able to judge it!.

Access Denied (AD): Your Internet address is not allowed to submit problems. Maybe you have setup to accept programs only from your E-Mail address: edit and update your personal information in the Web. Otherwise, contact us.

Non Authenticated (NA): Your E-Mail is not authenticated or the submit tool did not sent authentication information. If you aren't a hacker, please contact us.

Out Of Contest Time (OC): this message can only appear during a contest, if a program is submitted out of contest time.

Delayed (DL): if the judge host is too busy, the execution of programs which spent too much resources (inside the allowed limits) is delayed by some seconds or minutes. Don't re-submit again your program (the judge would spent even more time before replying).

শেষ কথা ঃ
 কন্টেস্ট এ participate করলে অনেক কিছু শিখা হয়ে যাবে আপনাআপনি। প্রথম প্রথম অনেক ভুল হবে, কিন্তু আস্তে আস্তে সবকিছু ঠিক হয়ে যাবে। আমার একটা experience শেয়ার করি ঃ
আমি যখন ভার্সিটির ১.১ এ ছিলাম তখন আই ইউ টি ( IUT ) তে national ict fest এ আমার ২ বন্ধু নিয়ে কন্টেস্ট করতে যাই, পারতাম না কিছুই, খালি ভার্সিটি স্লট পাইছে, তাই গিয়েছিলাম -_- । যাহোক, ওইখানে গিয়ে ৫ ঘন্টা আমরা খালি সেলফি তুলছি, বাঁকা করে কী-বোর্ড এর পিক ও তুলছি,  ওইটা আবার অনেকদিন ফেইসবুক এর কভার পিক ও দিয়ে রাখছিলাম, যাহক, কন্টেস্ট এর টাইম এ একটা প্রব্লেম, যেইটা give away টাইপ প্রব্লেম ছিল ( give away : একদম বিগিনারদের পারার জন্য সবচেয়ে easy যেই প্রব্লেম দেয় ওইটা )। তো, ওইটা আমরা সুন্দর সল্ভ করলাম, সাবমিট দিলাম ,verdict আসলো RTE -_- । এরপরে আমরা আরও অনেকভাবে কোড করলাম, সবকিছু ওকে, কিন্তু সাবমিট দিলেই RTE। আসলে ভুল টা ছিল যে array এর সাইজ ১০^৭ পর্যন্ত হতে পারবে, আমরা main () ফাংশন এর ভিতরে ১০^৭ সাইজ এর অ্যাারে ডিক্লার করেছিলাম, কিন্তু এটা যদি গ্লোবালি ডিক্লার করতাম, তাইলেই AC পাইতো :( । তখন ও ক্লাস এ লোকাল গ্লোবাল ভ্যারিয়েবল ডিক্লার পড়ায় নাই,তাই ব্যাপারটা আসলে জানতাম না। পরে কন্টেস্ট শেষে শাকিল ভাইয়ার কাছে শুনার পরে নিজেকে বড় মাপের ছাগল মনে হইতেছিল। সবচেয়ে মজার ব্যাপার হল, আমরা প্রব্লেমটা সাবমিট দিছিলাম মোট ৩৯ বার এবং প্রত্যেকবার verdict ছিল RTE। আর সন্ধ্যায় পুরষ্কার দেবার সময় ( may be কায়কোবাদ স্যার ছিলেন, ঠিক মনে নাই ) আমাদের কথা উনি বলছিলেন যে "একটা টীম A নম্বর প্রব্লেমটা ৩৯ বার সাবমিট দিছে, তারা একদম শেষ পর্যন্ত সাবমিট দিয়ে গেছে, কন্টেস্ট এর মাঝে তাই হাল ছাড়তে নেই।" ( আমি তো লজ্জায় শক্ত হয়ে বসে ছিলাম না জানি টীম এর নাম বলেন , যাহোক উনি ভালো মানুষ, নাম বলেন নাই, আরো অনেক inspirational কথাবার্তা বলেছেন, ওইগুলা এখন আর মনে নাই :( )
কাজেই, আজকে ভুল করা মানে এই না যে আগামীতেও ভুল করবা, আমি ফাঁকিবাজ মানুষ, তাই ঠিকমত কন্টেস্ট continue করিনাই, কিন্তু তোমরা যারা নতুন, তারা আশা করি আমার মত ভুল করবা না :) ।

Best of luck and happy programming <3.

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.