Hello, Codeforces!
On Saturday, Octorber 6th, 21:00 JST, AtCoder Beginner Contest 112 will be held.
The contest information is as follows:
- Duration: 100 minutes
- The number of problems: 4
- Scoring: 100 — 200 — 300 — 400
- Rated: Yes (for people whose rating is 1199 or lower)
Good luck and have fun!
Let's discuss about the problems after the contest.
UPDATE
1. The contest is over. Thank you for your participation.
2. Japanese editorial is published now. Editorial — Wait a moment for unofficial English editorial.
AtCoder doesn't officially share who the writer is, but I can tell that some of the problems in this contest, are written by E869120 and square1001!
Are you sure it doesn't share who the writer is?!
Well, I think that AtCoder is not sharing who the writer is, for "ABC Only" contests. They changed the system.
Still, AtCoder shares the writer of ARC and AGC.
C and D are nice problems.
How to solve c?
I just brute force the all possible cx and cy and figure out is there any possible H or not.
Here is my code : link
Can you please explain why to check this condition
and this
?
Actually my solution got accepted with luckily. If H > a + b hi must bigger than 0. I want to check is there any i which hi = 0 and a + b < H.I had to check is H bigger than minimum a + b or not. I don't know how my first solution got accepted :D.
Here is correct solution : link
Everyone, thank you for your participation.
Actually, problem A and C were written by E869120 and square1001. The other two problems were written by an other writer.
thanks for such interesting contest dude.
I think a diagram can be good for explanation of problem C.
How to solve D ?
Maximum divisor of M which satisfies (divisor * n) <= m.
Let assume answer is d. So all elements should divided by d so we can say. ai = bi.d
1 ≤ bi So we just need to check
Here is my code :link
Auto comment: topic has been updated by E869120 (previous revision, new revision, compare).
Writer's Editorial for All Problems (in English):
This problem was created in the idea of "making problem which has two or more patterns of input".
You should first input the integer N. If N equals 1, output "Hello World". Otherwise, you should input two more integers A and B, and output A+B. It's not so hard.
Implementation (C++) ： https://beta.atcoder.jp/contests/abc112/submissions/3340558
Implementation (Java) ： https://beta.atcoder.jp/contests/abc112/submissions/3340568
First, set minimum to infinity. Then, sequentially read input, and if you were given input like ti ≤ T, release minimum to min(minimum, ci).
The answer depends on minimum. The only case of "TLE" is that the minimum equals infinity.
Suppose that the field is A × A. In this problem, A equals 101.
You can brute-force the position. There are A2 = 10201 positions, so we are able to brute-force it.
If the position (px, py) has been determined, the height will be ht + |xt - px| + |yt - py|, if you choose t which ht ≠ 0. The time complexity is O(A2 × N).
There are some cases which all hi are zero, but such case only appears if N = A2 - 1 = 10200 (the case which H equals one, and heights for all points except center is determined), so the solution works within the constraints N ≤ 100.
Another solution also brute-forces H. You can say that H is more than or equal to max(hi), and less than or equal to max(hi) + A. Therefore, you can brute-force with time complexity O(A3 × N).
The answer will be "the maximum divisor which is less than or equal to M / N.
That's because, if there are sequence such that GCD equals x, then the sum will be one of the value of Nx, (N + 1)x, (N + 2)x, (N + 3)x, ..., which means "multiple of x which is at least Nx" (you can construct the sequence with a1 = (S - N + 1)x, ai = x(2 ≤ i ≤ N) when the sum equals Sx).
To solve problem C i was thinking of a Binary search solution where i would binary search for the height of the pyramid and for every height iterate over all the possible values of Cx and Cy and check if the height and value of Cx and Cy satisfies the conditions. but i was not able to figure out the condition wether to move to the next smaller segment or larger segment. Can someone please help who has solved this problem with binary search.
Before binary searching, are you sure this function is monotonic ?
Hey ! Did you guys write this contest ?
This must be your sixth contest then.
Why isn't AtCoder revealing the writers. They should, in my opinion.
Here are my solutions to this contest.
Here is my editorial to D :)
Actually the 7th one (if only limiting to official contest, there are also 5 square869120Contests)! Starting from ABC 064, we've also wrote ABC 076, 088, 096, 100, 105, 106, and 112 :)
ABC 105 was only problem B, and this ABC (ABC 112) was only problem A and C, though.
And the answer to "why isn't AtCoder revealing the writers of ABC-only Contests (they are revealing ARC and AGC and other sponsored contests' writers) is, I think "the system has changed from some recent ABC-only and since then many people do the writer in a single contest (in other words, only one (group of) writer created one contest)".
I remember you guys had a question called Snuke's Favourite Numbers or something like that ... I didn't understand the editorial on that one :)
When is your next contest ? :)