Optimize the solution by randomization?

Правка en3, от YocyCraft, 2022-12-20 18:04:57

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)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский YocyCraft 2022-12-20 18:04:57 1 Tiny change: 't solutioni](https://' -> 't solution](https://'
en2 Английский YocyCraft 2022-12-20 18:04:32 903
en1 Английский YocyCraft 2022-12-20 16:11:13 204 Initial revision (published)