“Around here, however, we do not look backwards for very long. We keep moving forward, opening up new doors and doing new things… and curiosity keeps leading us down new paths.” - Walt Disney and the theme of the movie: "Meet the Robinsons".

Last updated on: 04 May 2009 12:48:03 PM

Comment on this volume: Many hints for this volume are contributed by my CS3233 students:
10900-10949: Chua Kien Chuan, Chris (CC)
10950-10999: Dai Fei (DF)

Total hints in this volume: 37

10902 - Pick-up Sticks

Computational Geometry problem. Line Segment intersection. Simply apply the algorithm found on TopCoder website (or anywhere else). Keep a list of lines as lines are read from input, check whether they intersect with any line already in the list. Note that the online judge does not handle deletion of items in a list as per defined. As such, use another vector to contain the list iterators of items to delete then delete them after traversing the list.

10906 - Strange Integration

This is an Ad-hoc problem. Use an ADT to keep track of the expressions as two strings (left and right operands) and an operator. Resolve the
expression each time a simple expression is encountered and print the last one. The tricky part is figuring out when to output the parentheses, must read the BNF notation given.

10908 - Largest Square

This is a simulation problem. Just read in the string of input and starting from each given centre of the square increment the size of the
square and check whether all the edges of the new square is of the same character as the centre character.

10910 - Marks Distribution

This is a dynamic programming problem.
F (N, T, P) = f ( T - N*P, N );
Define f as the number of ways to put n number of things in
b number of boxes.
f ( n, b ) = summation ( for i= 0 -> n { f (i, b - 1) } )
Base cases: (x is a positive integer)
f ( x, 0 ) = 0
f ( 0, x ) = 1

Since 0 < N,T,P <= 70, just calculate 0 < num, boxes <= 70 for f.
This algorithm runs at near constant time of about 70*70+K passes (K is the number of test cases).

10912 - Simple Minded Hashing

Use memoisation (dynamic programming) in this problem. Use a function f(l, n, k) where f is the number of strings that start with the letter
l and are sum up to be n and have are of length k. f(l, n, k) = summation {f(i, n - i, k-1), where i is l+1 to 'z'}. f(x, 0, 0) = 1 for x <= 26 and f(a, y, 0) = 0 for any y != 0 and any a.

10916 - Factstone Benchmark

Adhoc/Mathematics problem. Use logarithms to simplify the formula:
2^(2^(y+2)) > n!
to:
2^(y+2) * log(2) > log 1 + log 2 + ... log n

Find the first number that exceeds 2^(y+2) and output n. y is calculated from y = (year - 1960) / 10

10919 - Prerequisites?

10919 is a simulation problem. Just keep track of meeting category requirements as the input is read. Keep a Boolean flag to track whether requirements have been met and print "yes" if requirements have been met and "no" otherwise.

10920 - Spiral Tap

This is an Ad-Hoc problem. Start from the centre of the grid system and keep track of the coordinates while iterating to reach P. Keep track of the direction of movement and increment (or decrement) x and y as per direction. The maximum number of iterations is ((99999 - 1)/2*4 + 1) = 199997. This is for the worst test case for this algorithm which is "99999 9999800001". This number can be halved for increased efficiency for large numbers of test cases by searching from the last spiral coordinate, but this adds some complexity of coding...

10921 - Find the Telephone (by: Niaz Morshed Chowdhury)

Very easy problem. Assign the given Numerical value in an array of size 26 according to the given table. These 26 value will actually indicate letters from A to Z.

Now,

Let ‘S’ is the input string.
Loop i = 0 to length –1  of S.
  if (S[i]== any letter)
    output the corresponding value from the table.
  else
    output the original value from S (See the note)

Note: The problem statement tells that other than A-Z there will be only three characters in the input, those are 1,0 and ‘-‘. In my solution I checked them specially and if there is any blank space because of this check still this method will work.

Alternative: Ad-Hoc problem. Keep a character array of the numbers that the alphabets map to. Traverse the string and replace the alphabets with the respective numbers.

10922 - 2 the 9s (by: Niaz Morshed Chowdhury)

This is actually not a Big Number problem. This problem can be solved very easily by using the divisibility testing by 9. This question has two parts. 1. Divisibility, 2. If so then Degree.

For Divisibility

