CodeChef Hints: January long 2018

Rectangle: Given four integers abc and d, we have to determine if there’s a rectangle such that the lengths of its sides are abc and d (in any order) .

Solution: The easiest problem of this set. We just need to find 2 unique integer each having frequency 2. Or only a single integer having frequency 4, in case it is a square (also a rectangle).

Maximum Score: Given N integer sequences, each sequence having N integers, we need to find the maximum number we can get by taking only a single element from each sequence so that, element of i-th sequence is strictly greater than element of (i-1)-th sequence.

Solution: We will solve this in reverse order. First think, if we need to make out score maximum, we should always take the maximum number of the last sequence. After that we will take integer strictly less than that one from previous sequence. Say we have sequence:
1, 2, 10
9, 5, 12
2, 12, 8
We will take values from last sequence. First we took 12, maximum value of the last sequence. Then we come to previous sequence. We need to take value from this sequence which is strictly less than 12. Simple binary search using lower bound technique will give us the index of our desired value. If no such index is present then there is no solution. If you don’t know about lower bound, look here. Of course we need to sort every sequence for this too.

K-Concatenation: Given an array A of size N, we need to make K copies of the array using concatenation of the array values, and then find the maximum subarray sum of that final array.

Solution: As N and K is so big, we can’t simply concate  A by K times and then find the maximum subarray sum. So, what we can do? we can observe somethings.

First observation: If summation of every element of the array is positve, then the result is summation of all the elements * K

Second observation: If all elements are negative, then the answer is the greatest number of all the elements.

Third observation: If there are mixed elements, then we can find largest subarray sum in 1-D space using Kadane’s algorithm. Now for using Kadane, there is some observations too. If K == 1, we have simply array A, and with the help of Kadane, we can easily find largest subarray sum from there. Notice, if K > 2 what should we do? As we have mixed elements, no matter how large K is, only concatening 2 times is enough for us to find the largest sum. Ok, why 2 times? See a case A = 1 -2 1 and K = 4 suppose, then we get
1 -2 1 1 -2 1 1 -2 1 1 -2 1 ; if we use Kadane here, we will get 2 as our maximum sum.
1 -2 1 1 -2 1 ; if we use Kadane here, we will also get 2. As we are concatening, each time a new concatenation arises, it depends on the previous structure also. So by concatening 2 times, we will get what, by concatening K times, we will get same result.

Final observation: It is the most important of all. Notice these case:  
A = 1 1 -9 2 3 4, K =  3, so, we get:
B = 1 1 -9 2 3 4 1 1 -9 2 3 4 1 1 -9 2 3 4

Now, we will check first observation: total sum of A = 2, as K = 3 times, so we get = 6. We will store this value to storage1.

Now, for second observation, all elements are not negative, so we will store a big negative number like -9999999999999…. to storage2.

Third observation, as there are mixed elements, we will use Kadane’s algo to find maximum subarray sum for 1 1 -9 2 3 4 1 1 -9 2 3 4  . And that is 11. So, storage3 = 11.

But let’s see our final array : 1 1 -9 2 3 4 1 1 -9 2 3 4 1 1 -9 2 3 4; If we take this subarray, we get 13. So this is the final observation of this problem. We need to find two maximum values of our initial array A. We will call it forward_max and backward_max.
forward_max = 1 1 -9 2 3 4 = 9
backward_max = 1 1 -9 2 3 4 = 2
So, our storage4 will be = forward_max+ S*(k-2) + backward_max ; S = summation of array A = 2
As, we took forward_max of our first part, backward_max of our last part, we are left with K-2 parts between. so we need to take all the remaining K-2 parts sum. Also notice, for final observation, K should be > 2

Our final result will be maximum of all the four storages 🙂

Partition the numbers: Given N and X, we need to partition N numbers in such two sets, that both set will have equal sum after subtracting X from N elements(consider elements from 1 to N).

Solution: First we will calculate summation of N elements using series sum formula: N*(N+1)/2 . Now subtract X from this sum. So, sum = N*(N+1)/2 – X.
Now, if sum is odd then there is no solution, as we can’t make an odd number partitioned in two disjoint sets. Also if N <= 3, there is no solution.

