UVA 10041 Vito's family

UVA 10041 Vito's family is a part of the set of problems under the sorting chapter (#4) from Programming Challenges book by Steven Skiena and Miguel Revilla. It took me 6 attempts before I got AC (accepted)
The most interesting discussion here: which is the best statistic required to build Vito's house. Mean? Median?

As an interesting experiment, I am including the test cases and the expected output here.

Input:
23
10 2 2 4 2 2 2 2 2 2 2
3 6 4 2
9 2 4 6 4 4 4 4 4 4
3 100 10 1
7 5 1 7 1 9 1 10
3 1 1 8
4 3 1 5 7
10 30 25 15 1 1 1 23 23 90 10
499 1 1 1 1 1 1 1 1 1 1 1 29999 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100 29999 29999 29999 29999 1 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999
5 100 1 1 1 1
5 4 6 6 6 3
5 4 6 1 1 13
2 1 4
1 888
16 5 49 12 23 29 100 44 47 69 41 23 12 11 6 2 62
2 8 8
499 29999 29998 29997 29996 29995 29994 29993 29992 29991 29990 29989 29988 29987 29986 29985 29984 29983 29982 29981 29980 29979 29978 29977 29976 29975 29974 29973 29972 29971 29970 29969 29968 29967 29966 29965 29964 29963 29962 29961 29960 29959 29958 29957 29956 29955 29954 29953 29952 29951 29950 29949 29948 29947 29946 29945 29944 29943 29942 29941 29940 29939 29938 29937 29936 29935 29934 29933 29932 29931 29930 29929 29928 29927 29926 29925 29924 29923 29922 29921 29920 29919 29918 29917 29916 29915 29914 29913 29912 29911 29910 29909 29908 29907 29906 29905 29904 29903 29902 29901 29900 29899 29898 29897 29896 29895 29894 29893 29892 29891 29890 29889 29888 29887 29886 29885 29884 29883 29882 29881 29880 29879 29878 29877 29876 29875 29874 29873 29872 29871 29870 29869 29868 29867 29866 29865 29864 29863 29862 29861 29860 29859 29858 29857 29856 29855 29854 29853 29852 29851 29850 29849 29848 29847 29846 29845 29844 29843 29842 29841 29840 29839 29838 29837 29836 29835 29834 29833 29832 29831 29830 29829 29828 29827 29826 29825 29824 29823 29822 29821 29820 29819 29818 29817 29816 29815 29814 29813 29812 29811 29810 29809 29808 29807 29806 29805 29804 29803 29802 29801 29800 29799 29798 29797 29796 29795 29794 29793 29792 29791 29790 29789 29788 29787 29786 29785 29784 29783 29782 29781 29780 29779 29778 29777 29776 29775 29774 29773 29772 29771 29770 29769 29768 29767 29766 29765 29764 29763 29762 29761 29760 29759 29758 29757 29756 29755 29754 29753 29752 29751 29750 29749 29748 29747 29746 29745 29744 29743 29742 29741 29740 29739 29738 29737 29736 29735 29734 29733 29732 29731 29730 29729 29728 29727 29726 29725 29724 29723 29722 29721 29720 29719 29718 29717 29716 29715 29714 29713 29712 29711 29710 29709 29708 29707 29706 29705 29704 29703 29702 29701 29700 29699 29698 29697 29696 29695 29694 29693 29692 29691 29690 29689 29688 29687 29686 29685 29684 29683 29682 29681 29680 29679 29678 29677 29676 29675 29674 29673 29672 29671 29670 29669 29668 29667 29666 29665 29664 29663 29662 29661 29660 29659 29658 29657 29656 29655 29654 29653 29652 29651 29650 29649 29648 29647 29646 29645 29644 29643 29642 29641 29640 29639 29638 29637 29636 29635 29634 29633 29632 29631 29630 29629 29628 29627 29626 29625 29624 29623 29622 29621 29620 29619 29618 29617 29616 29615 29614 29613 29612 29611 29610 29609 29608 29607 29606 29605 29604 29603 29602 29601 29600 29599 29598 29597 29596 29595 29594 29593 29592 29591 29590 29589 29588 29587 29586 29585 29584 29583 29582 29581 29580 29579 29578 29577 29576 29575 29574 29573 29572 29571 29570 29569 29568 29567 29566 29565 29564 29563 29562 29561 29560 29559 29558 29557 29556 29555 29554 29553 29552 29551 29550 29549 29548 29547 29546 29545 29544 29543 29542 29541 29540 29539 29538 29537 29536 29535 29534 29533 29532 29531 29530 29529 29528 29527 29526 29525 29524 29523 29522 29521 29520 29519 29518 29517 29516 29515 29514 29513 29512 29511 29510 29509 29508 29507 29506 29505 29504 29503 29502 29501
10 1 1 1 1 1 9 9 9 9 9
400 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999
499 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999 29999
499 25999 25998 25997 25996 25995 25994 25993 25992 25991 25990 25989 25988 25987 25986 25985 25984 25983 25982 25981 25980 25979 25978 25977 25976 25975 25974 25973 25972 25971 25970 25969 25968 25967 25966 25965 25964 25963 25962 25961 25960 25959 25958 25957 25956 25955 25954 25953 25952 25951 25950 25949 25948 25947 25946 25945 25944 25943 25942 25941 25940 25939 25938 25937 25936 25935 25934 25933 25932 25931 25930 25929 25928 25927 25926 25925 25924 25923 25922 25921 25920 25919 25918 25917 25916 25915 25914 25913 25912 25911 25910 25909 25908 25907 25906 25905 25904 25903 25902 25901 25900 25899 25898 25897 25896 25895 25894 25893 25892 25891 25890 25889 25888 25887 25886 25885 25884 25883 25882 25881 25880 25879 25878 25877 25876 25875 25874 25873 25872 25871 25870 25869 25868 25867 25866 25865 25864 25863 25862 25861 25860 25859 25858 25857 25856 25855 25854 25853 25852 25851 25850 25849 25848 25847 25846 25845 25844 25843 25842 25841 25840 25839 25838 25837 25836 25835 25834 25833 25832 25831 25830 25829 25828 25827 25826 25825 25824 25823 25822 25821 25820 25819 25818 25817 25816 25815 25814 25813 25812 25811 25810 25809 25808 25807 25806 25805 25804 25803 25802 25801 25800 25799 25798 25797 25796 25795 25794 25793 25792 25791 25790 25789 25788 25787 25786 25785 25784 25783 25782 25781 25780 25779 25778 25777 25776 25775 25774 25773 25772 25771 25770 25769 25768 25767 25766 25765 25764 25763 25762 25761 25760 25759 25758 25757 25756 25755 25754 25753 25752 25751 25750 25749 25748 25747 25746 25745 25744 25743 25742 25741 25740 25739 25738 25737 25736 25735 25734 25733 25732 25731 25730 25729 25728 25727 25726 25725 25724 25723 25722 25721 25720 25719 25718 25717 25716 25715 25714 25713 25712 25711 25710 25709 25708 25707 25706 25705 25704 25703 25702 25701 25700 25699 25698 25697 25696 25695 25694 25693 25692 25691 25690 25689 25688 25687 25686 25685 25684 25683 25682 25681 25680 25679 25678 25677 25676 25675 25674 25673 25672 25671 25670 25669 25668 25667 25666 25665 25664 25663 25662 25661 25660 25659 25658 25657 25656 25655 25654 25653 25652 25651 25650 25649 25648 25647 25646 25645 25644 25643 25642 25641 25640 25639 25638 25637 25636 25635 25634 25633 25632 25631 25630 25629 25628 25627 25626 25625 25624 25623 25622 25621 25620 25619 25618 25617 25616 25615 25614 25613 25612 25611 25610 25609 25608 25607 25606 25605 25604 25603 25602 25601 25600 25599 25598 25597 25596 25595 25594 25593 25592 25591 25590 25589 25588 25587 25586 25585 25584 25583 25582 25581 25580 25579 25578 25577 25576 25575 25574 25573 25572 25571 25570 25569 25568 25567 25566 25565 25564 25563 25562 25561 25560 25559 25558 25557 25556 25555 25554 25553 25552 25551 25550 25549 25548 25547 25546 25545 25544 25543 25542 25541 25540 25539 25538 25537 25536 25535 25534 25533 25532 25531 25530 25529 25528 25527 25526 25525 25524 25523 25522 25521 25520 25519 25518 25517 25516 25515 25514 25513 25512 25511 25510 25509 25508 25507 25506 25505 25504 25503 25502 25501
499 29999 29998 29997 29996 29995 29994 29993 29992 29991 29990 29989 29988 29987 29986 29985 29984 29983 29982 29981 29980 29979 29978 29977 29976 29975 29974 29973 29972 29971 29970 29969 29968 29967 29966 29965 29964 29963 29962 29961 29960 29959 29958 29957 29956 29955 29954 29953 29952 29951 29950 29949 29948 29947 29946 29945 29944 29943 29942 29941 29940 29939 29938 29937 29936 29935 29934 29933 29932 29931 29930 29929 29928 29927 29926 29925 29924 29923 29922 29921 29920 29919 29918 29917 29916 29915 29914 29913 29912 29911 29910 29909 29908 29907 29906 29905 29904 29903 29902 29901 29900 29899 29898 29897 29896 29895 29894 29893 29892 29891 29890 29889 29888 29887 29886 29885 29884 29883 29882 29881 29880 29879 29878 29877 29876 29875 29874 29873 29872 29871 29870 29869 29868 29867 29866 29865 29864 29863 29862 29861 29860 29859 29858 29857 29856 29855 29854 29853 29852 29851 29850 29849 29848 29847 29846 29845 29844 29843 29842 29841 29840 29839 29838 29837 29836 29835 29834 29833 29832 29831 29830 29829 29828 29827 29826 29825 29824 29823 29822 29821 29820 29819 29818 29817 29816 29815 29814 29813 29812 29811 29810 29809 29808 29807 29806 29805 29804 29803 29802 29801 29800 29799 29798 29797 29796 29795 29794 29793 29792 29791 29790 29789 29788 29787 29786 29785 29784 29783 29782 29781 29780 29779 29778 29777 29776 29775 29774 29773 29772 29771 29770 29769 29768 29767 29766 29765 29764 29763 29762 29761 29760 29759 29758 29757 29756 29755 29754 29753 29752 29751 29750 29749 29748 29747 29746 29745 29744 29743 29742 29741 29740 29739 29738 29737 29736 29735 29734 29733 29732 29731 29730 29729 29728 29727 29726 29725 29724 29723 29722 29721 29720 29719 29718 29717 29716 29715 29714 29713 29712 29711 29710 29709 29708 29707 29706 29705 29704 29703 29702 29701 29700 29699 29698 29697 29696 29695 29694 29693 29692 29691 29690 29689 29688 29687 29686 29685 29684 29683 29682 29681 29680 29679 29678 29677 29676 29675 29674 29673 29672 29671 29670 29669 29668 29667 29666 29665 29664 29663 29662 29661 29660 29659 29658 29657 29656 29655 29654 29653 29652 29651 29650 29649 29648 29647 29646 29645 29644 29643 29642 29641 29640 29639 29638 29637 29636 29635 29634 29633 29632 29631 29630 29629 29628 29627 29626 29625 29624 29623 29622 29621 29620 29619 29618 29617 29616 29615 29614 29613 29612 29611 29610 29609 29608 29607 29606 29605 29604 29603 29602 29601 29600 29599 29598 29597 29596 29595 29594 29593 29592 29591 29590 29589 29588 29587 29586 29585 29584 29583 29582 29581 29580 29579 29578 29577 29576 29575 29574 29573 29572 29571 29570 29569 29568 29567 29566 29565 29564 29563 29562 29561 29560 29559 29558 29557 29556 29555 29554 29553 29552 29551 29550 29549 29548 29547 29546 29545 29544 29543 29542 29541 29540 29539 29538 29537 29536 29535 29534 29533 29532 29531 29530 29529 29528 29527 29526 29525 29524 29523 29522 29521 29520 29519 29518 29517 29516 29515 29514 29513 29512 29511 29510 29509 29508 29507 29506 29505 29504 29503 29502 29501 

