love_you_ma's blog

Reducing Run Time

By love_you_ma, history, 9 years ago, In English

**Hi. A few days ago I have solved a Problem on UVa named Virtual Friends .

The link is here : Click Here .

This is a Union Find / Disjoint Set Find problem . I used that algorithm and Got Accepted verdict at 2.281 Sec. Although the problem says it's Time Limit is 10 Sec. May be the data set is Huge. I have seen the Best Submission ever for this problem is 0.104 Sec.

Now my Question is how to decrease my Run Time?? I want to get Accepted verdict less than 1 Sec. How to optimize my Code ??

My Code is : http://ideone.com/34YqH9

Thanks is Advance.**

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

Comments Comments (8)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You could try to use fast I/O.

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

You can hash the string instead of putting it into a map.

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

    How can I do that ??

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

      I have changed your code to use scanf to read the strings http://ideone.com/MXXktl Result: 0.760 s (-1.521 s)

      I have also tried to use hash table instead of map http://ideone.com/4qQZ1m Result: 1.624 s (-0.657 s)

      Two techniques combined: http://ideone.com/nROrJK Result: 0.257 s (-2.024 s)

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

        Thanks Sir.. it Really Worked ... But I didn't get you Hashing Function. Whats the idea behind Hashing ?microtony

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

          It converts a string into an integer of small range (here: 0-599999) Two equal strings should give the same integer while two different strings should hopefully give two different integers (collisions may occur but the hash function takes account of that (open addressing + linear probing)

          Read more here: https://en.wikipedia.org/wiki/Hash_table

          Note that in my code the choice of 23 is not very good you should try another larger prime number.

          → Reply