maroonrk's blog

By maroonrk, history, 4 months ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +125
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +14 Vote: I do not like it

thanks for leaving $$$N=K=1$$$ as a testcase in D

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I failed on that case, too. (38 ACs and 1 WA

»
4 months ago, # |
  Vote: I like it +167 Vote: I do not like it

Remind me why ARCs are not rated for 2800+?

»
4 months ago, # |
  Vote: I like it +126 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

I find B easier than A

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same, C was also really nice

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain B solution?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can check my video editorial of A and B if you have any confusion

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 6   Vote: I like it +18 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

Im painful. Anyone can tell me about just one WA TC? Submission

»
4 months ago, # |
  Vote: I like it +72 Vote: I do not like it

Problem D appeared last year on Luogu Monthly Contest. Fun fact, the writer participated in this contest.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Also it can be solved by doing a naive DFS. We can't prove that, but it got AC.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Someone had proved it in Luogu Discuss。

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, I don't understand very clearly.

        So I still can't figure out why dfs is right.

»
4 months ago, # |
  Vote: I like it +109 Vote: I do not like it

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, # |
  Vote: I like it +18 Vote: I do not like it

What is basis in Editorial of D?

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Note that problem D is same with a problem on a Chinese online judge.

link:https://www.luogu.com.cn/problem/P7949

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, you can copy the solution and change the 01into a Yes No.

    Then you can get it accepted.

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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, # |
  Vote: I like it +13 Vote: I do not like it

Thanks for task D Rolling_Code.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

fun contest

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

I have hard time understanding the editorial for problem B. Can somebody explain?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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, # |
  Vote: I like it -39 Vote: I do not like it

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, # |
  Vote: I like it +3 Vote: I do not like it

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.