AtCoder Beginner Contest 265 Announcement

We will hold AtCoder Beginner Contest 265.

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

We are looking forward to your participation!

• 17 hours ago, # ^ | have u done E i wrote dfs then tried memoizing it using map but haven't succeeded from tle

  • 17 hours ago, # ^ | Yes, I solved E with DP. you may see my submission.

    • 17 hours ago, # ^ | submission can u plz tell some optimization in this one btw thnx i will try using your approach

    • 17 hours ago, # ^ | LOL. My approach is exactly same. Submission

• 17 hours ago, # ^ | Agree. XD Btw can you tell me how to solve F if you solved?

  • 17 hours ago, # ^ | DP[i][d1][d2] = count of prefixes with d1 <= D and d2 <= D you can go from DP[i][d1][d2] to DP[i+1][d1 + |x — pi][d2 + |x — qi|] last part is prefix sums for fast transform

    • 17 hours ago, # ^ | Since time limit is 6 second it actually works also without any prefix sums.

      • 17 hours ago, # ^ | hmm, I added it because of tle with O(nD2×1000)O(nD2×1000)

      • 15 hours ago, # ^ | Your code fails after_contest tests

        • 15 hours ago, # ^ | Yes, I saw that. Guess it my lucky day ;)

• 28 minutes ago, # ^ | I did by applying brute force.

• • 17 hours ago, # ^ | Thank you, how much time does it take for a contest TCs to appear there?

    • 16 hours ago, # ^ | From the current available test-cases, it's probably 2 to 3 weeks.

• 15 hours ago, # ^ | ← Rev. 2 →   +3 While contest I assumed, since in each step we can make one of three choices, we can reach up to 3n3n points. But that is misleading, since there are only 3 kinds of steps, and order of the single steps does not matter, it is less than n3n3 different points possible. They can be described by dp[x][y][z] where x+y+z≤nx+y+z≤n

  • 13 hours ago, # ^ | But that is misleading, since there are only 3 kinds of steps, and order of the single steps does not matter, it is less than n3n3 different points possible. Can you explain this statement again? Thanks in advance.

  • 23 minutes ago, # ^ | hey, I tried E. wrap here is my code class solution{ public: ll a,b,c,d,e,f,n,m; void solve(){ cin>>n>>m; cin>>a>>b>>c>>d>>e>>f; vector<map< pair<ll,ll>, ll>> dp(n+1); set<pair<ll,ll>> st; forn(i,0,m){ ll x,y; cin>>x>>y; st.insert({x,y}); } cout<<rec(0,0,0,dp,st)<<endl; } ll rec(ll x, ll y, ll steps, vector<map< pair<ll,ll>, ll>> &dp, set<pair<ll,ll>> &st){ if(st.find({x,y})!=st.end()){ return 0; } //cout<<x<<" "<<y<<endl; if(steps==n){ return 1; } if(dp[steps].find({x,y})!=dp[steps].end()){ return dp[steps][{x,y}]; } return dp[steps][{x,y}]=(rec(x+a,y+b,steps+1,dp,st) + rec(x+c,y+d,steps+1,dp,st) + rec(x+e,y+f,steps+1,dp,st))%998244353; } }; cannot figure out why it would give me TLE on some cases, can you please tell me what am i missing to optimize?