Everyday TLEOptimize the solution by randomization?
Разница между en1 и en2, 903 символ(ов) изменены
[My submission for 1767EToday I implemented the [intended solution](https://codeforces.net/blog/entry/110225) of [1767E](https://codeforces.net/contest/1767/problem/E)↵
↵
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 solutioni](https://codeforces.net/contest/1767/submission/186104872)↵
↵
When you implemented an intended exponential complexity solution in editorial and got TLE:↵
↵
codeforTLEsI 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](https://codeforces.net/contest/1767/submission/186116293)↵
↵
(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)