Let a is number. Then, a is divisible by 9 if and only if the sum of the digits a(n) + a(n-1) + ... + a(1) + a(0) is divisible by 9.

For Degree

Degree means, how many times it is needed to add the digits together to convert the given number from the original form to an one digit number. Interestingly, you can see that if a number is divisible by 9 then after converting it to a one digit number it will be 9.

So, to solve this problem, convert the given number in an one digit number and track the degree while doing this process and finally if the number is 9 just output the statement according to the problem with number and the degree else tell this is not a multiple of 9.

Example

999
9+9+9 = 27 -> 2 + 7 = 9

So, its a multiple of 9 and having 9-degree of 2 as we needed to add it twice.

Alternative: Simulation. Run the recurrence as described by the problem. Store the result in a string for easy summing of the digits. Stop recurring (iterating) when the string becomes a length of 1 digit. If that digit is 9, it N is a multiple of 9, it's 9-degree is the number of iterations.

10923 - Seven Seas

BFS/Simulation problem. Simulate the movement of the ship and enemy ships. BFS can be very costly, O(b^d) which is 134217728 per given case. As such optimizations have to be used in the algorithm. Optimize by always processing the state with the least enemy ships left first so as to reach the goal state as soon as possible.

10924 - Prime Words (by: Niaz Morshed Chowdhury)

Probably the easiest prime related problem of this judge. According to this problem, a=1, b=2 ... z=26, A=27, B=28 ... Z=52. Given a string consist of these letters. Convert them to their corresponding numerical values and then add them all. If the sum is a prime number then it will be a prime word otherwise not. Note that the maximum sum can be 1020 (52 x 20). So, just generate the primes up to this limit and get it accepted.

Alternative: Use sieve method to find the primes up to 1040 since the largest number to be encountered is 20*52 by the definition of 'Z' and length L. Output whether the it is a prime word after calculating the sum of the alphabets.

10925 - Krakovia (by: Niaz Morshed Chowdhury)

A Big Number problem. Add the given number and then find the average. In case of finding the average, just ignore the remainder part.

Example

540
540
454

Sum = 1534 and Average is 511.33 or 1533 and 1 will remain as remainder. So, output only 1533. 

Alternative: BigInteger problem. Only issue with this problem is arithmetic with large numbers. Using Java's BigInteger, this problem is simplified.

10926 - How Many Dependencies? (by: Niaz Morshed Chowdhury)

You can solve this problem very easily by using modified DFS.
1. At first take the input and convert it to a graph.
2. Call DFS_visit function with each node of the graph individually.
3. Track how many nodes it visits while traversing through the Recursion.
4. Output the node number that visited most nodes.

Note

1. Initialize your color flag before calling each DFS_visit.
2. Start calling DVS_visit from 1. It will automatically handle the case if there is any tie.

Alternative: Simple graph problem, find the maximum depth considering each node as the root of a tree. DFS, using memoization to speed up the search (since max depth for each node remains the same, and there are no cycles).

10927 - Bright Lights

Computational Geometry. Use cotangent of the points to solve this question. Have a map to keep track of x / y (cotangent) . y == 0 is a special case and it's cotangent is INF or -INF depending on whether x is positive. A fraction can be used for this but the range and arithmetic does not require such precision and such just a double is used. For each element of the map keep track of poles in that gradient (cotangent) and order them by their distance from (0,0), for this, simply keep abs(x) instead of x, and when outputting, make sure to negate it back using the cotangent value.

10929 - You can say 11 (by: Niaz Morshed Chowdhury)

Another problem that can be solved by using divisibility testing.

Let a is the number. Then, a is divisible by 11 if and only if the alternating sum of the digits is divisible by 11.

More clearly, add all the even position digits and odd position digits separately. Then subtract even sum from the odd sum. If the subtracted value is divisible by 11 then the number will be divisible by 11.

Example

2937

If we look from the left side (as C array looks), then we will get 2 at zero, 9 at 1, 3 at 2 and 7 at 3 rd position. So, odd sum = 9 + 7 = 16 and even sum = 5. So the subtracted value will be 16-5 = 11 which is divisible by 11.

