Series « Yet Another Blog

Posts Tagged ‘Series’

Two problems from the local ACM ICPC in FCIS Ain Shams

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

Yet Another Blog

Posts Tagged ‘Series’

Two problems from the local ACM ICPC in FCIS Ain Shams

Archives

Meta

Tags

Follow “Yet Another Blog”