Please note the unusual start time.
We will hold AtCoder Regular Contest 118.
- Contest URL: https://atcoder.jp/contests/arc118
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210509T2205&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: maspy
- Tester: tempura0224, yamunaku
- Rated range: — 2799
The point values will be 300-400-500-700-800-1000.
We are looking forward to your participation!
Problem B. Republics don't have kings!
"The king has decided" should be replaced with "a bill has been introduced".
Now that the contest is over.. what the hell was A????
The tax included prices are strictly increasing, so if the tax included price of integer $$$A$$$ is $$$X$$$, there are $$$X - A$$$ skipped integers before $$$X$$$. Now you can use this to find some closed formula, or just binary search.
just break that division into A+(t*A)/100
Me in the contest
In problem C how to go beyond 2333 elements!
Use 14 and its multiples to generate the remaining numbers.
Sorry my solution was to split into 3 groups.. multiples of 6, 15 and 10. The first group will not have 5 as factor, second group will not have factor as 2 and third group will not have a factor as 3. This only gave 2333 elements
You could also include numbers that are multiples of
2*3*5=30
QwQ I missed these!
Just print all multiples of 6,10,15
So if you added the multiples of $$$30$$$, you would pass. $$$[6, 10, 15]$$$ already ensures that the global GCD is $$$1$$$.
I think you made some error in calculation. It will give 2666 elements.
This would generate till 2666, you dont need to avoid multiplles of 5 for 6 and so on. print all multiples and it would still be correct
I did the same thing, https://atcoder.jp/contests/arc118/submissions/22473696 for n=2500, the max(A[i]) will be 1996
I used multiples of $$$[6, 10, 15]$$$:
The only thing to notice is that when $$$n=3$$$, we should output $$$[6, 10, 15]$$$ instead of $$$[6, 10, 12]$$$.
For A, the answer is simply $$$n + \left\lfloor\dfrac{100 * n - 1}{t}\right\rfloor$$$.
The original formula is $$$n + \left\lceil\dfrac{100 * n}{t}\right\rceil - 1$$$.
$$$n + \left\lceil\dfrac{100 * n}{t}\right\rceil$$$ is the $$$n$$$-th number which has a gap between it and the previous number. So $$$n + \left\lceil\dfrac{100 * n}{t}\right\rceil - 1$$$ is the $$$n$$$-th missing number.
Can you please share — how does the formula come?
Hamiltonian cycle is hard to come up with in D, rest of the proof can be done using a primitive root of the given prime.
How to make it seem natural? I mean I can see what editorial wants to say but I doubt if I can come up with something like that in 2 hours.
How to pass the "numerical_error" tests in B ?
Take 1/MN common and Now try to minimize the max of |Bi*N — Ai*M|
You can have a look on my solution , it has no scope for numerical error . The basic idea is that either the value of Bi will be ceil of((Ai*m)/n) or floor of((Ai*m)/n Link to the solution https://atcoder.jp/contests/arc118/submissions/22475125
How to prove Bi will be ceil of((Ai*m)/n) or floor of((Ai*m)/n,I just know it is greater or equal to ceil of((Ai*m)/n).
Because if you take exactly (Ai*m)/n in decimal for all numbers, the sum would be m and all differences would be 0. Since you can't take decimal it would be optimal to either take the floor or ceil
We can consider Ai as Ai blocks of size 1 which in total are N , same we can consider Bi as Bi blocks of size 1 which in total are M , So if Ai is x , The value of Bi should be corresponding to x to minimise (Ai*m)/n .So either it will be floor or ceil as we have to make other Ai's and Bi's in the same ratio close to each other as well. This is how I thought it , If you are looking for formal proof then I just dont have it .
i did the same Submission
got WA on 50/60 cases :(
According to my understanding of your code , you are only trying to reduce the difference for first x no. and leaving the last few no.s on their own . You should consider that I had made a vector of pair to minimise it.
Thanks for the nice contest. Problem C involved much minor detail. I solved by making 4 sets. Let p1 = 2, p2 = 3, p3 = 5. Then,3 sets that include 2 of them but not third and lastly a fourth set which has all 3 of them. I saw that 167 numbers were left after I included first 3 sets, then I included the 4th one which gave extra 10000/30 numbers, exactly what I wanted.
For Problem B, I saw that the question is effectively to reduce abs(Bi*n — Ai*m). Given that sum of Bis = M. So, I first took Bi*n as Ai*m — (Ai*m)%n = Ci — Di, so, I have to distribute sum of Di to Ci — Di such that each value I give is a multiple of n(and that should be just n otherwise we would increase the maximum of abs(Bi*n — Ai*m)). Also, sum of Di is a multiple of n. So, just found out t = sum of Di / n and then go on giving n to first n maximum Di. Finally, obtain the Bi by dividing each found term by n.
For problem A, I observed that the number is the first number m, where t*m >= 100*n, then ans is m + n -1.
A
B
C
Just a suggestion or request , please make A a little bit easier from next time in ARC's because if A is like todays A it decreases Number of Participants Significantly. :)
Am I the only one who feel C < B < A ?
No . :)
Agreed, though I would say its maybe C = B < A
C was a fairly easy constructive problem once you realize how to do better than the naive answer of using all combinations of 12 primes.
B is pretty clearly binary search from the statement, and the checker function is fairly simple as well.
A for me was basically, print sequence for various t, print differences between terms, guess that the differences have period t and sum them up like that. I still have zero clue why it works.
C was much based on constraints and too so close. :(
I mean the limit on a_i is what makes the problem interesting in the first place. If it was $$$a_i \leq 10^{18}$$$, the the naive idea using all combinations of the 12 smallest primes for $$$n - 1$$$ places would work.
Also looking at your code I think you overcomplicated the implementation a bit, the main logic of my solution was less than 10 lines.
My idea was to make $$$a_1 = 3 \times 5 \times 7$$$, then take all numbers which divide at least one of $$$6$$$, $$$10$$$, or $$$14$$$ in increasing order. Clearly $$$gcd(a_1, a_i)$$$ is now greater than 1 as it can be divided by at least one of $$$3$$$, $$$5$$$, or $$$7$$$, and $$$gcd(a_i, a_j)$$$ for $$$i, j \gt 1$$$ has $$$2$$$ in common. Note that we go in increasing order, so our first $$$3$$$ numbers will be $$$3 \times 5 \times 7$$$, $$$2 \times 3$$$ and $$$2 \times 5$$$, so the total gcd is already guaranteed to be $$$1$$$. This generates a sequence of length around $$$2600$$$ for which any prefix satisfies the condition.
yes, I overcomplicated it as I was trying some solution and then adding some more to fulfill the constraints. But your thinking was much simpler and easier to implement. Thanks.
You can find my solution to A above, which is much simpler than the official solutions.
For C, what would be the max possible N that still satisfy the conditions of the problem? I know it can definitely go above 2500.
N<=2666
The set of all numbers that are multiples of 6 , 10 , or 15 has 2666 elements and satisfies the conditions.
Well, the editorial proposes multiples of $$$6$$$, $$$10$$$, $$$14$$$, $$$22$$$ and $$$1155$$$ ($$$2\cdot 3$$$, $$$2\cdot 5$$$, $$$2\cdot 7$$$, $$$2\cdot 11$$$ and $$$3\cdot 5\cdot 7 \cdot 11$$$) and does achieve $$$2926$$$ possible numbers this way. So this disproves $$$2666$$$ as upper limit. But can we go still further?
So, with my acute lack of mathematical proof I decided to write a program, which tries seeds with the given tasks conditions ($$$gcd(all)=1$$$, $$$gcd(pair)\neq 1$$$) and then counts how many possible numbers this seed can create (according to the same procedure as in the editorial):
The results are as following:
So it seems, that $$$2926$$$ is the maximum achievable number!
This obviously still misses the formal proof, that such an approach yields the optimal answer. But I personally feel confident about this, after analysing the problem. Also the resulting seeds have a really specific symmetry (all but one are made by multiplying $$$2$$$ with the smallest prime numbers, and the last one is made by multiplying all the used primenumbers except the $$$2$$$), which makes it very plausibel.
Nobody even mentioning E-F, I see.
What is there to say about them? They both look like exercises for those in the know: the idea behind GCJ 2008 Round 3 — Endless Knight is used as a trivial observation in E; and the editorial for F has a link to an ARC 033 problem back from when the rounds were in Japanese only. The point values are irrelevant as usual, the motivation behind spending such problems on regular rounds (esp. two problems on one round) is over my head as usual.
The rest of your comment serves to answer that question.
I found nice the idea in E that if we sum up inclusion-exclusion formulas over all ways to replace $$$-1$$$, it helps ensure that we're summing up over permutations since inclusion-exclusion over RD paths ignores non-monotonous subsets of forbidden cells. Not super revolutionary though.
Problem E can also be solved without PIE, but by a simple DP in which the state is the current position of the path and how many blocks we have fixed left/above of this position (seperate values for blocks above, left and above+left) See my solution for details.
Thanks! Your idea is great and very helpful for me. It's easy to understand your DP. :)
I have always found the questions of atcoder to be good, but sadly you cannot solve atcoder questions by selecting topic tags or by selecting the difficulty level. Does anyone know of any atcoder problem recommending site? Thanks in advance .
https://kenkoooo.com/atcoder/
How about D? I can understand the correctness of the official edtutorial. But what's the idea to make us jump the gap from G(a,b) to G(a,b)=m*n=P-1? Is there a prior knowledge for that? Any idea will be appreciated.