Now, when sum is even, we will make sum/2 using our 1 to N numbers without X. We will iterate from N to 1, each time we will check if needed sum is getting zero or not. if we can subtract a value, we will do that, and mark that value as set 1. One important thing is to notice that, while subtracting an integer, we need to check if the remaining sum can be represented by other available integers or not. There is may approach to solve this problem. Implement it however you want keeping some corner case in mind.

String Merging: You are given two strings A and B with lengths N and M respectively. You should merge these two strings into one string C with length N+M. Specifically, each character of C should come either from A or B; all characters from A should be in the same relative order in C as in A and all characters from B should be in the same relative order in C as in B.

Solution: This is a simple dynamic programming problem. Greedy solution won’t help you there. What we need to do is simply find the longest_common_subsequence of String A and B. Then our result would be M + N – LCS(A,B). But first, finding LCS between A and B we need to modify A and B string in such a way that no same character right beside each other. If A = “aaaxyyyzza”, we need to modify it as “axyza”, as there is no same character right after one character. Then we will perform LCS operation in our modifued string and get the final result.

 

Advertisements

Calculate Summation of GCD(i,n); for i = 1 to n

আমাদের এবারের কাজ হল ১ থেকে n পর্যন্ত সবগুলো সংখ্যার সাথে n এর গ.সা.গু. বের করে তাদের যোগফল বের করা।
শুনতে ব্যাপারটি সহজ মনে হলেও, আসলে ঠিক সহজ না, যদি না আমরা সঠিক এপ্রোচ না জানি। নরমালি আমরা যখন প্রোগ্রামিং এ নতুন, তখন আমরা ১ থেকে n পর্যন্ত লুপ চালায়ে তাদের যোগফল বের করতাম।


এখন কথা হচ্ছে, এভাবে করলে আমরা বড় বড় সংখ্যার জন্য আমরা TLE খাবো। যেমন n = 1000000000 এর জন্য আমাদের প্রচুর সময় লাগবে, ( ইচ্ছে করলে উপরের কোডটি নিজ দায়িত্বে রান করে দেখে নিতে পারো :3 )

এখন তাহলে আমরা কিভাবে এর সমাধান করবো? খেয়াল করলে দেখবো যে, আমরা যখন ১ থেকে n পর্যন্ত স্বাভাবিক সংখ্যাগুলোর সাথে n এর গসাগু বের করার চেষ্টা করছি,তখন আসলে আমরা প্রতিবার n এর সবগুলো বিভাজক( all divisor ; there maybe multiple occurance of divisors) নিয়ে তাদের যোগফলটা নিচ্ছি। যেমনঃ  n = 8 হলে, gcd(1,8) + gcd(2,8) + gcd(3,8) + gcd(4,8) + gcd(5,8) + gcd(6,8) + gcd(7,8) + gcd(8,8)  = 1+2+1+4+1+2+1+8 = 20।
এখানে খেয়াল করে দেখি যে, আমরা কিন্তু ১,২,৪,৮ ছাড়া আর কিছু যোগ করছিনা! আর এই সংখ্যাগুলি কিন্তু আসলে ৮ এর বিভাজক (divisor)। আমরা আপাতত গোনায় বাদ রাখলাম কোন সংখ্যা কতবার নিচ্ছি, কিন্তু আসল কথা হচ্ছে আমরা n এর divosr গুলিকেই নিচ্ছি আমাদের ক্যাল্কুলেশন এর জন্য। তাহলে বুঝা যাচ্ছে আমাদের আসলে n এর divisor গুলি বের করতে হবে। আর আমরা O(√n) কমপ্লেক্সিটি তে n এর divisor বের করতে পারি। কাজেই, n = 1000000000 এর জন্য আমরা 31622.77.. কমপ্লেক্সিটিতে divisor গুলি বের করে, এরপরে আমাদের বাকি কাজ করবো।

তাহলে  n = 8 এর জন্য, আমাদের যোগফল অনেকটা এরকম হবে দেখতেঃ

\sum _{ i=1 }^{ 8 }{ gcd(i,n) } = coef1*(1)+coef2*(2)+coef3*(4)+coef4*(8)

