lostbrain's blog

Parity @ Timus Online Judge — Time Limit Exceeding ?
By lostbrain, 9 years ago, In English

Hello everyone, I was trying this problem for some days.The idea was kind of simple.If the pair (x,y) has even parity then pair (0,x-1) and pair(0,y) will have same parity.If the pair(x,y) has odd parity then pair (0,x-1) and pair(0,y) will have different parity.I modeled the pairs to a graph.I defined two pairs to be adjacent if they have same parity.Then I used Depth First Search to spot any contradiction in the graph.I am certain that the algorithm is correct(Hopefully :P) but i am not sure why i am getting a Time Limit exceeding verdict.Is there a better idea or implementation to this problem ?? Please help me out. Here is my code

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

I havent solved it , but if its the problem with TLE , then i can suggest an improvement . Instead of dfs use union_find aka disjoint_set_union. This should get the computation within time limit

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you moinul.shaon.Your idea helped me get a AC.Here is my final AC code.Can anyone explain how DSU was passing the tests and DFS did not ?

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

    Before you were doing dfs after every query . So solution order O(q * (V+E) ) . After union_find O( q*log(V) ) .

    Union find is a good data structure to add edge in a graph and checking their connectivity . U needed just that

    → Reply