Yet Another Blog

Superstrings

Just decided to revive this blog after long hibernation! First of all, congratulations to the team of Ain Shams for ranking 64 in their first participation in the ACM ICPC World Finals this year. AFAIK, this year’s world finals was supposed to be in Sharm El-Sheikh in Egypt, but because of the revolution the contest was moved to the United States.

This post is about the solution to one of the three problems that I wrote for the local ACM ICPC at Ain Shams this year. The problem statement can be summarized as follows: Given an alphabet A, a string S that is constructed from the alphabet A, and an integer value L, calculate N[A,L,S], which is the number of possible strings of length L that can be constructed from the alphabet A and are superstrings of S. To make the problem easier, it is assumed that L and |A| are small integers, and the string S consists of distinct characters (i.e., no character exists twice within S). The complete problem statement can be found here.

The problem can be solved using dynamic programming as follows. First note that, given a superstring S’, S may exist multiple times within S’, but all the existences of S within S’ can’t overlap with each others since overlapping would require the existence of a sequence of characters that is both a prefix and a postfix of S, which is impossible because we assumed that S consists of distinct characters.

Let S* be the left-most occurrence of S within S’. The start position of S* within S’ (i.e., the position of the first character of S* within S) can be any index from 1 through L-len(S)+1. For example, if S=xyz and L=6, there are 4 possible start positions of S*; either 1, 2, 3, or 4.

If L-len(S)+1 < 1, then the solution to the problem is N[A,L,S]=0. Otherwise, let N[A,L,S,i] denote the number of possible superstrings of S in which the start position of S* is i. The value of N[A,L,S] is just the summation of N[A,L,S,i] for all i.

To compute N[A,L,S,i] let us divide S’ into three parts: a prefix that comprises the characters before S*, S* itself, and finally a postfix that comprises the characters after S*. Given that the start position of S* is i, the length of the prefix is i-1, and the length of the postfix is L-len(S)-i+1 characters.

Let $N_{pre}[A,L,S,i]$ be the number of possible prefixes, and $N_{post}[A,L,S,i]$ be the number of possible postfixes, given that S* starts at position i. Then $N[A,L,S,i] = N_{pre}[A,L,S,i] * N_{post}[A,L,S,i]$ . Using simple counting, the value of $N_{post}[A,L,S,i]$ can be computed as $\vert A\vert^{L-len(S)-i+1}$ , where |A| is the size of the alphabet. To compute $N_{pre}[A,L,S,i]$ note that S* by definition is the first occurrence of S within S’, thus a prefix should never contain S as a substring. Consequently, $N_{pre} [A,L,S,i] = \vert A\vert^{i-1} - N [A, i-1 ,S ]$ . That is, the set of all possible strings of length i-1 excluding superstrings of S. In conclusion,

$N[A,L,S] = \sum_{i} (\vert A\vert^{L-len(S)-i+1} ) ( \vert A\vert^{i-1} - N[A,i-1,S] )$

The last equation defines N[A,L,S] recursively as a function in N[A,i-1,S]. Obviously, i-1 is always less than L. Hence, the problem can be solved using dynamic programming by saving the values of N[A,L,S], for all L, in a table indexed by L.

P.S. I wrote this post while sitting in Istanbul’s international airport, waiting for a flight. Twelve hours of transit is really too much!

Written by Hatem Abdelghani

June 4, 2011 at 2:52 am

Posted in Problem Solving

Tagged with Algorithms, Counting, Dynamic Programming, ICPC

Alexandria University ranked 147 worldwide

Maximum number of crossed matchings between two sequences

First publication, to appear in SIGMOD 2010.

with 10 comments

I have just gotten my first paper accepted for publishing in SIGMOD 2010. Here are some learned lessons:

A paper is evaluated based on originality, significance, quality of presentation, technical depth, quality of experiments and whether the experimental results really support the work. You don’t have to be perfect in all aspects, do the best you can in each of them.
Make sure your introduction and related work sections clarify the significance and originality of your work. If the reviewer gets beyond those two sections unconvinced of the significance and originality of your paper, then he will never get convinced of that, no matter what comes later! This is a very precious quote from my advisor: “if the reviewer gets beyond the first page without getting convinced, then he will never get convinced”!
Related to the previous point, the stuff you leave to the end usually doesn’t receive as much attention as that at the beginning, even if it is of better quality!
Don’t stick yourself behind other researchers’ work, trying to improve their results. Instead, spend as much time as it takes searching for something that wasn’t investigated a lot, then your job will be much easier.
Don’t read any papers published in low-quality conferences/journals.
Read and attend lectures about other subjects, even if they are not obviously related to your research, they may inspire you with new ways to approach your research.
Spend more time thinking and imagining than reading and learning.
Keep cool and avoid stress!
There is nothing called “part-time research” !!

Written by Hatem Abdelghani

February 11, 2010 at 4:26 am

Posted in Research

Tagged with Research

Two problems from the local ACM ICPC in FCIS Ain Shams

with 5 comments

It has been a long time since I last posted here. Since this is the Eid and I have enough time to waste, it seems appropriate to add one more post. This post contains my solutions to the two problems that I wrote for the local ACM ICPC contest of FCIS Ain Shams University that was held in October 2009.

The first problem is about PQ trees. It is a simple counting problem where the input is a PQ tree, written in parenthesized form, and the output is the number of possible permutations that the tree represents. The problem statement can be accessed here. The solution is as follows. To parse the input, a simple recursive descent parser is sufficient. The number of permutations $nPerm$ is initialized by $1$ . For each $P$ node $p$ , the number of permutations $nPerm$ is multiplied by the factorial of the number of children of $p$ ; that is, $nPerm\leftarrow nPerm*nChildren(p) !$ . And for each $Q$ node $q$ , if $nChildren(q)>1$ , then the number of permutations is doubled; that is, $nPerm\leftarrow nPerm * 2$ . Otherwise, if $nChildren(q)\le 1$ , then $nPerm$ is not affected.

The second problem is about infinite geometric series. The problem statement can be accessed here. The problem can be summarized as follows. We have an amount of data that is initially zero. Each day $N$ kilobytes are added. All the data are compressed at the end of each day by a compression ratio $R$ , where the compression ratio is the size before compression divided by the size after compression. Note that the data are compressed multiple times. The data that are $k$ days old are compressed $k$ times. Given $N$ and $R$ , the problem asks for the the minimum storage capacity needed so that we may never run out of storage; in other words, the maximum size that our data might reach. The solution of the problem is as follows. After $k$ days we have $k$ chunks of data added, each was originally $N$ kilobytes. The chunk of data that was added $i$ days ago has been compressed $i$ times and thus its size has been divided by $R$ for $i$ times. Therefore, the amount of data that we have after the $k^{th}$ day is:

$\displaystyle\sum_{i=0}^{k}N.(1/R)^i\ =\ N\displaystyle\sum_{i=0}^{k}(1/R)^i\ =\ N\frac{1-(1/R)^{k+1}}{1-(1/R)}$

Since we seek the maximum amount of data that we will ever have, therefore we compute the amount of data after infinite number of days; that is, the amount of data as the value of $k$ tends to infinity:

$\displaystyle\lim_{k\rightarrow \infty}N\frac{1-(1/R)^{k+1}}{1-(1/R)}\ =\ N\frac{1}{1-(1/R)}\ =\ \frac{NR}{R-1}$

Written by Hatem Abdelghani

November 27, 2009 at 12:07 pm

Posted in Problem Solving

Tagged with Algorithms, Counting, ICPC, Series

The number of trailing zeros in the factorial of a large integer

with 3 comments

Problem

PKU – 1401

Given a (large) integer K, find the number of zeros on the right of the factorial of K. For example, factorial 15 = 1,307,674,368,000, so the number of zeros on right of the factorial (let’s denote it Z(1,307,674,368,000) ) equals 3.

The input integer K can be as large as 1000,000,000.

Solution

Given an integer N, let the prime factorization of N be $2^{p^N_2}.3^{p^N_3}.5^{p^N_5} ...$ .

The number of zeros on the right of N, that is Z(N), is simply the number of times N can be divided by 10 without getting a fraction. It is obvious that $Z(N)=min\{p^N_2,p^N_5\}$ .

Since N, in our case, is the factorial of another integer, K, then the prime factorization of N is just the product of the prime factorizations of all the integers from 1 to K inclusive. This can be written as

