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

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 log_ba, 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?

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:
α[x₁, y₁, z₁] + β[x₂, y₂, z₂] = [γ₁, γ₂, γ₃] ... (2)

Now if we apply the transformation from (1), we get a system of 2D vectors as follows:
α[y₁-x₁, z₁-x₁] + β[y₂-x₂, z₂-x₂] = [γ₂-γ₁, γ₃-γ₁] ... (3)

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

From (2), we get 3 equations:
αx₁ + βx₂ = γ₁ ... (I)
αy₁ + βy₂ = γ₂ ... (II)
αz₁ + βz₂ = γ₃ ... (III)

Similarly from (3) we get 2 equations:
α(y₁-x₁) + β(y₂-x₂) = γ₂-γ₁
α(z₁-x₁) + β(z₂-x₂) = γ₃-γ₁

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:
α₁[x₁, y₁, z₁] + α₂[x₂, y₂, z₂] + ... ... + α_n[x_n, y_n, z_n] = [γ₁, γ₂, γ₃]

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 γ₁ = γ₂ = γ₃ = γ 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!