We will hold AtCoder Beginner Contest 236.
- Contest URL: https://atcoder.jp/contests/abc236
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220123T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: Kodaman, leaf1415, Nyaan, physics0523
- Tester: penguinman
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
Beginner they said...
spent whole time trying dp solution for D without realizing lack of optimal substructure property lol
https://mirror.codeforces.com/blog/entry/21103?#comment-257777 saved my ass and rating
Did you know that
const ll inf = 1e18 + 23;is the same asconst ll inf = 1e18;? That's how I almost didn't solve Ex... I guess I will stick toconst ll inf = 1ll<<60from now on.(ll)1e18 + 23 fixes that I guess
1e18L + 23 is 100...0023
n<=16coder
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://mirror.codeforces.com/blog/entry/68953 ;
Am i the only one who stares at the screen for literally 80 minutes after solving D?
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 0
Editorial
Can you please explain approach how to solve this
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.
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.
Simply doing random shuffling is supposed to work. The distinct configurations are only $$$2027025$$$ (you can read the editorial for a detailed explanation).
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
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.
Is random shuffle $$$O(n)$$$? If yes, you can just swap $$$2$$$ random elements instead of doing random shuffle of the whole array.
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_randimplementation). Benchmarks: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.
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.
Please make TestCases public :)
I think they haven't update testcases since abc233. Link
Almost similar problem to E: https://mirror.codeforces.com/contest/1486/problem/D
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?
https://mirror.codeforces.com/blog/entry/68953