$\displaystyle\prod_{i=1}^K{2^{p^i_2}.3^{p^i_3}.5^{p^i_5} ...}$

So, $p^N_2=\displaystyle\sum_{i=1}^K{p^i_2}$ and $p^N_5=\displaystyle\sum_{i=1}^K{p^i_5}$ .

Consequently, $Z(N)=min\{\displaystyle\sum_{i=1}^K{p^i_2},\displaystyle\sum_{i=1}^K{p^i_5}\}$

In other words, that is the minimum between the sum of the number of times 2 has appeared as a factor for all integers in the range 1 through K versus the sum of the number of times 5 has appeared as a factor for all integers in the same range. Obviously the number of times 5 has appeared is smaller, because it appears every 5 integers, versus 2 in the case of 2. So actually we are interested in $p^N_5$ .

We might go through all the integers in the range 1 to K and find, for each integer in such range, how many times 5 appears as a factor. But due to the fact that we are dealing with large integers that won’t be feasible. Alternatively, we may solve it as follows: the integer division K/5 gives us the number of integers in the range 1 through K for which 5 is a factor at least once, K/25 gives the number of integers in the same range for which 5 is a factor at least twice, … and so on.

Consequently, $p^N_5=\displaystyle\sum_{i=1}^{\lfloor log_5 K\rfloor}{K/5^i}$ , where the division is integer division.

The formula is logarithmic in the value of K, so it is linear in the number of bits. That is efficient enough to handle the required input.

Written by Hatem Abdelghani

July 28, 2009 at 9:22 am

Posted in Problem Solving

Tagged with Algorithms, Number Theory, Online Judge, PKU

Second shortest path

with 3 comments

Problem

UVa – 10342

Given a simple weighted graph $G=(V,E)$ (having no loops and no multi-edges), we want to find for every two vertices a path between those vertices whose length is strictly greater than the length of the shortest path between them but still less than or equal to the length of any other path between them. Loops are allowed in our target path.

Solution

First use Floyd-Warshall to obtain shortest paths between all pairs. Let $\pi_1(i,j)$ denote the shortest path between the vertices $i$ and $j$ . The shortest path between a vertex and itself is zero. If there is no path between $i$ and $j$ then $\pi_1(i,j)=\infty$ .

Now use the following algorithm to obtain all-pairs second shortest paths. We will denote the second shortest path between a pair of vertices $i$ and $j$ as $\pi_2(i,j)$ . Initially $\pi_2(i,j)=\infty$ for any pair of vertices $(i,j)$ .

For each edge $(x,y)$ in $E$
$\$ For each pair of vertices $(i,j)$ in $V\times V$
$\$ $\$ Let the path $tmp(i,j)$ be the concatenation: $\pi_1(i,x)$ , $(x,y)$ , $\pi_1(y,j)$
$\$ $\$ If $len(\pi_1(i,j)) < len(tmp(i,j)) < len(\pi_2(i,j))$
$\$ $\$ $\$ $\pi_2(i,j)=tmp(i,j)$

The rationale behind that algorithm is as follows: Moving from a source vertex to a target vertex, if -at each vertex along our path- we move from our current vertex to an adjacent vertex that lies on the shortest path between the current vertex and the target vertex, we will eventually reach the target vertex throught shortest path. If, at one step, we made a mistake by moving to an adjacent vertex that doesn’t lie on the shortest path between the current vertex and the target vertex, we won’t reach our target vertex throught the shortest path. We need to know which wrong step will make us arrive through a path that is worse than the shortest path but still better than any other possible path. We also know that we have to make no more than one mistake since two mistakes will give us a path that is even worse than the second shortest path. So, for each pair of vertices $i$ and $j$ , we try to find all paths between $i$ and $j$ that is composed of a sequence of right steps (the shortest path between $i$ and some reachable vertex $x$ ) followed by an arbitrary step that could be our mistake (the edge $(x,y)$ ) then another sequence of right steps (the shortest path between $y$ and $j$ ). We search all such possible paths for a path that is longer than the shortest path (obtained through Floyd-Warshall) but still shorter than the rest.

Written by Hatem Abdelghani

July 4, 2009 at 2:24 am

