Syrus's blog

About Problem E. Matrix Transformation in EDU 173
By Syrus, history, 23 hours ago, In English

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.

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

»
21 hour(s) ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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))

→ Reply
»
20 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply