dush1729's blog

By dush1729, history, 4 years ago, In English
A
B
C
D
E

How to solve F? Does it use the fact that sequence is super increasing.

  • Vote: I like it
  • +11
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

For problem E, I used an optimization method as I was too lazy. All I did was that I bruteforced but I saved on each cell the direction I last covered. If I activated another bulb and found that this square is lit in the direction I covered, then I stop continuing the row/column. That is an $$$O(N^3)$$$ but off-course optimized. Passed in around $$$250ms$$$.

For problem C, I stored the remainder of 0,1,2 and handled some conditions(number theory) resulting in a complexity of $$$O(log_{10}(N))$$$ without using any DP.

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

    If you are stopping after you are seeing the bulb its not $$$O(N ^ 3)$$$, its $$$O(N ^ 2)$$$ since you will visit every point only once

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

      I visited each bulb and then visit each column and row from each bulb but with the optimized way I stated above.

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

        Yeah but this optimization becomes $$$O(N ^ 2)$$$ because you dont visit the same vertice again, you are stopping when you saw the vertice that have been already illuminated

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

          Not really. As it can be illuminated from another direction causing WA. So I only save where it was illuminated(its direction, either left, right, up, down). A case like(B=bulb, L=Left, R=Right, U=Upwards, D=Downwards, otherwise empty):

          B...

          .B..

          ..B.

          ...B

          Would simulate for each bulb in my code:

          BRRR

          DB..

          D.B.

          D..B

          BURR

          LBRR

          DDB.

          DD.B

          etc...

          Edit: Complexity was wrong. I mixed up with N of height and width and multiplication of them.

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

    Employed the same idea for my "dfs", passed in ~400ms. I only assumed that up/down and left/right directions are equivalent: if some cell is directed upwards and is luminated, then the light should have been emitted from downwards, which means that everything in upward and downward directions till the first block is luminated (same for left/right). Most cells are visited only 1 time, with a small minority being visited up to 6-15 times (to check and abort moves in already visited direction).

    Link for my submission

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

Another easier approach for E

Consider only 1 row. You can break row into multiple segments by blocked cells. If a segment contains bulb then this whole segment will be lit else it won't be lit.

Do this for every row and column.

Code

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

For E, it seems that you assumed that find the nearest blocked cells in one direction takes O(1) time. I used binary search to do this, which is O(logN). Can you elaborate on this?

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

    If a[i][j] is blocked then l[i][j] = j else l[i][j] = l[i][j - 1]. Do the same for other 3 directions.

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

Can anyone help me on B to find the only case I'm getting wrong..

My Submission

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

    I think your solution is not right if I understand your code correctly. You are checking the gcd for all pairs of Ai and Aj. But the answer does not have to be gcd. You should just check all possible values from 2 to the max of Ai.

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

I solved B and C just a few hours ago.I am practicing to solve B and C fast.I have a question.Will this method help me to solve Div-2 C consistently in Codeforces??

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

    I don't think solving B and C is sufficient to solve Div 2 C on codeforces. You should practice D too. And you can keep track of your progress on kenkoooo(just append your handle at the end of url) along with appropriate difficulties.

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

      Does solving C consistently lead one to become expert or does it lead to become specialist only?

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

        Yes solving C consistently should lead to expert.

        PS — I was talking about D on Atcoder not on Codeforces.

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

space?

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

I saw the solutions for E and I think i gave a simpler and more intuitive one.

Create the matrix itself, and just go over every column and row and do the following:
If you see a bulb, go back until you see another bulb/blocked cell, while marking all the cells as lit. Then continue forward while remembering that you saw a bulb (i.e 'light=true'), and mark cells you see as lit.
If you see a blocked cell, simply set 'light=false', which means that when you continue forward you will not mark cells as lit (unless you see a bulb later, in which case you will go back and set these cells as lit).

With this method you are going over every cell at most 4 times, once in each direction. which means the complexity is n*m.