7

Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Conte...

 3 years ago
source link: http://codeforces.com/blog/entry/101686
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138）Announcement

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!

13 hours ago, # |

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

  • 13 hours ago, # ^ |

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

13 hours ago, # |

Remind me why ARCs are not rated for 2800+?

13 hours ago, # |

Nice problems, but I am not sure if putting problems like EF in ARC is even reasonable if there are 55 and 22 ACs in the end...

Interesting fact: since 2021, maroonrk has authored 88 ARCs and 11 AGC alone, has coauthored 33 ARCs and 11 AGC, and wrote an entire OpenCup set (and there may be many more I am not aware of). How to be so productive...

13 hours ago, # |

I find B easier than A

  • 13 hours ago, # ^ |

    Same, C was also really nice

  • 13 hours ago, # ^ |

    Could you please explain B solution?

13 hours ago, # |

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

13 hours ago, # |

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

  • 13 hours ago, # ^ |

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

    • 13 hours ago, # ^ |

      Someone had proved it in Luogu Discuss。

      • 13 hours ago, # ^ |

        Well, I don't understand very clearly.

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

13 hours ago, # |

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?

  • 13 hours ago, # ^ |

    D is same as a Chinese contest's problem

  • 13 hours ago, # ^ |

    ← Rev. 4 →  

    +37

    this problem

    When you translate it into Japanese you'll find that THEY ARE EXACTLY SAME

    Here is the author Rolling_Code >_<

  • 13 hours ago, # ^ |

    Well, I was the writer:(

  • 13 hours ago, # ^ |

    It is the same problem as a Chinese contest's div1 A/div2 C.

  • 13 hours ago, # ^ |

    The same problem also appeared in IZhO 2019.

    Link

  • 11 hours ago, # ^ |

    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.

13 hours ago, # |

What is basis in Editorial of D?

  • 13 hours ago, # ^ |

    OK, it is some kind of linear algebra.

13 hours ago, # |

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

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

  • 13 hours ago, # ^ |

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

    Then you can get it accepted.

13 hours ago, # |

D is a famous problem and you can get the solution on a Chinese online judge. Many Chinese coder pass this problem quickly lol

13 hours ago, # |

Thanks for task D Rolling_Code.

  • 13 hours ago, # ^ |

    Change your name now!!!!!!!

13 hours ago, # |

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.

13 hours ago, # |

fun contest

12 hours 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 :)

11 hours ago, # |

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

  • 11 hours ago, # ^ |

    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.

    • 38 minutes ago, # ^ |

      Thank you for your help!AC!

26 minutes ago, # |

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??


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK