atcoder_official's blog

AtCoder Beginner Contest 353 Announcement
By atcoder_official, history, 3 weeks ago, In English

We will hold AtCoder Beginner Contest 353.

We are looking forward to your participation!

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

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

wow

→ Reply
»
3 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

I think the problem G is easier than usual because of the point values.

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

hope get a positive delta

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to Solve ABC

→ Reply
»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

ABC 353 may include:

  • Primes ($$$353$$$ is a prime)
  • Palindromes
→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hfhf

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

mAThCoder

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

how to do E?

→ Reply
»
3 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Nice C, D, E

→ Reply
»
3 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

太难了！！！

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me find out this code get WA for problem G:

https://atcoder.jp/contests/abc353/submissions/53380216

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

    Changing solve() to the following makes it accepted:

    void solve(){
    for(int i=1; i<=n; i++){
        __int128 nleft=get(1, 1, m, 1, t[i]).fi;
        __int128 nright=get(1, 1, m, t[i], m).se;
        dp[i]=p[i]+max((__int128)-t[i]*c+nleft, (__int128)t[i]*c+nright);
        update(1, 1, m, t[i], {dp[i]+t[i]*c, dp[i]-t[i]*c});
    }
    cout << max((ll)0, (ll)*max_element(dp, dp+n+1));
}

    The changes are that the for loop bound is n instead of m, and at the end take the maximum between 0 and the dp maximums to handle the case if it is better to not participate in any market at all.

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

c d e just a little more difficult as it should be in that place.

→ Reply
»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Why this gives WA for F? Code

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

    There is a corner case for K=2

    Example

    2
2 0
6 0

    Answer is 3

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Hi VLamarca,i've updated the code for k=2,still it gives WA for 6 test cases,Code ,any help?

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Your update is wrong, you can make assert(k!=2) to confirm that the 6 cases you are still failing are for k=2

        → Reply
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          ← Rev. 2   Vote: I like it -8 Vote: I do not like it

          Thanks for the help,the mistake i made was printing ans one loop earlier for k=2,this is beyond stupid.Code AC

          → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Hi Mr VLamarca，I still feel confused about what is special about the case when k = 2, and what ideas should we use to handle this case. Would you like to talk more details about it? Thank you so much.

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain what should i do to stop tle in problem C .What should i study to no get tle in next rounds?

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I added hints for G: Merchant Takahashi on CF Step

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

    Hi, amazing solution and explanation. I have one doubt though. While choosing the optimal position to the right of current index (say t), why are you checking for the max value in range [t,n-1] ? Shouldn't it be [t+1,n-1] ?

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

      $$$[t + 1, n - 1]$$$ will also work. But then you need to divide into 3 cases, Left, Right and the third case is when you go to a market from town $$$t$$$ to town $$$t$$$.

      But you can take advantage of the fact that distance between town $$$t$$$ and town $$$t$$$ is zero. So it can either be clubbed with the left half or right half. So both of these are valid.

      • $$$[0, t-1]$$$ and $$$[t, n - 1]$$$
      • $$$[0, t]$$$ and $$$[t + 1, n - 1]$$$.
      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to G ? I tried to come up with CHT but it may not work cuz i don't know how to deal with t[i]-t[j] :(

→ Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Define $$$dp[i]$$$ to be the profit when you end your journey at index $$$i$$$.

    Then, define $$$ldp[i] = dp[i] + c \cdot i$$$ and $$$rdp[i] = dp[i] - c \cdot i$$$.

    Then, $$$dp[t]$$$ would take contribution from prefix maxima of $$$ldp$$$ and suffix maxima of $$$rdp$$$. So a Segment Tree or Fenwick Tree suffices.

    → Reply
