We will hold AtCoder Beginner Contest 349.

- Contest URL: https://atcoder.jp/contests/abc349
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240413T2100&p1=248
- Duration: 100 minutes
- Writer: sotanishy, toam, kyopro_friends
- Tester: yuto1115, cn449
- Rated range: ~ 1999
- The point values: 100-200-300-450-450-525-625

We are looking forward to your participation!

Good luck to everyone!

GLHF!

Instresting survey.=)

why a different scoring distribution?

GLHF & Guess

Good :

OK, not bad :

Bad :

GLHF!

Hope Everyone one got a AK!

GLHF!

GL&HF!

was f related to sos dp?? how to solve f??

Consider the way of computing LCM by taking the maximum of exponents in prime factorization. For example, $$$LCM(2^{3} \cdot 3^{5}, 2^{4} \cdot 3^{1}) = 2^{max(3, 4)} \cdot 3^{max(5, 1)}$$$. Factorize $$$M$$$ and compute $$$num_i = prime_i^{exponent_i}$$$ in $$$M$$$. If some $$$a_i$$$ does not divide $$$M$$$, we can ignore $$$a_i$$$ (the exponent of some prime is bigger in $$$a_i$$$ than in $$$M$$$). For each $$$a_i$$$ that divides M, let's assign a bitmask to it. The j-th bit will be on if $$$num_j$$$ divides $$$a_i$$$. If it does not divide, it means that $$$a_i$$$ has a lower exponent on this prime that in $$$M$$$, so choosing $$$a_i$$$ in a subsequence won't contribute into getting LCM = $$$M$$$ in this particular prime. Note that this mask will have at most $$$13$$$ bits. So now your problem is: given some bitmasks, count in how many ways you can choose a subset of these bitmasks such that their bitwise OR is equal to the complete bitmask. We can do this with DP. $$$dp_{mask}$$$ = how many ways there is to choose a subset of bitmasks to form $$$mask$$$. This can be done by iteratively considering each bitmask, for a total of $$$O((2^{k})^{2})$$$, where $$$k = 13$$$. Submission

deleted

deleted

What is any adequate time complexity solution to F? How to solve it in any way other than fucking constant optimizing O(d(m) * 2^P) (where p is nr of distinct prime divisors of m)?

upd: why would you allow factorizing in O(sqrt(1e16))?

I did it in $$$O(4^P)$$$ xd

upd: as for factorization, i copied fastest code on Library Checker.

yeah, after reading others' codes already realized it was possible

which, however, raised question about why would anyone intentionally set such constraints for M if factorizing in O(sqrt) was intended

most probably because then there can be at most 13 distinct prime divisors for $$$m$$$, then that will cut off some unintended solutions? idk

my code takes 300ms, 1e8 really isnt a lot of operations.....

they set such constraints to allow sqrt factor but not allow O(4^p) [it didnt work tho ig, sad]

I believed 4^p can't work slower than 1e8 operations with modulo...

Was wrong sadly :D

oh 4^p isnt intended though? i have 3^p

it can be solved in $$$O(13^2\times(2^{13}))$$$ by fast mobius transform indeed, and the other bound is checking all divisors of $$$M$$$ in $$$a_i$$$.

How can I see the testcases? When will it be available in this link https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0

Can anyone please explain the solution of F-Subsequence LCM.Can anybody tell why does this submission https://atcoder.jp/contests/abc349/submissions/52354451 TLE?

I think your problem lies in floor(log2()), as it calculates the 'exact value' before taking the floor, and this wastes too much time when N is as big as 2^60. I modified your code and achieved an AC here: https://atcoder.jp/contests/abc349/submissions/52361678. (Actually, you don't even need to conduct << if using binary exponentiation)

Ah, Thanks for the help!

I think I did something wrong since I can't understand second the example of pE. Let's say Takanashi chose {1, 1}, {1, 3}, {2, 1}, {2, 2}, and {3, 2} (1-based, define the top-left corner as {1, 1}), than it's a draw. He got -1 +0 -4 -2 -1 = -8 points, while Aoki got -13 points, how can the answer be Aoki?

