Looking forward to ARC !!

As the writer, good luck and enjoy yourself! :D

What's the approximate rating of ARC's problems B & C according to CodeForces rating distribution?

math and counting round

I really suck at counting, but today I couldn't figure out what the 16 different permutations were in C, the most I found was 12 :P

Can anyone list those out please?

Could someone point out what case am I missing in my submission for B?

Submission : https://atcoder.jp/contests/arc145/submissions/33632229

My first AtCoder contest. The problems were good, it was interesting for me. Thanks !

D is just cantor set...

As a contestant, I was not a big fan of A,B,D. Those problems' ideas are not hard to get, but have very annoying corner cases...

Problem D is magic, but I want to know, why the set $$${1,2,4,7,11,...}$$$, which the differential sequence is $$${1,2,3,4,...}$$$ is not the optimal one.

Sequence of pC can be found here.

My friend told me the problem C is in the OEIS, what do you think of it?

void jaiishriRam(){ ll n; cin>>n; string s; cin>>s; if(n==2) { if(s=="BA" || s=="AB") { cout<<"NO"<<endl; return; } } if(s[0]=='A' && s[n-1]=='B') { cout<<"NO"<<endl; return; }

cout<<"YES"<<endl;

} could anyone help me to know what thing I did wrong in A above is the code

Can anyone plz tell me whats wrong here in my submission for problem B

Can anyone please tell me whats wrong here in my submission for problem D?

C could be solved by writing a brute force and searching the sequence on OEIS. Maybe those problems should be avoided by for example having problems parametrized by some more values, or making sure it isn't easy to find on the internet. It makes the contest experience less fun, if the answer is easily found on the internet. Problems A and B were fine. Problem D also suffered from this issue.

C is actually A152029(OEIS).

Why does this code give WA for problem A?

lng dp[3][SZ],n;string s;
lng solve(lng i,lng x)
{
 if(i==n-i){return 1;}
 if(i>n-i){return (x==0);}
 if(dp[x][i]!=-1){return dp[x][i];}
 lng j=(n-1)-i;
 char a=s[i],b=s[j];
 if(x==1){a='B';}
 if(x==2){b='A';}
 if(a==b)
 {
  lng z=solve(i+1,0);
  if(a=='A'){z=max(solve(i+1,1),z);}
  else{z=max(solve(i+1,2),z);}
  return dp[x][i]=z;
 }
 if(j-i==1){return 0;}
 if(a=='A'){return 0;}
 return dp[x][i]=max(solve(i+1,1),solve(i+1,2));
}
int main()
{
 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 cin >> n >> s;
 for(lng i=0;i<3;i++){for(lng j=0;j<SZ;j++){dp[i][j]=-1;}}
 if(solve(0,0)==1){cout << "Yes";rtr;}
 cout << "No";rtr;
 return 0;
}

Here lng=long long, rtr=return 0, SZ=2e5+7

This was my first contest on AtCoder, Can someone tell me, when do the editorials be out ?

nok0 My submission for A get AC but can be hacked with n=4 AAAA My submission

In problem A:

Why is "AB" a valid palindrome or can be changed to a palindrome according to editorial and tests?

for D you can just use brute force to get a set meet the last restriction,and change the largest/smallest number,then add x to all numbers to get sum=M

base 3 solution is beautiful but not necessary

I have different approaches for problem D and E:

D:

Ingore the limit of sum for now. Let $$$f(n)$$$ be the set of integers, one can find that

is good. Now consider the limit of sum. One can find that if we change the $$$\color{red}1$$$ into $$$2$$$, and add $$$1$$$ to some greatest elements in $$$f(n)$$$, it is still good.

E:

We can change $$$A_j$$$ to $$$A_i\oplus A_j$$$ ($$$i \lt j$$$) by performing operations $$$j,i+2,i+3,\ldots,j$$$ in order.

Now we change $$$A_i$$$ into $$$B_i$$$ from right to left, taking the lexicological largest basis each time. It turns out that the number of operations is OK. (It can take up to $$$N-1$$$ operations to change a single number, but each operation will move some basis vectors to the right)

My randomized solution for E:

