include&lt;bits/stdc++.h&gt;

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

6 месяцев назад, # ^ |

hint

→ Ответить

akashtomar19

6 месяцев назад, # ^ |

E using hashing.

→ Ответить

0xkn1gh7

6 месяцев назад, # ^ |

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

→ Ответить

Lotrick

6 месяцев назад, # |

-7

Nice C, D, E

→ Ответить

xk2013

6 месяцев назад, # |

-15

太难了！！！

→ Ответить

ShanC

6 месяцев назад, # ^ |

認同

→ Ответить

hhc0716

6 месяцев назад, # ^ |

Please talk in English（请使用英文对话）

→ Ответить

xk2013

4 недели назад, # ^ |

oh my i don't understand English!

→ Ответить

giaminh8368

6 месяцев назад, # |

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

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

→ Ответить

mohamedeltair

6 месяцев назад, # ^ |

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.

→ Ответить

giaminh8368

6 месяцев назад, # ^ |

Thanks, maybe today is my unlucky day.

→ Ответить

HaneDaniko

6 месяцев назад, # |

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

→ Ответить

6 месяцев назад, # |

-8

Why this gives WA for F? Code

→ Ответить

6 месяцев назад, # ^ |

There is a corner case for K=2

Example

2
2 0
6 0

Answer is 3

→ Ответить

6 месяцев назад, # ^ |

-8

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

→ Ответить

6 месяцев назад, # ^ |

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 месяцев назад, # ^ |

← 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

→ Ответить

SummerSky

6 месяцев назад, # ^ |

-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.

→ Ответить

ok12

6 месяцев назад, # |

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?

→ Ответить

not_insync

6 месяцев назад, # ^ |

your solution might be O(n * n) just sort the array and use binary search

→ Ответить

ok12

6 месяцев назад, # ^ |

← Rev. 2 →

https://atcoder.jp/contests/abc353/submissions/53347370 how i binary search and sorting helps in this ?

→ Ответить

6 месяцев назад, # ^ |

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

→ Ответить

AlyssonVictor

6 месяцев назад, # ^ |

i didnt .-.

→ Ответить

6 месяцев назад, # |

I added hints for G: Merchant Takahashi on CF Step

→ Ответить

AvaraKedavra

6 месяцев назад, # ^ |

← Rev. 2 →

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] ?

→ Ответить

6 месяцев назад, # ^ |

$$$[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]$$$.

→ Ответить

AvaraKedavra

6 месяцев назад, # ^ |

Understood. Thanks a lot!

→ Ответить

wibulord

6 месяцев назад, # |

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 месяцев назад, # ^ |

← Rev. 2 →

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 месяцев назад, # |

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...

→ Ответить

nichke

6 месяцев назад, # ^ |

-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 месяцев назад, # ^ |

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 месяцев назад, # ^ |

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 месяцев назад, # ^ |

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.

→ Ответить

hashman

6 месяцев назад, # ^ |

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

→ Ответить

hashman

6 месяцев назад, # ^ |

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

→ Ответить

6 месяцев назад, # ^ |

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.

→ Ответить

xiaofu15191

6 месяцев назад, # |

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

→ Ответить

Nilsin

6 месяцев назад, # ^ |

Same, lol

→ Ответить

nichke

6 месяцев назад, # |

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.

→ Ответить

_Subrata

6 месяцев назад, # ^ |

Got AC using double hash

→ Ответить

amoad

6 месяцев назад, # |

C >> D , how to solve C ?

→ Ответить

6 месяцев назад, # ^ |

comment

→ Ответить

prayanshsinha

6 месяцев назад, # |

-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

→ Ответить

eklavya_k

6 месяцев назад, # |

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

→ Ответить

nichke

6 месяцев назад, # ^ |

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

→ Ответить

GDCass1ni

6 месяцев назад, # |

Can someone tell me why problem F got

$$$\Large\color{red}{\text{WA} \times 4}$$$

→ Ответить

6 месяцев назад, # ^ |

-16

Corner case for K=2 probably?

2
2 0
6 0

Answer is 3

→ Ответить

GDCass1ni

6 месяцев назад, # ^ |

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 месяцев назад, # |

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.

→ Ответить

29logN

6 месяцев назад, # |

+48

sigma problemset

→ Ответить

lazy-guy-1618

6 месяцев назад, # |

Could someone tell why WA in C? T_T

Code

→ Ответить

_HUECTRUM_

6 месяцев назад, # |

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

→ Ответить

6 месяцев назад, # |

+18

Really liked F, really disliked G.

→ Ответить

6 месяцев назад, # ^ |

-8

Hi,this Code for F gives WA in 6 testcases,can you help?

→ Ответить

6 месяцев назад, # ^ |

Dunno but they will publish testcases on dropbox soon

→ Ответить

Dominater069

6 месяцев назад, # ^ |

+21

same

→ Ответить

pedastrian57

6 месяцев назад, # |

You can check video editorials of E and G here

→ Ответить

nobleknight

6 месяцев назад, # |

← Rev. 2 →

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.

→ Ответить

atulram3152

6 месяцев назад, # |

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;

}

→ Ответить

6 месяцев назад, # ^ |

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

→ Ответить

atulram3152

6 месяцев назад, # ^ |

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

→ Ответить

lucky_clover_

6 месяцев назад, # |

-8

Dislike F.

→ Ответить

sumitoutlook7932

6 месяцев назад, # |

← Rev. 3 →

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

→ Ответить

Dark_Kerm

6 месяцев назад, # |

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 месяцев назад, # |

← Rev. 2 →

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 месяцев назад, # ^ |

-8

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

→ Ответить

6 месяцев назад, # ^ |

yessir that seems fine as well

→ Ответить

MarioYC

6 месяцев назад, # ^ |

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

→ Ответить

6 месяцев назад, # ^ |

maybe not, because $$$c \leq 10^{9}$$$ and $$$y \leq 10^{5}$$$

→ Ответить

MarioYC

6 месяцев назад, # ^ |

Buth both c and y are int

→ Ответить

6 месяцев назад, # ^ |

← Rev. 2 →

i've defined a macro #define int long long

→ Ответить

6 месяцев назад, # ^ |

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.

→ Ответить