Last updated on: 04 May 2009 01:04:38 PM

Comment on this volume: The hints for this volume are contributed by my CS3233 students:
11000-11049: Gaurav Chandrashekar, Faculty of Engineering, 2008/09 (GC)
11050-11099: Guan Yizheng (GY)

Total hints in this volume: 44

11000 - Bee

The problem is a cloaked version of the Fibonacci sequence. For each n, the number of male bees is fibonacci(n+2)-1 and the total number of bees is fibonacci(n+3)-1.

11001 - Necklace

Given Vt and Vo, we need to maximize the length of the necklace. Assume the necklace has n rings, write the function of the length of the necklace. See the maxima, and the corresponding value of n.

11002 - Towards Zero

Use usd[i][j][k] (max bool usd[70][70][6000] ) to know whether a sum of k can be got when you reach (i,j) from (1,1). Since the sum can range from -3000 to 3000, I denote k accordingly. So usd[i][j][k] is true only when usd[i-1][j-1][l] is true and l+val[i][j]=k or usd[i-1][j][m] is true and m+val[i][j]=k. Complexity is N^2*6000.

11003 - Boxes

Define RC(Residual Capacity) [i][j] as the maximum load that can be stacked above a configuration using the first i boxes and of height exactly j. RC[i][j]= max( RC[i-1][j], min ( lc[i], RC[i-1][j-1] - w[i]) );

11005 - Cheapest Base

A simple problem of converting a number from base 10 to base [2,3,...36].

11008 - Anitimatter Ray Clearcutting

This is a DP problem. The state is the uncutted trees, and can be expressed by a bit string.
F[s]=1+min(F[s & (~L)] (L is a maximized set of trees which are located in a line, and S&L!=0)
The complexity is O(n^2*2^n), n is the number of trees.

11012 - Cosmic Cabbages

The distance between 2 points can be simplified with these 4 possibilities.
max(x[i]+y[i]+z[i])-min(x[j]+y[j]+z[j]);
max(x[i]+y[i]-z[i])-min(x[j]+y[j]-z[j]);
max(x[i]-y[i]+z[i])-min(x[j]-y[j]+z[j]);
max(x[i]-y[i]-z[i])-min(x[j]-y[j]-z[j]);
for all i and j.
and each case takes O(n) time. So the complexity becomes O(n), and the max value of the four cases is the answer.
Maintain a Max and Min for all these 4 values . Output the global max.

11015 - 05-32 Rendezvous

Given a graph of maximum 100 vertices, the idea is to find All Source Shortest Path. Use Floyd Warshall.

11019 - Matrix Matcher

A simple checking algorithm. Use scanf/printf for faster I/O.

11020 - Efficient Solutions

Use the C++ STL Set to solve a problem. Each time a gentlemen arrives, put him into set according to the rule.
LB < LA and CB <= CA, or
LB <= LA and CB < CA. WHEN B precedes A.
Once you insert into the set , output the rank using the "distance" function.

11022 - String Factoring

DP. Let SF[i][j] be the maximal factoring for string s[i-->j]. BC is SF[i][i]=1;
If there is a repeated string in s[i--->j], find the minimal length of repeated string say k. So SF[i][j]=SF[i][i+k-1];
else SF[i][j]=min(SF[i][j],SF[i][k]+SF[k+1][k]) i<=k<=(j-1).

11026 - A Grouping Problem

Here we need to find the sum of product of a k element subset given n elements.
Define C[m][k] as the sum of product of the first m element k element subsets.
C[m][k]= C[m-1][k]+C[m-1][k-1]*( Value of the mth element );

11028 - Sum of Product

Formula Check http://www.research.att.com/~njas/sequences/Seis.html

11029 - Leading and Trailing

1) To find the last 3 digits, use %1000 and fast exponentiation of POWER(n,k);
2) To find the first digits? . We can write n^k as 10 pow( klog10n ). Klog10n has an integer part i and a decimal part d.
Since n^k is pow(10,i)*pow(10,d) , pow(10,i) cannot give you the first 3 digits ( Why? ) . The first 3 digitsis the first 3 digits of pow(10,d)!

