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 Unavailable
503 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.
2 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:
next_permutation
) to figure out its rank.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
thanks
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$$$.
I need help, Getting WA in some test cases of Problem D.My code https://atcoder.jp/contests/abc150/submissions/9916209
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).