### atcoder_official's blog

By atcoder_official, history, 6 weeks ago,

We will hold AtCoder Beginner Contest 353.

We are looking forward to your participation!

• +34

 » 6 weeks ago, # |   0 wow
 » 6 weeks ago, # |   -15 I think the problem G is easier than usual because of the point values.
 » 6 weeks ago, # | ← Rev. 2 →   0 hope get a positive delta
 » 6 weeks ago, # |   0 Hope to Solve ABC
 » 6 weeks ago, # |   +8 ABC 353 may include: Primes ($353$ is a prime) Palindromes
•  » » 6 weeks ago, # ^ |   -15 Guessing problem from contest number is very useful for ABC.
•  » » » 6 weeks ago, # ^ |   0 I think the really useful thing for ABC is to improve your skill instead of make some "luck based" guesses.
•  » » » » 6 weeks ago, # ^ |   0 True, tourist is just insanely good at guessing
•  » » » » » 6 weeks ago, # ^ |   0 What do you mean by that ?
•  » » » » 6 weeks ago, # ^ |   0 Problem B is not clear of todays AtCoder Contest.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 After reading the example, it will clear.
•  » » 6 weeks ago, # ^ |   +8 obviously primes which are palindromes
 » 6 weeks ago, # |   0 hfhf
 » 6 weeks ago, # |   0 mAThCoder
 » 6 weeks ago, # | ← Rev. 2 →   0 how to do E?
•  » » 6 weeks ago, # ^ |   0 hint trie
•  » » 6 weeks ago, # ^ |   0 E using hashing.https://atcoder.jp/contests/abc353/submissions/53356096
•  » » 6 weeks ago, # ^ |   0 Use hashing and count for each prefix length upto the highest length. Remember to optimise checking only those strings which have length greater than equal to the current length you are checking for.Here is the code for the same — https://atcoder.jp/contests/abc353/submissions/53371485
 » 6 weeks ago, # |   -7 Nice C, D, E
 » 6 weeks ago, # |   -15 太难了！！！
•  » » 6 weeks ago, # ^ |   0 認同
•  » » » 5 weeks ago, # ^ |   0 Please talk in English（请使用英文对话）
 » 6 weeks ago, # |   0 Can someone help me find out this code get WA for problem G: https://atcoder.jp/contests/abc353/submissions/53380216
•  » » 6 weeks ago, # ^ |   0 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.
•  » » » 6 weeks ago, # ^ |   0 Thanks, maybe today is my unlucky day.
 » 6 weeks ago, # |   0 c d e just a little more difficult as it should be in that place.
 » 6 weeks ago, # |   -8 Why this gives WA for F? Code
•  » » 6 weeks ago, # ^ |   0 There is a corner case for K=2Example 2 2 0 6 0 Answer is 3
•  » » » 6 weeks ago, # ^ |   -8 Hi VLamarca,i've updated the code for k=2,still it gives WA for 6 test cases,Code ,any help?
•  » » » » 6 weeks ago, # ^ |   +3 Your update is wrong, you can make assert(k!=2) to confirm that the 6 cases you are still failing are for k=2
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   -8 Thanks for the help,the mistake i made was printing ans one loop earlier for k=2,this is beyond stupid.Code AC
•  » » » 6 weeks ago, # ^ |   -8 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.
 » 6 weeks ago, # |   0 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?
•  » » 6 weeks ago, # ^ |   0 your solution might be O(n * n) just sort the array and use binary search
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 https://atcoder.jp/contests/abc353/submissions/53347370 how i binary search and sorting helps in this ?
•  » » » » 6 weeks ago, # ^ |   0 for a particular A[i] break the cases in 2 parts A[j] < 1e8 — A[i] and A[j] >= 1e8 — A[i] and then you will see the soln
•  » » » » » 6 weeks ago, # ^ |   0 i didnt .-.
 » 6 weeks ago, # |   0 I added hints for G: Merchant Takahashi on CF Step
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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] ?
•  » » » 5 weeks ago, # ^ |   0 $[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]$.
•  » » » » 5 weeks ago, # ^ |   0 Understood. Thanks a lot!
 » 6 weeks ago, # |   0 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] :(
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 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.
 » 6 weeks ago, # |   +8 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...
