chokudai's blog

By chokudai, history, 7 weeks ago, In English

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!

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve d?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DP and only transition from valid states.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it
    #include <bits/stdc++.h>
    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, # |
  Vote: I like it +42 Vote: I do not like it

Problem F is same as: 1285D - Dr. Evil Underscores

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

E is easier than D, for people who are less comfortable with DP.

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Great Round! solved A-F for the first time :3

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Got TLE on E using 2 multisets, anyone got AC with this approach please share their solution

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same happened with me. Had to use ordered sets to pass.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My submission uses 2 multisets.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    here

    hope that helps

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    Your explain in D in ur video is good enough, thank u.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

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.