এখানে coef1,coef2… এগুলোই আমাদের বের করতে হবে। divisor গুলি আমরা আগেই পেয়ে গেছি।
১ থেকে n পর্যন্ত সংখ্যাগুলোর সাথে n এর গ.সা.গু. বের করতে গেলে,গ.সা.গু = ১ কতবার আসবে, সেই সংখ্যাটা আসলে n এর অয়লার ফাংশন। অয়লার ফাংশন সম্পর্কে না জানলে এই লিঙ্ক দেখার অনুরোধ রইল আগে।
আচ্ছে এখান থেকে আমরা একটু মনযোগ দেয়ার চেষ্টা করি, 

phi (8) = 4.
phi (4) = 2.

phi (2) = 1.
phi (1) = 1.
আমরা এখানে আসলে ৮ এর divisor গুলির phi এর মান দেখলাম।
আচ্ছে এখন দেখা যাক, phi(8) = 4 এর জন্য, কোন কোন জোড়া নিলে আমাদের গসাগু ১ আসছেঃ
(1,8), (3,8), (5,8), (7,8); কাজেই, আমাদের coef1 = 4 হবে। ( coef1*(1); এই 1 এর মানে হচ্ছে, ঐসব জোড়া আমরা নিবো, যাদের মাঝের গ.সা.গু. = 1 হবে, এরকম জোড়া আছে 4 টি, কাজেই আমাদের coef1 = 4 )
এখন আমরা বের করবো coef2 এর মান। কাজেই আমাদের বের করতে হবে এমন কতটি জোড়া আছে, যারা 8 এর সাথে গ.সা.গু.  = 2 হবে। এজন্য আমাদের দরকার phi(8/2) = phi(4) এর মান। আমরা আগেই বের করে রেখেছি, phi(4) = 2. কাজেই আমাদের coef2 = 2. একইভাবে, coef3,coef4 বের করতে পারবো আমরা। ফাইনালি,

coef1 = phi(8/1) = phi(8) = 4. ; divide by first divisor = 1.
coef2 = phi(8/2) = phi(4) = 2. ; divide by second divisor = 2.
coef3 = phi(8/4) = phi(2) = 1. ; divide by third divisor = 4.
coef4 = phi(8/8) = phi(1) = 1. ; divide by forth divisor = 8.

কাজেই, আমাদের ফাইনাল রেজাল্ট ঃ
phi(8/1)*1 + phi(8/2)*2 + phi(8/4)*4 + phi(8/8)*8
= 4*1 + 2*2 + 1*4 + 1*8 = 20
 

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

without pre computing phi values:


এখন আমাদের অনেক কুয়েরি থাকলে আমাদের আগে থেকে phi এর মান বের করে রাখতে হবে। ঐ ব্যাপারটা তোমরা নিজেরা করে দেখো। আবার যদি আমাদের n এর মান অনেক বড় হয়ে যায় যে, আমরা O(√n) এও TLE খাচ্ছি, তাহলে আমাদের number theorem এর অন্যরকম এপ্রোচ নিতে হবে। এগুলো নিয়ে পরে আলোচনা করা যাবে। 

Euler’s Totient or Phi Function φ(n)

phi ফাংশন কি?

phi ফাংশন একটি arithmetic function যেটি count করে একটি সংখ্যা N এর সমান বা ছোট কতটি ধনাত্মক সংখ্যা আছে যেগুলো N এর  সহমৌলিক (relative prime). অর্থাৎ 1 থেকে শুরু করে N পর্যন্ত মোট কতটি সংখ্যা আছে যেগুলোর সাথে N এর 1 বাদে অন্য কোন সাধারন উৎপাদক (common divisor) নেই, আরেকটু সহজ করে বলতে গেলেঃ 1 থেকে N এর মাঝে, যাদের সাথে N এর GCD = 1. উদাহরন :
15 সংখ্যাটি বিবেচনা করি,

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
এর মধ্যে থেকে 15 এর সাথে common divisor আছে এমন সংখ্যাগুলোকে মার্ক করিঃ
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

