Sola Fide, Sola Gracia, Sola Scriptura - Only by Faith, by Grace, and God's word

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

Comment on this volume: None

Total submit-able problems in this volume: 100
Solved problems: 28
Problems in Wrong Answer list from this volume: 5
Unattempted problems: 67
Total hints in this volume: 36

10500 - Robot maps

Don't use DFS -_-', this problem is a pure simulation only !!!, you can't backtrack like what DFS did and update your map... your robot CANNOT do that !!!.... Simply simulate the robot movement according to the problem description (go North,East,South,West... in that order...)

10502 - Counting rectangles

At first I thought this problem will be difficult. But when I see the high acceptance rate, I thought that brute force may be possible... and it is. I have 6 nested loops in my solution (two for starting index (x1,y1), next two for ending index (x2,y2), and another final two loops to check whether rectangle with two corners (x1,y1,x2,y2) have all '1'...). It works :)

10503 - The dominoes solitaire

Backtracking. Max 13 spaces only. Remember you can flip domino. i.e. domino (1,2) can be used as domino (2,1). Just try all possibilities to make sure whether first and last dominoes (given in the input), can be joined using other given dominoes to fill in the empty spaces.

10504 - Hidden squares

Brute force, O(n^4). Do for loops, (i,j) then (k,l). If grid[i][j] contains the character, then do find the next grid[k][l] which contains the character too, where k >= i, and l > j (notice, l strictly greater than j, since we only want to check for east and south east region to avoid multiple counting).

Okay, after you got index (i,j) and (k,l), you have "found" two vertices of the square. Now just test the remaining two vertices of a square (try drawing some squares on a paper to help you understand the following derivation):

deltaX = k-i;
deltaY = l-j;
vertex3X = k+deltaY;
vertex3Y = l-deltaX;
vertex4X = i+deltaY;
vertex4Y = j-deltaX;

If vertex3[X][Y] and vertex4[X][Y] has the same character... then yes, this is a square :D, increase counter. If any of them has different character, no... this is not a square.

Simple isn't it :D.

10507 - Waking up brain

Every time you encounter the word 'connected', it's a hint to use disjoint forest Union-Find data structure.

In this problem, you have 2 sets, 1 set of awake areas (initially you have 3 elements here) and a set of the remaining slept areas.

Your goal is to check whether for each slept areas, you have 3 adjacent neighbors who are already in awake set (check using Find method), if yes then at the end of iteration, Union them with this awake set (they are now part of awake Set), increment year by 1.

Repeat the above process until no more slept areas or until there is no more slept area can be awaken. If no more slept areas, output : "WAKE UP IN, N, YEARS". If there is one or more slept areas left, output "THIS BRAIN NEVER WAKES UP".

10508 - Word Morphing

Key hint: Number of words = Number of letters + 1. Just find the difference, then order these morphing words according to their differrence.

10509 - R U Kidding Mr. Feynman?

Simple math... if n is a perfect cube, directly output the cubic root of n, otherwise, use Feynman approximation formula as previewed for square roots... In case you are confused how to derive the formula, I'll show you how:

n^(1/3) = a + dx
n = (a + dx)^3
n = (a^2 + 2*a*dx + dx^2) (a + dx)
n = a^3 + 3*a^2*dx + (3*a*dx^2) --> drop this small term 3*a*dx^2
n = a^3 + 3*a^2*dx
dx = (n - a^3) / 3*a^2

Feynman will output a + dx as his approximation answer.

10510 - Cactus

This problem is to check the property of a given directed graph. It should be a strongly connected graph and have this "cactus" property as given in the problem statement. I haven't solve this actually, but this shouldn't be too difficult other than tedious...

10515 - Power et al.

Observe this pattern:

Note: I just care the last digit
0^1=0, 0^2=0, 0^3=0, 0^4=0, (0^5 == 0 == 0^1 ...)
1^1=1, 1^2=1, 1^3=1, 1^4=1, (1^5 == 1 == 1^1 ...)
2^1=2, 2^2=4, 2^3=8, 2^4=6, (2^5 == 2 == 2^1 ...)
3^1=3, 3^2=9, 3^3=7, 3^4=1, (3^5 == 3 == 3^1 ...)
4^1=4, 4^2=6, 4^3=4, 3^4=6, (4^5 == 4 == 4^1 ...)
5^1=5, 5^2=5, 5^3=5, 5^4=5, (5^5 == 5 == 5^1 ...)
6^1=6, 6^2=6, 6^3=6, 6^4=6, (6^5 == 6 == 6^1 ...)
7^1=7, 7^2=9, 7^3=3, 7^4=1, (7^5 == 7 == 7^1 ...)
8^1=8, 8^2=4, 8^3=2, 8^4=6, (8^5 == 8 == 8^1 ...)
9^1=9, 9^2=1, 9^3=9, 9^4=1, (9^5 == 9 == 9^1 ...)

