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

Pollard's Rho in Java

This is a Pollard's Rho implementation in java. Not very fast, but works for uva online judge. The reason behind using java is the default support of the BigInteger class.

import java.math.BigInteger;
import java.security.SecureRandom;
import java.io.*;
import java.util.*;

public class PollardRho {

    private final static BigInteger ZERO = new BigInteger("0");
    private final static BigInteger ONE  = new BigInteger("1");
    private final static BigInteger TWO  = new BigInteger("2");
    private final static SecureRandom random = new SecureRandom();

    static Vector<BigInteger> v = new Vector<BigInteger>();

    public static BigInteger rho(BigInteger N) {

        BigInteger divisor;
        BigInteger c  = new BigInteger(N.bitLength(), random);
        BigInteger x  = new BigInteger(N.bitLength(), random);
        BigInteger xx = x;

        if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;

        do {
            x  =  x.multiply(x).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            divisor = x.subtract(xx).gcd(N);
        } while((divisor.compareTo(ONE)) == 0);

        return divisor;
    }

    public static void factor(BigInteger N) {

        if (N.compareTo(ONE) == 0) return;

        if (N.isProbablePrime(20)) {
            v.add(N);
            return;
        }

        BigInteger divisor = rho(N);
        factor(divisor);
        factor(N.divide(divisor));
    }

    public static void main(String[] args) throws Exception {

        String string = "";
        InputStreamReader input = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(input);

        while(null != (string = reader.readLine())) {
            BigInteger N = new BigInteger(string);
            v.clear();
            factor(N);
            Collections.sort(v);
            for(int i = 0; i < v.size(); i++) System.out.println(v.get(i));
            System.out.println();
        }
    }
}

I have seen this piece of code years ago somewhere in the internet, but can't remember exactly where. So, I will be glad if anyone can comment/mail me the original source. However, for spoj, I need to write a much much better version of this in C++ :( Exam sucks life...

UVa, SPOJ & TopCoder

First of all, thanks to Fahim vai, he gave me the idea first...

This is a very easy way to add a cool bookmark item on your browser which can easily locate UVa, SPOJ & TopCoder problems for you. After you follow these steps, you will be able to open any UVa / SPOJ problem with just a click, you even do not need to enter any web address !

UVa Locator:

Right click on bookmark toolbar of your browser. Then right click on it and select "New Bookmark...". So the new bookmark box will arrive. On the name field, put whatever you want, like "UVa" or something else and on the location field, paste the following javascript:

javascript:var%20pid=prompt('Enter%20problem%20number:');
location.href='http://uva.onlinejudge.org/external/'+pid.substring(0,pid.length-2)+'/'+pid+'.html';

Now, after clicking "Add", you will see a new bookmark item has been added to your browser's toolbar, just click on it and enter the problem number.. that's it!

Spoj Locator:

Similar process, add e new bookmark item, now, give a different name, for example, "SPOJ" and on the location, paste the following javascript:

javascript:var%20pid=prompt('Enter%20problem%20name:');
location.href='https://www.spoj.pl/problems/'+pid.toUpperCase()+'/'

Click "Add" and done!. Now you will get a similar bookmark item as the previous one. But as you know, spoj problems are recognized with their codnames, not numbers. So enter a code name in the textbox, don't bother about case, and click ok. It will open the page of the problem if it is there. For example, to open the problem "Longest Common Substring", it has a codename LCS, you should enter "LCS" in the box, (not necessarily all should be uppercase).

TopCoder Locator:

Similarly, topcoder problems are known by their respective class names, you can add a simple search box for topcoder problems by adding the following javascript in the similar way stated above:

javascript:var%20pid=prompt('Enter%20class%20name:');
location.href='http://www.topcoder.com/tc?module=ProblemArchive&class='+pid

It will not open the problem, it is a simple javascript that calls the search engine on topcoder to find the class name you provide.

As these will open in current window, make sure you open a new tab before using these to save some back, forward clicks ><><><
Have Fun !!!

Factorial of negative number

Is it possible to find factorial of negative numbers?

By definition,
N! = 1 x 2 x .... x N
⇒ N! = 1 x 2 x .... x N x (N+1) / (N+1)
⇒ N! = (N+1)! / (N+!)

Now, let's try some values:
3! = 4! / 4 = 6
2! = 3! / 3 = 2
1! = 2! / 2 = 1
0! = 1! / 1 = 1

So, that's how 0! = 1. Let's not stop at 0!, if we continue this fashion, we get:
(-1)! = 0! / 0 = Undetermined

Many people still keeps arguing about whether x / 0 = +∞ or Undefined, it really doesn't matter though, because it is well established that anything divided by zero is undefined.

However, in this post, we are going to talk about a problem from UVa Online Judge, UVa-10323 (Factorial! You Must be Kidding!!!). This problem actually requires you to calculate even the factorials of negative numbers, which does not really exist in real world.

In this context, we are forced to assume that x / 0 = +∞. There was a mistake on my previous post, this section is updated as per the comment from a fellow reader আহনাফ তাহমিদ:
(-1)! = 0! / 0 = +∞
(-2)! = (-1)! / -1 = -∞
(-3)! = (-2)! / -2 = +∞
(-4)! = (-3)! / -3 = -∞
(-5)! = (-4)! / -4 = +∞
and so on..

Hence, we can see that, if N is odd, then (-N)! = +∞, otherwise (-N)! = -∞. Note that, this specific problem statement calls +∞ as Overflow and -∞ as Underflow.

Hope it helps!

Easy problems at UVA OJ

Here are some suggestion about some very easy problems on UVA Online Judge

Programming is fun!!! especially for the beginners, and new programmers find a great inspiration on solving easy problems first as these problems are good for learning the ropes. To help some of my new friends i.e. new programmer friends who intend to solve problems on UVA OJ, here is a list of very easy problems.

Some problems among these may not seem so easy at a first glance, but after a little thinking, they will be easily solved. These problems will also help you to understand common programming techniques along with the verdict variations.


136 very easy problems for beginners:

   105    119    136    138    145    154    190    200
   256    264    272    278    294    332    344    355
   362    374    378    382    389    394    401    409
   412    412    414    417    422    424    426    438
   441    444    445    455    458    460    465    466
   468    474    476    477    478    482    483    484
   486    489    490    492    494    495    496    498
   499    530    535    543    568    573    575    579
   583    587    591    621    713    834    900    944
   974  10006  10008  10013  10018  10019  10035  10055
 10060  10071  10078  10079  10093  10104  10110  10161
 10195  10209  10221  10242  10281  10297  10302  10323
 10340  10347  10407  10432  10451  10469  10490  10499
 10515  10522  10533  10573  10591  10678  10679  10683
 10783  10784  10790  10812  10815  10922  10929  10931
 10991  11058  11121  11152  11172  11192  11192  11219
 11220  11233  11332  11343  11388  11417  11437  11455

Good Luck !!!