atcoder_official's blog

AtCoder Beginner Contest 353 Announcement
By atcoder_official, history, 6 months 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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wow

→ Reply
»
6 months 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
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

hope get a positive delta

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to Solve ABC

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

ABC 353 may include:

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

hfhf

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

mAThCoder

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

how to do E?

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

Nice C, D, E

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

太难了！！！

→ Reply
»
6 months 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
  • »
    »
    6 months 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
»
6 months 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
»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Why this gives WA for F? Code

→ Reply
  • »
    »
    6 months 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
    • »
      »
      »
      6 months 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
      • »
        »
        »
        »
        6 months 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
        • »
          »
          »
          »
          »
          6 months 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
    • »
      »
      »
      6 months 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
»
6 months 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
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I added hints for G: Merchant Takahashi on CF Step

→ Reply
  • »
    »
    6 months 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
    • »
      »
      »
      6 months 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
»
6 months 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
  • »
    »
    6 months 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
»
6 months 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
  • »
    »
    6 months 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
  • »
    »
    6 months 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
    • »
      »
      »
      6 months 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
    • »
      »
      »
      6 months 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
      • »
        »
        »
        »
        6 months 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
        • »
          »
          »
          »
          »
          6 months 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
        • »
          »
          »
          »
          »
          6 months 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
»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
6 months 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
»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

C >> D , how to solve C ?

→ Reply
»
6 months 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
»
6 months 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
  • »
    »
    6 months 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
»
6 months 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
  • »
    »
    6 months 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
    • »
      »
      »
      6 months 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
»
6 months 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
»
6 months ago, # |
  Vote: I like it +48 Vote: I do not like it
sigma problemset
→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone tell why WA in C? T_T

Code

→ Reply
»
6 months 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
»
6 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Really liked F, really disliked G.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can check video editorials of E and G here

→ Reply
»
6 months 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
»
6 months 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
  • »
    »
    6 months 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
    • »
      »
      »
      6 months 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
»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Dislike F.

→ Reply
»
6 months 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
»
6 months 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
»
6 months 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
  • »
    »
    6 months 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
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    6 months 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
    • »
      »
      »
      6 months 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
»
6 months 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
»
6 months 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
»
6 months 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
»
6 months 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
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why no english editorial atcoder_official

→ Reply
»
6 months 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