### atcoder_official's blog

By atcoder_official, history, 3 months ago,

We will hold Daiwa Securities Co. Ltd. Programming Contest 2023（AtCoder Beginner Contest 331）.

We are looking forward to your participation!

• +34

 » 3 months ago, # |   -7 Atcoder beginner contests are really great.
 » 3 months ago, # |   -8 I hope I can get better grades than before......
•  » » 3 months ago, # ^ |   -8 me too
 » 3 months ago, # | ← Rev. 2 →   +4 D with 450 points… seems scary
•  » » 3 months ago, # ^ |   0 Yeah……Maybe i will solve E first.
 » 3 months ago, # |   +3 Guess the order of difficulty among A,B,C,D :)
•  » » 3 months ago, # ^ |   0 I guess A < B < C < D.
 » 3 months ago, # |   +4 Good luck to everyone!
 » 3 months ago, # |   +12 D is more scary than E……
 » 3 months ago, # |   0 我是菜狗
•  » » 3 months ago, # ^ |   0 me too
•  » » 3 months ago, # ^ |   0 Maybe you should use English instead of Chinese that this is a English website.
•  » » » 3 months ago, # ^ |   0 I just want to express my powerless feeling. QAQ
•  » » » 3 months ago, # ^ |   0 how did you make your contribution into a negative number?
 » 3 months ago, # |   +3 D seems pretty complex and difficult...
 » 3 months ago, # | ← Rev. 2 →   +5 Problem F is exactly same as this.Solution can be found online anywhere, one of the solution is — Solution
 » 3 months ago, # |   0 What is mistake in F https://atcoder.jp/contests/abc331/submissions/48142191
 » 3 months ago, # | ← Rev. 2 →   0 $D$ is such a heavy implementation problem ,I took a lot of time in it to solve ,like finding stupid bugs and typos killed a lot of time of mine, then went to $E$ just to find that it's just a submission bait which I speed ran implementation in last 4 mnts but missed out by fucking 3 seconds , such a stupid performance in the end which could have been a far better contest if I executed implementation well fuck!!
 » 3 months ago, # |   +3 Lol I got nervous and solved B by DP, turns out it has better time complexity and almost O(1) space
•  » » 3 months ago, # ^ |   0 my solution was $O(N^3)$ and you did it speaks of bad contest giving style where you overkill an easy problem and kill time , best thing of Atcoder Beginner Contests is that they help you increase speed and improve implementation skills
•  » » » 3 months ago, # ^ |   0 because I got nervous personally easier for me to think dp than brute force or greedy
•  » » 3 months ago, # ^ |   0 I solved B by DFS.
 » 3 months ago, # |   +2 I think only problem D and G were smart anyone agree?
•  » » 3 months ago, # ^ |   +3 you solved $G$?
 » 3 months ago, # |   +23 Atcoder please do not directly copy the CSES problem.
•  » » 3 months ago, # ^ |   0 +1 They just copied problem F from Palindrome Queries
•  » » » 3 months ago, # ^ |   0 What is mistake in this soln for F https://atcoder.jp/contests/abc331/submissions/48142191
 » 3 months ago, # |   +1 D should definitely be worth more points than E
