### maroonrk's blog

By maroonrk, history, 4 months ago,

We will hold Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138）.

The point values will be 400-500-600-700-1000-1000.

We are looking forward to your participation!

• +125

 » 4 months ago, # |   +14 thanks for leaving $N=K=1$ as a testcase in D
•  » » 4 months ago, # ^ |   0 I failed on that case, too. (38 ACs and 1 WA
 » 4 months ago, # |   +167 Remind me why ARCs are not rated for 2800+?
 » 4 months ago, # |   +126 Nice problems, but I am not sure if putting problems like EF in ARC is even reasonable if there are $5$ and $2$ ACs in the end...Interesting fact: since 2021, maroonrk has authored $8$ ARCs and $1$ AGC alone, has coauthored $3$ ARCs and $1$ AGC, and wrote an entire OpenCup set (and there may be many more I am not aware of). How to be so productive...
 » 4 months ago, # |   0 I find B easier than A
•  » » 4 months ago, # ^ |   0 Same, C was also really nice
•  » » 4 months ago, # ^ |   0 Could you please explain B solution?
•  » » » 4 months ago, # ^ |   0 You can check my video editorial of A and B if you have any confusion
•  » » » » 4 months ago, # ^ |   0 Thanks!
•  » » » 4 months ago, # ^ | ← Rev. 6 →   +18 B solution that may be easier than editorial solution:First, consider the problem in reversed time (so you start with the given array and want to reduce it to empty. Op A is "remove first element, which must be 0, then flip remaining elements", op B is "remove last element, which must be 0")Notice that op B should always be done if possible. That's because if op B is possible, doing some number of op A first would either make it not possible anymore, or simply make it possible again, and then performing op B then would just put you in the same position as if you did op B before those ops A. The operation choice is now deterministic and can be easily tried by simulation (using a parity bit to emulate flipping the array, or just notice that it's equal to the parity of your left-pointer)
 » 4 months ago, # |   0 Im painful. Anyone can tell me about just one WA TC? Submission
 » 4 months ago, # |   +72 Problem D appeared last year on Luogu Monthly Contest. Fun fact, the writer participated in this contest.
•  » » 4 months ago, # ^ |   +22 Also it can be solved by doing a naive DFS. We can't prove that, but it got AC.
•  » » » 4 months ago, # ^ |   0 Someone had proved it in Luogu Discuss。
•  » » » » 4 months ago, # ^ |   0 Well, I don't understand very clearly.So I still can't figure out why dfs is right.
 » 4 months ago, # |   +109 Thanks for participating! I didn't intend to make ARC this challenging, but E and F were much harder than I thought.BTW, is D known in China?
•  » » 4 months ago, # ^ |   +56 D is same as a Chinese contest's problem
•  » » 4 months ago, # ^ |   +37 task D appeared in luogu contest last year :https://www.luogu.com.cn/contest/55488
•  » » 4 months ago, # ^ | ← Rev. 4 →   +40 this problemWhen you translate it into Japanese you'll find that THEY ARE EXACTLY SAMEHere is the author Rolling_Code >_<
•  » » 4 months ago, # ^ |   +131 Well, I was the writer:(
•  » » 4 months ago, # ^ |   +21 It is the same problem as a Chinese contest's div1 A/div2 C.
•  » » 4 months ago, # ^ |   +45 The same problem also appeared in IZhO 2019.Link
•  » » » 4 months ago, # ^ |   0 \abcorz/
•  » » 4 months ago, # ^ |   +56 E and F are very good and interesting. Thank you for these problems. I like them very much! They are better than polynomial problems lol.
•  » » » 4 months ago, # ^ |   +15 In fact E can become a polynomial problem by changing n to $10^5$.
 » 4 months ago, # |   +18 What is basis in Editorial of D?
•  » » 4 months ago, # ^ |   +10 OK, it is some kind of linear algebra.
•  » » 4 months ago, # ^ |   0 Here is great tutorial on xor basis: https://codeforces.com/blog/entry/68953.I used it's implementation to find basis and solve the problem: https://atcoder.jp/contests/arc138/submissions/30920108
•  » » » 4 months ago, # ^ |   +5 Thanks for detailed tutorial.
 » 4 months ago, # |   +13 Note that problem D is same with a problem on a Chinese online judge.
•  » » 4 months ago, # ^ |   0 Actually, you can copy the solution and change the 01into a Yes No.Then you can get it accepted.
 » 4 months ago, # |   +8 D is a famous problem and you can get the solution on a Chinese online judge. Many Chinese coder pass this problem quickly lol
 » 4 months ago, # |   +13 Thanks for task D Rolling_Code.
•  » » 4 months ago, # ^ |   -20 Change your name now!!!!!!!
 » 4 months ago, # |   0 Problem A&B is much easier than before,and problem D appeared on luogu,a Chinese online judge.It's surprising that there are 16 Chinese contestants in the top 20.
 » 4 months ago, # |   0 fun contest
 » 4 months ago, # | ← Rev. 2 →   0 The idea behind problem C is so wonderful! I never tried to guess that we are always able to get the maximum N/2 values. Moreover, the trick of proving this fact and construction is also amazing, really beyond my imagination. Problem writer has done a great job, thank you :)
 » 4 months ago, # |   0 I have hard time understanding the editorial for problem B. Can somebody explain?
•  » » 4 months ago, # ^ |   +11 For B, I used deque as the data structure because I planned to both pop in the front and pop at the back of the deque. In the beginning, I kept popping '0' at the back of the deque until I cannot. Then I check if the front of the deque is '0' and if so, I pop_front() and then flip the remaining deque. Otherwise, the front of the deque is '1', return 'No'. I keep doing the above until the deque is empty. If I can reach empty deque, the answer is yes. The above is the brute force way. It will TLE. Therefore, make a boolean flag to record the current state is flipped or not. Then there is no need to flip the deque. Based on the current state of flip, we treat '0' as '0' or treat '0' as '1' and '1' as '0'. Then, there will be no TLE.
•  » » » 4 months ago, # ^ |   0 Thank you for your help!AC!
•  » » » 2 months ago, # ^ |   0 thanks, that was insightful
»
4 months ago, # |
-39

for problem A: my approach was for each element of the input array from index k to n-1 we can find the best possible place to swap it with, this would be the rightmost element amongst the first k numbers that has a value less than the element we are examining currently, I sorted the numbers in the first half and then used binary search to come up with the best possible index to replace with the current number here is my code:

# include<bits/stdc++.h>

using namespace std; long long gcd(long long a, long long b) { if (b == 0) { return a; } return gcd(b, a % b); } long long bp(long long a, long long b) { long long res = 1; while (b) { if (b & 1) { res *= a; } a *= a; b /= 2; } return res; } void solve() {

int n, k;
cin >> n >> k;
vector<pair<int, int>> seen(k);

vector<int> v(n);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
v[i] = x;
if (i < k) {
seen[i] = { v[i],i };
}
}
sort(seen.begin(), seen.end());
int ans = INT_MAX;
for (int i = k; i < n; i++) {
if (v[i] < seen[0].first) {
continue;
}
else {
int pos = -1;
int low = 0;
int high = k - 1;
while (high >= low) {
int mid = (high + low) / 2;
if (seen[mid].first <= v[i]) {
if (v[i] > seen[mid].first) {
pos = max(pos, seen[mid].second);
}
low = mid + 1;
}
else {
high = mid - 1;
}
}
if (pos == -1) {
continue;
}
ans = min(ans, k - 1 - pos + i - k);
}
}
if (ans == INT_MAX) {
cout << -1 << endl;
}
else {
cout << ans+1 << endl;
}


} int main() { int t = 1; while (t--) { solve(); } }

I got WA in 9 test cases could someone tell me what is wrong here??

 » 4 months ago, # |   +3 In this contest I registered unrated and I didn't have any submission. Why this contest still rated for me?. link. maroonrk Pls check. Thanks u.