স্লাইডিং উইন্ডো (Sliding Window Technique)

প্রোগ্রামিং কন্টেস্টে আমাদের অনেক সময় ৩ বা ৪ বা এরচেয়েও বেশি লুপ এর কোড লিখতে হয়। ব্যাসিকালি ব্রুটফোর্স যাকে বলে। এখন আমরা যেই টেকনিক দেখবো, এটি এরকম একাধিক লুপ এর প্রব্লেমকে কম সময়ে সল্ভ করে দিতে পারবে। 

স্লাইডিং উইন্ডো সমস্যার বিভিন্ন রূপ আছে। কিন্তু তাদের সবারই একটি কমন বৈশিষ্ট আছে : একটি সাব-অ্যারেকে (আমরা একে ‘উইন্ডো’ বলে থাকি, যা স্ট্যাটিক বা ডাইনামিক দৈর্ঘ্য থাকতে পারে) আমরা  n সংখ্যক উপাদানগুলির অ্যারে এর বাম থেকে ডান দিকে লিনিয়ারভাবে সরায়ে কিছু কম্পিউট করার চেষ্টা করবো। এভাবে উইন্ডো স্লাইড করার টেকনিক কেই স্লাইডিং উইন্ডো বলে। স্লাইডিং উইন্ডোর অনেক রকম ভ্যারিয়েশন আছে। যেমন ঃ 

  1. একটি অ্যারের মাঝে ফিক্সড সাইজের কোন সাব-অ্যারের ম্যাক্সিমাম সামেশন বের করা। যেমন ঃ অ্যারে  A = {10, 40, 10, 30, 20} এবং উইন্ডো সাইজ w = 3 হলে, মাক্সিমাম সামেশন = 40+10+30 = 80. 
  2. একটি অ্যারের মাঝে ফিক্সড সাইজের সকল সাব-অ্যারের ম্যাক্সিমাম অথবা মিনিমাম সংখ্যা বের করা। যেমন ঃ
    অ্যারে A = {0, 5, 5, 3, 10, 0, 4} , n = 7 এবং উইন্ডো সাইজ w = 3, হলে এখানে n-w+1 = 5 টি ভিন্ন ভিন্ন সাব-অ্যারে আছে যাদের সাইজ = 3; {0, 5, 5}, {5, 5, 3}, {5, 3, 10}, {3, 10, 0}, {10, 0, 4}. এবং আমরা এদের ম্যাক্সিমাম সংখ্যা বের করতে চাইলে এগুলি হবে ঃ 5, 5, 10, 10, 10 প্রতি সাব-অ্যারের জন্যে। 
  3. একটি অ্যারের মাঝে এমন মিনিমাম দৈর্ঘ্যের সাব-অ্যারে বের কর, যার এলেমেন্ট এর সাম, নির্দিষ্ট কোন সাম থেকে বড়/ সমান/ ছোট হয়। যেমন ঃ অ্যারে A = {5, 1, 2, 3, 4, 2} এবং S = 7 হলে,
    মিনিমাম দৈর্ঘ্য == 7 : 2,  {5, 1, 2, 3, 4, 2}
    মিনিমাম দৈর্ঘ্য > 7 : 3,  {5, 1, 2, 3, 4, 2} , {5, 1, 2, 3, 4, 2}, {5, 1, 2, 3, 4, 2}
    মিনিমাম দৈর্ঘ্য < 7 : 1,  {5, 1, 2, 3, 4, 2} ; যেকোনটাই হতে পারে।
     
  4. একটি অ্যারের মাঝে এমন মিনিমাম দৈর্ঘ্যের সাব-অ্যারে বের কর যাতে  [ 1 to w ] পর্যন্ত সকল সংখ্যা কমপক্ষে একবার করে হলেও থাকবে। যেমনঃ A = {1, 2, 3, 7, 1, 12, 9, 11, 9, 6, 3, 7, 5, 4, 5, 3, 1, 10} এবং w = 4, আমরা 13 length এর একটি সাব-অ্যারে পাবো, যাতে 1, 2, 3, 4 আছে। এই সেইম অ্যারের জন্যে যদি w = 3 হয়, তাহলে A = {1, 2, 3, 7, 1, 12, 9, 11, 9, 6, 3, 7, 5, 4, 5, 3, 1, 10} আমরা 3 length এর একটি সাব-অ্যারে পাবো। 

সলুশন (Solution)
উপরের প্রবেল্মগুলি আমরা নরমালি বারে বারে লুপ চালায়ে সল্ভ করতে পারবো তখনি, যখন রেঞ্জ কম হবে, যা আমাদের given time এর মাঝে সল্ভ করা সম্ভব হয়। আমরা ব্রুটফোর্স এর ব্যাপারগুলি বাদ দিয়ে সরাসরি আমাদের স্লাইডিং উইন্ডো টেকনিক এ চলে আসি, যা কিনা O (n) সময়ে সল্ভ করতে সক্ষম।