•  » » 3 months ago, # ^ |   0 I think this too
•  » » » 3 months ago, # ^ |   0 How did you solve E?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 my approach#include #define eb emplace_back #define ll long long #define w(t) while(t--) #define F first #define S second #define pii pair #define pll pair using namespace std; set s[100010]; ll a[200010]; struct aaa{ ll val; int idx; }b[100010]; int main(){ ios::sync_with_stdio(0);cin.tie(0); int n,m,l,c,d; cin>>n>>m>>l; ll ans=0; for(int i=0;i>a[i]; for(int i=0;i>b[i].val; b[i].idx=i; } for(int i=0;i>c>>d; c--; d--; s[c].insert(d); } sort(b,b+m,[](aaa gg,aaa hh){ return gg.val>hh.val; }); for(int i=0;i
•  » » » » » 3 months ago, # ^ |   0 E is like E in last Atcoder beginner contest, just add one point:Enumerate the main dish and find the most expensive side dish, then update the answer. my code#include using namespace std; struct node { int x, id; }brr[100010]; int n, m, y[100010], l, arr[100010], ans; pair x[100010]; set s; int main() { cin >> n >> m >> l; for(int i = 1; i <= n; i++) { cin >> arr[i]; } for(int i = 1; i <= m; i++) { cin >> brr[i].x; brr[i].id = i; } for(int i = 1; i <= l; i++) { cin >> x[i].first >> x[i].second; } sort(brr + 1, brr + m + 1, [](node a, node b) {return a.x == b.x? a.id < b.id : a.x > b.x;}); sort(x + 1, x + l + 1); for(int i = 1; i <= m; i++) { s.insert(i); y[brr[i].id] = i; } for(int i = 1; i <= l; i++) { x[i].second = y[x[i].second]; } for(int i = 1, j = 1; i <= n; i++) { int l = j; for(; x[j].first == i; j++) { s.erase(x[j].second); } if(s.size()) { ans = max(ans, brr[*s.begin()].x + arr[i]); } for(int a = l; a < j; a++) { s.insert(x[a].second); } } cout << ans << '\n'; return 0; } 
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 I have solved it using segment tree with update. https://atcoder.jp/contests/abc331/submissions/48142030
•  » » » » 3 months ago, # ^ |   +3 hint: The answer is among the L+1 largest pairs.
•  » » » » 3 months ago, # ^ |   0 I just use simple multiset idea for every element in B make a multiset of elements of A that are not allowed for that B, then from a global multiset of all the values in A remove those from it. Do this for every element in B and take cur + end element of multiset.One thing to take care: Don't do this is B has all the elements of A, then it should be skipped as it can't be paired codecin >> n >> m >> l; vl a(n), b(m); rep(i, n) cin >> a[i]; rep(i, m) cin >> b[i]; vector> x(m); rep(i, l) { int u, v; cin >> u >> v; --u, --v; x[v].insert(a[u]); } vpll p; rep(i, m) p.pb({b[i], i}); sort(rall(p)); ll res = -1e18; debug(p) multiset ms; rep(i, n) ms.insert(a[i]); rep(i, m) { if(x[p[i].se].empty()) { chkmax(res, p[i].fi + *ms.rbegin()); continue; } if(x[p[i].se].size()==n) continue; multiset chenSuX; for(auto &h: x[p[i].se]) { chenSuX.insert(h); ms.erase(ms.find(h)); } if(!ms.empty()) { chkmax(res, p[i].fi + *ms.rbegin()); for(auto &h: chenSuX) ms.insert(h); } } cout << res << nl; I think it's very easy idea maybe
•  » » » » » 3 months ago, # ^ |   0 This work and not TLE because L <= min(1e5, N*M-1)
•  » » » » » 3 months ago, # ^ |   0 What? Three almost SAME ideas?And I can explain that complexity of using just normal set is $O(L \log M)$.
 » 3 months ago, # |   +8 Instead of enumerating solve B in O(n) low iq int s, m, l; cin >> n >> s >> m >> l; vl dp(n+100, 1e18); dp[0] = 0; rep(i, n+1) { dp[i+6] = min(dp[i+6], dp[i]+s); dp[i+8] = min(dp[i+8], dp[i]+m); dp[i+12] = min(dp[i+12], dp[i]+l); } // debug(dp) ll res = 1e18; rng(i, n, n+100) chkmin(res, dp[i]); cout << res << nl; 
•  » » 3 months ago, # ^ |   0 That was smart approach.
 » 3 months ago, # |   -13 Why so many Gs (and Ex when there was Ex) are math?
•  » » 3 months ago, # ^ |   0 Is it just me or most of them are about finding the expected number?
•  » » » 3 months ago, # ^ |   0 why expected value questions are asked most frequently, i am just bad at probability..
•  » » 3 months ago, # ^ |   +3 +1, adding Centroid Decomp, HLD, CHT or flows sometimes would be good at G.
•  » » 3 months ago, # ^ |   +5 cause math so good
 » 3 months ago, # |   0 Problem F was copied from CSES. Even the title. 😒
 » 3 months ago, # |   0 Problem A was the hardest TBH.
 » 3 months ago, # |   +3
•  » » 3 months ago, # ^ |   +11 You type faster than I think.
 » 3 months ago, # |   0 Problem F can be passed by force.
 » 3 months ago, # |   0 no sense between the title and problem statement on problem B.
 » 2 months ago, # |   0 Can someone provide a better explanation for G. The editorial is too tough to understand.
•  » » 2 months ago, # ^ |   0 I do think so.