chokudai's blog

AtCoder Beginner Contest 150 Announcement
By chokudai, history, 5 years ago, In English

We will hold AtCoder Beginner Contest 150.

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

We are looking forward to your participation!

  • Vote: I like it
  • -14
  • Vote: I do not like it

Comments Comments (40)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the time is a little bit bad, cause cf Div.2 round 613 is right after it!

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

Not able to access the site. It says 502 Bad gateway.

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

site not working in india???

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

502 Bad Gateway

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

EXPLOSION!

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

503 Service Temporarily Unavailable

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

503 Service Temporarily Unavailable

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

Atcoder Not Working....... 503 Service Temporarily Unavailable

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

RIP AtCoder. T_T

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

Problem Resolved... Contest Starts Again

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

Is contest still rated?

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

    The contest has been declared unrated due to some invalid inputs for problem D :(

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

      Then how have many people got that accepted?

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

        May be there approach was different , which does not directly depend on parity of elements.. maybe

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

          My solution passed because I wrote an if: if any number is odd, then output 0, before noticed constraint that a_i are even.

          → Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it
After my poor perfomance in ABC 149 and 150
→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

2 continuous ABC(149,150) became unrated !!! lets hope rated for next rated round.

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

    And can we downvote the annoucement when an atcoder contest becomes unrated?

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

What is the problem in inputs of question D?

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

    There were odd integers in the array in some of the test-cases.

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

Quick commentary:

  • A: Implementation.
  • B: Implementation.
  • C: $$$N \leq 8$$$ means we can generate a list of all permutations and sort them to learn their ranks, then look up $$$P$$$ and $$$Q$$$. Alternatively, we can take a permutation and count its successors (C++ builtin next_permutation) to figure out its rank.
  • D: We seek $$$X \equiv \frac{1}{2} \textrm{ (mod } a_i)$$$ for all $$$i$$$, which uniquely determines $$$X$$$ modulo $$$\textrm{LCM}(a)$$$. If such an $$$X$$$ exists, it must be congruent to $$$\frac{1}{2}$$$ modulo $$$\textrm{LCM}(a)$$$. The LCM is even, so we simply want $$$\frac{\textrm{LCM}(a)}{2}$$$. We can compute and test it, being careful to avoid overflow by exiting early if the LCM exceeds $$$2M$$$ in any intermediate computation.
  • E: Assume for simplicity that costs are distinct. To minimize $$$f$$$ we should modify elements in increasing order of cost. Among positions which differ between $$$S$$$ and $$$T$$$, the number of times a cost is paid is equal to the number of costs greater than it plus 1. The total number of times the $$$k^{\textrm{th}}$$$ highest cost (where $$$k$$$ is 0-indexed) is paid across all $$$(S, T)$$$ is equal to $$$2 \cdot 4^{N - k - 1} \cdot 2^k \sum_{x \leq k} (x+1)\binom{k}{x}$$$. It can be computed in constant time by using the combinatorial identity $$$\sum_{x} x\binom{k}{x} = k \cdot 2^{k-1}$$$.
  • F: The value of $$$k$$$ uniquely determines $$$x = a[k] \oplus b[0]$$$. We can determine which $$$k$$$ work for each bit independently and take the intersection to get the final answer. In the 1-bit version, we want to know which rotations of $$$a$$$ are equal to either $$$b$$$ or $$$!b$$$ (corresponding to $$$x = 0$$$ and $$$x = 1$$$). We can do it by doubling $$$a$$$ and applying a string-searching algorithm (e.g. KMP) to find all occurrences of $$$b$$$ and $$$!b$$$.
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain how we get the formula for k-th highest cost? Thank you!

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

      The $$$k^\textrm{th}$$$ highest cost has $$$k$$$ costs greater than it. If we pay it, $$$S$$$ and $$$T$$$ must differ at its position, so there are $$$2$$$ possible configurations for it ($$$01$$$ or $$$10$$$). For each of the $$$N - k - 1$$$ positions with lower cost, there are $$$4$$$ possible configurations. Suppose $$$x$$$ of the $$$k$$$ positions with higher cost differ; we can select them in $$$\binom{k}{x}$$$ ways and we'll pay the cost $$$x+1$$$ times. Finally, there are $$$2$$$ possible configurations for each of the positions with higher cost since for each of them we already fixed whether it differs or not.

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

        Now I understand, thank you very much for your explanation!

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

    Thank you! This is better then the official editorial!

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

Randomised Solution for F- https://atcoder.jp/contests/abc150/submissions/9403740

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

How to Solve D ?

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

    Lemma: if $$$x$$$ is a semi-common multiple of $$$A$$$, then $$$\frac{2x}{a_{i}}$$$ is odd for all $$$a_{i}$$$ in $$$A$$$.

    Proof: since $$$x$$$ is a semi-common multiple of $$$A$$$, then $$$x = a_{i} \times (p+0.5) \Rightarrow 2x = a_{i} \times (2p+1)$$$ for some integer $$$p$$$. Hence $$$\frac{x}{a_{i}} = 2p+1$$$ which is odd.

    This implies that $$$2x$$$ and $$$a_{i}$$$ have the same number of twos in their prime representation and $$$lcm(a_{1}, \dots , a_{n}) \ |\ 2x$$$ moreover that $$$2x/lcm$$$ is odd.

    So assert that all the numbers have the same number of twos in their prime factorization (if not, then there is no such $$$x$$$), find the $$$lcm$$$ of all the given numbers, then find all the numbers $$$x$$$ less than or equal to $$$m$$$ which satisfy that $$$2x/lcm$$$ is odd.

    You can view my submission. Its a little messy though

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

In problem E sample test case 2 how is the output 124. According to my understanding, there will 8 pairs with exactly 1 difference and 4 pairs with 2 differences

So the output should be 8 * 5 + 4 * 18 = 112.

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

    Out of those 8 differing on 1 position four differ on position 1 and can be solved with cost 5, and four differ on position 2, so can be solved with cost 8

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

      Oh I was taking the minimum costs each time. Thanks

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

Will there be editorial in English?

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

I was reading the English editorial of problem D, and I noticed some mistakes there:

1) If there exist i, j such that the number of times a_i is divided by 2 and the number of times a_j is divided by 2, then ...

should be

If there exist i, j such that the number of times a_i is divided by 2 and the number of times a_j is divided by 2 is not equal, then ...

2) Let T be the least common multiple of T.

should be

Let T be the least common multiple of (a_1/2, a_2/2, ..., a_n/2).

→ Reply