Hero Image
InfiniteSequence topcoder SRM413 div2 level3

Introduction If you have not tried to solve this problem by yourself, please do so. Otherwise, this post will make little sense to you. The statement of the problem is a recursion, $a_i = a_{[i/p]} + a_{[i/q]}$, $a_0 = 1$. $p, q$ are integers. The symbol $[\cdot]$ represents the floor. The question is to find the value of $a_n$ for any given $n$, $p$, and $q$. The constraints are that $ 0 \leq n \leq 10^{12} $ and $ 1 < p, q \leq 10^9 $.

    Saturday, April 1, 2017 | 5 minutes Read
    Hero Image
    StringsAndTabs topcoder SRM412 div2 level3

    Introduction If you have not tried to solve this problem by yourself, please do so. Otherwise, this post will make little sense to you. This problem has a very interesting background: translate a tablature (tab) from one string instrument to another, i.e. guitar to ukulele or balalaika and vise versa. Knowing the tab system definitely helps, but even if one has no background on tab, the explanation is very clear. 🎸 The solution is straightforward, but to write a bug-free code in a short period is challenging.

      Saturday, April 1, 2017 | 6 minutes Read
      Hero Image
      How to Learn Programming

      Recently, a graduate student asked me for advice on how to improve programming skills. My immediate response in my mind is that “You asked the wrong person a right question”. But I think he will feel bad if I do not try to respond. So, here it is… Note that, this guidance is biased toward to a scientific computing rather than general software engineering. But I think the basic things like data structures and algorithms are common.

        Tuesday, March 28, 2017 | 8 minutes Read
        Hero Image
        HoleCakeCuts topcoder SRM411 div2 level3

        Introduction If you have not tried to solve this problem by yourself, please do so. Otherwise, this post will make little sense to you. Given a square cake of size $L$ with a square hole of size $\ell < L $, and a set of vertical cuts, $vcut$, and horizontal cuts, $hcut$, how many pieces of cake in the end. A Solution using Logic Let $n= \vert vcut\vert$ and $m=\vert hcut\vert$, if the cake has no hole, the total number of pieces is $ s\equiv (m+1)\cdot (n+1)$. Now, let us see how the hole affects the result.

          Saturday, March 18, 2017 | 2 minutes Read
          Hero Image
          TeleportsNetwork topcoder SRM409 div2 level3

          Introduction If you have not tried to solve this problem by yourself, please do so. Otherwise, this post will make little sense to you. Solution to this problem is straightforward, which can be broke down into two parts: construct the graph; find the min-max inconvenience. Part-I: Graph Construction Let $G(V,E)$ be the graph, and we know the order of $G$ is $\vert V\vert = n$. Because each city, except the capital, is going to build one road, the total number of edges is $\vert E\vert = m = n-1$. The rule of building a road from a city $i$ can be restated as “find the closest city $j$, ${\arg\min}_{j\in V,\ j\neq i} d(i,j)$, such that $d(0,j) < d(0,i)$”, where $d(\cdot)$ is the Euclidean distance between two cities. If the situation is degenerate, use $x$ and $y$ coordinates to resolve it. This is done in the function of build_road().

            Wednesday, March 15, 2017 | 5 minutes Read
            Hero Image
            The Stupidest Miskates I Have Made

            Here is a list of the stupidest mistakes I have made so far. So, from time to time, I can look at them and laugh at myself. 😂 title += "So Far..." NOTE: all codes are mistakes! How to convert a char to an int in C++ char c = '1'; int a = int(c); assert( a == 1 ); // NO! How to give a pointer a new content in C++ int * ptr = nullptr; void foo( int* ptr ){ ptr = new int(1); } assert( *ptr == 1 ); // NO! How to grow a vector and iterate it at the same time in C++ // generate all products of 2^a \times 3^b vector<int> v = {1}; int p = 2, q = 3, t = 30; auto pitr = v.begin(); auto qitr = v.begin(); while( t -- ){ int x = *pitr*p, y = *qitr*q; v.push_back( min( x,y ) ); if( x < y ){ ++ pitr; }else if ( x > y ) { ++ qitr; }else{ ++ pitr; ++ qitr; } } assert( v[3] == 4 && v[7] == 12 ); // No! How to use rval-reference in C++ to avoid copying struct BitArray{ uint32_t* ptr; // stores bits BitArray( size_t N ){ ptr = new uint31_t[N]; } BitArray & operator=(BitArray && rhs){ // rval-ref ptr = rhs.ptr; // move the ownership of the allocated chunk to avoid copy rhs.ptr = NULL; // so it does not deallocate the chunk } }; /* can you spot a memory leak? */ Solutions If you have not figure it out:

              Tuesday, March 14, 2017 | 3 minutes Read