Expected output:
2
4
4
99
23
7
8
163
29998
29998
99
5
17
3
0
347
0
62250
40
5999600
7469502
62250
62250

Watch out for the exact number of newline characters that are required. I guess a few of my attempts were lost in the battle for matching the number of newlines.

TopCoder SRM 565 Div2 500points: MonstersValley2

I thought this was a very simple problem, but not so :-)

Compressed problem statement: Given a list of monsters with their dread score (scariness score) and the price to be paid for bribing, what is the total minimum bribe to be paid. Monster 1 has to be bribed. You bribe a monster and it becomes a part of your troop. You don't need to bribe monster[i] if the total scariness of the monsters with you exceed the scariness score of monster[i], otherwise you better be wise to bribe.

I get the idea that while maximizing the dread score, we need to minimize the total price. Interesting combination. What algo fits here? Found it - Dynamic programming. Now, it is time to understand, write code and get practice points :-)

What's your typing speed?

I took several tests ranging from 1 to 2 min from http://www.typingtest.com/. My speed is close to 48 wpm. How to improve this? Interesting.
I also used backspace quite a few times. I remember my colleague Rajesh Seenivasan typing without pressing a backspace. Now, that is something I took up as a personal challenge and was able to get past many backspaces, but there are a few more to trim :-)

