chokudai's blog

AtCoder Beginner Contest 236 Announcement
By chokudai, history, 3 years ago, In English

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!

  • Vote: I like it
  • +41
  • Vote: I do not like it

Comments Comments (23)
| Write comment?
»
3 years ago, # |
  Vote: I like it +95 Vote: I do not like it

Beginner they said...

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

spent whole time trying dp solution for D without realizing lack of optimal substructure property lol

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

https://mirror.codeforces.com/blog/entry/21103?#comment-257777 saved my ass and rating

→ Reply
»
3 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

n<=16coder

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ;

→ Reply
»
3 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Am i the only one who stares at the screen for literally 80 minutes after solving D?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain approach how to solve this

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like 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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Simply doing random shuffling is supposed to work. The distinct configurations are only $$$2027025$$$ (you can read the editorial for a detailed explanation).

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      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=8
      Generated testcase example for N=8

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Is random shuffle $$$O(n)$$$? If yes, you can just swap $$$2$$$ random elements instead of doing random shuffle of the whole array.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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:

          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.

          → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Please make TestCases public :)

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Almost similar problem to E: https://mirror.codeforces.com/contest/1486/problem/D

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply