Optimize the solution by randomization?
source link: https://codeforces.com/blog/entry/110357
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK