Блог пользователя chokudai

Автор chokudai, история, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • -14
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

site not working in india???

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

502 Bad Gateway

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

EXPLOSION!

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

503 Service Temporarily Unavailable

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

503 Service Temporarily Unavailable

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

RIP AtCoder. T_T

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem Resolved... Contest Starts Again

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is contest still rated?

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
After my poor perfomance in ABC 149 and 150
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What is the problem in inputs of question D?

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

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$$$.
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you! This is better then the official editorial!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Coutertest
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to Solve D ?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will there be editorial in English?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).