### chokudai's blog

By chokudai, history, 4 months ago,

We will hold AtCoder Beginner Contest 236.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

• +41

 » 4 months ago, # |   0 Best of luck everyone!
 » 4 months ago, # |   +95 Beginner they said...
 » 4 months ago, # |   +11 spent whole time trying dp solution for D without realizing lack of optimal substructure property lol
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Could you please explain why is there no optimal substructure property?Edit: I think I got this. For a given mask the path to achieve that mask matters and that's why the state mask is inappropriate.
 » 4 months ago, # |   +11 https://codeforces.com/blog/entry/21103?#comment-257777 saved my ass and rating
 » 4 months ago, # |   +33 Did you know that const ll inf = 1e18 + 23; is the same as const ll inf = 1e18;? That's how I almost didn't solve Ex... I guess I will stick to const ll inf = 1ll<<60 from now on.
•  » » 4 months ago, # ^ |   0 (ll)1e18 + 23 fixes that I guess
•  » » 4 months ago, # ^ |   +8 1e18L + 23 is 100...0023
 » 4 months ago, # |   +28 n<=16coder
 » 4 months ago, # |   0 For F, the update in O(2^N) time trick is cool. Basically they maintain the span of a set of vectors as explicitly, and rely on the fact that it will not change very often.An alternative I used was to maintain the basis elements instead, as in https://codeforces.com/blog/entry/68953 ;
 » 4 months ago, # |   +36 Am i the only one who stares at the screen for literally 80 minutes after solving D?
•  » » 4 months ago, # ^ |   0 In E I desperatly tried to find a way how to implement the binary search, and I think I was close to see that:Does the average exceed K?“The average of $x_1,...,x_n$ is greater than K ⇔ $(x_1-K)+...+(x_n-K)$ is more than 0Editorial
•  » » » 4 months ago, # ^ |   0 Can you please explain approach how to solve this
•  » » » » 4 months ago, # ^ |   0 As the editorial explains, we want to solve this problem with binary search. So, we need to be able to check (like in O(n)) for a given value y if it is possible to choose some element from the array as the rules imply, so that the avg (and also for median) is bigger or equal that y.The trick to do tjos is to "adjust" the array a[] by y, ie for all i do a[i]-=y. Then we can solve on this adjusted array a simpler problem, namely find to choose elements so that the sum is >=0.To solve that we can do a simple dp going from left to right throug the array maintaining states for the two cases that we choose the current element, or not choose it.
 » 4 months ago, # |   +24 I have to confess that now I have claimed points from problem D with an incorrect solution in two ABC contests in a row.Simply doing random shuffling for almost 2 seconds (28754398 => AC) instead of trying all permutations (28749189 => TLE) has a very good chance to dodge WA. Tests are weak.
•  » » 4 months ago, # ^ |   +29 Simply doing random shuffling is supposed to work. The distinct configurations are only $2027025$ (you can read the editorial for a detailed explanation).
•  » » » 4 months ago, # ^ |   +18 Thanks, you are right! So the probability of finding the maximum XOR value after a single shuffle is $2^N \frac{N!}{(2 N)!}$ and if $K$ is the total number of shuffles, then the probability of failing a single testcase can be calculated as $P_{fail} = (1 - 2^N \frac{N!}{(2 N)!})^K$But now the number of shuffle trials that can be performed without exceeding the time limit actually plays a major role. In my submission the value of $K=5833915$ and the failure probability for a single worst possible testcase can be calculated as 5.6%. Such worst possible testcase can be constructed using this Ruby testcase generator, the expected correct answer is 2^N-1 or 255 for N=8puts n = 8 a = (2 * n).times.map { [0] * (2 * n) } (2 * n).times.to_a.shuffle.each_slice(2).with_index do |x, idx| i, j = x.sort a[i][j] = 1 << idx end (2 * n - 1).times do |row| puts a[row].slice(2 * n - (2 * n - 1 - row), (2 * n - 1 - row)).join(" ") end  Generated testcase example for N=88 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 128 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 32 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 1 0 0 0 A 5.6% failure chance per testcase isn't very encouraging, though it's unlikely that all 28 testscases from the AtCoder's set are stressing the worst possible scenario. So I got my AC verdict on the 3rd attempt during the contest. This wouldn't work well on Codeforces because of system tests (or because of 12 hours of hacking in education rounds). But AtCoder has its own rules.Increasing the number of tried random shuffles can drastically reduce the chance of failure. Even for $K=10000000$ the probability of failure per worst testcase already drops to 0.72%. This makes improving the performance of random shuffles really important. Appears that the default Mersenne Twister PRNG from the standard D language library is far from optimal. Replacing it with jsf64 can make the whole thing more than twice faster, but that's a good topic for a separate blog post.
•  » » » » 4 months ago, # ^ |   +1 Is random shuffle $O(n)$? If yes, you can just swap $2$ random elements instead of doing random shuffle of the whole array.
•  » » » » » 4 months ago, # ^ |   +8 Yes, I was doing a 15-elements array shuffle each time and this was indeed excessive. Thanks again for a very useful hint!Changed the code to do only 2 random elements swap per iteration and reworked XOR updates to make them $O(1)$ too. Everything is much faster now. Additionally I found this very interesting blog: https://www.pcg-random.org/posts/bounded-rands.html (and borrowed their optimized bounded_rand implementation). Benchmarks: K=30M iterations, standard libraries only: GNU C++ 1507 ms, Clang++ TLE, LDC 766 ms, GDC 960 ms, DMD 1163 ms K=30M iterations, jsf32 prng, unbiased bounded_rand: GNU C++ 259 ms, Clang++ 199 ms, LDC 210 ms, GDC 202 ms, DMD 352 ms K=300M iterations, jsf32 prng, biased bounded_rand: GNU C++ 1796 ms, Clang++ 1710 ms, LDC 1614 ms, GDC 1687 ms The solution is now fast enough to even handle N=9 (0.4% probability to fail a testcase with K=350M iterations). Standard D and C++ prng libraries are very slow (3x-6x times slower than necessary!) and this was a big unpleasant surprise. Looks like having a custom code template makes a lot of sense for prng heavylifting.
 » 4 months ago, # |   +3 Problem G is very similar to the problem (USACO 2007 Nov. Gold) Cow Relays. Just changing a bit of the program can lead to AC problem G.
 » 4 months ago, # |   +12 Please make TestCases public :)
•  » » 4 months ago, # ^ |   0 I think they haven't update testcases since abc233. Link
 » 4 months ago, # |   +3 Almost similar problem to E: https://codeforces.com/contest/1486/problem/D
 » 4 months ago, # |   0 In problem F, I couldn't understand from the editorial how are we checking if a certain hotness can be obtained from some elements of S in O(N) time. Any help?
•  » » 4 months ago, # ^ |   0