Alternative: Ad-hoc problem. Mathematics/Number theory might be used to solve this problem but another way is to manipulate the string. Let s = 11 * n for any integer n. The least significant digit of s is also the least significant digit of n. As such the second least significant digit of s can be found by subtracting the second least significant digit of n and so on. If the digit is less than the previous digit, then a carry over has to be done. If carry over cannot be done after traversing through all the digits including the most significant digit, then the number is not divisible by 11, else continue until the most significant digit, and if the most significant digit is 0 at the end of the algorithm, then the number is divisible by 11. Other methods maybe used to solve this problem, but this solution was conceived without any reference to number theory.

10930 - A-Sequence

Ad-hoc. Keep track of all the sums of the 2 or more previous numbers in the sequence using a set and a bitset. Check whether a new number is larger than the previous number, and whether it is true in the bitset. Stop checking once the sequence is found to be not A-Sequence.

10931 - Parity (by: Niaz Morshed Chowdhury)

One of the easiest problem of this judge.

Task to do:
1. Divide each number by 2 until it will become zero.
2. At each step check whether the remainder is zero or one and also print the value.
3. If one then increase your count (initialized by zero) and finally it will hold the parity.

Note : Be careful about the least/most significant bit while printing.

Alternative: Can manually use modulus, but the use of bitset in STL makes this problem simply just using it to construct, count() and output as string. Make sure to print only the relevant substring, number of digits calculated by the floor of the log base 2 of N.

10935 - Throwing cards away I (by: Niaz Morshed Chowdhury)

This is basically a simulation problem. According to the problem statement - “Throw away the top card and move the card that is now on the top of the deck to the bottom of the deck.”. Just simulate this process.

You can also find the result by some tricky calculation as the time limit of this problem is quite fine to do the simulation. We can keep the energy to find that tricky calculation for the problem 10940 which is actually an extended version of this one.

Alternative: Simulation with a deque data structure.

10940 - Throwing cards away II (by: Niaz Morshed Chowdhury)

This problem is actually an extended version of the problem 10935. Here we have been asked to find the last card after doing the simulation that we did in problem 10935. This time the input size to too big and we can not just do a simulation. We need to find some tricky way to get the last card at the end of the process without doing any simulation. Here is my algorithm.

Algorithm

Take the input n.
Let x is an integer initialized by 1.
Loop until x>=n
  x = x*2
s = x%n
Result = n – s
Output = Result.

How does it work ?
1. By multiplying x with 2, we are actually tracking the cards after throwing and moving at the bottom.
2. By s = x%n and Result = n – s,  we are getting the card position and card number.

NB : During the contest time, all on a sudden I discovered this algorithm and I do not have any proof for it. But it works pretty nicely.

Alternative: Ad-Hoc. Similar to a previous 3233 Contest question. Using a dp-like bottom-up approach by observing the order or reordering of the cards, a 50000 integer array can be filled. Another way is to simply find the largest power of 2 smaller than or equal to given N (call this number K), and 2*(N-K) is also the answer, this is from observing the numbers.

10945 - Mother Bear (by: Niaz Morshed Chowdhury)

Simple problem. You need to find whether the given string is a palindrome or not. But you must consider some extra thing while need to ignore some other things.

To Consider : You need to consider the string as a case non-sensitive one.
To Ignore :  '.', ',', '!', '?' and blank spaces.

Example

Madam, Im adam!
After removing the ignoring items we get,
MadamImadam
As they are all case non-sensitive, it looks,
madamimadam
which is a palindrome.

Alternative: Ad-hoc. Read in each line of input check whether the alphabets are same with two iterators one from the beginning and one from the end. Skip non-alphabetical characters and lowercase the characters before comparing. Output "You won't be eaten!" if it is a palindromic sentence else output "Uh oh..".

10948 - The primary problem (by: Niaz Morshed Chowdhury)

An easy prime related problem. Here goes my algorithm.
1. Generate prime up to 1,000,000 using sieve.
2. Let n is the input.
3. Now start I from 2 to up to n/2 + 1.
4. If  I is a prime and n – I is also a prime then break.
5. Else No Way !

Note : “If there are more than one set of sums for which this is true, choose the set of sum the maximizes the difference between them.” As we start from a smaller side, in each step we get the numbers with maximum difference. As a result this statement will automatically be maintained by the algorithm.

10950 - Bad Code

Since only the first 100 is required, check in alphabetical order, and output the first 100 result.
Output one line after each test case, not output one line between each two test cases.

10954 - Add All