If the answer is Yes, we first randomly manipulate the sequence for a small number of times, and then operate on index $$$n$$$ more than $$$n$$$ times repeatedly. Then we can (roughly) assume that $$$a_n \oplus b_n$$$ is a linear combination of $$$a_{n-r+1 \cdots a_{n-1}}$$$, where $$$t$$$ is about $$$60$$$.

We can then solve $$$a_n \oplus b_n = \bigoplus_{j \in S} a_j$$$ with Gaussian elimination. If $$$a_{n-1} \not \in S$$$, operate on $$$n$$$ so that $$$a_{n-1} \in S$$$.

Then we operate on the second minimum element $$$t$$$ in $$$S$$$. Then $$$\min S$$$ is removed from $$$S$$$ and all indices between $$$\min S$$$ and $$$t$$$ are added. Repeat this process until $$$S = {a_{n-1}}$$$ and operate on $$$n$$$. Do this for $$$n - 1 \dots 2$$$ and we are done. This solution uses ~60000 operations in randomly generated inputs.

implementation

UPD: More than 1000 random operations at first are needed to guarantee randomness.

Can somebody explain here problem D, how exactly are we constructing the required set after we have figured out the base 3 condition where each digit should be 0/1.

F is some wild generalization of IMO 1995 P6. I like it

Such a magical problem D!

Base-3 representation is such a trick that could perfectly beat the rule of $$$2y \neq x + z$$$.

Next, by first keeping the rightmost digit of all n integers as zero and then change some of them to 1, so that $$$|m - sum| \% n = 0$$$. At the same time, all n integers are still distinct and satisfy the "good set" rule.

Finally, add $$$(m - sum) / n$$$ to each integer so that $$$sum = m$$$, and at the same time, adding the same integer will not lead to any $$$2y = x + z$$$, although they may not belong to the "good set" anymore.

Thanks to the problem writer for coming up with such a clever and unbelievable construction problem!

This round is good, arc should contain magical counting and constructing problems like this.

A different way to think for D.

We can construct as follow (P is a set,initial $$$P={1},len=1$$$): $$$P\to P\cup (P+(2len-1)),len\to 3len-1$$$

$$$P+a$$$ means add $$$a$$$ to all elements in $$$P$$$.

And it can prove that $$$y−x\not=z−y$$$ for every triple $$$x,y,z (x \lt y \lt z)$$$ of distinct elements in $$$P$$$.

(Which is similar to the official editorial)

and we can construct the set with $$$n+2$$$ elements, and enumerate which two to delete. It can solve the problem.

Sorry for asking it late,

Can any one please the explain this line of editorial :

Here, if the elements in P are scanned from left to right, there must always be more left elements than right elements. The number of such arrangements corresponds to that of parenthesis sequences.

What I understood is that, lets say we have (1,2),(3,4),(5,6),(7,8) as corresponding (ai and bi).
Permutation : (1,2,4,3,5,6,7,8) have more right elements(2) than left elements(1) in first 3 elements (1,2,4) but still it can be divided it into two sequences A(1,3,5,7) and B(2,4,6,8), but in editorial it is told that it should not be possible ( as per I understood ) .
I know I have understood it wrong.
Anyone who did this problem or got the editorial please explain the line in blue

Editorial link : Link

sorry for asking late. i'm confused about problem C on how/why the legal arrangement corresponds to parenthesis sequences. (that seems strange to me)

i know we are arranging some pairs like (1,2)(3,4)... , but in my opinion and based on some experiments and some comments like this. i claim an arrangement is legal if and only if there is no pair contains another pair.

for example, (1,2,3,4) legal because pair(1,2) and (3,4) doesn't contains the other. (1,3,2,4) is legal because two pair intersect not contain. (1,3,4,2) not legal because of containing.

however, if you see the pair as parentheses, (1,3,4,2) is legal because they can be mapped to "(())". that's a contradiction (do i misunderstand something?)

however again, when we consider the number of it, these two somehow are equal. here i take some example on n=3 to illustrate.

you see, if we take the view of parentheses, their correspondence(left parentheses and right parentheses) is really strange (at least differ from matching them greedily)

in general, i'm not negate the editorial, but i think i need some more clear intuition to understand this transform