Contest Analysis: IUT 6th National ICT Fest 2014, UVa 12830 – 12839

forthright48 on August 20, 2015

I participated in this contest last year. Our team “NSU Shinobis” managed to solve 5 and placed in the top 10 ( failed to find the rank list ). The IUT 7th ICT National Fest 2015 is going to be held next month, so I thought I would try to up solve the remaining problems. I tried to compile detailed hints for the problems here.

UVa 12830 – A Football Stadium

Complexity: $O(N^3)$
Category: Loop, DP, Kadane’s Algorithm

Given $N$ points, we have to find the largest area of the rectangle which can fit such that there is no point inside the rectangle. Points on boundaries of the rectangle are allowed.

Now imagine a rectangle which has no point inside it and also no point on its boundary. Now focus on the top boundary of that rectangle. Since there is no point on that boundary, we can extend it up until it hits a point or limit. Same can be said for the bottom, left and right boundary. That is, the largest rectangle will have its boundary aligned with the limits or points.

Now let us fix the top and lower boundary of the rectangle. How many possible values can they take? Each boundary can take values of $y$-coordinate from one of the $N$ points or the limits $0$ and $W$. Using two nested loops, we can fix them.

Next we need to fix the left and right boundary. Lets us sort the points according to $x$ first and then according to $y$. Next we iterate over the points. Initially set the left boundary of rectangle aligned to $y$-axis, that is aligned with the left boundary of Sand Kingdom.

Now, for each point, if the $y$ coordinate of the point is above or below or on the boundary we fixed then we ignore them, cause they don’t cause any problem. But if they fall inside, then we need to process this point. We put the right boundary aligned to the $x$ coordinate of this point and calculate this rectangle.

But it’s not over. We shift the left boundary over to current right boundary and continue to process remaining points.

This is a classical problem of Kadane’s Algorithm. With two nested loops to fix upper and lower boundary and another loop inside iterating over $N$ points makes the complexity $O(N^3)$.

$O(N^2)$ solution is possible, by constructing a histogram for each row ( $O(N)$ ) and the calculating area of histogram in $O(N)$. But that’s not necessary here.

Code: http://ideone.com/FjvTN2

UVa 12831 – Bob the Builder

Complexity: $O(\sqrt{V}E)$
Category: Max Flow, Bipartite Matching, Dinic’s Algorithm, Path Cover

Another classical problem, though we had a hard time solving this one. Mainly cause we didn’t realize this was a path cover problem which can be solved using Max Flow.

Take each number provided and generate all child. Consider each number a node and if it possible to generate $B$ from $A$, then add a directed edge from $A$ to $B$. When you are done, you will have DAG.

Now split all the nodes in two. We are going to create a bipartite graph now. On the left side, we will have all the original nodes and on the right side we will have the copy we got by splitting the nodes. Now, for each edge between $A$ and $B$, add an edge in the bipartite graph from $A$ on the left side to $B$ on the right side.

Find the matching ( or maximum flow ) of this graph by running Dinic’s Algorithm. The answer will be $\text{Total Nodes} – \text{Matching}$.

Code: http://ideone.com/U1VPNB

UVa 12832 – Chicken Lover

Complexity: $O(M)$
Category: Expected Value, Probability, DP, Combination

If a shop can make $N$ different items, and in a single day prepares $K$ items from those $N$ items, then how many different sets of menus ($total$) can they make? $total = C^N_K$. Now, if they decide to make chicken that day for sure, how many sets of menus ( $chicken$ ) can they make now? $chicken = C^{N-1}_{K-1}$. So what is the probability $P$ that if I visit a shop I will get to eat chicken? $P = \frac{chicken}{total}$. And what is the probability that I will not eat chicken? $Q = 1- P$.

So now I know the probability of eating chicken for each shop. How do we find the expected value? We will find it using dynamic programming.

The states of dp only be the shop number. $dp(x)$ will give me the expected number of chicken that I can eat if I visit all shops starting from $x$. Our result will be $dp(1)$.

At each state, I have $P_i$ probability that I will eat chicken and $Q$ probability that I will not. So result for each state will be:

$dp ( pos ) = P \times ( 1 + dp ( pos + 1 ) + Q \times dp ( pos + 1 )$
$dp ( pos ) = P + P \times dp ( pos + 1 ) + Q \times dp ( pos + 1 )$
$dp ( pos ) = P + dp ( pos + 1 ) \times ( P + Q )$
$dp ( pos ) = P + dp ( pos + 1 )$.

In order to print the result in $\frac{A}{B}$ form, we need to avoid $double$ and use integer arithmetic in all places. I implemented my own fraction class for that purpose.

Code: http://ideone.com/mGKwuL

UVa 12833 – Daily Potato

Complexity: $O(26 \times N)$
Category: String, Manacher’s Algorithm

For each query, we have to count the number of palindromes which are the substring of $S$, starts and ends with given $C$ and has exactly $X$ occurrences of $C$ in it. Since it deals with palindrome, perhaps it has something to do with Manacher’s Algorithm?

With Manacher’s Algorithm, we can find out the maximum length of palindrome in $O(N)$. But what’s more, we can actually generate an array $M$ which gives us, for each center in the extended string $E$, ( $aba$ when extended becomes ^#a#b#a#$ ) the maximum length of palindrome with that particular center. How can we use this knowledge to solve our problem?

Let us consider the character $’a’$ only. We can easily extend it for other characters by repeating the whole process $26$ \times.

Suppose we are working with center $x$. It has a palindrome from it with length $y$. Therefore, in the extended string of manacher, the palindrome starts from $x-y$ and ends in $x+y$. Now, how many \times does $’a’$ occurs in this palindrome? Using Cumulative Sum it is possible to answer in $O(1)$. Let that occurrence be $f = \text{# of times ‘a’ occurs in palindrome with center x}$. Let us mark this in another array $freq$. That is we mark it like $\text{freq[f]++}$, meaning we have $freq[f]$ palindromes where $’a’$ occurs $f$ times. But wait, what if the palindrome does not start and end with $’a’$? Simple, we keep on throwing the leading and trailing character until it starts and ends with $’a’$ and it will still have $f$ occurrences of $’a’$ in it.

So we repeat this for all possible center. Now, if the query is to find the number of palindromes that starts and ends with $’a’$ and $’a’$ occurs exactly $X$ \times, how do we solve it?

First of all, our result will contain $res = freq[X]$ in it. What’s more, our result will also contain $res \text{+=} freq[X+2] + freq[X+4] + freq[X+6] + …$. Why is that? Take any palindrome that contains more than $X$ occurrences of $’a’$. Since they start and end with $’a’$, we can just throw them out of that palindrome and reduce the occurrence of $’a’$ in it by $2$. After that, we keep on trimming down head and tail of that palindrome until we reach $’a’$ again. That is, a palindrome with $Y$ occurrences of $’a’$ can be trimmed down to palindrome with $Y-2$, $Y-4$, $Y-6$, $…$ occurrences of $’a’$.

Instead of getting the result $res = freq[X] + freq[X+2] + freq[X+4] + \dots$ we can just use cumulative sum again to find it in $O(1)$ here. Just find the cumulative sum of alternate terms.

Code: http://ideone.com/brZKXL

UVa 12834 – Extreme Terror

Complexity: $O(N: logN )$
Category: Adhoc

This was the easiest problem. Each shop gives me some money ($income$) and then for that shop I have to give Godfather some cut ($expense$). So for each shop I get $profit = income – expense$. So I calculate profit for each shop and then sort them. I can now skip $K$ shops. I will of course skip shops for which profit is negative as long as I am allowed to skip.

Code: http://ideone.com/s3iHGz

UVa 12835 – Fitting Pipes Again

Complexity: $O(N!: N^2)$
Category: Geometry, Trigonometry, Permutation, Packing Problem

It’s a packing problem. At first glance, it seems like a tough problem but it’s not. Let us first define a few variables first.

This is the polygon. Each polygon has two horizontal lines through it. We will call them the low and top line. Each side of the polygon has a length of $x$. The radius of the polygon is $r = \frac{x}{2} + y$.

We are given the height of each polygon. But first, we will need to calculate the value of $x$ and $y$. We can find their values using trigonometry.

$y^2 + y^2 = x^2$
$2y^2 = x^2$
$x = \sqrt{2y^2}$

We also know that $h = y + x + y$. From that we can derive:

$y + x + y = h$
$2y+x = h$
$2y + \sqrt{2y^2} = h$
$2y + y\sqrt{2} = h$
$y( 2 + \sqrt{2} ) = h$
$y = \frac{h}{2} +\sqrt{2}$

With the above, we can find the value of $y = \frac{h}{2} +\sqrt{2}$ and $x = \sqrt{2y^2}$ But why did we find their values?

Okay, what happens when we put to polygon side by side? In order to solve this problem, we need to be able to find the distance between the center of two polygons $A$ and $B$.

Now if two polygons are of the same height and they are placed side by side, then the difference between their centers will be $d = r_a + r_b$. What happens when two polygons of arbitrary height come beside each other?

$3$ things can happen when two polygon $A$ and $B$ are placed side by side. $A$ is on left of $B$.

Height of bottom line of $A$ is higher than height of top line of $B$. In this case, $A$ is so big that $B$ slides inside the radius of $A$.
Height of bottom line of $B$ is higher than height of top line of $A$. In this case $A$ is so small that it slides inside the radius of $B$.
Nobody can slide inside each others radius. So $d = r_a + r_b$.

We need to calculate the value of $d$ for step $1$ and $2$. That can also be easily done using trigonometry. Try to draw some diagram yourself.

So we used $x$ and $y$ to find the value of $d$ between two polygons. How do we use this to find the minimum width of the box?

Suppose we are trying to pack the polygons in some order. Which order? We don’t know which order will give us minimum width so we try them all. There will be $N!$ order.

So for each order, what will be the minimum of width. First let’s take the first polygon, and put it inside the empty box such that it touches the left side of the box. We will calculate the center of each polygon relative to the left side of the box. The first box will have the center at $r_0$.

Now take the second box. First, imagine there is no polygon in the box. There where will be the center of the second polygon? Ar $r_1$. Now, since there is a polygon, we will try to put it besides that one. Where will be the center now? $r_0 + d$. We will take the maximum possible center.

Repeat this for the third polygon. Empty box, besides the first polygon, besides the second polygon. Take the maximum again. Repeat this for all polygon.

From all polygon, find the one with the maximum center position. Add radius of that polygon to its center to find the width.

Take the minimum width from all permutation.

Code: http://ideone.com/kphGx5

UVa 12836 – Gain Battle Power

Complexity: $O(N^2)$
Category: Interval DP, LIS, Knuth Optimization

First, we need to calculate the power of each Deatheater. We can do that by calculating LIS from both directions and then adding them.

Once we calculate the power, we run an interval dp between $1$ and $N$. The dp will have states $start$ and $end$. Inside the dp a loop between start and end will run, choosing different cut sections. We will take the one with minimum value.

But this results in $O(N^3)$ solution. Using Knuth’s optimization we can reduce it to $O(N^2)$.

Code: http://ideone.com/XD6hZP

UVa 12837 – Hasmot Ali Professor

Complexity: $O(100 \times |S|^2 )$
Category: String, Trie, Data Structure

We will create two trie trees. The first one will contain all the queries. Take a query and concatenate them in a special way. Take the first string of the query and add a $\text{‘#’}$ and then reverse the second string of the query and attach it to result. That is, if we have $abc$ and $pqr$ as query, then special string will be $\text{abc#rqp}$. Insert all special strings for each query in the first tries.

Now, let us process the main string $S$. We will take each of its suffixes and insert into the second trie. Now, when inserting the suffixes, each time a new node is created, we can say that we found a unique substring.

Each time we find a unique substring we will process it further. Take the unique substring, and using brute force generate all possible special strings ( the one we made using query strings ) with the first and last characters of the unique string. We don’t need to take more than $10$ characters from each end.

For each of those special string we made from unique substring, we will query the first trie with it and find the node where it ends. We will add one to that node number in a global array.

Once we finish processing all nodes in the second trie, we will simply traverse the first trie according to each query and print the result found in that node.

Code: http://ideone.com/fsYMxI

UVa 12838 – Identity Redemption

Complexity: Unknown
Category: Matching on General Graph

I didn’t manage to solve this yet. It looks like matching on a general graph.

UVa 12839 – Judge in Queue

Complexity: $O(N:logN)$
Category: Data Structure, Heap

We want to minimize the waiting time for each person. So first we will sort the people in descending order. Next, we will create a priority queue, which will contain all the service center along with the information about when that service center will be free. Initially, all service centers are free.

Now, we take each person and take out the service center that will get free at the earliest time. The person had to originally wait $x$ minutes and it took $y$ minutes for the service to get free again. So the person had to wait for $x+y$ minutes. We insert the service again inside the heap and update its free time by the time it takes to serve one person.

Repeat and keep track of the highest time a person had to wait.

Code: http://ideone.com/KVHnTX

Conclusion

I hope the details are clear enough for everyone to understand. Let me know if you find any mistakes.

Modular Exponentiation

forthright48 on August 17, 2015

Problem

Given three positive integers $B, P$ and $M$, find the value of $B^P \mod M$.

For example, $B=2$, $P=5$ and $M=7$, then $B^P \mod M = 2^5 \mod 7 = 32 \mod 7 = 4$.

This problem is known as [ref1] Modular Exponentiation. In order to solve this problem, we need to have basic knowledge about [ref2] Modular Arithmetic.

Brute Force – Linear Solution $O(P)$

As usual, we first start off with a naive solution. We can calculate the value of $B^P \mod M$ in $O(P)$ time by running a loop from $1$ to $P$ and multiplying $B$ to result.

int bigmodLinear ( int b, int p, int m ) {
    int res = 1 % m;
    b = b % m;
    for ( int i = 1; i <= p; i++ ) {
        res = ( res * b ) % m;
    }
    return res;
}

A simple solution which will work as long as the value of $P$ is small enough. But for large values of $P$, for example, $P > 10^9$, this code will time out. Also note that in line $2$, I wrote $res = 1 \mod m$. Some people tend to write $res = 1$. This will produce a wrong result when the value of $P$ is $0$ and value of $M$ is $1$.

Divide and Conquer Approach - $O(log_2(P) )$

According to [ref3] Wiki,

A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type (divide), until these become simple enough to be solved directly (conquer).

That is, instead of solving the big problem $B^P \mod M$, we will solve smaller problems of similar kind and merge them to get the answer to the big problem.

So how do we apply this D&C (Divide and Conquer) idea?

Suppose we are trying to find the value of $B^P$. Then three thing can happen.

Value of P is 0 ( Base Case ): $B^0$ is $1$. This will be the base case of our recursion function. Once we reach this state, we no longer divide the problem into smaller parts.
Value of P is Even: Since $P$ is even, we can say that $B^P = B^{\frac{P}{2}} \times B^{\frac{P}{2}}$. For example, $2^{32} = 2^{16} \times 2^{16}$, $3^6 = 3^3 \times 3^3$. Therefore, instead of calculating the value of $x = B^P$, if we find the value of $y = B^{\frac{P}{2}}$, then we can get the value of $x$ as $x = y \times y$.
Value of P is Odd: In this case we can simply say that $B^P = B \times B^{P-1}$.

Using these three states, we are can formulate a D&C code.

int bigmodRecur ( int b, int p, int m ) {
    if ( p == 0 ) return 1%m; // Base Case

    if ( p % 2 == 0 ) { // p is even
        int y = bigmodRecur ( b, p / 2, m );
        return ( y * y ) % m; // b^p = y * y
    }
    else {
        // b^p = b * b^(p-1)
        return ( b * bigmodRecur ( b, p - 1, m ) ) % m;
    }
}

In line $2$, we have the base case. We return $1 \mod m$ in case value of $m$ is $1$. Next on line $4$ we check if $p$ is even or not. If it is even, we calculate $A^{\frac{P}{2}}$ and return after squaring it. In line $8$, we handle the case when $P$ is odd.

At each step we either divide $P$ by $2$ or subtract $1$ from $P$ and then divide it by $2$. Therefore, there can be at most $2 \times log_2(P)$ steps in D&C approach. Hence complexity is $O(log_2(P) )$.

A Better Solution

A better solution to this problem exists. By using the Repeated Squaring algorithm, we can find the Modular Exponentiation faster than D&C. Repeated Squaring Algorithm has the same complexity as D&C, but it is iterative, thus does not suffer from recursion overhead.

We need to know about bitwise operations before we learn Repeated Squaring algorithm. Since we did not cover this topic yet, I won't write about this approach now. Hopefully, once we cover bitwise operations I will write another post

Resource

Wikipedia - Modular Exponentiation
forthright48 - Introduction to Modular Arithmetic
Wikipedia - Divide and conquer algorithms
forthright48 - Introduction to Number Systems

Leading Digits of Factorial

forthright48 on August 15, 2015

Problem

Given an integer $N$, find the first $K$ leading digits of $N!$.

For example, for $N=10$ and $K=3$, then first $3$ leading digits of $10! = 3628800$ is $362$.

Finding leading digits uses concepts similar to [ref1] Number of Trailing Zeroes of Factorial.

Brute Force Solution

Finding the value of $N!$ and then printing the first $K$ digits is a simple but slow solution. Using long long we can calculate value $N!$ up to $N \leq 20$ and using Big Integer we can calculate arbitrary $N!$ but with complexity worse than $O(N^2)$.

Solution Using Logarithm

In [ref1], we say that a logarithm of value $x$ is $y$ such that $x = 10^y$. For now let us find out leading digits of a value $x$ instead of $N!$. We will extend it to cover factorials later.

So, we know that $log_{10}(x) = y$, where $y$ will be some fraction. Let us separate $y$ into its integer and decimal part and call them $p,q$. For example, if $y = 123.456$, then $p=123$ and $q=0.456$.

Therefore, we can say that $log_{10}(x) = p + q$. Which means, $x = 10^y = 10^{p+q}=10^p \times 10^q$.

Now expand the values of $10^p$ and $10^q$. If $A=10^p$, then $A$ will simply be a power of $10$ since $p$ is an integer. To be more exact, $A$ will be $1$ with $p$ trailing zeroes. For example, $A=10^3 = 1000$. What about $B=10^q$?

Since $q$ is a fraction which is $0 \leq q < 1$, value of $B$ will be between $10^0 \leq B < 10^1$, that is, $1 \leq B < 10$.

Okay, we got the value of $A$ and $B$, what now? We know that if we multiply $A$ and $B$ we will get $x$. But don’t multiply them just yet. Think for a bit what will happen when we multiply a decimal number with $10$. If it is integer, it will get a trailing zero, e.g, $3 \times 10 = 30$. But if it is a fraction, its decimal point will shift to right, e.g $23.65 \times 10 = 236.5$. Actually, decimal points shifts for integer numbers too, since integer numbers are real numbers with $0$ as fraction, e.g $3 = 3.00$. So in either case multiplying $10$ shifts decimal point to the right.

So what happens if we multiply, $A$, which is just $10^p$ to $B$? Since $A$ has $10$ in it $p$ times, the decimal point of $B$ will shift to right $p$ times. That is all $A$ does to $B$ is change its decimal point. It does not change the digits of $B$ in any way. Thus, $B$ contains all the leading digits of $x$.

For example,
$log_{10}(5420) = 3.7339993 = 3 + 0.7339993$.
$\therefore B = 10^0.7339993 = 5.4200$.

So, if we need first $K$ leading digits of $x$, we just need to multiply $B$ with $10^{K-1}$ and then throw away the fraction part. That is $res = \lfloor B \times 10^{K-1} \rfloor$. Why $10^{K-1}$ not just $10^K$? That’s because we already have $1$ leading digit present in $10^q$ before shifting it.

Extending to Factorial

It is easy to extend the idea above to $N!$. First we need to find out the value of $y=log_{10}(N!)$.

$y= log_{10}(N!)$
$y= log_{10}(N \times (N-1) \times (N-2) \times… \times 3 \times 2 \times 1 )$
$y= log_{10}(N) + log_{10}(N-1) + log_{10}(N-2) + … + log_{10}(2) + log_{10}(1)$

So we can simply find out the value of $y$ by running a loop from $1$ to $N$ and taking its log value.

After that we decompose $y$ into $p$, integer part and $q$, fraction part. The answer will be $\lfloor 10^q \times 10^{K-1}\rfloor$.

Code

const double eps = 1e-9;

// Find the first K digits of N!
int leadingDigitFact ( int n, int k ) {
    double fact = 0;

    // Find log(N!)
    for ( int i = 1; i <= n; i++ ) {
        fact += log10 ( i );
    }

    // Find the value of q
    double q = fact - floor ( fact+eps );

    double B = pow ( 10, q );

    // Shift decimal point k-1 \times
    for ( int i = 0; i < k - 1; i++ ) {
        B *= 10;
    }

    // Don't forget to floor it
    return floor(B+eps);
}

The code does exactly what we discussed before. But note the $eps$ that we added when flooring value in line $12$ and $22$. This due to precision error when dealing with real numbers in C++. For example, due to precision error sometimes a value which is supposed to be $1$, becomes $0.9999999999999$. The difference between these two values is very small, but if we floor them both, the first one becomes $1$ whereas the second one becomes $0$. So in order to avoid this error, when flooring a positive value we add a small number ( epsilon = $0.000000001$ ) to the number.

Summary

We need to execute the following steps to find the first $K$ leading digits of a number $x$ ( in our problem $x=N!$ ):

Find the log value of the number whose leading digits we are seeking. $y=log_{10}(x)$.
Decompose $y$ into two parts. Integer part $p$ and fraction part $q$.
The answer is $\lfloor 10^q \times 10^{K-1} \rfloor$.

Resource

forthright48 - Number of Trailing Zeroes of Factorial