### maroonrk's blog

By maroonrk, history, 6 weeks ago,

We will hold AtCoder Regular Contest 126. Please note the unusual start time (1 hour later than usual)

The point values will be 300-400-600-600-800-1100.

We are looking forward to your participation!

• +88

 » 6 weeks ago, # |   +11 The start time of ARC is the same as the end time of Opencup. Can it be delayed by 15 mins or so.
•  » » 6 weeks ago, # ^ |   +67 I tried to avoid the clash with Opencups but I didn't want ARCs to be too late in Japan, so that's the reason for the tight schedule. Though I can't change the contest time now, perhaps I'll have a margin of 5 mins next time, if not 15mins.
 » 5 weeks ago, # |   +16 LimitCoder
 » 5 weeks ago, # |   +11 Problem C is the same as this, but with harder limits.
 » 5 weeks ago, # | ← Rev. 3 →   -52 Nice problems in this contest.I didn't solve any problems during the contest, but I solved C using Binary Search just a minute after the contest ended.My submission is here.Here's my stream that was private/unlisted during the contest.
 » 5 weeks ago, # |   -68 This is really irritating. I think that problem A was a generic ILP problem, but normally there are big math applications or libraries, which take care of it without any need to bother about what is happening under the hood. During the whole contest time I tried to find any usable code snippet or small library suitable for competitive programming environment, but failed.Here's my broken submission, which tried to use using Simplex Algorithm.cpp code from YouKn0wWho's (The Ultimate) Code Library. But it's LP and I couldn't figure out how to modify it to get an integer solution. Or made some other embarrassing mistake. Was I on a wrong track all along?
•  » » 5 weeks ago, # ^ |   +11 This is Atcoder and problem A so the solution would most likely be greedy.
•  » » » 5 weeks ago, # ^ |   0 this is my A solution just tried to use the larger sticks first code link
•  » » » 5 weeks ago, # ^ |   -24 This is Atcoder and problem A so the solution would most likely be greedy. Many problems can be solved in different ways. And I don't see what's wrong with overkilling a simple problem with a more advanced algorithm. Considering the total absence of any useful responses and all the downvotes, my conclusion is that there's no appreciation for Linear Programming in the competitive programming community. And this is a bit sad, because LP is reasonably useful in the real world.LP is effective at solving problems of this kind even if the number of variables and constraints is large. It also does the job when greedy algorithms fail. This is similar to how the classic "minimum coin change" problem can be sometimes solved by a greedy algorithm, but sometimes something more advanced (such as DP) is required.May I ask you something? How would you approach the same problem A — Make 10 if it was required to create sticks whose lengths were exactly 13 instead of 10? Also if a provable exact solution was too difficult, then being off by up to something like +-5 was also acceptable (we are dealing with up to $10^{15}$ sticks and a super accurate precision is rarely needed at this scale).
•  » » 5 weeks ago, # ^ |   0 May you provide which line contains your objective function? (or something related to that)
•  » » » 5 weeks ago, # ^ |   0 The objective function is configured by these two lines in my code: Spoiler long double obj[] = { 1.0, 1.0, 1.0, 1.0, 1.0 }; lp::init(5, obj, MAXIMIZE); The used Simplex Algorithm code template contains the following comment: Maximize or minimize f0*x0 + f1*x1 + f2*x2 + ... + fn-1*xn-1 subject to some constraints. In this particular case, the objective function is just $f(x) = x_0 + x_1 + x_2 + x_3 + x_4$ and all the $f_i$ constants are equal to 1. The variables are: $x_0$ is the number of 2+2+2+4 sticks $x_1$ is the number of 3+3+4 sticks $x_2$ is the number of 2+2+2+2+2 sticks $x_3$ is the number of 2+2+3+3 sticks $x_4$ is the number of 2+4+4 sticks GNU MathProg model can be used to test or prototype the solution and various online sites can process it: Spoiler param n2 := 1125; param n3 := 1231; param n4 := 1159; var x0 >= 0, integer; var x1 >= 0, integer; var x2 >= 0, integer; var x3 >= 0, integer; var x4 >= 0, integer; maximize obj: 1*x0 + 1*x1 + 1*x2 + 1*x3 + 1*x4; subject to constraint1: 3*x0 + 0*x1 + 5*x2 + 2*x3 + 1*x4 <= n2; subject to constraint2: 0*x0 + 2*x1 + 0*x2 + 2*x3 + 0*x4 <= n3; subject to constraint3: 1*x0 + 1*x1 + 0*x2 + 0*x3 + 2*x4 <= n4; solve; display x0; display x1; display x2; display x3; display x4; display obj; end; I have pushed a corrected summission to AtCoder and now it got an AC verdict. I have also added a lot of comments there, hopefully explaining everything. But feel free to ask more questions if anything is not clear.
 » 5 weeks ago, # |   0 Prob B couldn't be solved by using binary search LIS?
