Monday, May 16, 2011

Hints for UVA Problem Set 11000


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.
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.
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.
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]) );
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.
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.
Given a graph of maximum 100 vertices, the idea is to find All Source Shortest Path. Use Floyd Warshall.
A simple checking algorithm. Use scanf/printf for faster I/O.
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.
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).
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 );
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)!
Basically Longest Increasing Subsequence to be solved in O(n log n).
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));
http://www.algorithmist.com/index.php/UVa_11038
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];
The only answers possible are 1,2,4 and TOO COMPLICATED. Think about it.
A simple math problem : "cout<<( ((int)n/3) * ((int)m/3) )<<endl;"
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).
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.
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.
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.
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.
Brute force to find all sequence products: the input is considerably small.
This document, volC10.html, has been accessed 4609 times since 19-Feb-09 21:42:38 SGT. This is the 2nd time it has been accessed today.
A total of 2394 different hosts have accessed this document in the last 779 days; your host, 119.30.39.82, has accessed it 3 times.
If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.
Alternative: A simple adhoc, as the input size is very small 18... so we just go through all possibilities...
Another string processing problem. First read in the string by lines , if the last one is - then change the - to 0, after read the string, reformat it. That is, if there is 0, delete it. So that the dis-ney will became dis0ney and disney. Split the word by token, add them into a set and use the iterator to output. Remember to convert all uppercase to lower.
11063 - B2-Sequence

Another simple search. As the input of each number is bounded. so the difference of the two numbers are bounded. Construct an array to store whether it appear before. Take note that if there consist of negative number, it is not a B2 sequence.

11064 - Number Theory

A math problem of number theory. We can compute the gcd(m,n) = m first, by computer all the divisor. by n=a1^b1*....ak^bk...number of divisor is (b1+1)* (b2+1)...(bk+1). Computer the gcd(m,n) = 1 by the Euler's totient function...see http://en.wikipedia.org/wiki/Euler%27s_totient_function. The coding is simple...

11067 - Little Red Riding Hood

Straight forward DP. The (i,j)is the sum of (i-1,j)+(i,j-1), the point which is possible to encounter the wolf is considered 0;

11068 - An Easy Task

Simple adhoc. Just compute the intersection of two lines. Note that the line can be parallel. Further more, the line many be vertical or horizontal..

11069 - A Graph Problem

A simple "DP". The formula is dp[i]=dp[i-1]+dp[i-5]; As the input is between 1 and 76. Better to pre-calculate all the results.
11074 - Draw Grid

Simple string simulation. Just follow the pattern... Note the output format...
Adding all permutations is a math problem. We need to calculate how many times the digit will occur in the place. For each digit, the adding time for each digit is the (n-1)!/ k! where k is number of repeat of the digit. so just multiply the digit with the adding time. As the permutation, the number should be the same in every decimal place. So just make sure to add c/10 to the next decimal place. Output every decimal place.
A ad hoc problem. Try to find the max difference between any two number in the sequence in O(n) time. If the current max if greater than the one, and the gap is greater than the max gap, update the max gap. If the current max is smaller than the one, update the current max. Do it for all numbers.
This is another ad hoc problem. First just compute all the solutions for the 8 queen problem. Read the input and compare each input with each solution, and find the minimum move one.
Composite prime. this is a math problem. Make the 4 as the first cprime. and do the same thing as the seive prime algorithm. If the number is not a prime and it is in the cprime list, then it is a composite prime.
It is a problem about recursion. First we can recursively find the number of k-digit numbers. So given the input we can determine the numbers of digits the output should be. Then we can determine the first digit of the number. We can minus the number of k-digit number. The remaining number, we do it recursively. The base case is 1 and 2. Remember to consider the number of 0s to print when doing the recursion.
it is a recursion problem (or some sense DP)
the formula is
f[n]=p[n]-q[n];
for (int j=n-1;j>=1;j--)
  if (f[j+1]<=0) f[j]=f[j+1]+p[j]-q[j];
  else f[j]=p[j]-q[j];
temp=0;
min=2147483647;
ff[1]=0;
for (int j=1;j<=n-1;j++)
{
  temp=temp+p[j]-q[j];
  if (temp<min) min=temp;
  ff[j+1]=min;
}
fff[1]=totalgas-totalneed;
for (int j=2;j<=n;j++)
  fff[j]=fff[j-1]-p[j-1]+q[j-1];
the fff[j] is the one.
answer is min(f[j], ff[j]+fff[j])
if answer>0 then j is satisfied.
This is a math problem. To avoid TLE we cannot brute force. For a give input we just get all the factors. And we create a queue. Adding all the numbers with the same factors into the queue. Find the minimum one which is greater than the input.

Posted by at