NUS Home8
Home | Up


- Above All -
- Lenny LeBlanc & Paul Baloche -

Above all powers

Above all things

Above all nature and all created things

Above all wisdom and all the ways of man

You were here before the world began

Above all kingdoms

Above all thrones

Above all wonders the world has ever known

Above all wealth and treasures of the earth

There's no way to measure what You're worth

Crucified

Laid behind the stone

You lived to die

Rejected and alone

Like a rose trampled on the ground

You took the fall

And thought of me

Above all

Last updated on: 07 August 2008 12:04:09 PM

Comment on this volume: N/A.

No

Problem Name

*

Algorithm

10800-10808

10800

Not That Kind of Graph

4.0

String Processing

10801

Lift Hopping

*

TLE - Graph (Shortest Path)

10802

Lex Smallest Drive

*

Haven't try yet

10803 Thunder Mountain 4.0 Graph (Shortest Path)

10804

Gopher Strategy

*

Haven't try yet

10805

Cockroach Escape Networks

*

Haven't try yet

10806

Dijkstra, Dijkstra.

*

Haven't try yet

10807

Prim, Prim.

*

Haven't try yet

10808

Rational Resistors

*

Haven't try yet

10809-10813

10809

Great Circle

*

Haven't try yet

10810 Ultra-QuickSort 4.5 Sorting

10811

Up the Ante

*

Haven't try yet

10812 Beat the Spread! 2.5 Math

10813

Traditional BINGO

3.0

Ad Hoc

10814-10819

10814

Simplifying Fractions

*

Haven't try yet

10815 Andy's First Dictionary 4.5 String

10816

Travel in Desert

*

Haven't try yet

10817

Headmaster's Headache

*

Haven't try yet

10818

Dora Trip

*

Haven't try yet

10819

Trouble of 13-Dots

*

Haven't try yet, look at Eduard's notes

10820-10829

10820

Send a Table

*

Haven't try yet - Pre-calculate the answer?

10821

Constructing BST

*

Haven't try yet

10822

Planet of the Rock, Paper and Scissors

*

Haven't try yet

10823

Of Circles and Squares

*

Haven't try yet

10824

Regular Polygon

*

Haven't try yet

10825

Anagram and Multiplication

*

Haven't try yet

10826

Hot or Cold?

*

Haven't try yet

10827

Maximum sum on a torus

*

Haven't try yet

10828

Back to Kernighan-Ritchie

*

Haven't try yet

10829

L-Gap Substrings

*

Haven't try yet

10830-10839

10830

A New Function

*

Haven't try yet

10831

Gerg's Cake

*

Haven't try yet

10832

Yoyodyne

*

Haven't try yet

10833

Lunar Forest

*

Haven't try yet

10834

The Story of Two Coins

*

Haven't try yet

10835

Playing with Coins

*

Haven't try yet

10836

The Maximum Term

*

Haven't try yet

10837

A Research Problem

*

Haven't try yet

10838

The Pawn Chess

*

Haven't try yet

10839

The Curse of Barbosa

*

Haven't try yet

10840-10899

10843

Anne's Game

-

Haven't try yet

10849

Move the Bishop

-

Haven't try yet

10852

Less Prime

-

Haven't try yet

10865

Brownie Points I

-

Haven't try yet

10878

Decode the tape

-

Haven't try yet

10879

Code Refactoring

-

Haven't try yet

Total submit-able problems in this volume: 100
Solved problems: 10
Problems in Wrong Answer list from this volume: 1
Unattempted problems: 91
Total hints in this volume: 14


10800 - Not That Kind of Graph

This is a string processing problem, just follow the problem description. To help you determine whether you already get a correct implementation or not, let me give you several examples (see the highlighted text to view the whitespaces):

Input:

4
RCRFCRFFCCRRC
FFFCCC
RFCRFC
CCCRRF

Output:

Case #1:
|             _
|  _/\_/\    /
| /      \__/
+---------------

Case #2:
| \
|  \
|   \___
+--------

Case #3:
| /\_/\_
+--------

Case #4:
|     /\
| ___/
+--------


10801 - Lift Hopping