এই সংখ্যাগুলিকে বাদ দিবো, কেননা 15 এর গুননীয়ক ঃ 3 এবং 5. কাজেই, এদের গুনিতক (3, 5, 6, 9, 10, 12, 15) এগুলো বাদ যাবে।
তাহলে অবশিষ্ট থাকে টি সংখ্যা – 1, 2, 4, 7, 8, 11, 13, 14
সুতরাং, φ( 15 ) = 8.

এখন চিন্তা করি, মৌলিক সংখ্যার জন্য phi এর মান কত হবে?
খেয়াল করলে দেখবো যে, আসলে কোন মৌলিক সংখ্যার সাথে তার আগের সকল সংখ্যাই সহমৌলিক, অর্থাৎ এদের মাঝে ১ ছাড়া আর কোন গুননীয়ক নেই। অর্থাৎ, φ(প্রাইম) = প্রাইম – ১

7 সংখ্যাটি একটি prime number. তাহলে 7 এর জন্য,
1, 2, 3, 4, 5, 6, 7
so, φ(7) = 7-1 = 6.
so, φ(prime) = prime-1

মৌলিক সংখ্যার ক্ষেত্রে কাজটা অনেক সহজ হলেও অন্যান্য ক্ষেত্রে কিছুটা জটিল। এজন্য আমাদের একটি Theorem জানতে হবে। সেটি হলঃ

φ( i*j ) = φ( i ) * φ( j ), when i and j is relatively prime

এর জন্য, আমাদের i এবং j, উভয়কেই সহমৌলিক হতে হবে। এখন খেয়াল করি, আমরা যদি, i এবং j কে এমনভাবে নিয়ে আসতে পারি, যে তারা উভয়েই প্রাইম হবে, অর্থাৎ যেকোন সংখ্যাকে আমরা প্রাইম এর ফ্যাক্টরে নিয়ে আসতে যদি পারি, তাহলে আমাদের জন্য φ(prime) = prime-1 দিয়ে প্রতি প্রাইম ফ্যাক্টর এর phi বের করা খুবি সহজ, এবং সেখান থেকে φ( i*j ) = φ( i ) * φ( j ) এই ফর্মুলার মাধ্যমে আমরা প্রাইম ফ্যাক্টর থেকে প্রাপ্ত phi এর মান গুন করে দিলেই মূল সংখ্যার phi এর মান পেয়ে যাবো। উদাহরনঃ

φ( 30 ) = φ( 2 ) * φ( 3 ) * φ( 5 )
now, φ( 2 ) = 1, φ( 3 ) = 2, φ( 5 ) = 4.
so, φ( 30 ) = 1 * 2 * 4 = 8

অর্থাৎ 1 থেকে 30 এর মাঝে, 30 এর সাথে সহমৌলিক 8 টি সংখ্যা আছে।
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
এগুলো হলঃ 1, 7, 11, 13, 17, 19, 23, 29 (Total 8 numbers).

এখন ধরা যাক, আমরা 4-এর φ ফাংশনের মান বের করতে চাই। আমরা এখন পর্যন্ত যা জানি, তা অনুযায়ী,

 φ(4) = φ(2)*φ(2) = 1*1 = 1.

কিন্তু ,
GCD(1,4) = 1, রিলেটিভলি প্রাইম
GCD(2,4) = 2
GCD(3,4) = 1, রিলেটিভলি প্রাইম
GCD(4,4) = 4
অর্থাৎ, φ(4) = 2

এটি কিন্তু আমাদের ফর্মুলা অনুযায়ী মিলেনি। তাহলে আমরা এখান থেকে একটি জিনিস খেয়াল করতে পারি যে, যখন আমাদের প্রাইম ফ্যাক্টরের ঘাত (power) ১ হবে, কেবলমাত্র তখনি আমরা আমাদের উপোরক্ত ফর্মুলা ব্যবহার করতে পারবো। তাহলে এরকম ক্ষেত্রে আমাদের ফর্মুলার একটু পরিবর্তন আসবে এভাবে ঃ
φ( n) = n– nk-1 , when n is prime and k != 1.