»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Whoa, so many people know about segment trees, it's crazy... after seeing so many ACs on G I expected it to have a simpler solution, but nope...

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Tbh G was simpler than C to me. It could have easily been an E, considering it was quite literally just about implementing a segtree.

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Isnt segment tree somewhat basic? Specially without lazy propagation, it is a very common topic, a little bit more advanced than binary search. You can just learn to use it as a black box, it is easier to learn than dynammic programming, about the same level as dijkistra or fast pow IMO.

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

      Agreed, especially with Atcoder providing its AC library, they do expect the participants to be aware of its usage as a black box.

      If you recall, there have been problems at position E (out of 7 problems) in past ABC where the intended solution was segtree. See ABC340E : Mancala 2

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

      I reached high purple without ever using a segtree, and now many cyans casually use it. Blackboxing data structures in later problems is not the direction I want competitions to go in.

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        ABC is literally built for the purpose of making participants aware of these data structures. What do you expect?

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

          By the way, it's not like CF hasn't had such problems before.

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

          This old thread shares my sentiment and has indeed established that it is better to perceive ABCs as AtCoder Educational Contests with no specific limitations regarding beginner-friendliness of involved concepts. It's a pity I wasn't aware of it at the time of writing my previous comment.

          → Reply
»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

When I didn't AC Problem C,my brain be like:

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I crazy or is double hashing really meant to fail on E? I solved it using trie in the end, but struggled with 3 tests failing my double hash.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

C >> D , how to solve C ?

→ Reply
»
3 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

include<bits/stdc++.h>

using namespace std;

int N = 1e+8; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector vec(n); for(int i=0;i<n;i++){ cin>>vec[i]; } vector vec1; for(int j=0;j<n-1;j++){ for(int i=j+1;i<n;i++){ vec1.push_back(((vec[j])%N+(vec[i])%N)%N); } } long long int sum = accumulate(vec1.begin(),vec1.end(),0); cout<<sum;

}

i wrote this code but i m getting tle but this should be o(n^2) time complexity so is there any way to optimise this code

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why is using 1E8 (link) instead of 100000000 (link) giving wrong ans. I submitted 6 different solutions for prob c all of them correct but used 1E8 and none passed

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

    If you convert to int as in (int)1e8 it should work. It's the double comparison that is giving you troubles most likely.

    → Reply
»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone tell me why problem F got

$$$\Large\color{red}{\text{WA} \times 4}$$$
→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    Corner case for K=2 probably?

    2
2 0
6 0

    Answer is 3

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      thanks, although my code gives the correct answer for this case :(

      My mistake is when a point is in a $$$1 \times 1$$$ matrix, i will let it go to a $$$K \times K$$$ matrix. But two points in the same $$$K \times K$$$ matrix like below case, it will give WA.

      5
2 2
3 3
      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

If you want to build intuition for today's G (specifically the trick of splitting the $$$|.|$$$ operator in DP problems), you can attempt ABC334F : Christmas Present 2. I also created a video and practice contest for the same.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +48 Vote: I do not like it
sigma problemset
→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone tell why WA in C? T_T

Code

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Join me laughing at myself for what is probably the most overengineered E solution possible boop

→ Reply
»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Really liked F, really disliked G.

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You can check video editorials of E and G here

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I wrote a solution of problem D in 50+ lines. Implemented Binary Modular Exponentiation, Grade School Addition and Suffix Sum. I was happy to get AC. Then found out that these guys are writing 10 lines solutions with no fancy algorithms.

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Its giving me TLE for C. PLease help me optimize the code

include

using namespace std;

int main() { int n; cin>>n; long long a[n];

for(int i=0;i<n;i++)
{
    cin>>a[i];
}

long ans = 0;

int i = 0;
int j = n-1;

while(i<j)
{
    ans += (a[i]+a[j])%100000000;
    j--;
    if(j==i)
    {
        i++;
        j = n-1;
    }
}

cout<<ans<<endl;

return 0;

}

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

    it's O(n^2) and n <= 1e5. btw you could also write this soln with 2 for loops why did you complicate it

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

      I wrote a 2 for loop approach...thought this approach would give me O(n)

      → Reply
»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Dislike F.

→ Reply
»
3 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

in question D it is giving wrong answer only 2 test case passed .

include <bits/stdc++.h>

using namespace std;

define int long long

define fastio \

ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)

