YocyCraft's blog

Optimize the solution by randomization?
By YocyCraft, history, 2 years ago, In English

Today I implemented the intended solution of 1767E

Which unexceptedly got TLE...

Then I tested the sample which input is small (n=10, m=40) and recorded the time consuming of each step in my first solution

I discoverd that when good mask1 of vertex set A (1-m/2) is too much (about 2^19), the preparation of dp takes very long time (about 1000ms on my computer but 1700+ms on official judge)

However, in most of test samples the time consuming is not that much beacuse of a smaller set of good mask1. So I thought about if I permute the number of colors randomly......

In 1st attempt I still got TLE, but after changed the seed of java.util.Random, I got AC in the 2nd attempt

(I know there must be better implementation but I'm lazy QwQ)

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

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

Auto comment: topic has been updated by YocyCraft (previous revision, new revision, compare).

→ Reply
»
2 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Why downvote??

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

The solution with $$$O(2^{\frac{n}{2}})$$$ is the correct solution but maybe java is too slow... You can also try Bron's algorithm with $$$O(3^{\frac{n}{3}})$$$ which is a little faster. See the fastest code or my solution: 185938971

→ Reply