Posted in Problem Solving

Tagged with Algorithms, Graph Theory, Online Judge, UVa

Minimum-maximum integral rectangle partitioning

Analyzing a random search in a tree

with 2 comments

Problem:
This is a 500-points problem from TC SRM440 Div1. It can be summarized as follows:

We are given a matrix. Some cells are marked closed and others are marked open. We can only move from one open cell to an adjacent open cell. The matrix is defined such that there is one and only one way from one open cell to another.

Our target is to reach a specific open cell, let’s call it the target cell. Our starting point is uniformly random (can be the target cell itself). Moving from one cell to another takes one second. Our motion is also uniformly random; that is, whenever we are in an open cell, the probability to move from that cell to any of the adjacent open cells is the same for all adjacent open cells (but we must move, we can’t stand still).

It is required to calculate the expected time to reach the target cell.

Solution:
Since the starting cell is uniformly random, we will calculate the expected time to reach the target cell for each possible starting cell; then the required overall expected time is just the average of all those expected times.

Let the open cells be $c_0, c_1, c_2, ... , c_n$ where $c_0$ is the target cell. For the special case where $c_0$ is the starting cell, the expected time equals $0$ . We need to calculate the expected time for the rest.

For any cell $c_i$ , where $0<i\le n$ , let the expected time to reach $c_0$ be $E_i$ . If the degree (the number of adjacent cells) of $c_i$ is $d_i$ then the probability of going to any of the adjacent cells is $\frac{1}{d_i}$ . If we are in cell $c_i$ , and we chose to go to the adjacent cell $c_j$ then the expected time to reach $c_0$ will be one second (for moving from $c_i$ to $c_j$ ) plus $E_j$ (the expected time to reach $c_0$ from $c_j$ ). We end up with the following formula for $E_i$ :

$E_i = \displaystyle\sum_{j:\ c_j\ adjacent\ to\ c_i} {\displaystyle\frac{1}{d_i} (1+E_j)} = 1 + \displaystyle\frac{1}{d_i} \displaystyle\sum_{j:\ c_j\ adjacent\ to\ c_i} E_j$

This is a system of linear equations that can be solved with any appropriate method, for example Gauss-Jordan elimination.

Comments:
The interesting thing with this problem is that it is asking for an algorithm to analyze the performance of a heuristic! We can think of this matrix as an undirected graph, where open cells of the matrix are vertices of the graph, and adjacent open cells correspond to adjacent vertices. Since there is one and only one way between any two open cells then it is actually a tree, and the algorithm is just analyzing the performance of a random search in a tree.

Written by Hatem Abdelghani

May 13, 2009 at 10:59 pm

Posted in Problem Solving

Tagged with Algorithms, Linear Algebra, Probability, SRM, Top Coder

The number of the factors of the factors of a number!

with 2 comments

Problem:

PKU – 3604

Given an integer N, find all the factors of N including the trivial factors (1 and N). For each factor f, find the cube of the number of factors of f. Then sum all those cubes.

For example, if N=4, the set of all possible factors are 1, 2 and 4. 1 has only one factor which is 1. 2 has 2 factors: 1 and 2. 4 has 3 factors: 1, 2 and 4. So the result equals $1^3 + 2^3 + 3^3 = 1 + 8 + 27 = 36$

Solution:

A naive solution won’t work since the input is too large (up to 500,000 test cases and N can be as large as 5,000,000).

The idea is as follows: According to the fundamental theorem of arithmetic, any integer N>1 has a unique prime factorization (i.e., there is one and only one way to factorize this integer into a product of prime numbers). For example, 420 has the following unique prime factorization:

420 = 2 * 2 * 3 * 5 * 7

For a given integer N, let the prime factorization of N be $\sum_{i=1}^{n} {F_i^{p_i}}$ where n is the number of prime factors of N, $F_i$ is the $i^{th}$ distinct prime factor which is raised to the power $p_i$ .

We can see that the total number of general factors of N (all factors, not only the primes) equals $\prod_{i=1}^n {(p_i+1)}$ .

