### maroonrk's blog

By maroonrk, history, 2 weeks ago,

We will hold AtCoder Regular Contest 165.

The point values will be 400-600-600-700-700-800.

We are looking forward to your participation!

• +119

 » 13 days ago, # |   0 tough contest
 » 13 days ago, # |   -10 C is tough!
 » 13 days ago, # |   -10 Cool contest, especially $B$ & $C$. Maybe there is easier solution, i solved $B$ using segtree(it is straightforward to find such index $f$, that after an operation on $v[f : f + k - 1]$, $v$ is maximal. We can compare results of operations $v[x: x + k - 1]$, $v[y : y + k - 1]$ in $O(\log n)$.) $C$ is pretty cool too. Thanks!
•  » » 13 days ago, # ^ |   0 How you solved C?
•  » » » 13 days ago, # ^ |   0 Binary search on asnwer. THe same as editorial.
•  » » » 13 days ago, # ^ |   +26 There is a solution way easier than the editorial. Make a MST, and Color the vertices by the odd or even of its depth on the MST.
•  » » 13 days ago, # ^ |   0 Share code, please.
•  » » » 13 days ago, # ^ |   0 My codeI did similar thing
•  » » » 13 days ago, # ^ |   0
•  » » 13 days ago, # ^ |   +3 I solve B greedy: As it is sure that after sorting the array will become lexicographically <= of the original array. First I calculate the longest increasing subarray. Case 1If this is longer than k then there is no need to do sorting as we can perform this operation on this subarray which is ready sorted. Case 2In this case, it is optimal to sort the last k element. But we have to consider the case as for ex: "6 4 [3 4 6 5 1 2]" If we sort the last k elements — [3 4 1 2 5 6] which is not optimal. If we sift the k size window from the last k element to at max k-1 before such that the elements before that are all already sorted and lesser than the last remaining k size window elements. Here last k elements are [6,5,1,2] are remaining [3,4] which are already sorted so, we move the window to [3,4,6,5] which only affects the last two elements in sorting.May be I am wrong but give me AC. submissions/45685014
 » 13 days ago, # |   +25 I passed D in the last 2sec!!!!!my submission
 » 13 days ago, # | ← Rev. 3 →   0 how to solve Aedit : solved
•  » » 13 days ago, # ^ |   0 to make the elements a1, a2, ...., ak to have N as their LCM these should be the prime factors of the number N.To make the sum equal to N, you need to check if the number of prime factors are atleast 3 because one of the prime factors would always be 1, and lcm(1, x) = x, which won't let the lcm to be equal to N. for example consider the case N = 10, we find out the prime factors of 10 as 1, 2 and 5. We can add these as 5+2+1+1+1 == 10 and LCM(1,1,1,2,5)==10Again consider the case N=8, prime factors of 8 = 1, 2 even though we can make the sum of prime factors equal to 8, we won't be able to make the LCM equal to 8 because LCM of 1 and 2 comes out to be 2. // implement the isPrime function here... void solve() { long n; cin>>n; vector factors; factors.push_back(1); for(long i=2;i<=sqrt(n);i++) { if (n%i==0) { if (isPrime(i)) factors.push_back(i); if (n/i!=i && isPrime(n/i)) { factors.push_back(n/i); } } } if (factors.size()>2) cout<<"Yes"<
 » 13 days ago, # | ← Rev. 2 →   0 is this code O(n^2)? https://atcoder.jp/contests/arc165/submissions/45684077 or did i make a error somewhere. (I asserted some places, so i do think its O(n^2)) (The Solution is to find scc, condense them, refind scc. i pass a graph of size atmost m atmost n times and my m pointers also move atmost n times, so i believe its n^2)
•  » » 13 days ago, # ^ |   +10 Since you don't clear the graph fully I believe that it can have $O(nm)$ edges, so it will work in $O(n^2 m)$?
•  » » » 13 days ago, # ^ | ← Rev. 3 →   +11 Towards the end of my solve function, you can check just before i call scc() i assert the graph has <= m edges
•  » » » » 13 days ago, # ^ |   +8 Oh, I didn't notice that you don't add a new edge if the pointer didn't move.Well, asserts seem to confirm that it is $O(n(n+m))$. The general structure of the solution is correct.Probably vector> is not a great idea. I generated a test: 223740510.
•  » » » » » 13 days ago, # ^ |   0 unfortunate (and surprising since my friends have as low as 200ms) but thanks anyways
 » 13 days ago, # |   +46 B test cases too weakPassed with checking for the last 100 indexes and indices of elements 1...200 and taking the best of themhttps://atcoder.jp/contests/arc165/submissions/45673283
