Блог пользователя dush1729

Автор dush1729, история, 4 года назад, По-английски
A
B
C
D
E

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

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        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 года назад, # ^ |
          Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

          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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

My Submission

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes solving C consistently should lead to expert.

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

space?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.