TopCoder:SRM233:SmartWordToy

This entry is about SmartWordToy problem from the Single Round Match 233 of TopCoder Division 1 and it is a 500 point problem:

Have you visited the TopCoder Algorithm tutorials page? You must have seen the mention of BFS (Breadth First Search) there and probably started to try the first problem listed there: SmartWordToy. I started too.

It seemed an interesting problem: there are 4 letter blocks; each block contains 2 buttons; left makes the letter go the previous letter in the sequence; right button takes the letter one step forward; given a start, end and a set of disallowed combinations, what is the minimum number of button presses required to reach the end?

The sequence of letters are cyclic which means that if you are seeing 'a' and press the left button, you will see 'z'. Also, if you are at 'z' and press the right button, you will see 'a'. Every time a button is pressed, the total score adds up until the end is reached.

The first test case in the problem being:
start = "aaaa"
end = "zzzz"
forbidden = { "aaaz", "aaza", "azaa", "zaaa", "azzz", "zazz", "zzaz", "zzza"}

v0.1:
I created a graph that would generate 8 new strings (or state) from a given string (state). For instance:
aaaa = zaaa baaa azaa abaa aaza aaba aaaz aaab
This is the set that results from pressing 1 button (left or right) on each block.
The graph generation took about 9 seconds to finish and if i had submitted this version, it would say 'Time Limit Exceeded'. We will come to this problem later.

