cgy4ever's blog

By cgy4ever, history, 3 years ago, In English,
 
 
 
 
  • Vote: I like it
  • +35
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Update: we added one more SRM on Jan 11th and moved the SRM on 14th to 21st.

So we will have 3 SRMs in January! See details: 705, 706, 707

»
3 years ago, # |
  Vote: I like it +41 Vote: I do not like it

SRM 707 will start in 24 hours!

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

In second problem I find answer. But I can't restore answer. Can you check my code?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could people describe some clean solutions for Div 1 250?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was thinking in terms of BFS initially couldn't get any clue.. Then tried zig zag patterns. No idea at all :(

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Is always possible to generate a pattern of the following form:

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! I guess this can be done in O(N2) too, but O(N4) seems safer to code for TopCoder SRMs.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This was my intuition. But how to find the rows and cols required and the zig zag pattern?

      Note that the above pattern does not have any up direction moves.

      We should also consider the symmetric case where we have to do a pattern with no left direction moves.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Take a 50 * 50 grid with all cells "Safe". Note that the initial shortest path is 98. Handle K < 98 separately.

        Then, whenever you are forced to move one step left/up, you increase the shortest path by 2. Thus, if you block enough cells you can make any even number in the range [100, 1000].

        For odd K, use a 49 * 50 grid and repeat the same process.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't understand. How do u decide where to place the walls?

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Suppose your grid is n * m. You place it in the following order :-

            (0, 1) (1, 1) (2, 1) ... (n - 2, 1)

            (n - 1, 3) (n - 2, 3) (n - 3, 3) ... (1, 3)

            (0, 5) (1, 5) (2, 5) ... (n - 2, 5)

            and so on....

            Basically you're forcing an up movement here and constraints are small enough for you to compute the current shortest path after each addition.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How to prove that this zig-zag approach gives the maximum k, i.e., it gives the maximum number of left steps + up steps?

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            What do you mean by maximum number? Restating what I said earlier, every "up" movement that you make increases your shortest path by 2, so if K is even and n + m - 2 is even, then you will reach K by forcing sufficient number of "up" movements. The case where K is odd is analogous, just make sure that n + m - 2 is odd.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              Here is some code for reference.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              Ignore this comment

              Thanks for the reply.

              "if you block enough cells you can make any even number in the range [100, 1000]."

              Say for a 50 * 50 grid, how to prove that 1000 is the upper bound, and not something higher?

              In other words, how to prove max number of "up" movements we can force on a board?

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            It doesn't. For instance, there's a pattern which can give up to steps but it's too complicated for 250.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Ah I see why I was confused, I didn't pay attention to k <= 1000 constraint. Silly me!

              Thanks a lot for your help!

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it -6 Vote: I do not like it

              Could you please share with us how to make that pattern?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution for Div2 500 and 1000 ? everybody failed Div2 500 .

»
3 years ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

There is an invalid test case in Div2-500

{{"...", ".#.", "..#"}, 4}

Expected (System test output): "DDRR"

Received (My Output): ""

Answer checking result: There exist a solution, but your output is "".

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    Yes, we are fixing it.

    Sorry for the delay.

    Update: Fixed now.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Return "Exists" if there is at least one cross on the given board. Otherwise, return "Does not exist". Note that the return value is case-sensitive.

      Exist — Exists. I couldn't find bug around 30 minutes. System expected "Exist".

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is the in 13 test cases. I getting segmentation fault...

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Please check my solution (Handle — AM51) . System tests are passing but someone challenged the solution before . Are you also reconsidering the challenges that might have been made with wrong cases ?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did it affect challenge phase in div2?

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What's the correct way to solve Div 1 450?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    After applying K multiply operations and L add operations, S can be express in the form:

    S * BK + A(Bp1 + Bp2 + ... + BpL) where pi <  = K

    Iterate K from 0 to 64 (or a bit bigger), consider remain = (T - S * BK) / A, we'll try to express this as sum of power of B. This can be done with a simple greedy.

    And make sure to check the case B = 0 first. I failed because of this :(

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I actually checked the case B = 0 wrongly. I didn't realize you can jump back to 0 if B = 0 -_-

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Is there any extra constraint like

      p1 >= p2 >= .. >= PL=1

      if we consider p1 is largest among them.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It doesn't matter. Just 0 ≤ Pi ≤ K will do.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

approach for Div2 1000 ?

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone help me understand one thing.
How does the following code may result in segmentation fault for the following input:
{{".#...", ".#.#.", ".#.#.", ".#.#.", "...#."}, 3000}

Div2 500

I cannot reproduce that problem locally and I get the correct output.

»
3 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain DIV 2 500 problem ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The way i solved it : Write a recursive function bool canSolve(int row,int col,int stepsLeft) which tells you if it is possible to reach cell (n-1,m-1) from cell (row,col) in exactly stepsLeft steps . Transitions are pretty straightforward , just recurse on all 4 adjacent cells .

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      where to stop that recursion when steps left becomes zero ?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Base Case : if(stepsLeft == 0) { return row == n-1 && col == m-1 ; }

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          can we have this approach 1. find the shortest path such that ((K-pathlength)==even_number) 2. print that path 3. repeat last two consecutive characters (K-pathlength) times .

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            How do you find such a shortest path ? K-pathlength can be odd too , if you can find such a path , it should work i think .

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Yes, I did exactly that.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              ccsnoopy i stucked in the first part , how to efficiently find such path can you please explain ?

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Since the graph is unweighted, you can simply do BFS from upper left corner and find the distance on the lower right corner.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  in this BFS we should not visit the already visited cell ,am i correct ?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain div2 hard in the context of Min Max flow ? how to reduce the problem to min and max flow ?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Do Solutions submitted for practice problems on TopCoder checked on Full test cases in web arena ?