### chokudai's blog

By chokudai, history, 4 years ago,

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

| Write comment?
 » 4 years ago, # |   0 the time is a little bit bad, cause cf Div.2 round 613 is right after it!
 » 4 years ago, # | ← Rev. 2 →   +19 Not able to access the site. It says 502 Bad gateway.
 » 4 years ago, # |   +2 site not working in india???
 » 4 years ago, # |   +11 502 Bad Gateway
 » 4 years ago, # |   +1 EXPLOSION!
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 you can let me explosion??
 » 4 years ago, # |   +1 503 Service Temporarily Unavailable
 » 4 years ago, # |   0 503 Service Temporarily Unavailable
•  » » 4 years ago, # ^ |   0 Working now
 » 4 years ago, # | ← Rev. 2 →   +10 Atcoder Not Working....... 503 Service Temporarily Unavailable
 » 4 years ago, # |   +10 RIP AtCoder. T_T
 » 4 years ago, # |   0 Problem Resolved... Contest Starts Again
 » 4 years ago, # |   0 Is contest still rated?
•  » » 4 years ago, # ^ |   +10 The contest has been declared unrated due to some invalid inputs for problem D :(
•  » » » 4 years ago, # ^ |   0 Then how have many people got that accepted?
•  » » » » 4 years ago, # ^ |   0 May be there approach was different , which does not directly depend on parity of elements.. maybe
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 My solution passed because I wrote an if: if any number is odd, then output 0, before noticed constraint that a_i are even.
 » 4 years ago, # |   +9 After my poor perfomance in ABC 149 and 150
 » 4 years ago, # | ← Rev. 2 →   0 2 continuous ABC(149,150) became unrated !!! lets hope rated for next rated round.
•  » » 4 years ago, # ^ |   +17 And can we downvote the annoucement when an atcoder contest becomes unrated?
 » 4 years ago, # |   +1 What is the problem in inputs of question D?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 There were odd integers in the array in some of the test-cases.
 » 4 years ago, # | ← 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$.
•  » » 4 years ago, # ^ |   0 Could you explain how we get the formula for k-th highest cost? Thank you!
•  » » » 4 years ago, # ^ |   +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.
•  » » » » 4 years ago, # ^ |   0 Now I understand, thank you very much for your explanation!
•  » » 4 years ago, # ^ |   0 Thank you! This is better then the official editorial!
 » 4 years ago, # |   0 Randomised Solution for F- https://atcoder.jp/contests/abc150/submissions/9403740
•  » » 4 years ago, # ^ |   +1 Coutertest#include using namespace std; void output(const vector &f, int k, int x) { int n = f.size(); for (int i = 0; i < n; ++i) printf("%d%c", f[(i + k) % n] ^ x, i == n - 1 ? '\n' : ' '); } int main() { const int n = 2e5; printf("%d\n", n); vector f(n); for (int i = 0; i < n; ++i) f[i] = i % 2 ^ (i == 1410 || i == 1411); output(f, 0, 0); output(f, 12345, 0); } 
•  » » » 4 years ago, # ^ |   0 thanks
 » 4 years ago, # |   0 How to Solve D ?
•  » » 4 years ago, # ^ |   +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
•  » » » 4 years ago, # ^ |   0 can you solve third sample example here using your idea
•  » » » » 4 years ago, # ^ |   0 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$.
•  » » » 4 years ago, # ^ |   0 I need help, Getting WA in some test cases of Problem D.My code https://atcoder.jp/contests/abc150/submissions/9916209
 » 4 years ago, # |   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.
•  » » 4 years ago, # ^ |   +1 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
•  » » » 4 years ago, # ^ |   0 Oh I was taking the minimum costs each time. Thanks
 » 4 years ago, # |   0 Will there be editorial in English?
 » 4 years ago, # |   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 beIf 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 beLet T be the least common multiple of (a_1/2, a_2/2, ..., a_n/2).