An ASCII Art Explanation of This Problem and My C Solution


  • 5
    D
    //           =   a l l    c a s e s   =
    // 
    //     case 1     case 2: expanding   case 3: collapsing
    //                     (global)           (local)
    //                  (not crossing)   (may not crossing)
    // 
    //    <------+     +------------+      +---------+
    //           |     |            |      |         |
    //           |     |  +-----+   |      |  +---+  |
    //           |     |  |     |   |      |  |   |  :
    //           #     |  |     #   |      |  v   |  :
    //                 |  |         |      |      |  
    //                 |  +---------+      +------+  
    //                 |
    //                 +--------->
    // 
    //     case 4: failed expanding                
    //      
    //      +----+
    //      |    |
    //      |  <----[2]----^     [2]: second failure
    //      |    #         |
    //      |             [1]    [1]: first  failure
    //      |              |
    //      +--------------+
    // 
    //     case 5: failed expanding & then collapsing
    // 
    //      +----+
    //      |    |
    //      |    |  +------+
    //      |    #  | [C]  |     [C]: may be perfectly collapsed
    //      |       +--->  |
    //      |              |
    //      +--------------+
    // 
    //     case 6: failed expanding                
    // 
    //         +---+
    //         |   |
    //         |   |
    //         |   #
    //         |
    //       <---[2]----+        [2]: second failure
    //         |        |
    //         |       [1]       [1]: first  failure
    //         |        |
    //         +--------+
    // 
    //     case 7: failed expanding & then collapsing
    // 
    //         +------+
    //         |      |
    //         |      #
    //         |
    //         |  +-----------+
    //         |  |  +-----+  |
    //         |  |  +-->  | [1] [1]: failure
    //         |  |        |  |
    //         |  +--------+  |
    //         +--------------+
    // 
    //    *notice: case 3 = case 6 + case 7
    // 
    //     case 8: docking!
    // 
    //         +-------+
    //         |       |
    //         |       #
    //         |
    //         |       ^
    //         |       |
    //         +-------+
    // 
    // #: starting point 
    
    // case 3
    bool isPerfectCollapsing( int cur, int len, int *data )
    {
        while ( cur < len ) {
            if ( data[cur] < data[cur-2] ) {
                ++cur;
            } else { return false; }
        }
        return true;
    }
    
    bool isPerfect( int *data, int len )
    {
        // case 1
        if ( len <= 2 ) { return true; }
        // case 8
        if ( len >= 5 &&
             data[3]==data[1] &&
             data[2]<=data[0]+data[4] )
        {
            return false;
        }
    
        int cur = 2;
        while ( cur < len && data[cur] > data[cur-2] ) {
            ++cur;
        }
        if ( cur == len || cur == len-1 ) {
            // case 2: perfect expanding
            return true;
        }
    
        // collapsed!
        if ( cur == 2 || cur == 3 ) {
            // case 3
            return isPerfectCollapsing( ++cur, len, data );
        }
    
        if ( data[cur]+data[cur-4] >= data[cur-2] ) {                    // case 4/5
            if ( ++cur < len ) {
                if ( data[cur]+data[cur-4] >= data[cur-2] ) {            // case 4
                    return false;
                } else { return isPerfectCollapsing(++cur, len, data); } // case 5
            } else { return true; }
        } else { return isPerfectCollapsing(++cur, len, data); }         // case 6/7
    }
    
    bool isSelfCrossing( int *x, int xSize ) {
        return !isPerfect( x, xSize );
    }

  • 0
    M

    Maybe I'm dense, but does your algorithm/reduction accommodate this case?

      ┏━━━━━━━━━━━━━━━━━━━━━━━━━┓
      ┃ ┏━━━━━━━━━━━━━━━━━━━━━┓ ┃
    E ┃ ┃ ┏━━━━━━━━━━━━━━━━━┓ ┃ ┃
    ┃ ┃ ┃ ┃ ┏━━━━━━━━━━━━━┓ ┃ ┃ ┃
    ┃ ┃ ┃ ┃ ┃ ┏━━━━━━━━━┓ ┃ ┃ ┃ ┃
    ┃ ┃ ┃ ┃ ┃ ┃ ┏━━━━━┓ ┃ ┃ ┃ ┃ ┃
    ┃ ┃ ┃ ┃ ┃ ┃ ┗━━━┓ ┃ ┃ ┃ ┃ ┃ ┃
    ┃ ┃ ┃ ┃ ┃ ┗━━━┓ ┃ ┃ ┃ ┃ ┃ ┃ ┃
    ┃ ┃ ┃ ┃ ┗━━━━━┛ ┃ ┃ ┃ ┃ ┃ ┃ ┃
    ┃ ┃ ┃ ┗━━━━━━━━━┛ ┃ ┃ ┃ ┃ ┃ ┃
    ┃ ┃ ┗━━━━━━━━━━━━━┛ ┃ ┃ ┃ ┃ S
    ┃ ┗━━━━━━━━━━━━━━━━━┛ ┗━┛ ┃
    ┗━━━━━━━━━━━━━━━━━━━━━━━━━┛
    

    If so, could you explain how?


  • 1
    M

    Wait, never mind. There are no 0-length moves, and the "cursor" is always moving counter-clockwise, so the above pattern isn't a valid test case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.