•  » » 13 days ago, # ^ |   0 The tests are not weak, maybe author don't even expect such fake solution:)
 » 13 days ago, # | ← Rev. 2 →   +49 First time in Top 10!Also, problem F is really similar to IOI19 arranging shoes. F just added "lexiographically smallest" to IOI19 shoes, but it made the implementation way harder.
 » 13 days ago, # |   +25 Are tests for B too weak? Looking at first python AC solution: https://atcoder.jp/contests/arc165/submissions/45672082It seems like it should fail for something like: 4 3 3 4 1 2 It outputs 1 3 4 2. I think it should be 3 1 2 4
•  » » 13 days ago, # ^ |   0 Yeah, there seem to be a lot of solutions that should wa on similar testcases, but got ac in the contest.Another such example (if I'm not mistaken): https://atcoder.jp/contests/arc165/submissions/45680434
•  » » 13 days ago, # ^ |   +1 My Solution outputs 1 3 4 2,too.But it gets AC,too :)
 » 13 days ago, # |   +10 I have little difference with editorial in solution to $C$. I calculate the maximum $x$, such that if we remove edges with $w \ge x$, graph is bipartite. I use binary search for it. Let it be $A$. But then I don't calcalute minimum weight of path with length $2$ for remaining edges. Instead, in the whole graph I calculate minimum weight $B$ of path with length $2$, only once. The answer is $min(A, B)$.
 » 13 days ago, # | ← Rev. 2 →   0 I wrote I solution to C using binary search and checking whether the graph bipartite. But is gets WA, I have no idea why. I was debugging it for an hour, then I wrote a DSU solution. Code (WA)#include using namespace std; #define ll long long #define ld long double #define fi first #define se second #define pb push_back #pragma GCC optimize("unroll-loops,O3") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,sse4.2") #define cok cout << (ok ? "YES\n" : "NO\n"); #define dbg(x) cout << (#x) << ": " << x << endl; #define dbga(x,l,r) cout << (#x) << ": "; for (int ii=l;ii const int N = 1e6+9; vector vec[N], g[N]; int used[N]; int n, m; int ch() { int ans = 2e9 + 100; for (int i=0;i st; for (auto [b, c]: vec[i]) st.insert(c); if (st.size() > 1) { int tek = 0; auto it = st.begin(); tek += *it; it++; tek += *it; ans = min(ans, tek); } } return ans; } bool good(int mid) { for (int i=0;i q; used[0] = 1; q.push(0); while (q.size()) { int v = q.front(); q.pop(); for (auto [u, c]: g[v]) { if (!used[u]) { used[u] = used[v] == 1 ? 2 : 1; q.push(u); } else { if (used[u] == used[v]) return 0; } } } return 1; } signed main() { cin.tie(0);ios_base::sync_with_stdio(0); cin >> n >> m; for (int i=0;i> a >> b >> c; a--;b--; vec[a].pb({b, c}); vec[b].pb({a, c}); } for (int i=0;i 1) { int mid = (l + r) / 2; for (int i=0;i
•  » » 13 days ago, # ^ |   +5 Graph can become disjoint after removing edges. And you check only one connected component of it.
•  » » » 13 days ago, # ^ |   0 Oh, thank you. I have to be more careful.
 » 13 days ago, # | ← Rev. 5 →   +5 Why is this solution correct for B? On the following input 6 3 6 3 2 5 1 4 The program outputs 6 3 1 2 5 4 When we can obtain 6 3 2 1 4 5 By applying operation on the last 3 elements. Please can anyone tell me what i am missing?
•  » » 13 days ago, # ^ | ← Rev. 2 →   +15 You aren't missing anything. Tests are apparently weak.
 » 12 days ago, # |   +11 How to (or, Can we) add hacks for B? Tests are too weak.
 » 12 days ago, # |   +38 As some of you mentioned, tests for B were weak. We added a few extra tests as after_contest.
•  » » 11 days ago, # ^ |   0 Will the solutions be rejudged(or perhaps rating recalculated)?
•  » » » 11 days ago, # ^ |   0 No, it doesn't affect in-contest submissions.
 » 12 days ago, # |   0 In second solution of C can someone explain me how to find the weight of the edge at which the graph first becomes non-bipartite when starting from a graph with N vertices and 0 edges and adding M edges in ascending order of weight. I wasn't able to understand how the approach given in the editorial works to find this.