11031 - Looking for a Subset

Basically Longest Increasing Subsequence to be solved in O(n log n).

11032 - Function Overloading

1st Observation: Since sod(i) can be only from 1 to 63, we need to check only for a-1 to a-63 in the fun(a);
2nd Observation: Since we need to know for fun(a,b) , the number of numbers between a to b , that return -1( or equivalently the return value of not -1) from fun(a) : Hence we store this value in f[i]; the output will be f[b]-f[a-1];

11034 - Ferry Loading IV

Simple simulation. Count how many times the ferry should cater to the left shore, denote this vaue by l. Now, count how many times the ferry should cater to the right shore, denote this value by r. Final answer - printf("%d\n",max(2*l-1,2*r));

11038 - How Many 0's

http://www.algorithmist.com/index.php/UVa_11038

11039 - Building Designing

Greedy Strategy. Sort the red and blue buildings. Start with the building color with the least floor space. Keep alternatively picking the next color floor with the least greater area.

11040 - Add bricks in the wall

For the odd rows, the gaps between the given numbers can be filled using the expression a[i][j]=(a[i-2][j-1]-a[i][j-1]-a[i][j+1])/2;
and for the even rows the sum is calculated normally using a[i][j]=a[i+1][j]+a[i+1][j+1];

11042 - Complex, difficult and complicated

The only answers possible are 1,2,4 and TOO COMPLICATED. Think about it.

11044 - Searching for Nessy

A simple math problem : "cout<<( ((int)n/3) * ((int)m/3) )<<endl;"

11045 - My T-shirt suits me

A maximum matching problem.

a) Mark Source 0.Node 1 to M represent the M volunteers. Node (M+1) to (M+6) represent the T-shirts.Node (M+7) is the sink.
b) Connect Source to the M volunteers with cost 1. Connect all the T shirts to the sink with N/6. For each volunteer , connect the two shirt that fits him with cose 1.
Print the maxflow (Graph simulated).

11047 - The Scrooge Co Problem

A simple Floyd Warshall Implementation. To print the path store in p[i][j], the last but one vertex visited in the shortest path from i ---> j.

11054 - Wine trading in Gergovia

This is a greedy problem.
The problem is actually an array containing different numbers representing the wine.
The positive and negative means the demand and supply.
So we can greedily make it linear. That is make the first house 0. transport the supply or demand to the second.
And then, to the third.....At the same time, record down the moves required.
The greedy works because every move of the wine can be broken into the move between two consecutive houses.

11055 - Homogeneous squares

A math problem..
consider the simplest case, n=2, so a1+b2==a2+b1;
quite simple, consider the n=3, it is easy to see that, if and only if every 2*2 square in 3*3 is Homogeneous square.
more generally, by mathematical induction, we can prove that n*n is Homogeneous square if and only if every (n-1)*(n-1) is
Homogeneous square.
so we can conclude that if the square is Homogeneous, every sub 2*2 square satisfy the a1+b2==a2+b1.
the coding is quite easy.

11056 - Formula 1

A sorting problem. I just count the time by ms. convert all the time to millisecond and compare them (use long long is enough) right a cmp function such that if it is equal, sort by the name. use strcasecmp to compare string case insensitively.

11057 - Exact Sum

Use the sliding window technique: To find 2 numbers whose sum is equal to K from a sorted array.

Alternative: very simple adhoc problem. just brute force all solutions, find the solution. remember when having multisolution, output the one with the smallest difference.

11058 - Encoding

A string processing problem. First just read the string and the rule. Apply the later rule first. Just do the simulation you will get it.

11059 - Maximum Product

Brute force to find all sequence products: the input is considerably small.