The numbers calculated earlier will be calculated for more times. So calculate small numbers first. Use a priority queue to store the numbers.
Each time, pick 2 from the queue to get the sum. Add sum to totalSum, push sum back into queue. Output totalSum.

10958 - How Many Solutions?

Critical difficult is time.
From the function given, prove it is a hyperbola and (0,0) must be a point on it.
Prove it is symmetrical. Then the aim is to find sum = integer points on half of it.
Return sum*2-1 since (0,0) is on it but is not a solution for this problem.
Prove the hyperbola is x*y=d, where d = abs(m*n*p*p).
Number of integer solution on half of hyperbola sum = positive factor number of d.
d can be as large as 1000*1000*1000*1000, and there can be 1001 test cases in 2 second.
Use long long.
Find the factor count (slower than this will cause time limit exceed):

sum = 1;
fac = 2;
facCount = 0;
while (fac <= d) {
  if (d % fac) {
    sum *= (facCount + 1);
    fac++;
    facCount = 0;
  } else {
    d /= fac;
    facCount++;
  }
}
sum *= (facCount + 1);
Output sum*2-1

10959 - The Party, Part I (by: Niaz Morshed Chowdhury)

A simple BFS problem. Here is the process:
1. Take the input.
2. Form the input as a bi-directional graph, which means if a is connected with b and b will also be connected with a.
3. 0 is Don Giovanni’s number. Call BFS with 0.
4. In the distance matrix, you will get all the distance from 0. Print this matrix.

10961 - Chasing After Don Giovanni

Just simulate the process.
Remember to continue reading all even after checked fail, to avoid interfere next test case.
For each single step, check succeed. If not succeed, check caught. If not caught, perform the step.

10963 - The Swallowing Ground

Check every column to see if every column has the same y2-y1.

10964 - Strange Planet

Calculate x and y coordinates by a certain function. O(1). Output distance between (x1,y1) and (x2,y2).

10967 - The Great Escape

Shortest path can be solved by BFS.

10970 - Big Chocolate (by: Niaz Morshed Chowdhury)

Smallest problem I have ever solved. If you look at the chocolate matrix then you can easily find the formula. Still giving here, Simple formula, result = m*n – 1. My accepted solution took just 2 core lines of code !

My Code:

#include<stdio.h>
int main() {
  int m,n;
  while (scanf("%d%d",&m,&n) == 2)
    printf("%d\n",m*n-1);
  return 0;
}

Alternative: Each cut will increase piece number by 1. To get M*N pieces from 1 pieces, M*N-1 cuts are needed. Output M*N-1.

10973 - Triangle Counting

The problem mentioned time.
Define triangle as (x,y,z), x<y,y<z. Store only the edges(i,j) such that i<j.
Loop i from 1 to n, loop j from i to n, loop k from j to n. If found triangle<i,j,k>, count increase.
Total is about O((n^3)/6). Fast enough.

10976 - Fractions Again?!

Let 2 numbers be A and B such that A/(K*C)+B/(K*C)=1/K=(A+B)/(K*C) and A+B=C=1
Assume gcd(A,B)=1. Otherwise if gcd(A,B)=d, A=ad,B=bd,C=A+B=(a+b)d, gcd(a,b,c)=d, then just assume A/(K*C)+B/(K*C)=1/K to be
a/(K*C)+b/(K*(a+b))=1/K, which is another set of A,B, or say another solution.
Since gcd(A,B)=1,gcd(A,C)=1,gcd(B,C)=1. A/(K*C)=1/something, so K%A=0. For the same reason, K%B=0.
So, A and B are just two factor of K which has gcd(A,B)=1.
Test from 1 to K/2 to find K's factors adding K itself. Store them.
REP(i, fac[0], fac[fac.size-2])
REP(j, i, fac[fac.size-1])
if (gcd(i,j)==1)
Output certain results.

10977 - Enchanted Forest

Read input. Mark unvisitable points. Perform BFS to find the shortest path. Output the shortest path.

10978 - Let's Play Magic!

Just simulate it. "Put card" at the time of "Picking card". Maybe linked list will be faster, but I was only accepted for the array simulating one.

10980 - Lowest Price in Town

Dynamic programming. Only 1 dimension that is the itemCount.
For each uninitialized price for a certain itemCount, search among all given prices, and then search among all smaller cases to find the best price, and then save and return it.

10982 - Troublemakers