### maroonrk's blog

By maroonrk, history, 3 years ago,

Please note the unusual start time.

We will hold AtCoder Regular Contest 118.

The point values will be 300-400-500-700-800-1000.

We are looking forward to your participation!

• +179

| Write comment?
 » 3 years ago, # |   +50 Problem B. Republics don't have kings!
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 "The king has decided" should be replaced with "a bill has been introduced".
 » 3 years ago, # |   +4 Now that the contest is over.. what the hell was A????
•  » » 3 years ago, # ^ |   +11 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +9 just break that division into A+(t*A)/100
 » 3 years ago, # |   +7 Me in the contest Work on A for 50 minutes, WA Work on B for 50 minutes, WA Finish C in 10 minutes Reverse the order of numbers to process on B, got AC
•  » » 3 years ago, # ^ |   0 In problem C how to go beyond 2333 elements!
•  » » » 3 years ago, # ^ |   0 Use 14 and its multiples to generate the remaining numbers.
•  » » » » 3 years ago, # ^ |   0 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
•  » » » » » 3 years ago, # ^ |   0 You could also include numbers that are multiples of 2*3*5=30
•  » » » » » » 3 years ago, # ^ |   0 QwQ I missed these!
•  » » » » » 3 years ago, # ^ |   +1 Just print all multiples of 6,10,15
•  » » » » » 3 years ago, # ^ |   0 So if you added the multiples of $30$, you would pass. $[6, 10, 15]$ already ensures that the global GCD is $1$.
•  » » » » » 3 years ago, # ^ |   0 I think you made some error in calculation. It will give 2666 elements.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » 3 years ago, # ^ |   0 I did the same thing, https://atcoder.jp/contests/arc118/submissions/22473696 for n=2500, the max(A[i]) will be 1996
•  » » » 3 years ago, # ^ |   +17 I used multiples of $[6, 10, 15]$: $6, 10, 12, 15, 18, 20, 24, 30, \dots$The only thing to notice is that when $n=3$, we should output $[6, 10, 15]$ instead of $[6, 10, 12]$.
 » 3 years ago, # | ← Rev. 3 →   +17 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.
•  » » 3 years ago, # ^ |   +1 Can you please share — how does the formula come?
 » 3 years ago, # |   +33 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.
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 How to pass the "numerical_error" tests in B ?
•  » » 3 years ago, # ^ |   0 Take 1/MN common and Now try to minimize the max of |Bi*N — Ai*M|
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » 3 years ago, # ^ |   0 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).
•  » » » » 3 years ago, # ^ |   +3 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
•  » » » » 3 years ago, # ^ |   0 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 .
•  » » » 3 years ago, # ^ |   0 i did the same Submissiongot WA on 50/60 cases :(
•  » » » » 3 years ago, # ^ |   +1 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.
 » 3 years ago, # | ← Rev. 4 →   +19 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
 » 3 years ago, # |   +15 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. :)
 » 3 years ago, # |   +67 Am I the only one who feel C < B < A ?
•  » » 3 years ago, # ^ |   +11 No . :)
•  » » 3 years ago, # ^ |   -17 Agreed, though I would say its maybe C = B < AC 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.
•  » » » 3 years ago, # ^ |   0 C was much based on constraints and too so close. :(
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   +3 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.
•  » » » » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   +9 You can find my solution to A above, which is much simpler than the official solutions.
 » 3 years ago, # |   +10 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.
•  » » 3 years ago, # ^ |   0 N<=2666 SpoilerThe set of all numbers that are multiples of 6 , 10 , or 15 has 2666 elements and satisfies the conditions.
•  » » » 3 years ago, # ^ |   0 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?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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): Program#include using namespace std; #define MAXN 20000 vector primes = {2, 3, 5, 7, 11, 13}; int maxSeeds = 3; template ostream& operator<<(ostream& os, const vector& v) { os << "["; for (int i = 0; i < v.size(); ++i) { os << v[i]; if (i != v.size() - 1) os << ", "; } os << "]"; return os; } int best = 0; vector bestSeeds; void countSeed(vector seeds) { vector valid(MAXN + 1, false); int sum = 0; for(int s : seeds) { int step = s; while(step <= MAXN) { if(!valid[step]) { sum++; valid[step] = true; } step += s; } } //cout << seeds << ": " << sum << "\n"; if(sum > best) { best = sum; bestSeeds = seeds; } } int bitseedToNum(int bitSeed) { int prime = 1; for(int j = 0; j < primes.size(); j++) { if(bitSeed & 1) prime *= primes[j]; bitSeed = bitSeed >> 1; } return prime; } vector bitseedToNums(vector& bitSeeds) { vector seeds(maxSeeds); for(int i = 0; i < maxSeeds; i++) { seeds[i] = bitseedToNum(bitSeeds[i]); } return seeds; } void iterateSeed(vector& bitSeeds, vector& seeds, int pos) { if(pos == maxSeeds) { // check gcd(all)=1 int gcdbits = bitSeeds[0]; for(int i = 1; i < maxSeeds; i++) { gcdbits = gcdbits & bitSeeds[i]; } if(gcdbits == 0) { countSeed(seeds); } return; } for(int bitmask = 0; bitmask < (1 << primes.size()); bitmask++) { // need at least two different primes, sort primes by size if(__builtin_popcount(bitmask) < 2) continue; seeds[pos] = bitseedToNum(bitmask); if(seeds[pos] > MAXN) continue; if(pos > 0 && seeds[pos] <= seeds[pos - 1]) continue; // check gcd(bit, bit)!=1 && bit!=bit and bit%bit!=0 bool valid = true; for(int i = 0; i < pos && valid; i++) { int andBit = bitmask & bitSeeds[i]; if( andBit == 0 || andBit == bitmask || andBit == bitSeeds[i]) valid = false; } if(valid) { bitSeeds[pos] = bitmask; iterateSeed(bitSeeds, seeds, pos + 1); } } } int main() { vector bitSeeds(maxSeeds, 0); vector seeds(maxSeeds, 0); iterateSeed(bitSeeds,seeds, 0); cout << bestSeeds << " : " << best << "\n"; return 0; } The results are as following: ResultN=100003: [6, 10, 15] : 2666 4: [6, 10, 14, 105] : 2762 5: [6, 10, 14, 22, 1155] : 2926 6: [6, 10, 14, 286, 1155, 1365] : 2738  N=200003: [6, 10, 15] : 5334 4: [6, 10, 14, 105] : 5524 5: [6, 10, 14, 22, 1155] : 5854 6: [6, 10, 14, 22, 26, 15015] : 6166 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.
 » 3 years ago, # |   +14 Nobody even mentioning E-F, I see.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +11 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.
•  » » » 3 years ago, # ^ |   0 What is there to say about them? 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.
•  » » 3 years ago, # ^ |   +11 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.
•  » » » 3 years ago, # ^ |   +10 Thanks! Your idea is great and very helpful for me. It's easy to understand your DP. :)
 » 3 years ago, # |   0 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 .
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   0 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.