### maroonrk's blog

By maroonrk, history, 6 weeks 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! Comments (53)
 » 6 weeks ago, # | ← Rev. 4 →   .
 » Problem B. Republics don't have kings!
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   "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.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   just break that division into A+(t*A)/100
 » 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
•  » » 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.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   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]$: $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]$.
 » 6 weeks ago, # | ← Rev. 3 →   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|
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   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 Submissiongot 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.
 » 6 weeks ago, # | ← Rev. 4 →   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
 » NumPy should be blocked for python users man. It makes code soo simple.
 » 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 < 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.
•  » » » C was much based on constraints and too so close. :(
•  » » » » 6 weeks ago, # ^ | ← Rev. 4 →   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.
 » 6 weeks ago, # | ← Rev. 2 →   In the editorial of B, there was written a term called — " Decision Problem " . Can anyone explain what is the meaning of Decision Problem ? And please share some problems / tutorials based on Decision Problem tag. SpoilerI have searched my query in Google but didn't get any satisfactory answer. Btw, I love the solution based on Binary Search on B.
 » 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 SpoilerThe 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?
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   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; 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.
 » Nobody even mentioning E-F, I see.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   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.
•  » » » 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.
•  » » 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 .
•  » »
 » 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.