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

About Problem E. Matrix Transformation in EDU 173
Автор Syrus, история, 24 часа назад, По-английски

I find Problem E to be very interesting, as it can be solved by modeling with graph theory on matrices. However, it seems there are many different ways to approach this problem. Could everyone share their insights? Or perhaps provide some problems that help in learning such skills? Thank you very much.

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

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

personally i didn't model it to a graph,instead i solved it by

just in case

here is my submission 298383591

my time complexity is O(nm*log(max ai)*log(n+m))

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

I divided the problem to solving for every bit

Then what i saw is if i want to correct a position i might need to change a whole row or column, which can trigger new changes in other places, I can do them but then it can change other people ect...

So the question is given that i need to trigger changes in some specific places am i gonna be able to do all the changes that will be triggered, or will it go into an infinite loop? Thats when I understood i could model "triggering" as an edge in a graph and it became checking for a cycle with an operation i must do in it

→ Ответить