This value follows from the fact that any general factor $f_j$ of N is just the product of some of the prime factors of N. So any such general factor $f_j$ has the prime factorization $\sum_{i=1}^{n} {F_i^{q_{j,i}}}$ where $0\le q_{j,i}\le p_i$ . The case where $q_{j,i}=0$ for all i will give us the general factor $f_j=1$ . The case where $q_{j,i}=p_i$ for all i will give us the general factor $f_j=N$ (the number itself).

However, we are not interested in the number of general factors of N; we are interested in the number of general factors of each general factor of N (!!) to be cubed each and summed together.

This value can be obtained as follows: using the same reasoning mentioned above, for each general factor $f_j$ of N, the number of general factors of $f_j$ equals $\prod_{i=1}^n {(q_{j,i}+1)}$ . For each j and i, the value of $q_{j,i}$ ranges from 0 to $p_i$ inclusively, therefore the required value, the summation of cubes of numbers of general factors of all general factors of N, equals:

$\sum_{q_{j,1}=0}^{p_1}\sum_{q_{j,2}=0}^{p_2}...\sum_{q_{j,n}=0}^{p_n} {\prod_{i=1}^n {(q_{j,i}+1)}}^3$

Re-distributing the summation we get the following formula:

$\sum_{q_{j,1}=0}^{p_1} (q_{j,1}+1)^3 * \sum_{q_{j,2}=0}^{p_2} (q_{j,2}+1)^3 * ... * \sum_{q_{j,n}=0}^{p_n}(q_{j,n}+1)^3$

Using the well-known series $\sum_{i=1}^{n} i^3 = (n(n+1)/2)^2$ we can re-write our formula again as follows:

$((p_1+1)(p_1+2)/2)^2 * ((p_2+1)(p_2+2)/2)^2 * ... * ((p_n+1)(p_n+2)/2)^2 \\ = \prod_{i=1}^n ((p_i+1)(p_i+2)/2)^2$

Thus, all we need to calculate is the prime factorization of N, from which we can get the value of $p_i$ for each i.

Necessary Optimizations:

Due to large input sizes, calculating the prime factorization of every input value from the scratch will give TLE. The process can be optimized by using simple dynamic programming.

For every integer N, the value we need to calculate is

$res(N) = \prod_{i=1}^n ((p_i+1)(p_i+2)/2)^2 \\ = ((p_1+1)(p_1+2)/2)^2 \prod_{i=2}^n ((p_i+1)(p_i+2)/2)^2\\ = ((p_1+1)(p_1+2)/2)^2 res(N')$

where N’ is some integer less than N. So actually we can re-use the values of res( ) computed for smaller input values to compute larger ones. All we need for any given integer N is to find one of its $p_i$ values (the power of one of its prime factors), then we can calculate res(N) recursively, and there comes dynamic programming.

Finding a power $p_i$ of one of the prime factors $F_i$ of N can be done easily once the prime factor itself $F_i$ is found. We can use a modified version of Sieve of Eratosthenes to find a prime factor for each integer in a given range.

The original Sieve was used to determine which natural numbers are prime and which are not, up to some maximum number MAX. Starting from counter=2, we mark all multiples of the counter as not-prime until MAX is reached. Move the counter forward to the next unmarked integer (which will always be prime since it is not a multiple of any smaller integer).

In the modified version, instead of marking the multiples of the counter as not-prime, we will associate the counter with its multiples as a prime factor of them. This way we get a prime factor for each natural number up to MAX (which equals 5,000,000 is our case).

Having reached such step, dynamic programming can be done easily by iterating through natural numbers up to MAX, for each natural number N, we can calculate res(N) using the prime factor of N we have obtained before and res(N’) for some smaller natural number N’ also calculated before.

Written by Hatem Abdelghani

May 7, 2009 at 6:28 am

Posted in Problem Solving

Tagged with Algorithms, Counting, Dynamic Programming, Number Theory, Online Judge, PKU

Yet Another Blog

Superstrings

Alexandria University ranked 147 worldwide

Maximum number of crossed matchings between two sequences

First publication, to appear in SIGMOD 2010.

Two problems from the local ACM ICPC in FCIS Ain Shams

The number of trailing zeros in the factorial of a large integer

Second shortest path

Minimum-maximum integral rectangle partitioning

Analyzing a random search in a tree

The number of the factors of the factors of a number!

Archives

Meta

Tags

Follow “Yet Another Blog”