To make full use of this pattern, you only need to consider the last two digits from the input m and n (note that m and n can be extremely long number, but we only need the last two digits from m and n).

There is also a special case when n = 0, then the result will be 1, since everything raised to the power of zero is defined as 1.

10519 - !! Really Strange !!

Output n*n - n + 2 using Big Integer. The derivation? I'm not sure yet... Anyone want to help?

10522 - Height to Area (by: Tam Wai Lun)

10522 is a maths problem so after figuring out the formula it's easy to implement. The vague part was that, if any of the input is zero or negative, the answer must be "invalid". The formula I used was x^2 = 1 / (A+B+C)(-A+B+C)(A-B+C)(A+B-C) where A,B,C is 1/Ha, 1/Hb, 1/Hc respectively. So if the rhs is negative, the answer is "invalid", otherwise sqrt it to get the answer. This was my working.

Let a,b,c be the length of the sides, x be the area

From Heron's formula,
x=sqrt(s(s-a)(s-b)(s-c)) ---(2)
where s=(a+b+c)/2 ---(1)

With x=(1/2)(base)(height), express a,b,c in terms of x,Ha,Hb,Hc,
a = 2x/Ha
b = 2x/Hb
c = 2x/Hc

Sub into eqn (1),
s = (a+b+c)/2
= (2x/Ha + 2x/Hb + 2x/Hc) / 2
= x(1/Ha + 1/Hb + 1/Hc)
And,
s-a = x(-1/Ha + 1/Hb + 1/Hc)
s-b = x( 1/Ha - 1/Hb + 1/Hc)
s-c = x( 1/Ha + 1/Hb - 1/Hc)

Let A,B,C be 1/Ha, 1/Hb, 1/Hc resp. and sub into eqn (2),
x^2 = s(s-a)(s-b)(s-c)
x^2 = x^4 (A+B+C)(-A+B+C)(A-B+C)(A+B-C)
1/x^2 = (A+B+C)(-A+B+C)(A-B+C)(A+B-C)
x^2 = 1 / (A+B+C)(-A+B+C)(A-B+C)(A+B-C) ---(3)

10525 - New to Bangladesh?

Shortest path problem with multi criteria. You must prioritize shortest time first, then if ties, shortest distance. Backtracking or Floyd Warshall (with some modification) will do.

10528 - Major Scales

A straightforward problem. Just follow the problem description.

10530 - Guessing Game

Set up an array Possible_Guess of 10 elements, initially all true, every time we encounter "too high", mark this number up to 10 as false, if we encounter "too low", mark this number down to 1 as false. Finally when we encounter "right on", check our boolean array, if true, then Stan is not lying, but if false, Stan is dishonest.

10533 - Digit Primes

First you will need to know the digit primes. Use Sieve of Eratosthenes to generate primes from 1 to 1.000.000, then for each prime found, sum it's digits and check for digit prime property. Store how many digit primes found so far, so when you are given the range, you can tell how many digit primes quickly by using digitPrimeSoFar[t2] - digitPrimeSoFar[t1].

10534 - Wavio Sequence

You need an O(n log k) Longest Increasing Subsequence (DP-LIS) algorithm, where k is the length of the LIS. Probably you know O(n^2) LIS algorithm, this O(n log k) algorithm is a modification of that algorithm, by using binary search for the inner loop. For more detail, please search the internet first.

In this problem, you need to do LIS from left to right and then LIS from right to left (you can use LDS/longest decreasing subsequence for this too). To show the common mistake that usually occurs with this problem, I'll use this test case:

7
1 4 2 3 2 4 1

Output should be 5, yeah, you can't do full LIS from left to right and obtain increasing sequence: 1 2 3 4, and decreasing sequence 4 1 => making wavio length of only 3...

10535 - Shooter (by: Sohel Hafiz)

10536 - Game of Euler

Just emulate all the possibilities and use memoization. I'll write more after I got this accepted...

10539 - Almost Prime Numbers (by: Teng Junbin)

Use sieve to generate the primes between 1 and 1.000.000, then find all multiples of these primes. Sort the multiples (prime^2, prime^3...and so on while not exceeding 10^12) and use binary search to get the answer. (Almost prime is a non-prime which only have one prime factor, so obviously, multiples of a prime number is "almost prime number").

For your information, there exist 80070 almost prime numbers from 1 to 10^12, which can be pre-calculated and stored easily in a long long array of size 80070.

10541 - Stripe - (by: Stephanus Indra)

This is combination of Dynamic Programming and Big Integer. DP is simple. You can also use mathematic. (Tip : Use DP to avoid big number multiplication and division)

10543 - Traveling Politician

