We will hold AtCoder Beginner Contest 150.

- Contest URL: https://atcoder.jp/contests/abc150
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200110T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: camypaper, DEGwer, kyopro_friends, gazelle, satashun, EnumerativeCombinatorics, yuma000
- Rated range: ~ 1999

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

We are looking forward to your participation!

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

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

site not working in india???

502 Bad Gateway

EXPLOSION!

you can let me explosion??

503 Service Temporarily Unavailable503 Service Temporarily Unavailable

Working now

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

RIP AtCoder. T_T

Problem Resolved... Contest Starts Again

Is contest still rated?

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

Then how have many people got that accepted?

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

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

After my poor perfomance in ABC 149 and 1502 continuous ABC(149,150) became unrated !!! lets hope rated for next rated round.

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

What is the problem in inputs of question D?

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

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$$$.Could you explain how we get the formula for k-th highest cost? Thank you!

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.

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

Thank you! This is better then the official editorial!

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

Coutertestthanks

How to Solve D ?

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

can you solve third sample example here using your idea

Sure. You can see that $$$6 = 2^{1} \times 3$$$ so there exist at least one solution. We have $$$lcm(6,\ 2) = 6$$$. The numbers $$$x$$$ between $$$1$$$ and $$$10^{9}$$$ satisfying that $$$2x/lcm$$$ is odd $$$= ceil(10^{9}/lcm) = 166666667$$$.

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.

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

Oh I was taking the minimum costs each time. Thanks

Will there be editorial in English?

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