•  » » 6 weeks ago, # ^ |   -8 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.
•  » » 6 weeks ago, # ^ |   +3 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.
•  » » » 6 weeks ago, # ^ |   0 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
•  » » » 6 weeks ago, # ^ |   0 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.
•  » » » » 6 weeks ago, # ^ |   +3 ABC is literally built for the purpose of making participants aware of these data structures. What do you expect?
•  » » » » » 6 weeks ago, # ^ |   0 By the way, it's not like CF hasn't had such problems before.
•  » » » » » 6 weeks ago, # ^ |   0 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.
 » 6 weeks ago, # |   +8 When I didn't AC Problem C,my brain be like:
•  » » 6 weeks ago, # ^ |   0 Same, lol
 » 6 weeks ago, # |   0 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.
•  » » 6 weeks ago, # ^ |   0 Got AC using double hash
 » 6 weeks ago, # |   +1 C >> D , how to solve C ?
•  » » 6 weeks ago, # ^ |   0
»
6 weeks ago, # |
-23

# 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

 » 6 weeks ago, # |   0 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
•  » » 6 weeks ago, # ^ |   0 If you convert to int as in (int)1e8 it should work. It's the double comparison that is giving you troubles most likely.
 » 6 weeks ago, # |   +8 Can someone tell me why problem F got $\Large\color{red}{\text{WA} \times 4}$
•  » » 6 weeks ago, # ^ |   -16 Corner case for K=2 probably? 2 2 0 6 0 Answer is 3
•  » » » 6 weeks ago, # ^ |   +8 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 
 » 6 weeks ago, # |   0 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.
 » 6 weeks ago, # |   +48 sigma problemset
 » 6 weeks ago, # |   0 Could someone tell why WA in C? T_TCode
 » 6 weeks ago, # |   0 Join me laughing at myself for what is probably the most overengineered E solution possible boop
 » 6 weeks ago, # |   +18 Really liked F, really disliked G.
•  » » 6 weeks ago, # ^ |   -8 Hi,this Code for F gives WA in 6 testcases,can you help?
•  » » » 6 weeks ago, # ^ |   0 Dunno but they will publish testcases on dropbox soon
•  » » 6 weeks ago, # ^ |   +21 same
 » 6 weeks ago, # |   0 You can check video editorials of E and G here
 » 6 weeks ago, # | ← Rev. 2 →   0 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.
»
6 weeks ago, # |
0

# 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;

}

•  » » 6 weeks ago, # ^ |   0 it's O(n^2) and n <= 1e5. btw you could also write this soln with 2 for loops why did you complicate it
•  » » » 6 weeks ago, # ^ |   0 I wrote a 2 for loop approach...thought this approach would give me O(n)
 » 6 weeks ago, # |   -8 Dislike F.
»
6 weeks ago, # |
Rev. 3   0

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

# include <bits/stdc++.h>

using namespace std;

# 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

 » 6 weeks ago, # |   0 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?
 » 6 weeks ago, # | ← Rev. 2 →   0 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
•  » » 6 weeks ago, # ^ |   -8 Maybe your mistake is when there are 2 markets in the same location one after the other, are you handling this correctly?
•  » » » 6 weeks ago, # ^ |   0 yessir that seems fine as well
•  » » 6 weeks ago, # ^ |   0 When calculating $c*(y+1)$ you may have an overflow.
•  » » » 6 weeks ago, # ^ |   0 maybe not, because $c \leq 10^{9}$ and $y \leq 10^{5}$
•  » » » » 6 weeks ago, # ^ |   0 Buth both c and y are int
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 i've defined a macro #define int long long
•  » » 6 weeks ago, # ^ |   +1 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.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 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 failingUpd : 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!!!)
 » 6 weeks ago, # |   0 Can someone please help- me understand my the below solution for C is failing https://atcoder.jp/contests/abc353/submissions/53411613
 » 6 weeks ago, # |   0 Can someone please help with problem E? My solution uses trie and got 41 AC, 7 WAhttps://atcoder.jp/contests/abc353/submissions/53412393
•  » » 6 weeks ago, # ^ |   0 Use long long instead of int. I changed your code and submitted. Now it is AC.
•  » » » 6 weeks ago, # ^ |   0 Thanks a lot!
 » 6 weeks ago, # |   0 Ha the code for the editorial of F is relly strange to me
 » 6 weeks ago, # |   0 I thin E is more easier than D. D->60min, E->15min
 » 5 weeks ago, # |   0 why no english editorial atcoder_official
»
5 weeks ago, # |
0

# 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