After this, I added the start state to the queue and started the BFS. Pick the first state from the queue, check if it the goal state, if not, add it to the visited states, get the 8 possible states from this state, add it to the queue. If it is the goal state, end.

Problems with this approach:
1. Graph has been generated taking really long time.
2. How do we count the button presses?
3. On looking at the program trace, you see that the path taken does not go towards the goal. Even if the goal state was reached, it is certainly not the optimal path. This raises the question: how do we really use BFS?

v1.0
1. Addressed the early graph creation by adding the start state to the queue. Picking the item off the queue, checking if it is present in the graph, if not, add it to the graph along with the set of states that it generates.
2. Added a cost to each state by computing the distance from a given state to the goal state. This was interesting because there are 2 possible costs: forward cost (distance from a to z is 25) and reverse cost (distance from a to z is 1)
3. Now, I used Dijkstra's min path algorithm to pick the state with the least cost and then go towards the goal.

This solution passed all the sample test cases for the problem and some of my own. With confidence, I submitted the solution and got 469 out of 500. I then ran the system tests and saw that one test case fails:
String start = "aaaa";
String finish = "xxxx";
String[] forbidden = { "xz xz xz z", "xa xa xa b" };
Expected = 12, my output is 14. Need to find the root cause and fix it.

Learnings:
1. Just in time execution
2. Go towards the goal :-)

foss.in 2012 videos online: http://hasgeek.tv/fossdotin/

Need I say more.

The inaugural talk by Atul Chitnis starts after a set of photos are flashed and Subbu is featured in the photos :-)

ArsDigita: Discrete Math: Prof.Shai Simonson

I have been fortunate to have come to know of the videos from the courses taught by Prof.Shai Simonson at ArsDigita University (http://aduni.org/) Here are the links:
1. Discrete Mathematics: http://aduni.org/courses/discrete/index.php?view=cw
2. Algorithms: http://aduni.org/courses/algorithms/index.php?view=cw
My friends (Radha, Prasad, Subbu) and I ordered the DVDs and we have the complete collection of the courses.

I particularly like the courses taught by Prof.Shai and interestingly enough, some of the material that he goes over have appeared in the interviews I have been to. Also, I got to see the video of Proj.Jerry Sussman of the 'Structure and Interpretations of Computer Programs' fame talking about his experiences. Wonderful.

I came across these videos because another friend Malatesh shared them with me many years ago. Thank you Malto.

I am enjoying these videos and the learning that comes from them.

Topcoder SRM 562 Div2 250 point problem: Cucumber Market

Problem in short: Kid goes to cucumber market with a budget and chooses k items out of available n items.  He can choose any of all possible k combinations and the return is 'YES' if he can successfully buy any such combination, otherwise 'NO'. The inputs being the array of prices and the number k.

My approach: Initially, I sorted the price array and got totals of k items (0..k, 1..k+1, 2..k+2, so on until n) and found test cases to pass except the 2nd one. I seemed to have gotten lost when I needed to sum up items 0, 2, 3,.. which is basically taking any of the k elements from the n elements.

Now, the problem seemed to need all possible k combination from n items. I thought of looking up how to get all the k combinations and then coding phase time ran out. 

Challenge phase: In this phase, I looked up one solution which had picked up the worst possible set of k items and if that did not satisfy the criterion, it returned 'NO'. This felt rather intimidating. How could I possibly miss this?

Anyway, one thing I need to learn is to figure out how to find all k items from n items.

Found an interesting link in StackOverflow:

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n