This long (and a bit confusing) problem description can be reduced into a simple BFS/DFS problem (BFS is more appropriate). You need to find a path with length k <= path_len <= 20 (omitting the last city as intermediate vertex, since when you reached last city, you must stop...). If your path_len is less than k or greater than 20, output "LOSER".

10549 - Russian Dolls (by: William Anggakusuma)

This problem can be solved easily using backtracking. First, you must sort the dolls by their heights to reduce the searching area then use backtracking to try all possible placement.

10550 - Combination Lock - (by: Stephanus Indra)

Easy problem just follow the steps in the problems. Be careful! Notice the combination lock picture. Due to this picture, the clockwise dial will have counter-clockwise effect and the counter-clockwise dial will have clockwise effect.

10551 - Basic Remains - (by: Stephanus Indra, Zhang Kaicheng)

Compute (A_n A_n-1 A_n-2… A₁A₀) (base b) modulo (R)₁₀, denoted by (s)₁₀ = (A_n A_n-1 A_n-2… A₁A₀)_b mod (R)₁₀
Simulate the modulo step by step using the following algorithm:

s = 0;
for (i=n; i>=0; i--) {
  s *= b;
  s += An;
  s %= R;
}

10554 - Calories from Fat

For those with poor English, it will be a hard task to decipher the meaning of the first two paragraphs, which basically just a medical information regarding fat...  I'll give you a summary of the problem description again here:

You'll be given a list of foods
Each food has 5 components: fat, protein, sugar, starch, and alcohol
Each component is given in 3 formats: grams, Calories, and percent Calories
What you need to do is to convert all food's components to calories and then give percentage, how many calories actually comes from the fat component...

The hardest thing maybe the conversion between grams, Calories, and percentage to Calories...

for grams to Calories, you are given a rules that:
1g fat = 9 Calories,
1g protein = 4 Calories,
1g sugar = 4 Calories,
1g starch = 4 Calories,
1g alcohol = 7 Calories

for Calories, you don't need to convert... just accumulate total Calories so far

for percent Calories to Calories, you need to accumulate total Calories from other food's components first, and then the actual Calories for that particular food is:
total Calories from other components * 100 / (100-totalPercentCalories of this food)

At the end, if total Calories is 100 Cal and 20 Cal of it comes from fat, output 20/100 = 20%
and so on...

10573 - Geometry Paradox

The trap is that there is no 'impossible' case actually. If only t is given, you can assume that r1 = r2, t become the diameter of the outer circle :) Thus the area of the outer circle becomes PI*(t/2)*(t/2) and area of the two identical inner circles become 2*PI*(t/4)*(t/4), thus the area of the gray part = (PI*t*t)/4 - (PI*t*t)/8 = (PI*t*t)/8.

While in the other case, you are given r1 and r2. Calculating the gray area will be:
PI*(r1+r2)*(r1+r2) - PI*r1*r1 - PI*r2*r2 = (outer circle area-2 inner (different) circle area)
PI*r1^2 + 2*PI*r1*r2 + PI*r2^2 - PI*r1^2 - PI*r2^2 = (expand the equation)
2*PI*r1*r2. (after simplification)

Btw, don't forget to define PI as 2*acos(0.0), otherwise you'll get that stupid precision error problem.

10576 - Y2K Accounting Bug (N/A)
I forgot how I derive the solution. This is a backtracking problem anyway.

10578 - The Game of 31 (N/A)
I forgot how I derive the solution. You can solve this either using backtracking or DP.

10579 - Fibonacci Numbers

This is a 'simple' Fibonacci number problem. The difficult part is that you need to use Big Integer to hold values up to 1000 digits.

10582 - ASCII Labyrinth

The given input is complex text based pattern..., carefully read the input and convert them to a nice data structure. I'll tell you my way.

+---+ ==> I represent this with constant 0
|   |
|   |
|   |

+---+ ==> I represent this with constant 1
|   |
|***|
|   |

+---+ ==> I represent this with constant 2
|   |
|** |
| * |

So, the sample input:

+---+---+---+---+---+---+
|   |   |   |   |   |   |
|***|***|** |** |** |***|
|   |   | * | * | * |   |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
|   |** |** |***|** |** |
|   | * | * |   | * | * |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
|***|** |***|***|***|** |
|   | * |   |   |   | * |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
|** |   |***|   |** |** |
| * |   |   |   | * | * |
+---+---+---+---+---+---+

will be translated to:

1-1-2-2-2-1
0-2-2-1-2-2
1-2-1-1-1-2
2-0-1-0-2-2

Now the remaining task is to start from top left square, do an exhaustive backtracking to see whether you can reach bottom right square, considering that square indicated with 0 will block your way, square indicated with 1 will bypass your direction, and square indicated with 2 will have two choices, turn left or turn right (because you can rotate your square rite).

