Saturday, September 21, 2013

Book on Git internals on GitHub and the book Pro Git by Scott Chacon

Just saw this book on Git internals by Scott Chacon that I have always wanted to read: Git Internals PDF book. It is opensourced too :-)

Pro Git by Scott Chacon. Can be downloaded in different formats. Must read for people using Git/ want to use Git.

Highly recommended. Just pure awesomeness by Scott.

My ACM UVa source code on github

After a really long time, I committed my source code for the UVa problems here.
GitHub welcome email said - "We're pretty certain this is the start of something really special, so we wanted to take a moment to personally welcome you to GitHub."
Felt good seeing that.

Tuesday, September 10, 2013

How I solved UVa 100 - 3n + 1

Problem link: 3n + 1
Many thanks to Praveen and Prasad for bringing this problem back to me after many years. I had solved this problem long back and it had taken more than 3s initially (with AC of course!).
Prasad started to solve it again and I jumped in too. This time, I submitted 2 solutions:
1. Pre-compute the cycle length of all numbers [1,999999]. Read the inputs and print the outputs from the pre-computed array. Time = 0.442s.
2. I had suggested to Prasad to try and use the idea of computing the cycle length of a number just once. In the previous solution, we compute the cycle length of a number multiple times. I used a stack to keep track of the numbers and once I see a pre-computed cycle length for any number in the sequence, I just unwind the stack and set the cycle lengths for all numbers on the stack. Time = 0.062s.
Both the solutions use scanf, printf, & (bitwise and), >> (right shift), *=, +=.
Looks like the OJ (online judge) runs on really fast processors these days! The OJ upgrade is on :-)
One more spoiler: here's the source code :-) Am finally onto GitHub and it is befitting to add the source of the very first problem I solved years back and solved again due to Prasad.

Saturday, September 7, 2013

How I solved the UVa 10976 - Fractions Again

Here's the problem link:
Caution: This is a spoiler with complete solution. Do not read further if you haven't tried it yet.

Abbreviated problem definition: Given a fraction 1/z, it can be represented as 1/x + 1/y where x >=y. Find all combinations for a given 0 < z <= 10000.

Sample Inputs:
2
12

Sample Outputs:
2 --# of solutions
1/2 = 1/6 + 1/3
1/2 = 1/4 + 1/4
8 --# of solutions
1/12 = 1/156 + 1/13
1/12 = 1/84 + 1/14
1/12 = 1/60 + 1/15
1/12 = 1/48 + 1/16
1/12 = 1/36 + 1/18
1/12 = 1/30 + 1/20
1/12 = 1/28 + 1/21
1/12 = 1/24 + 1/24

Expression:
1/z = 1/x + 1/y
1/z = (y + x)/ (x * y)
z = (x * y)/(x + y) --(1)

z * (x + y) = (x * y)
z * x + z * y = y * x
z * y = (y - z) * x
x = (z * y) / (y - z) --(2)

Looking at the pattern for the samples, we decrease y and find the x,
if possible.

Start with y = 2 * z = 2 * 2 = 4:
1/2 = 1/4 + 1/4
2 = (4 * 4)/(4 + 4) --using (1)  above.

Try y = 3;
2 = (x * 3)/ (x + 3)
2 * (x + 3) = x * 3
2*x + 6 = 3*x
3*x - 2*x = 6
x = 6
So, one more solution found:
1/2 = 1/6 + 1/3

We cannot go further as y becomes equal to 2.
1/2 = 1/4 + 1/4
1/2 = 1/6 + 1/3

Let us look at the second sample:
Start with y = 12 * z = 12 * 2 = 14:
1/12 = 1/24 + 1/24 --Obvious :-)

Reduce y to 23:
Using (1) above we get:
12 = (x * 23)/(x + 23)
12 * (x + 23) = 23 * x
12*x + 276 = 23*x
276 = 11*x
x = 276/11 = 25.0909 => NOT a solution as we need 11 to exactly divide 276

Reduce y to 22:
Using (1) above we get:
12 = (x * 22)/(x + 22)
12*x + 12 * 22 = 22 * x
12 * 22 = 10 * x => NOT a solution

Reduce y to 21:
Using (1) above we get:
12 = (x * 21)/(x + 21)
12 * (x + 21) = 21 * x
12*x + 12 * 21 = 21*x
12 * 21 = 9*x
x = 28 => We have a solution :-)
1/12 = 1/28 + 1/21

Reduce y to 20:
Using (1) above we get:
12 = (x * 20)/(x + 20)
12*x + 12*20 = 20*x
12*20 = 8*x
x = 30 => we have a solution :-)
1/12 = 1/30 + 1/20

Reduce y to 19:
Using (1) above we get:
12 = (x * 19)/(x + 19)
12*x + 12*19 = 19*x
12*19 = 7*x
x = 32.57 => NOT a solution

Reduce y to 18:
Using (1) above we get:
12 = (x * 18)/(x + 18)
12*x + 12*18 = 18*x
12*18 = 6*x
x = 36 => we have a solution :-)
1/12 = 1/36 + 1/18

Reduce y to 17:
Using (1) above we get:
12 = (x * 17)/(x + 17)
12*x + 12*17 = 17*x
12*17 = 5*x
x = 40.8 => NOT a solution

Reduce y to 16:
Using (1) above we get:
12 = (x * 16)/(x + 16)
12*x + 12*16 = 16*x
12*16 = 4*x
x = 48 => we have a solution :-)
1/12 = 1/48 + 1/16

Reduce y to 15:
Using (1) above we get:
12 = (x * 15)/(x + 15)
12*x + 12*15 = 15*x
12*15 = 3*x
x = 60 => we have a solution :-)
1/12 = 1/60 + 1/15

Reduce y to 14:
Using (1) above we get:
12 = (x * 14)/(x + 14)
12*x + 12*14 = 14*x
12*14 = 2*x
x = 84 => we have a solution :-)
1/12 = 1/84 + 1/14

Reduce y to 13:
Using (1) above we get:
12 = (x * 13)/(x + 13)
12*x + 12*13 = 13*x
12*13 = 1*x
x = 156 => we have a solution :-)
1/12 = 1/156 + 1/13

END when y = 12
There you go :-)
There could be some optimization that can be performed for quickly
discarding some values of y. Will update.

We have used complete search to arrive at the solution.
One more spoiler: here's the source code

Thursday, September 5, 2013

UVa 10815 - Andy's first dictionary

Andy's first dictionary is an interesting problem which looks quite simple. I got it right at the 5th attempt because, I missed reading the key sentence of the problem: In this problem, a word is defined as a consecutive sequence of alphabets, in upper and/or lower case.
After seeing the key sentence, AC wasn't far off!
Just wanted to say so much :-)
One more spoiler: here's the source code.