•  » » 5 weeks ago, # ^ |   0 here is my solution of Prob B, it is different like my old binary search before $O(n\log n)$. In code,my thoughts are finding the non-decreasing subsequence,but in fact I am looking for strictly ascending subsequence. and then is pass.This maybe help you
•  » » » 5 weeks ago, # ^ |   0 I aleady found how to solve using binary search. But thank you for your reply :)
 » 5 weeks ago, # |   +99 Can I already say that rainboy will win next IOI?
•  » » 5 weeks ago, # ^ |   0 I am wondering what would be his real rating if he do all the problems that he can in each contest!
 » 5 weeks ago, # |   0 Got a solution like $O(N2^KKlog2(K))$ for D but too bad I couldn't squeeze it into the limit :(
 » 5 weeks ago, # |   -8 Task A can also be solved using brute force
•  » » 5 weeks ago, # ^ |   0 Nice idea.
•  » » 5 weeks ago, # ^ |   0 Can't A be solved in $\mathcal O(1)$?
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   +33 Yes, but i was not sure of some particular way better than the other. So i just brute forced over different possible configurations. I observed that there are only 5 possible ways to get 10 from given set of sticks . So i created a vector containing these ways , and permuted over different possible orders where each order corresponds to priority of getting 10 using a particular way from left to right. So it takes 5.5! operations for each caseHere is my submission : https://atcoder.jp/contests/arc126/submissions/26014537
•  » » » » 5 weeks ago, # ^ |   +11 That's pretty cool. I had a hard time deciding which of (4, 4, 2) and (3, 3, 2, 2) should be picked first and it eventually costed me more time than B or C did.
•  » » » » 5 weeks ago, # ^ |   0 Can you please explain more how your solution works
 » 5 weeks ago, # |   -8 B was really nice. My solution is a bit different to the editorial. SolutionThe main idea is the find the LIS, but with a tweak.Let's rearrange the input like this: 1: 1 2: 1 2 3: 2 3 4: 5 6 5: 6: Now we just want to find the LIS, but we can only choose one number per row.There are several LIS algorithms, but one that works here and is relatively simple uses binary search. Let top[i] be the smallest number that can end a longest common subsequence of length i so far. For each row, we can try adding each number, and then update top after everything has been checked (so that we don't take 5 and 6 from the fourth row for example).Note that in my implementation, I sort each row to make sure to not update a 6 to a 5, for example. Another way would be to set top to $\infty$, and then simply check before updating, but this is what came to mind during the contest after a WA. Code#include using namespace std; #define all(v) v.begin(), v.end() constexpr int maxn = 200005; vector adj[maxn]; int top[maxn], upd[maxn]; int main() { int n, m; cin >> n >> m; for (int a, b, i = 0; i < m; ++i) { cin >> a >> b, --a, --b; adj[a].push_back(b); } int L = 0; top[0] = -1; for (int i = 0; i < n; ++i) { int k = 0; sort(all(adj[i])); reverse(all(adj[i])); for (const int x: adj[i]) { int l = 1, h = L+1; while (l < h) { int m = l+(h-l)/2; if (top[m] < x) l = m+1; else h = m; } upd[k++] = l; } for (int j = 0; j < k; ++j) { top[upd[j]] = adj[i][j]; L = max(L, upd[j]); } } cout << L << '\n'; } Submission