For the sample input, the two solutions possible are indicated below:

1-1-2-2-2-1
0-2-2-1-2-2
1-2-1-1-1-2
2-0-1-0-2-2

and

1-1-2-2-2-1
0-2-2-1-2-2
1-2-1-1-1-2
2-0-1-0-2-2

10583 - Ubiquitous Religions

Use Union-Find data structure. Prepare n sets of n students. Union set i (representing student i) and set j (representing student j) if they believe in the same religion. At the end, output how many sets remaining.

10585 - Center of symmetry

Sort the input points based on x-axis first. If there are ties, sort by y-axis, then greedyly compute the mid point of point 1 and n, and then check whether points (2,n-1),(3,n-2)... and so on have exactly the same middle point...

10586 - Polynomial Remains

There is a quick way to solve this problem. I will illustrate it with sample input 1:
You must divide polynomial: 6 3 3 2 0 1 (x^5+2x^3+3x^2+3x+6) with 1 0 1 (x^2+1)

Simply:

6 3 3 2 0 1
      1 0 1   (align to the rightmost non zero coefficients)
----------- -
6 3 3 1 0 0
  1 0 1       (align to the rightmost non zero coefficients)
----------- -
6 2 3 0 0 0
3 0 3         (align to the rightmost non zero coefficients, times 3)
----------- -
3 2 0 0 0 0

Since 3 2 represents 2x+3 which is already smaller than 1 0 1 (x^2+1),
stop here and output 3 2 as the polynomial remain :). This algorithm is very fast :)

10589 - Area

In the input format... be careful with this special case for N, which can be represented as 10^k. After that, this problem is just testing whether points (x,y) is inside the stripe. For (x,y) (note that this point is always inside rectangle) to be inside the striped region, it should be inside the four circles with radius a, originated at A,B,C,D. You can then use your math formula, that a point (x0,y0) is inside circle (x,y,r) if (x-x0)^2 + (y-y0)^2 <= r^2.

Notice that there’s typo in the problem description, area should be m*a*a/n.

10591 - Happy Number

Simulate the process. Taking into account that Unhappy numbers have 'eventually periodic' sequences of Si which do not reach 1. Once you detect this periodic sequence, stop it at once and output "Unhappy", otherwise you'll get TLE/crash. Note that 'eventually periodic' is not always start with the original number.

Examples:
4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4.
This sequence starts with 4 and 4 occurs again later, a periodic sequence. => 4 unhappy.

17 -> 50 -> 25 -> 29 -> 85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89.
This sequence starts with 17, but there is periodic subsequence inside. => 17 unhappy.

Refer to http://mathworld.wolfram.com/HappyNumber.html for more details.

10596 - Morning Walk

This problem is just to determine the existence of Euler Cycle.

Theorem: A directed graph possesses an Eulerian cycle iff
1) It is connected
2) For all {v} in {V} indegree(v) = outdegree(v)

But, in this problem, you have several special cases:

1. You don't really need to visit all vertex, only visit R edges given... done...
So, input:
3 2
0 1
1 0
Must be answered: "Possible", even though vertex '2' is not visited at all

2. No need in / out degree... just check whether the total degree is even, because we assume that the graph is undirected...

3. Surprisingly, you only need to check the connectedness of the graph by checking whether vertex 0 (Kamal's starting point), is connected to any of the other vertex (i.e. degree of vertex 0 is not 0).

10599 - Robots(II) (by: Md Erfan Hoque)

This can solved by LIS algorithm. Convert this problem to a LIS problem. Observe if you are in (r1,c1) and you can go to (r2,c2) then r2>=r1 AND c2>=c1. So if you pick up coords of the garbages then you can find the Longest Increasing Subsequences to know the maximum number of garbage that you can collect. And to find the number of possible ways, you just need to count all possible LISs.

It is not so difficult. Start with the numbers that can be at the end of LIS. Give each a number of possibilities 1 then for all numbers that can be one before the end, sum up the values of all numbers that can follow them. Then for all numbers two before the end, sum up the values of all numbers one before the end that can follow them.

For example:
1 3 2 6 5
length of LIS is 3
6 and 5 can be at the end of LIS
then 3 and 2 one before the end and LIS starts with 1
1 3 6 (1)
2 5 (1)
you give 6 and 5 number of possibilities 1
1 3 (2) 6 (1)
2 (2) 5 (1)
3 and 2 get both 1, because after 3, there can be either 6 or 5 as
last number of LIS and similar with 2 and 1 gets number 4 (sum of values of 2 and 3).
but you can't always sum up all values; sometimes you must skip numbers that can't follow in LIS
Example:
1 3 4 2
1 3 4
2
for 2 value is 0, because 4 can't follow 2 in LIS
so for this check you need to know the original position of each number.