This problem, although is a bit weird for real-life situation, can be transformed into graph problem. Give edges between floors that can be served within one lift, the weight of this edges is the gap between floors * time required by this lift to move one floor. Also, add another edges that connects two lifts if they stop at the same floor, give weight 60. The solution is the shortest path from floor 0 to floor k by traversing this graph. Please use Dijkstra algorithm.

10803 - Thunder Mountain

A simple all-pairs shortest path problem. Firstly, build a distance matrix (use floating point). Set the distance to a very big number (say, 1 million) if it is bigger than 10 km. Then, perform floyd warshall algorithm to obtain the shortest path from any pair of towns. Then, pick the longest path among these shortest path distances, this will be your answer... if the answer is greater than 1 million, then output "Send Kurdy" since there exist a pair of town that are unreachable.

10810 - Ultra-QuickSort

This problem is actually a problem of counting "inversion index" using merge sort. Since merge sort runs in O(n lg n), 500.000 lg2 500.000 ~~ 10.000.000 operations... doable...

To compute inversion index, merge sort can be slightly modified. When the right partition goes in first in merge step, that means all the remaining items in left partition < first element in right partition (i.e. you have to swap with all of them).

Note: since the number of such op swaps can be very large, you must use unsigned long long to store op.

10812 - Beat the Spread!

From the problem description, we know that:

score1 + score2 = s, and
score1 - score2 = d (assuming score1 >= score2).

Therefore:

score1 = (s+d)/2
score2 = s-score1

This formula will only valid if (s+d)%2 == 0 and score1 >= 0 and score2 >= 0.

10813 - Traditional BINGO

This problem is quite straightforward. Just follow the description given in the problem description. For the 'free space' in the center, mark it from the beginning, that's all...

10815 - Andy's First Dictionary

Simple string processing problem. Tokenize each word (word is defined as sequences of a-z/A-Z only!), lowercase them, and then hash them to a good hashtable (in C++, I use STL map). Finally, output the strings in sorted order.

10820 - Send a Table

This is what I can derive so far:
TotalPrecalculated[1] = 1; // base case
TotalPrecalculated[i] = TotalPrecalculated[i-1] + 2*(number of occurrences of j, j<=i, and gcd(j,i) == 1)

I think I will going to pre-calculate this values up to 50000, store it in a table, and then send this table to the judge?...

10843 - Anne's game (by: Niaz Morshed Chowdhury)

This problem looks very tough but only to them who don’t know Cayley’s formula. It gives the number of distinct spanning trees in a complete graph on n vertices.

Basic formula :  n^(n-2).

But for higher value of n, like n = 100, you can easily understand the situation. It will cause overflow. So, to avoid this problem, we can take the help of Number Theory. From Chinese Remainder rule we know, In case of consecutive multiplying if we MOD a  number at each step of multiply by a particular number then the result will be same as the result of doing MOD at the end of the multiplications that particular number.   

Example

22 * 1 = 44
44 * 2 = 88
88 * 3 = 264

264 % 10 = 4

But,

22 * 1 = 44 % 10 = 4
4 * 2 = 8 % 10 = 8
8 * 3 = 24 % 10 = 4

So, we can see the result is same in both the cases. In this problem we just need to write a function that will find the power of any number and at each intermediate step it will MOD the result by 2000000011. Then there will be no chance of having Over Flow.

10849 - Move the Bishop (by: Niaz Morshed Chowdhury)

For this problem we can say that a bishop needs to move at best twice to go from any square to another one. WHY? Very simple! Look at the chess board. You can understand it.

So, the possible results will be:
0 – if the source and destination is same.
1 – if the source and destination situated on the same line. (In the picture for black we have shown the lines by red and green colors.)
2 – if the source and destination situated  on the same color but different line.
no move – if source and destination situated on different color.

We will be given N (matrix size) and x1,y1 (source), x2,y2 (destination)

Use if else just following this order!

Case # 1 : Out of the board

If any one of x1,y1,x2,y2 is greater than N then “no move”
Explanation: As the board size is N, no value can not be greater than it.

Case # 2 : Source and Destination is same

If x1=x2 and y1=y2, then “0”
Explanation: As source and destination are same.

Case # 3 : On the same line (Red lines in the picture)