•  » » 5 weeks ago, # ^ |   +6 It was also pretty classic.
 » 5 weeks ago, # | ← Rev. 2 →   0 ...
 » 5 weeks ago, # | ← Rev. 2 →   +25 I don't see any change in my rating for this contest. When will be the rating change available?
 » 5 weeks ago, # |   +3 please explain anyone, problem D — Pure Straight
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +16 I can explain a different solution that works in $O(2^KNK)$. Let us call the sequence $1,2,\cdots, K$ a "good sequence". If I choose $K$ different numbers at indices $x_1 < x_2 < \cdots < x_K$, I want to create a good sequence starting at $i$. Then, the optimal way of doing this can be thought of as performing two steps: "Compressing" the indices $x_1, x_2, \cdots, x_K$ into the indices $i,i+1,\cdots, i+K-1$ by the means of adjacent swaps, while preserving the order. So if I start with $2,*,*,1,*$ and I want to make the good sequence start at $i=2$, I would make the sequence $*,2,1,*,*$. The cost of doing this is clearly $\sum_{k=1}^K |x_k - (i+k-1)|$. Once I do this, I need to sort the sequence. The minimum number of adjacent swaps to do this is the inversion count, i.e. $inv(a_{x_1},a_{x_2}, \cdots, a_{x_k})$. This gives us the same cost from the editorial. My goal is to find the minimum cost of having a good sequence starting at any $i \in [1,n]$. To do this, I want to use DP, but the roadblock here is that I'd need to consider numbers coming from both the left and the right of $i$. Instead, I'll split this into two parts — the prefix and the suffix. Let $dp_{pr}[i][S]$ be the cost of getting a contiguous sorted sequence of numbers in $S$, such that all the numbers are from indices $\leq i$, ending at $i$. Similiarly, let $dp_{su}[i][S]$ be the cost of getting a contiguous sorted sequence of numbers in the set $S$, such that all the numbers are from indices $\geq i$, starting at $i$. Then, we can get the cost of a good sequence starting at $i-|S|$ from the formula: $f(i,S) = dp_{pr}[i][S] + dp_{su}[i+1][[k] \setminus S] + inv(S,[k] \setminus S)$where $[k]$ is the set of the first $k$ natural numbers. $dp_{pr}[i][S]$ will cover the cost of "compressing" the prefix as well the inversion count within the prefix, $dp_{su}[i][[k] \setminus S]$ will cover the cost of doing this for the suffix, and $inv(S,[k] \setminus S)$ will cover the inversion count across the prefix and suffix. Hence, the minimal cost would be the minimum of $f(i,S)$ over all $i$ and $S \subseteq [k]$.We can find the DPs in $O(2^KNK)$ and $inv$ in $O(1)$ after $O(K2^K)$ precalculation. The transitions are fairly trivial, you can see them in my submission.
•  » » » 5 weeks ago, # ^ |   0 Actually,we can solve it in $\mathcal{O}(2^KN)$ , my submission.
•  » » » » 5 weeks ago, # ^ |   0 Can you explain a little bit about your code, pls?
 » 5 weeks ago, # |   +8 F is very interesting. Thanks for the contest
 » 5 weeks ago, # | ← Rev. 4 →   0 Is $O(Max(a)log^2(Max(a)))$ intended to give TLE. Or Am I doing something strange in C? Spoiler#include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long k; cin >> n >> k; vector a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } long long sum = 0; int mx = *max_element(a.begin(), a.end()); for (int i = 0; i < n; i++) { sum += mx — a[i]; } long long ans = 1; if (sum < k) { ans = mx + (k — sum) / n; } else { // the case in which the gcd is between 1 and mx sort(a.begin(), a.end()); for (int i = 2; i < mx; i++) { long long current = (long long)i * n — accumulate(a.begin(), a.end(), 0LL); for (int j = 1; i * j < i + mx; j++) { auto up = upper_bound(a.begin(), a.end(), i * j); auto down = upper_bound(a.begin(), a.end(), i * (j + 1)); if (down != a.begin()) { down--; current += (down — up + 1) * j * i; } } if (current <= k) { ans = i; } } } cout << ans; return 0; } I am using the fact that $j mod i = j - (j // i) * i$
 » 5 weeks ago, # |   0 In Problem B , why Do we sort like this ?  sort(segs.begin(), segs.end(), [&](auto x, auto y) { return x.first < y.first || (x.first == y.first && x.second < y.second); }); 
•  » » 5 weeks ago, # ^ |   0 If the first element of two pairs are equal, we can choose at most one of them. So we have to sort them somehow that doesnt conflict with the LIS part. Now the best way is to let the one with larger second element, come first
 » 4 weeks ago, # |   0 Problem B is similar to https://leetcode.com/problems/russian-doll-envelopes/ (with larger constraints)
 » 2 weeks ago, # | ← Rev. 3 →   0 Here is my solution to problem C, which is $O(N\sqrt {A_i})$.Let $g(m)=\sum\limits_{i=1}^N \lceil \frac{A_i}{m} \rceil$We wish to find the largest $m$ such that $mg(m) \le K+\sum\limits_{i=1}^N A_i$We know for all $m>\max A_i, g(m)=N$The idea is that we can compute $g(m-1)-g(m)$ for all $m\ge \sqrt{\max A_i}$ in $O(N \sqrt{A_i})$ time and $O(N)$ space. Note $\lceil \frac{A_i}{m} \rceil - \lceil \frac{A_i}{m+1} \rceil$ is either 0 or 1To find $m$ st $\lceil \frac{A_i}{m} \rceil = t, \lceil \frac{A_i}{m+1} \rceil = t-1$ in O(1) is left as an exercise to the reader.We can find all $m$ such that above holds in $O(\sqrt{A_i})$. Doing this $N$ times, we check $O(N\sqrt{A_i})$. We store results using a sparse/occurrence array. This actually stores $g(m)-g(m+1)$ for all $m>\sqrt{A_i}$ so we can compute $g(m)$ for $m<\sqrt{A_i}$ and $m>\sqrt{A_i}$ in $O(\sqrt{A_i}N)$, which works. My implementation