btw can we really define " play optimally for victory" ? In real world, we'll think much. For instance, we try to avoid our opponents from getting an " L-shape ".

Answers by brute force will keep every possibilities that is a draw, including the unreasonable ones.

F could be solved with PIE and bitset in $$$\mathcal O(\sqrt m + \dfrac{2^kn}{w})$$$ ($$$k = 13$$$ here)

Sorry, what's PIE?

Principle of Inclusion-Exclusion. You can read about it CP Handbook

I used the same logic still i am getting 9 TLE and 2 WA. Can you point out the mistake?? My Submission

int overflow.

SpoilerThanks issue solved.

Got it. Thanks! Also learned it, awesome concept

aryan can you briefly explain your PIE ? I understood till where we represent each number as mask of exponents of prime of M. We essentially want to calculate or sum to all bits set, calculating this in 4^k where k is number distinct primes is easy, how do we use IE here in terms of each bit and what is to be included/excluded ?

And there is an easy greedy solution for G:

Lets iterate $$$i$$$ from $$$1 \to n$$$:

It is not hard to prove that if the solution exists, we can find the smallest one by this.

How to check if the solution exists? We can simply run a manacher to check it.

Time complexity : $$$\mathcal O(n)$$$.

My idea is completely different.

My solution was an extension of my submission of 103388L - Listing Passwords

My idea was as follows -

We create a DSU size $$$2*N$$$.

Nodes in the same component denote that values at those places are same.

We start by merging $$$i$$$ and $$$2*N-i-1$$$ in DSU.

Now, $$$S[L,R]$$$ is a palindrome if $$$S_L=S_R$$$, $$$S_{L+1}=S_{R-1}$$$, $$$S_{L+2}=S_{R-2}$$$, and so on...

Let $$$U=L$$$ and $$$V=2*N-R-1$$$

Because of the above merge nodes, we can also merge $$$U+i$$$ with $$$V+i$$$ for each $$$0 \le i \le R-L$$$

Doing this natively with just one DSU will lead to TLE.

So, we maintain $$$\log N$$$ DSU.

If $$$L$$$ and $$$R$$$ are in the same component in $$$i$$$ DSU. It denotes, $$$(L+j,R+j)$$$ are in the same component for each $$$0 \le j \lt 2^i$$$.

We can split $$$(U+j,V+j)$$$ merging into $$$O(\log R-L+1)$$$ different merges of sizes of powers of 2.

At last, if any conflicting pair is in the same component we print NO. Otherwise, the answer is YES.

We can greedily find an assignment for YES.

My submission

Hacker Move Sir!!

Should the time complexity of the function

`mergeSeg2()`

in your code be $$$O(n \log n)$$$ ?if so, how to prove that it wouldn't TLE ?

great solution, i was trying to do something like this only but rather than checking this(there exists j that j+aj>i) i was trying to greedily put choose si and then choose all j such that j>i && j-aj<=i, but could not think of quick way of doing it, you solution is good.

could somebody help why this submission WA or provide a test case for problem F?

https://atcoder.jp/contests/abc349/submissions/52362844

Your code prints 2, the answer is 1.

Thank you , I shoud handle the case when m = 1 separately.

void yes() { cout<<"Yes\n"; } void no() { cout<<"No\n"; }

int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); string S; string T; cin>>S>>T; int val=0; string t=to_lower(T); for(auto x:t){ size_t pos=S.find(x); if(pos!=string::npos){ val++; } } if(val==3||(val==2&&(T.back()=='X'))) yes(); else no();

return 0; }

anyone please what's wrong in this can't figure it ?? Problem C .

the order of letter in S or T should be same

lac LCA

got,it. thanks!!

can anyone tell me why https://atcoder.jp/contests/abc349/submissions/52364933 got ac while https://atcoder.jp/contests/abc349/submissions/52364920 got wa?

Can someone tell me where I went wrong ? https://atcoder.jp/contests/abc349/submissions/52354647

https://codeforces.com/blog/entry/128367?#comment-1140265

I didn't get this ? okay just a comment ?

why in problem $$$D$$$ always taking the largest power of two that divides works? Any proof?

When will the official editorials be translated into English? Youtube is prohibited in Chinese Mainland..