Results 1 to 25 of 30

Thread:

Hybrid View

Previous Post Previous Post   Next Post Next Post
  1. #1
    ! vbTheKing's Avatar
    Join Date: Sep:2003
    Location:
    Posts: 4,138

    Lightbulb

    ...

    [1..N].
    i - Aj, - . , Ai .
    - b*N , b*N*N
    :
    1, 9, 8, 5, 9, 3, 4, 5, 2
    9, 0, 9, 9, 0, 4, 5, 0, 0

    b , .. 100, , 999999 b*N (99999900) .

    .

    9-, , 8- ... , , .
    ''? * *
    - !
    ...

  2. #2
    ɐ-əpoɔᴉu⋂ ɐ ə anrieff's Avatar
    Join Date: Apr:2004
    Location: Sofia
    Posts: 8,448
    , : ? , . seen[] , A[] . A - - seen[], - 0. - 10*N, .. b = 10
    , . .
    "640K ught to be enough for anybody" - Bill Gates, 1981
    ::Machine specs::Fract::AGG::::Baileys::blog::YouTube channel

  3. #3
    N/A Demoman's Avatar
    Join Date: Sep:2005
    Location:
    Posts: 3,098
    Quote Originally Posted by anrieff View Post
    , : ? , . seen[] , A[] . A - - seen[], - 0. - 10*N, .. b = 10
    - . ( ).

  4. #4
    ɐ-əpoɔᴉu⋂ ɐ ə anrieff's Avatar
    Join Date: Apr:2004
    Location: Sofia
    Posts: 8,448
    Quote Originally Posted by Demoman View Post
    - . ( ).
    , . , Kaspirtov: "1 2 3 1000000000", seen , , .

    , , .. STL- set<int>. seen seen.insert(x), - seen.lower_bound(x).
    - O(N logN), .
    ( ), , Pesho
    , . .
    "640K ught to be enough for anybody" - Bill Gates, 1981
    ::Machine specs::Fract::AGG::::Baileys::blog::YouTube channel

  5. #5
    ! vbTheKing's Avatar
    Join Date: Sep:2003
    Location:
    Posts: 4,138
    , , ...
    ''? * *
    - !
    ...

  6. #6
    Defender Kaspirtov's Avatar
    Join Date: Jun:2006
    Location: Sf
    Posts: 7,414
    ...

    :
    :
    8, 3, 5, 1, 1, 2, 1, 4, 5, 3, 8
    1) 2- , j, j-1 1 (- - 0) 2-, 0 > 2; 2-, -1, .. -2;
    :
    8, 3, 5, 2, 2, -2, 1, 4, 5, 3, 8
    2) 3- , j, j-1 1 -2, 0, 3-, 0, 2 > 3; 3-, -1, .. -3;
    :
    8, -3, 5, 2, 2, -2, 1, 4, 5, -3, 8
    3) 4-, :
    8, -3, 5, 2, 2, 4, 4, -4, 5, -3, 8
    4) 5-, :
    8, 5, -5, 2, 2, 4, 4, 5, -5, -3, 8

    ...
    :
    -8, 5, 8, 2, 2, 4, 4, 5, 8, 8, -8
    0. :
    0, 5, 8, 2, 2, 4, 4, 5, 8, 8, 0

    b*N , b- N ; b*N+N =(b+1)*N ;

    Edit:
    , .. (b+1)*(N + 1) ;

    Edit 2:
    , , (b+1)*N.
    @anrieff, .
    Last edited by Kaspirtov; 20th May 2008 at 23:20.
    " , , , , ."

  7. #7
    Registered User
    Join Date: Dec:2007
    Location:
    Posts: 655
    Quote Originally Posted by Kaspirtov View Post
    , .. (b+1)*(N + 1) ;
    , b , : , . , , - .

  8. #8
    ! vbTheKing's Avatar
    Join Date: Sep:2003
    Location:
    Posts: 4,138
    ! .
    ''? * *
    - !
    ...

  9. #9
    ɐ-əpoɔᴉu⋂ ɐ ə anrieff's Avatar
    Join Date: Apr:2004
    Location: Sofia
    Posts: 8,448
    Kaspirtov, `b'.

    "1 2 3 1000000000" .
    , . .
    "640K ught to be enough for anybody" - Bill Gates, 1981
    ::Machine specs::Fract::AGG::::Baileys::blog::YouTube channel

  10. #10
    Defender Kaspirtov's Avatar
    Join Date: Jun:2006
    Location: Sf
    Posts: 7,414
    Quote Originally Posted by anrieff View Post
    Kaspirtov, `b'.

    "1 2 3 1000000000" .
    ->
    Extra , )))
    , 3 . -

    @-85, - - , b -1 ( ) b , const.
    Last edited by Kaspirtov; 20th May 2008 at 23:50.
    " , , , , ."

  11. #11
    Registered User
    Join Date: Dec:2007
    Location:
    Posts: 655
    Quote Originally Posted by Kaspirtov View Post
    @-85[/B], - - , b -1 ( ) b , const.
    , , , .

  12. #12
    Defender Kaspirtov's Avatar
    Join Date: Jun:2006
    Location: Sf
    Posts: 7,414
    Quote Originally Posted by AK-85 View Post
    , , , .
    ! )) , b
    10q anireff!
    " , , , , ."

  13. #13
    Registered User
    Join Date: Dec:2007
    Location:
    Posts: 655
    , - , b , . b "" N, , , , ?

    , - , . .

  14. #14
    ! vbTheKing's Avatar
    Join Date: Sep:2003
    Location:
    Posts: 4,138
    -85, - , , ...
    , , 100 1000, , .
    ''? * *
    - !
    ...

  15. #15
    Registered User
    Join Date: Dec:2007
    Location:
    Posts: 655
    Quote Originally Posted by vbTheKing View Post
    , , 100 1000,
    , ! , . :
    - , , , , . 32- 64-, 32- 64-, , , , .

    ( ), , .

    Quote Originally Posted by Kaspirtov View Post
    , , 100 ?!
    , . ( ; , ). , , .
    Last edited by AK-85; 21st May 2008 at 00:30.

  16. #16
    ! vbTheKing's Avatar
    Join Date: Sep:2003
    Location:
    Posts: 4,138

    Lightbulb



    , .

    Quote Originally Posted by vbTheKing View Post

    b , .. 100, , 999999 b*N (99999900) .
    , , b ( ), - N.
    ''? * *
    - !
    ...

  17. #17
    Registered User
    Join Date: Dec:2007
    Location:
    Posts: 655
    Quote Originally Posted by vbTheKing View Post
    , , b ( ), - N.
    , ... Kaspirtov , , , Pesho .

  18. #18
    Defender Kaspirtov's Avatar
    Join Date: Jun:2006
    Location: Sf
    Posts: 7,414
    Quote Originally Posted by AK-85 View Post
    , ... Kaspirtov , , , Pesho .
    ))
    : , Pesho, , b , "" N. , - , - b N-1.

    .. Pesho .

    , ! ))
    " , , , , ."

  19. #19
    Pesho's Avatar
    Join Date: Nov:2001
    Location: Sofia
    Posts: 5,169
    ( C):

    1. A[1..N], : B[1..N] C[1..N], "max".

    2. B[N] = 0; max = A[N];

    3. for (i = N-1; i >= 1; --i)

    3.1. if (A[i] >= max) { B[i] = 0; max = A[i]; continue; }

    3.2. for (j = i+1; B[j] != 0; j = C[j])

    3.2.1. if (A[j] > A[i]) { B[i] = A[j]; C[i] = j; break; }

    3.3. if (B[j] == 0) { B[i] = 0; }

    4. A = B

    ( o worst-case ), . i amortized ( log(N)), O(N), O(N*log(N)). , - .
    Last edited by Pesho; 21st May 2008 at 01:18.

  20. #20
    Registered User
    Join Date: Dec:2007
    Location:
    Posts: 655
    : ( - ) - , ( , C[k] , A[k], 0, A[k] >= max).

    - . C ?

    Kaspirtov, , : , . Pesho , (- ) .
    Last edited by AK-85; 21st May 2008 at 04:44.

  21. #21
    Pesho's Avatar
    Join Date: Nov:2001
    Location: Sofia
    Posts: 5,169
    Quote Originally Posted by AK-85 View Post
    : ( - ) - , ( , C[k] , A[k], 0, A[k] >= max).

    - . C ?

    , ( ...). C, ( , , 0).

    ... . , C++ ( ):

    Code:
    #include <iostream>
    #include <vector>
    
    std::vector<int> transform(const std::vector<int>& A) {
        int N = A.size() - 1;
        int max = A[N];
        std::vector<int> B(N + 1), C(N + 1);
        B[N] = 0;
        for (int i = N-1; i >= 1; --i) {
            if (A[i] >= max) { B[i] = 0; max = A[i]; continue; }
            int j = i+1;
            while (1) { 
                if (A[j] > A[i]) { B[i] = A[j]; C[i] = j; break; }
                if (B[j] == 0) { B[i] = 0; break; }
                j = C[j];
            }
        }
        return B;
    }
    
    void print(const std::vector<int>& A) {
        for (unsigned i = 1; i < A.size(); ++i) std::cout << A[i] << ' ';
        std::cout << std::endl;
    }
    
    int main()
    {
        std::vector<int> A(10);
        A[1] = 1; A[2] = 9; A[3] = 8; A[4] = 5; A[5] = 9; A[6] = 3; A[7] = 4; A[8] = 5; A[9] = 2;
        print(A);
        print(transform(A));    
    }

    , - O(N). , (while(1)...) N. "max" , O(N).
    Last edited by Pesho; 21st May 2008 at 21:44.

  22. #22
    ! vbTheKing's Avatar
    Join Date: Sep:2003
    Location:
    Posts: 4,138

    Cool

    Pesho, ! .
    , ++ , .
    - Kaspirtov.

    , !

    P.S. , , - .
    ''? * *
    - !
    ...

  23. #23
    ! vbTheKing's Avatar
    Join Date: Sep:2003
    Location:
    Posts: 4,138
    , . ""
    ''? * *
    - !
    ...

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Copyright © 1999-2011 . .
iskamPC.com | mobility.BG | Bloody's Techblog | | 3D Vision Blog |