najmul.csebuet's blog

By najmul.csebuet, history, 4 years ago, In English

I am trying to solve following problem.

Problem

Any hint and more better a solution is appreciated. I am trying a lot but not solved yet.

My New Code
  • Vote: I like it
  • -9
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
You should put your long code into the spoiler

By the way, I am unable to see the problem :(

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

    s >= 1 so no MST I think. Now trying to make some edge set from sequence 1. Then When i process seq 2, trying to filter previous choices. What do you think?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      Related to Hint 1

      Also the number of possible edge set can be exponential

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

        I applied some edge fixing. Passed 4 cases then TLE. See my updated code on the message.

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

          As discussed your solution won't likely work :(

          Your solution works in $$$O(S(N+M))$$$ which is probably too slow