তাহলে আমরা এতক্ষনের আলোচনা থেকে ৩ টি গুরুত্বপূর্ণ ব্যাপার দেখলাম। এগুলি হলঃ 

  1. φ( n ) = n – 1, when is prime and power is 1.
  2. φ( n) = n– nk-1 ,when n is prime and k != 1.
  3. φ( i*j ) = φ( i ) * φ( j ), when i and j is relatively prime.

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

আমরা 1 থেকে N পর্যন্ত লুপ চালায়ে ব্রূট ফোর্স অ্যালগরিদম লিখতে পারি এভাবেঃ

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

৩৬ = (২*২)*(৩*৩)
φ(৩৬) এর সর্বোচ্চ মান হতে পারে ৩৬। কাজেই আমরা ইনিশিয়ালি, result = 36 লিখে রাখবো।
এর মৌলিক গুণনীয়ক আছে দুইটিঃ ২ এবং ৩। এখন,
১ থেকে ৩৬-এর মধ্যে ২-এর গুণনীয়ক কয়টি আছে?  উত্তরঃ ৩৬/২ = ১৮ টি।
তাহলে, আমরা লিখবো result = result – 18 = 36 – 18 = 18.

এখন আমরা ৩৬ কে ২ দিয়ে যতবার ভাগ করা যায়, করে ফেলবো। এক্ষেত্রে ২ বার ভাগ করার পরে আমরা পাবো ৯।
এখন ১ থেকে ১৮ এর মাঝে ৩ এর গুণনীয়ক আছে , ১৮/৩ = ৬ টি।
তাহলে আমরা লিখবো result = result – 6 = 18 – 6 = 12.
সুতরাং, φ(৩৬) = ১২।

এরপরে আমরা আবার ৯ কে ৩ দিয়ে ভাগ করতে থাকবো। যদি আমাদের n এর মান ১ হয়ে যায়, তাহলে আমাদের আর কিছু করার দরকার নাই। কিন্তু যদি ১ না হয়, তাহলে আমরা result = result – result/n করবো, কেননা, ১ যেহেতু হয়নি, কাজেই, n আসলে প্রাইম নাম্বার ছিল। আর আমরা আগেই জানি, প্রাইম এর জন্য φ(prime) = prime-1

এতক্ষন আমরা যেসব phi জেনারেট করলাম, তার সবই সিম্পল কুয়েরির ক্ষেত্রে ভালো এবং দ্রুত আউটপুট দিবে, কিন্তু, আমাদের যদি কুয়েরির মান অনেক হয়, তাহলে বারবার phi ফাংশন কল করলে আমাদের প্রোগ্রাম TLE দিবে। এজন্য আমাদের আরও এফিশিয়েন্ট অ্যালগরিদম দরকার, যার মাধ্যমে আমরা সহজে অনেকগুলি phi এর মান আগে থেকে জেনারেট করে এরপরে কুয়েরির অ্যান্সার করবো। ঠিক সীভ (sieve of eratosthenes) যেভাবে জেনারেট করতাম, সেভাবে জেনারেট করবো। সকলের জন্য পরামর্শ রইল নিজে কোডটি লিখার। চেষ্টা করার পরে না পারলে এরপরে নিচের কোড দেখে শিখে নেয়া যাবে।

ফাইনালি, একটি সুন্দর জিনিস দেখা যাক।
For any integer n, the sum of the totient(phi) values of each of its divisors equals n”.

এখন দেখা যাকঃ
n = summation of φ( x ) ; where x are the divisors of n.
যেমন, 30 এর divisor = 

1 x 30
2 x 15
3 x 10
5 x 6
so,  30 = φ( 1 )+φ( 2 )+φ( 3 )+φ( 5 )+φ( 6 )+φ( 10 )+φ( 15 )+φ( 30 ) = 1+1+2+4+2+4+8+8 = 30
অর্থাত, যেকোন সংখ্যার সকল divisor এর phi এর মানের যোগফল, ঐ সংখ্যার সমান হবে।

Practice Problems

 

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

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

MySQL XAMPP Connection for Java jdbc Program


First we will open our XAMPP server.

1

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:

    2

  • 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