if  abs(x1-x2) = abs(y1-y2), then “1”.
Explanation: Look at the picture along red lines. 1,3 – 2,4 – 3,5 – 4,6 etc.
At each square index is increasing by 1 in both x and y axis. So, if the difference of  x and y of source and destination is same then they will be on the same line.

Case # 4 : On the Same line (Green Lines in the picture)

if x1+y1 = x2+y2 , then “1”.
Explanation: Look at the picture along green line. 1,7 – 2,6 – 3,5 – 4,4 etc.
At each square index is decreasing by 1 in y axis and increasing by 1 in x axis. As a result, sum is always same. So, if the sum of [x,y](source) and sum of [x,y](destination) is same then they will be on the same line.

Case # 5 : On the same color (For white)

if x is odd and y is even  or if x is even or y is odd then this square is white.
Now, if source and destination is white and case 1 to 4 fails, then answer is “2”
Explanation: This is just my observation. Look at the picture. You can also understand it.

Case # 6 : On the same color (For Black)

if x and y both are even or if x and y both are odd then this square is Black.
Now, if source and destination is Black and case 1 to 4 fails, then answer is “2”
Explanation: This is just my observation. Look at the picture. You can also understand it. 

Case # 7 : Un reachable

If case 1 to 6 fails then unreachable. So, the answer is “no move”.

10852 - Less Prime (by: Niaz Morshed Chowdhury)

This is actually an easy prime problem.

Problem wants, “Let n be an integer, 100 ≤ n ≤ 10000, find the prime number x, x ≤ n, so that n-p*x is maximum, where p is an integer such that p*x ≤ n < (p+1)*x.” If we simplifies this statement then we can locate the position of the desired prime number !

If n is the input then our desired prime number will be just the prime number after/from this number “k = n/2 + 1”. Now, generate the prime numbers and check according to this statement and you will easily get it accepted. 

Example

n = 101
k = n/2 + 1 = 50 + 1 = 51.

So the next prime number from this number is 53.

10865 - Brownie Points I (by: Niaz Morshed Chowdhury)

This is actually a checking problem. At first we need to find the dividing line region. Then will start to check for each point based on some criteria for Stan and Olie. Here goes the algorithm.

k=N/2+1; // mid point that is actually the dividing line region.
x=a[k]; // a[] holds the X co-ordinate value and x is the X of the mid point.
y=b[k]; // b[] holds the Y co-ordinate value and y is the Y of the mid point.

stan=0; // Initially both of them have 0 score.
olie=0;

for (i=1; i<=N; i++) {
  if ((a[i]>x && b[i]>y)||(a[i]<x && b[i]<y)) // Criteria for Stan
    stan++;
  if ((a[i]>x && b[i]<y)||(a[i]<x && b[i]>y)) // Criteria for Olie
    olie++;
}

Just print the value of stan and olie.

10878 - Decode the tape (by: Niaz Morshed Chowdhury)

Very easy problem. To solve this problem at first you need to decode what the problem actually wants. In the problem description you can not find any type of hint of actually what you need to do ! The only clue is the sample input and which is really sufficient. 

Look at the sample input. You will get something like this one,
___________
| o   .  o|
|  o  .   |
| ooo .  o|
| ooo .o o|
___________

Just ignore the first and the last line. Consider from second to second last line and also ignore there the first (from left), 7th and 11th character. From rest of the character consider ‘space’ as ZERO and ‘o’ as ONE. Now convert this binary number to decimal and output the corresponding character.

Example

| o   .  o|

x01000x001 => 01000001(b) => 65(d) => A.

10879 - Code Refactoring (by: Niaz Morshed Chowdhury)

Trust me! Just find arbitrarily any two numbers that forms the given number. Here you need to find two such pair. Its a special judge problem and there is nothing called special or critical test case.

My Process:
1. Start from 2 to find two divisor of the given number.
2. Now, divide the given number with these two numbers and get another two!
3. Just print them according to the given format and get it accepted.


This document, volC8.html, has been accessed 7393 times since 12-Apr-05 20:24:42 SGT. This is the 6th time it has been accessed today.

A total of 3841 different hosts have accessed this document in the last 1275 days; your host, 38.103.63.60, has accessed it 2 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.