chokudai's blog

By chokudai, history, 7 weeks ago,

We will hold AtCoder Beginner Contest 281.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

• +57

 » 7 weeks ago, # |   0 how to solve d?
•  » » 7 weeks ago, # ^ |   0 DP and only transition from valid states.
•  » » 7 weeks ago, # ^ |   -10 #include using namespace std; #define int long long const int N = 100 + 10; int f[N][N][N]; int exist[N][N][N]; signed main() { int n, k, d; cin >> n >> k >> d; exist[0][0][0] = 1; int a[n+1]; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) { for(int j = 0; j < i; j++) { for(int t = 0; t < k; t++) { for(int v = 0; v < d; v++) { if(exist[j][t][v]) { exist[i][t+1][(v + a[i]) % d] = 1; f[i][t+1][(v + a[i]) % d] = max(f[i][t+1][(v + a[i]) % d], f[j][t][v] + a[i]); } } } } } int ans = -1; for(int i = 1; i <= n; i++) if(exist[i][k][0]) ans = max(ans, f[i][k][0]); cout << ans << endl; return 0; } 
 » 7 weeks ago, # |   +42 Problem F is same as: 1285D - Dr. Evil Underscores
•  » » 7 weeks ago, # ^ |   0 Lol, I was happy that I solved it in 6 minutes. Now, I have realized I solved the same one a few years ago.
 » 7 weeks ago, # | ← Rev. 2 →   0 E is easier than D, for people who are less comfortable with DP.
 » 7 weeks ago, # |   +1 Great Round! solved A-F for the first time :3
 » 7 weeks ago, # |   0 Got TLE on E using 2 multisets, anyone got AC with this approach please share their solution
•  » » 7 weeks ago, # ^ |   0 Same happened with me. Had to use ordered sets to pass.
•  » » 7 weeks ago, # ^ |   0 My submission uses 2 multisets.
•  » » 7 weeks ago, # ^ |   0 herehope that helps
•  » » » 7 weeks ago, # ^ |   0 I checked both of your submissions (You and the comment above) but did not find any significant differences than my implementation, dont know whats the issue
•  » » » » 7 weeks ago, # ^ |   0 notice that when m==k, s2 will always be empty, so s2.erase(s2.begin()); in line76 can cause an error. here is my quick fix. no tle, but get a re... so there remains something to fix
•  » » » » » 7 weeks ago, # ^ |   0 Thanks for the reply found out that deleting from an empty set was the issue. Though I did not except a TLE for that, if got RE then would have thought in that direction
•  » » » » 7 weeks ago, # ^ |   0 I used two multisets and it worked.https://atcoder.jp/contests/abc281/submissions/37191709
•  » » 7 weeks ago, # ^ |   0 Your explain in D in ur video is good enough, thank u.
•  » » » 7 weeks ago, # ^ |   0 Thank you
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I checked your submission, your implementation is incorrect (I did the same thing without those bugs and it passes under 200ms). Hint 1:- Check for m = 1, Hint 2:- count() takes O(f + logn) time where f is the frequency of the searched element.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Thanks got it now. It was the case for handling empty sets for M=1, never thought of it as was not expecting TLE because of that. Thanks again
 » 7 weeks ago, # |   +1 Any idea why this is giving a wrong answer on the samples? https://atcoder.jp/contests/abc281/submissions/37185737 Replacing min with max for some reason passes the samples (however not the system tests), but min seems more appropriate.
 » 7 weeks ago, # |   0 I think there is no multiset in python. And most approaches uses multiset or Fenwicktree to solve the problem E in today's contest. Can anyone please provide a working of either of the mentioned Data Structures, with a good resource so that once can implement the same in python.Heap is one of the options used by people who were able to solve in python, But it requires some clever use of heaps, anyone explaining their idea will also be helpful. Thanks!
 » 7 weeks ago, # |   0 AtCoder founder and CEO guided ChatGPT to take part in ABC281 virtually. The result is that only A,B,C,D are completed. YouTube link.