int32_t main() { fastio; int n; cin>>n; int mod=998244353; vector v(n);

for(int i=0;i<n;i++) cin>>v[i];

int ans=0,s=0,m=0;

for(int i=n-1;i>=0;i--){

ans+=v[i]*m+s;

   m+=pow(10, to_string(v[i]).length());

   s+=v[i];

}

cout<<ans%mod;

return 0;

}

unable to find the error

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D: I am not able to find the bug, it passes for the example test cases but fails for the rest. Here is my submission for the problem, Can someone please help me debug this?

→ Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone please debug my submission for G? I'm not able to pinpoint where i'm going wrong, everything seems right on a high level. I'd really appreciate you taking your time for this

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Maybe your mistake is when there are 2 markets in the same location one after the other, are you handling this correctly?

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

    When calculating $$$c*(y+1)$$$ you may have an overflow.

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You are mixing up the zero based indexing and one based indexing. Here's your almost correct solution, where I used zero based indexing for segtree as well as $$$|.|$$$ operator. After the fix, your code passed 55 testcases instead of just 14 testcase.

    The rest 18 testcases fail due to a completely different issue, which is obvious to me, but I'll let you figure out and debug on your own. If you are still not able to, feel free to ping on the thread.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      well i changed -inf to $$$-10^{18}$$$ and changed final answer to $$$max(0, max(dp))$$$ now it fails on last 2 tests only xD, no clue as to where they are failing

      Upd : Got AC now, changed $$$dp[y] = max({left, right})$$$ to $$$dp[y] = max({left, right, p + dp[y]})$$$. Thank you so much for helping me out!! (also i love cf step, great initiative!!!)

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help- me understand my the below solution for C is failing https://atcoder.jp/contests/abc353/submissions/53411613

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help with problem E? My solution uses trie and got 41 AC, 7 WA

https://atcoder.jp/contests/abc353/submissions/53412393

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Ha the code for the editorial of F is relly strange to me

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I thin E is more easier than D. D->60min, E->15min

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why no english editorial atcoder_official

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

include<bits/stdc++.h>

using namespace std;

define int long long

const int mod=998244353;
const int inf=1e18;

int bin_exp(int n,int x,int mod) { if(x==0) { return 1; }

if(x%2==0)
{
    return bin_exp(((n%mod)*(n%mod))%mod,x/2,mod);
}

return ((n%mod)*(bin_exp(((n%mod)*(n%mod))%mod,(x-1)/2,mod))%mod)%mod;

}

int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL); 

int n;
  cin>>n;
  vector<int>vec(n);
  for(int i=0;i<n;i++)
  {
      cin>>vec[i];
  }

  vector<int>prefix(n);
  prefix[0]=vec[0];
  for(int i=1;i<n;i++)
  {
      prefix[i]=prefix[i-1]+vec[i];
  }

  vector<int>digits(n);
  string some=to_string(vec[0]);
  digits[0]=bin_exp(10,some.size(),mod);

  for(int i=1;i<n;i++)
  {
      some=to_string(vec[i]);
      int whole=bin_exp(10,some.size(),mod);
      whole%mod;

      digits[i]=digits[i-1]+whole;
      digits[i]%mod;
  }

  int ans=0;
  for(int i=0;i<n;i++)
  {
      int ans1=prefix[n-1]-prefix[i];
      ans1=ans1%mod;

      int ans2=digits[n-1]-digits[i];
      ans2%=mod;
      ans2=ans2*vec[i];
      ans2%=mod;

      ans+=ans1+ans2;
      ans=ans%mod;
  }

  cout<<ans<<endl;

  return 0;

}

question number 4 solution

→ Reply