Tuesday, February 6, 2018

Toph: XOR Master

Problem link: XOR Master

Solution:

In this problem we are given N integers. We have to count the number of pairs (i,j) (1<=i<=j<=N) for which A[i] XOR A[j] will contain at least 1 in it's bit pattern.

Say for the case here:
4
1 2 2 2

Here are 3 such pair that A[i] XOR A[j] has at least one 1 in it's bit pattern. They are:

1 XOR 2 = 01(Binary of 1) XOR 10(Binary of 2) = 11 (has two '1's) ; for three 2's, and a single 1, we get 3 such pair of (1,2)

But as we can see, 2 XOR 2 = 10 XOR 10 = 00, here no '1' is present. So this will not be counted.

So, how can we solve this? Firstly, see that one integer can get at least one '1' in it's bit pattern if it is XOR-ed with any integers except itself. So, a simple binary search with upper_bound technique can be really helpful to find solution in O(log N). For frequent values, we can store them in a map data structure that is built in C++ function.


Thursday, February 1, 2018

Toph: Horrible Queries

Problem link: Horrible Queries

Solution:

In this problem, we will be given some integers from 1 to 50. And also integer L,R,K. We need to find how many unique values have at least K occurence in the subarray between L & R, where L<= R.
As numbers can only be between 1 to 50, we can implement this simply without the use of segment tree. What we need to do is that, we will create 50 array of size N (each for 1 to 50 integers) to compute the occurence of every integers in a cumulative way. Then for each query, we will simply check for every integers if cumulative sum (occurence of that integer) of that integer in given range is at least K or not. Then we will simply increase the counter to get our answer. Try to implement it any way you like keeping in mind about the cumulative frequency of occurance. Then you can check my code below.

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