Saturday, March 19, 2011

DP @ UVa


300 DP problems from UVa, enjoy!

103 108 111 116 147 164 166 182 231 242
250 323 357 431 437 473 481 495 497 507
526 531 559 562 580 585 590 607 647 662
672 674 682 702 709 714 751 757 825 828
836 861 882 899 900 907 909 910 926 950
957 959 963 970 976 983 986 988 990 991
10003 10029 10032 10050 10051 10066 10069 10072 10074 10081
10086 10091 10097 10100 10118 10128 10130 10131 10149 10154
10157 10163 10192 10198 10201 10207 10239 10243 10247 10254
10261 10271 10280 10304 10306 10313 10324 10328 10337 10359
10364 10365 10405 10419 10444 10446 10453 10454 10465 10487
10497 10502 10516 10518 10529 10532 10534 10536 10541 10559
10564 10568 10590 10593 10597 10599 10604 10616 10617 10625
10626 10634 10635 10643 10648 10651 10654 10658 10667 10681
10684 10688 10690 10692 10694 10702 10711 10712 10715 10721
10722 10723 10733 10739 10743 10747 10755 10759 10788 10791
10811 10817 10819 10820 10826 10827 10835 10839 10859 10860
10874 10888 10891 10904 10908 10910 10911 10913 10918 10930
10934 10943 10953 10980 11002 11003 11008 11022 11026 11031
11040 11052 11067 11069 11077 11081 11084 11088 11091 11104
11125 11126 11133 11137 11151 11162 11169 11171 11176 11181
11191 11218 11229 11252 11258 11259 11261 11264 11266 11280
11282 11284 11285 11288 11293 11303 11307 11310 11311 11318
11320 11324 11328 11341 11361 11365 11370 11372 11375 11391
11394 11400 11404 11405 11413 11420 11421 11427 11431 11432
11433 11441 11444 11450 11456 11471 11472 11481 11485 11486
11499 11502 11514 11515 11517 11523 11531 11532 11534 11545
11546 11552 11553 11555 11566 11569 11578 11584 11590 11598
11601 11605 11611 11617 11645 11653 11691 11753 11790 11908
Courtesy: Jane Alam Jan & Felix Halim

Friday, March 11, 2011

C++ log() and log10()


log (or written commonly as ln) has a great significance in the world of mathematics, however, for computer implementation on some specific cases, I am not sure which one is better.

Yesterday, I was trying to solve a problem from uva online judge where I needed to find logba, which is calculated as log(a) / log(b) in C++. However, doing so led to a "wrong answer". Then, just to check, rewrote that formula with an equivalent one using log10(a) / log10(b), and this time it worked fine. Really confusing, so I come to this conclusion, log (e based) is not quite precise on computer implementation, especially with gcc/g++. Because, both produces same output on my machine, but different in uva's gcc/g++ compiler. Any other reason?


Thursday, March 3, 2011

3D to 2D vector?



I was just curious to see some mathematical approach to justify the transformation of a 3D vector to 2D vector in the following way:
x' = y-x
y' = z-x ... ... (1)

This is quite simple and obvious, that the mapping can be performed (as shown below). Now the question is, why do we do that? As the exact answer is unknown to me, my answer is, it will be easier to handle linear systems of certain type, i.e. involving 3D vectors, as we can change them to systems of 2D vectors easily (from a programming perspective).

Here, I will denote [x, y, z] format as a 3D vector with components x, y, z and [x', y'] as a 2D vector with components x', y' where, [x, y, z] and [x', y'] satisfies the transformation showed in (1).

Lets assume we have a linear system consisting of 2 such 3D vectors:
α[x1, y1, z1] + β[x2, y2, z2] = [γ1, γ2, γ3] ... (2)

Now if we apply the transformation from (1), we get a system of 2D vectors as follows:
α[y1-x1, z1-x1] + β[y2-x2, z2-x2] = [γ21, γ31] ... (3)

Now lets see if we can show (2) and (3) to be equivalent:

From (2), we get 3 equations:
αx1 + βx2 = γ1 ... (I)
αy1 + βy2 = γ2 ... (II)
αz1 + βz2 = γ3 ... (III)

Similarly from (3) we get 2 equations:
α(y1-x1) + β(y2-x2) = γ21
α(z1-x1) + β(z2-x2) = γ31

It is quite obvious to see that, we can get the later 2 equations from the first set, by subtracting (I) from both (II) and (III).

Similarly, this can be extended to a more general format:
α1[x1, y1, z1] + α2[x2, y2, z2] + ... ... + αn[xn, yn, zn] = [γ1, γ2, γ3]

Thus, we can conclude, (2) and (3) represents the same system. And, following this way, we can always reduce the dimensions of vectors involved in a linear system.

Additionally, if γ1 = γ2 = γ3 = γ then clearly, this is more simple, as in 2D, the vector in right side will be just [0, 0].

Actually, one of my desperate friend hit me today with this, as, if we can't get the answer, he will suicide... So, this is what I told him. Unfortunately, I am not from a mathematics background, and therefore, I may have abused some mathematical terms, sorry for that, and if anyone can tell me something more details and more general about it (what should I call this? I don't know either), or, if you find this post is totally wrong, please, save my friend from committing suicide by letting me know :p

Thank you!