১ম টেকনিক (First Technique):

আমরা প্রথমে উইন্ডো তে আমাদের প্রথম w টি ইন্টিজার ইন্সার্ট করে দিলাম এবং এদের সাম বের করে তাকে curr_sum ভ্যারিয়েবল এ রাখলাম। এরপরে আমরা স্লাইড করে করে আগাবো। আমরা ডান পাশে একটি একটি করে এলেমেন্ট উইন্ডো তে ইন্সার্ট করবো এবং বাম দিক থেকে একটি করে সরায়ে দিব, ফলে আমাদের উইন্ডোর সাইজ সেইম থাকবে।এলেমেন্ট ইন্সার্ট এর সময় আমরা চেক রাখবো যে এখন আমরা ম্যাক্সিমাম সাম পেলাম কিনা। প্রতিবার ইন্সার্ট করার সময় আমাদের নতুন সাম হবে curr_sum + inserted_element – removed_element. এভাবে আমরা পুরো অ্যারেকে স্লাইড করে রেসাল্ট পাবো। 

২য় টেকনিক (Second Technique):

যদি n এর মান অনেক বড় হয়, সকল সাব-অ্যারের মাক্স/মিন বের করা একটু কঠিন হবে। এজন্য আমরা deque (double ended queue) ব্যবহার করবো। এখন আমাদের উইন্ডো হবে আমাদের deque টি। আমরা deque কে ascending order ( ছোট থেকে বড় ) এ সাজাবো ( যদি মিন বের করতে চাই)। deque এর প্রথম দিকে আমাদের মিনিমাম এলেমেন্ট গুলি থাকবে। কিন্তু এভাবে কাজ করতে গেলে একটি বড় প্রব্লেম হল, আমাদের মূল অ্যারের ইন্ডেক্সগুলি উল্টাপাল্টা হয়ে যাবে, এজন্য আমাদের ইন্ডেক্স এর ট্র্যাক রাখতে হবে যাতে আমরা বুঝতে পারি যে, এলেমেন্ট উইন্ডো তে আছে কি নাই। নিচের একটি স্যাম্পল কোড দেয়া হল ঃ 

৩য় টেকনিক (Third Technique):

আমরা একটি ডাইনামিক সাইজ উইন্ডো মেইন্টেইন করবো, যেখানে ভ্যালু যোগ করতে থাকবো। মিন/ ম্যাক্স/ ইকুয়াল, কোন এক কন্ডিশন পেলে আমরা আমাদের মিনিমাম উইন্ডো সাইজ পেয়ে যাবো। প্রোগ্রাম এ কি চাওয়া হয়েছে তার উপরে ভিত্তি করে আমাদের কোড এ কন্ডিশন এর পরিবর্তন হবে। এখানে আমরা ১ম টেকনিক এর মত করে ইন্সার্ট করতে থাকবো এবং কন্ডিশন চেক করবো। আর এলেমেন্ট উইন্ডোতে আছে কিনা, উইন্ডো সাইজ কি আমাদের মূল অ্যারে থেকে বড় হয়ে গেলো কিনা – এসব আমরা ২য় টেকনিক এর মত একটি deque নিয়ে চেক করতে পারি।

৪র্থ টেকনিক (Fourth Technique):

আমরা এমন একটি উইন্ডো মেইন্টেইন করবো যা কিনা 1 to w সকল সংখ্যা যদি না পাই, উইন্ডো সাইজ বারাতে থাকবে, নাহলে সাইজ কমাতে থাকবে। আমরা মিনিমাম উইন্ডো সাইজের ট্র্যাক রাখবো। 1 to w সকল এলেমেন্ট পেয়ে গেলাম কিনা এটি আমরা নরমাল একটি ফ্রিকুয়েন্সি কাউন্টের মাধ্যমে করতে পারি। যখন সকল এলেমেন্ট এর কাউন্ট >0 হবে, তখন আমরা আমাদের মিনিমাম উইন্ডো সাইজ রিটার্ন করে দিবো।

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

Advertisements

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.

1.JPG

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.

1.JPG

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.

LightOj: Algebraic Problem

Problem Link: loj1070
Technique: Matrix Exponentiation

Given the value of a+b and ab you will have to find the value of an+bna and b not necessarily have to be real numbers. I solved this using matrix exponentiation technique. I will now write about how I modelled the base matrix for multiplication. There may be other approaches too. But first please read this blog if you don’t know about how to create a matrix from a recurrance relation.

First let’s observe some cases.
If n = 0, a0+b= 1+1 = 2
If n = 1, a1+b= a+b – 0
If n = 2, a2+b= (a+b) (a+b) – 2ab
If n = 3, a3+b= (a+b) ( (a+b)– ab ) – 2ab (a+b)
…………..     …………..     ………….     ……………..

So, basically the recurrence somehow turns like this –>

(a1+b1) = (a+b) + (-0)
(a2+b2) = (a+b) (a+b) + 2(-ab)
So,
base  =  | (a+b)   -ab  |
            |   1           0   |

We will multiply (a+b) with base [0][0] and 2 with base [0][1], then we will get our final output by summing these two elements.

So, when n = 0 , ans will be 2.
When n = 1, ans will be a+b
When n = 2, ans will be (base)= (a+b) * (a+b) + 2 * (-ab) = (a+b)2 – 2ab
When n = 3, ans will be (base)2  = (a+b) * [(a+b)2 -ab)] + 2 * [-ab*(a+b)]

Let’s see this : (for n = 3)
yo.jpg
In our base matrix, after performing exponentiation, at base [0][0] we get [(a+b)2 -ab)], and we will multiply it with (a+b). Similarly, at base[0][1] we get [-ab*(a+b)], so we will multuply it with 2. And by summing these two elements, we will get our final output.

NOTE : As For each test case, print the case number and (an+bn) modulo 264, we will use unsigned long long for each variable instead of applying modulus operation. This will save our time. Infact, without this, the program will get TLE.

“Don’t directly copy code. First try to understand how each step works, then do your own coding.”

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:

11

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.

12.JPG

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 😛 ).
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

13.JPG

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.

14.JPG

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.

15.JPG

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:

16.JPG

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.

17.JPG

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 ).

18.JPG

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.

19.JPG

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.

 

HackerEarth: Fibonacci with GCD

Problem: Fibonacci with GCD

Editorial: It’s a segment tree problem with simple matrix exponentiation for generating fibonacci numbers. In this problem, we will be given some numbers. Then we will be asked to perform some queries.  Each query there will be a range, from that range we need to find GCD of all the elements fibonacci numbers. Say for 2 4 8, we need to calculate GCD ( fib[2], fib[4], fib[8] ) = GCD ( 1, 3, 21 ) = 1.

We will create a segment tree, where we will store the gcd of every elements of the array. Basically our segment tree will be made of calculating gcd for a given range. Then for the query we will calculate part by part in the range for our gcd. If left and right both child node is -1, then we will simply return 1. If left child is -1 but right child has positive value, then we will return right child. Similarly we will do for the right child being -1 also. And when both the child have positive value, we will return the gcd between them. After getting the gcd value from the elements of the range from our query, then we will find the fibonacci number of that gcd value. We will do that with matrix exponentiation.

So, basically, for this problem, we will create segment tree first with corresponding gcd, and then after the query, we will calculate the fibonacci number. Say for values : 2, 4, 8, the GCD = 1. So our answer will be fibonacci [ 1 ] and that is 1. ( Fibonacci series : 1, 2, 3, 5,….).

CF: Squares and not squares

Problem Link: Squares and not squares
Editorial: At first we can pre compute square numbers from 0 to 31623, as 31623*31623 = 1000014129, which is greater than 109.
Then we will take two seperate vectors, one for storing square numbers and other for non square numbers. We can store them at the time of taking input. Simply binary searching in the pre computed square numbers vector would be greate.
Now, we will count how many square numbers are there in the square vector. Say it is count1. And number of non squared number would be count2 = n – count1. Now–>

  1. If count1 == n/2, then the answer is zero.
  2. If count1 > n/2, then we need to make some of our squared numbers into non squared number.
  3. If count1 < n/2, then we need to make some of the non squared number to squared number.

count1 > n/2:
We need to check what is the maximum number of the squared numbers. If max_value is <=0, then for each squared number to make a non squared number we need to add +2 if the number is zero (0) else +1.
For 0, we should add +2 to make it 2, as 2 is not a squared number, but 1 is a square number. And we need to make (  count1- n/2 ) non_squared numbers.

count1 < n/2:
Now we need to find the closest squared number for each element of our non squared vector. Simply iterate through all the values from non squared vector and we will find upper_bound of each element in our pre computed square vector. We will take another vector to store the minimum value we got from each element via upper_bound. Finally we will sort the vector, and print the sum of the first (  n/2 – count1 ) elements from that vector.

Here is the solution of mine : solution

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 and M, we need to find summation of first even numbers modulo and summation of first 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 1018 – 1 and M can be 1018, 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 = 1018 – 1, M = 1018.

Now, from modular arithmatic we know that

– (a * b) % m = (( a%m ) * ( b%m ))%m
– (a + b) % m = (( a%m ) + ( b%m ))%m

Say, = 1018 and b = 10 and m = 1018 – 1.
So, ( (1018 – 1) %1018 ) * (1018 – 1) %1018 ) ) % 1018= ( (1018 – 1) * (1018 – 1) ) % 1018 = 0 ; here 
(1018 – 1) * (1018 – 1) will cause overflow.

But,(((1018 – 1)%1018) + ((1018 – 1)%1018) + ….

We can easily add (1018 – 1 + 1018 – 1) and then mod it with 1018. We will do this 1018 times, and by using modulo operation each time, there won’t be any overflow.
As 1018 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.