tourist's blog

AtCoder Grand Contest 020
By tourist, history, 7 years ago, In English

What is better than setting one AtCoder Grand Contest? Setting two AtCoder Grand Contests, of course!

AtCoder Grand Contest 020 will be held on Sunday (time). The writer is tourist.

Contest Link

Contest Announcement

This is the first contest of 2018 counted towards AtCoder Race Ranking. If you get into top 30 in this contest, you will get GP30 scores.

The point values will be 300 — 500 — 700 — 1100 (500) — 1400 — 2100. Note that the contest duration is unusual (130 minutes).

Let's discuss problems after the contest.

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

Comments Comments (54)
| Write comment?
»
7 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

What is better than setting two AtCoder Grand Contest? Participating in two AtCoder Grand Contests held by tourist, of course!

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +71 Vote: I do not like it

Previous AGC set by tourist was 4,5 months ago, it's kinda hard to believe but these two AGCs are two AGCs in a row xD. Glad to see AGCs coming back (next one is scheduled three weeks after this).

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

    Isn't the next one three weeks after this and not two?

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

      Indeed, thanks for nice catch, I will correct it

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

    Pls kill me, I forgot about it and slept too long >_> Moreover before changing timezone AGC was always at 2PM, but now it is at 1PM, so it was 13min versus 1h13min being late in my case xd

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

      Hm so the takeaway here for me is that you sleep past 1pm. Impressive.

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

        1pm? These are rookie numbers

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

          Judging from your personality, I thought you were trying F.

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

Score for D: 1100(500) means? is 500 partial score like in Codechef?

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

    1100 (500) means that the full score of problem D is 1100, but it's possible to get 500 points for solving the problem for partial constraints mentioned in the problem statement.

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

It is unfortunate, I wasn't able to submit in last 2 minutes, page just didn't want to load :( You maybe should have extended the contest for 5/10 minutes because of such issues.

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

What is the solution to problem F?

I found the solution to the case where all L's are equal here, but the obvious generalization to the case where L's can be different was incorrect.

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

    Uploaded the editorial.

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

      Thanks. I've already seen it. By the way, why is there no subtask for solving the case where all L's are equal?

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

        Well, the fact that it's searchable on the Internet is a good counterargument.

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

    It seems that we can speed up editorial solution a little by using one more bitmask in the dp state, instead of generating all (N - 1)! permutations..

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

      Nice, you are right, we didn't notice that. In fact, 5! < 25·5, but the complexity becomes O(22N - 2·N3·C2).

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

Solution for C?

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

    I solved by using bitset. O(n2 × a) DP is obvious but if I use bitset seems like we can achieve O(n2 × a / 64). Is it true that bitset is always very fast in use of bitwise operation?

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

      Something else that passes is probabilistic solution of shuffling array and then assuming that optimal solution likely never has delta at any time exceeding 50000 (that is when we are solving problem of partitioning array into two halves as close in sum as possible, in our dp we can limit current delta between halves to [-50000, 50000]).

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

        The delta between halves is at most 2000 because if it exceeds, we can move one element from the larger side to the smaller side and get a better solution.

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

          So this makes sense for the final delta, however how does this help us during our dp? As in although final delta is <= 2000, the delta at when we are say midway through our dp can be greater, or is there some easy way to avoid this?

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

            Right, I didn't get exactly what you were trying to say. In that case the delta can indeed be larger.

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

          The final delta is indeed at most 2000, but if we add elements to halves in random order, intermediate deltas may be larger. I assume they are bounded by something like with high probability, since the process looks like a random walk.

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

      Can we binary search on the answer (say X) and see if exactly (2N - 1) / 2 subsequences have sum less than X? Would that work within TL?

      We can use DP to check that. f(i, j) represents no. of subsequences using first i numbers with sum  < j. Maintain only 2 rows in the DP table to avoid exceeding memory limit.

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

        Numbers can get very large, on order of 2^2000, what is your plan of avoiding this? Or if you do have such large numbers, I imagine TLE.

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

What a coincidence... Getting AC after fraction of a second...

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

    You were 8ms late

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

    You should ask organizers to accept this. The only thing that matters is submission time.

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

What makes you to make it required to use bitset in problem C? Is there any trouble if n<500?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    We can calculate Dp[i][j][t] (1 ≤ i ≤ N, 1 ≤ j ≤ N·Max, 1 ≤ t ≤ C) the number of ways to have sum j using the first i elements modulo P[t] in O(N2·Max·C). We can choose P[t] (1 ≤ t ≤ C) to be a prime number ~262. Now we can find for sure the (2N - 1)th element if we choose C = 8 primes.

    I'm not sure that's the reason though...

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

      Right, we didn't want straightforward counting solutions to get accepted.

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

        And you didn't think about slow languages such as Java or C#? (I know Python is too slow for programming contests though)

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

          We did. Our Java solution using built-in java.util.BitSet gets accepted in 619 ms, which is less than 1 / 3 of TL.

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

      Can you also tell why we'll be able to surely find (2N - 1)th element using C = 8 primes? That doesn't seem very intuitive to me.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        Suppose you have that x ≡ 2N (mod Pt) for every t (1 ≤ t ≤ C) then by Chinese Reminder Theorem . Because we choose 2N to be smaller than the solution is unique in our case.

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

          Why not just use big integers to compute dp?

          → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Atcoder is another judge?

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

What could be the worst case for problem D subask.1 ? I try q=1000 with all a=b=1000, and c=1, d=100. and it runs very fast on my computer, but I get TLE on it when submitting it.

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

    It gives verdict on all cases combined.So if you attempt for partial you will get TLE. But the score reflects on standings page.

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

AtCoder Race Ranking

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

In problem E, I don't understand the explanation of the "Programmer's way" to figure out that the number of DP state is not large.

  1. Is each element of V a mask of bit or a single bit?
  2. The editorial said "Vi means that character i is logical AND of the corresponding characters in the original string". In the DP recurrence, different value of K and |A| will give different set of "corresponding characters". So what exactly is "corresponding characters" here?
  3. The editorial said "Now, call f({{1}, {2}, ..., {N}}) for N = 100". What does {1}, {2}, ..., {N} here mean?
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Suppose we are given string S as input. Then, we call f(S). Let T be any string passed as a parameter to f in a later call. It turns out that for every i, for some sets .

    Now, instead of accepting S as input, accept only its length |S| and assume the general case. Initially, for all i. For subsequent calls of f, these sets can be formed in the same way as DP is calculated.

    Thus:

    1. Every element of V is a bitmask.
    2. I'm not sure I understand this question correctly, but the "corresponding characters" are meant to be "in the original string". Just like in DP calculation, every pair of K and |A| results in a different call to f.
    3. I abuse notation of sets and bitmasks and consider them equivalent. is a set containing one element i, or, equivalently, a bitmask with a single set bit i.
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think I got it. Thanks for the clarification.

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

      Just a curious question... Did you intend that many people would come up with the "Programmer's way" and "Mathematician's way" during the contest, tourist?

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

        Of course I expected most people to come up with "Believer's way", or even just "Submitter's way" :)

        I had to prove my solution in order to set this problem, though, and I came up with "Programmer's way", but I didn't expect anyone to implement it. rng_58 came up with "Mathematician's way" while solving the problem, and I think it was possible to convince oneself using similar observations during the contest.

        → Reply