Good luck to all participants.

I keep participating in coding contests like a true code connoisseur, gracefully decreasing my rating with each attempt. It's like I have a secret mission to redefine the concept of 'progress' in the coding universe!

java 20 when

The first question was quite interesting :)

The webpage keeps returning 403. Does anyone have the same problem?

Is the website down for about half an hour? I received 403 status code.

Is this closer to div2 or div1?

D seems impossible :/ , would appreciate it a lot if anyone could explain it after the contest , I feel like there is some interpretation or observation that makes things much easier , couldnt noticed it tho

$$$D$$$ has very complex model. It took me much time to understand, what happens. There should be more complex samples, as with such first sample I spent much time writing solution, which finds incorrect thing.

The problems are really interesting and challenging. (for me)

I think I've just participated in ParityForces.

AC'ed E 47s after the contest ended. My contest ruined by the corner case for [L, R]=[1, n].

E is a very good problem, though it would be better to add some corner cases in the sample :(

Can anyone tell what's the problem in my code? It passed all test cases except 2 :(.

The question in B- Switching Travel.

Code: https://atcoder.jp/contests/arc164/submissions/43434476

I used the same logic as given in editorial, find cycles and checking if there exists a cycle with alternating node color except 2 consecutive nodes.

in problem B I find all cycles in the graph and then for every cycle, if is from pattern 10101... or 010101... etc , I test all possible starts in the cycle for example 100 is also valid because I can express it as 010 if i start from second position get all test ac but wa in the last test can anyone provide me a counter test for my solution because i can't find it

My code for B:

...
bool h[400012];
int de[400012];
bool alr[400012];
int cnt=0;
bool dfs(int x,int d,int y)
{
	cnt++;
	if(!y) alr[x]=true;
	if(de[x]!=-1&&de[x]%2!=d%2&&y==1) return true;
	if(y>=2) return false;
	if(de[x]!=-1) return false;
	de[x]=d;
	int ii=fdlks.first[x];
	while(ii!=-1)
	{
		if(dfs(fdlks.sds[ii].to,d+1,y+(h[x]==h[fdlks.sds[ii].to]))) return true;
		ii=fdlks.sds[ii].next_side;
	}
	de[x]=-1;
	return false;
}
...

This one got AC, but get $$$cnt = 1.26 \cdot 10^8$$$ in Test 40, which is obivously not $$$O(N)$$$. Is it $$$O(N^2)$$$?

(Whole code: Submission 43433400)

Can anyone provide the logic or observations in problem D, I was not able to think of any during the contest.

Damn! Miss ARC D because I use = instead of +=.

Anyway I debugged this 15 minutes after contest, that is not a short time so I deserve it.

WA: https://atcoder.jp/contests/arc164/submissions/43435075

AC: https://atcoder.jp/contests/arc164/submissions/43436250

How do you solve A? I followed the logic in the editorial but still got WA. Here's my last submission: https://atcoder.jp/contests/arc164/submissions/43432250.

For E, I had a O(n^3 + Q) solution, with dp of the form:

dp[L][R] = min( max(combine(dp[L][k], dp[k+1][R]), {1, #queries intersecting [L,R]*2})) over all k inside [L,R].

Can this be optimised by knuth as shown in here: https://cp-algorithms.com/dynamic_programming/knuth-optimization.html#generic-implementation ?

It seem to give WA for some reason. Is the cost function and combine function (instead of simple plus) valid to be used here? (Brute n^3 solution seem to work and give TLE instead so the dp should be correct)

Thank you for your participation!

Enjoyed the contest. Had fun solving D. I see most of the people tried to do it using combinatorics I had a rather simple solution using dp. I had two dp , $$$dp[index][balance$$$ $$$till$$$ $$$index$$$ $$$i]$$$ = sum of distances till index i, $$$ways[index][balance$$$ $$$till$$$ $$$index$$$ $$$i] =$$$ # of strings with the current balance. The transitions would be $$$dp[index + 1][balance$$$ $$$till$$$ $$$index$$$ $$$i$$$ $$$+ (s[i] ==$$$ '+' $$$? +1 : -1)]$$$ += $$$dp[index][balance] + ways[index][balance] * abs(balance + (s[i] ==$$$ '+' $$$? +1 : -1)$$$.

any one can give me hints or the full idea for C?

Whats the deal about drafts by gpt-4 ?
Could it really solve even the last question ...

I think I have a cleaner and better solution for problem D. (I read other people's solutions as well as the editorial, but I didn't understand anything from them, so I think it's worth to mentioning it.)

You can just skip this to the end and see the code and think about it to see how it actually works!

Simpler Version (sub-problem)

First suppose our string is fixed and there is no $$$?$$$ in it.
We call this string $$$s$$$.

We will use Double Counting Technique (in CP, it is known as Contribution to the sum Technique).

Definitions:

• i-th Gap: i-th gap is the gap between number i and i+1 in 1-dimensional coordinate which in the initial state i-th ball and (i+1)-th ball placed in them.

• Ball Pair: The pair of a particular ball is a ball in which the two cancel out each other in some position and both disappears.

• $$$ans_i$$$: The sum of the movements that the balls made on the i-th gap.

There are two cases for a ball moving in i-th gap:

1. If the ball disappears in this gap, it can also be concluded that its pair is also moving in this gap from opposite direction and somewhere in the middle they meet each other and will disappear. In this case the ball and its pair both together contribute 1 to the $$$ans_i$$$.
2. If the ball doesn't disappears in this gap, it can also be concluded that its pair doesn't even enter in this gap. In this case we contribute 1 to the $$$ans_i$$$.

Actually in both cases the ball and its pair both together contribute 1 to the $$$ans_i$$$.

Now, using the above facts, it is enough to know how many balls enter in the i-th gap from the left side of it. This number is equals to absolute of cumulative sum of ballses values in left of this gap (*).

Finally we have $$$p(s) = \sum_{i=1}^{n-1} ans_i$$$.

Original Problem

But now how to solve the original problem!?

Definitions:

• Balance of a prefix: sum of +1 and -1 in that prefix.

• Pattern: a string $$$s$$$ with size $$$i$$$ has pattern of the prefix $$$t[1...i]$$$ if it can be obtained from $$$t[1...i]$$$ by only replacing $$$?$$$ with $$$+$$$ or $$$-$$$.

• $$$f(i, b) := $$$ number of strings which has pattern of prefix $$$t[1...i]$$$ and the balance of them is $$$b$$$.

• $$$g(i, b) := $$$ sum of the $$$\sum_{j=1}^{i} ans_j$$$ (with the same definition as to solve the simpler problem that doesn't include $$$?$$$.) for every possible string $$$s$$$ which has the pattern of prefix $$$t[1...i]$$$ and the balance of that is $$$b$$$. (Note that this value actually stores the sum of partial sum for $$$ans_{j=1...i}$$$)

Now to calculating the values of two functions $$$f$$$, $$$g$$$ recursively we need to consider three cases:

"$$$\times |b|$$$" part for each case comes from the sub-problem that we solved.

1. $$$t[i]= \space$$$'$$$+$$$':
   • $$$f(i, b) = f(i-1, b-1).$$$
   • $$$g(i, b) = g(i-1, b-1) + f(i-1, b-1) \times |b|.$$$
2. $$$t[i]= \space$$$'$$$-$$$':
   • $$$f(i, b) = f(i-1, b+1).$$$
   • $$$g(i, b) = g(i-1, b+1) + f(i-1, b+1) \times |b|.$$$
3. $$$t[i]= \space$$$'$$$?$$$':
   • $$$f(i, b) = f(i-1, b-1) + f(i-1, b+1).$$$
   • $$$g(i, b) = (g(i-1, b-1) + f(i-1, b-1) \times |b|) \space \space + \space \space (g(i-1, b+1) + f(i-1, b+1) \times |b|).$$$

• Base Cases: $$$f(i=0, b=0) = 1, \space \space g(i=0, b=(-n)...(+n)) = 0.$$$

Now we can just implement this two functions using $$$dp$$$ and also shift $$$b$$$-dimension by $$$+n$$$ to avoiding "Out Of Memory Error".

Here is my submission (using forward dp)

(*): We don't care about how actually pairing of balls done before the i-th gap we just care about how many of them remains unpaired in left of i-th gap, the number of them is the number of remained + or - in left of this gap (or to right depend on how you implement it) which is equals to absolute of cumulative sum of ballses values in left of this gap. but why? If you are ok with its intuition, you don't need to read the rest of this section.

Here we should see where is pair of a ball actually located? if you use two stack one for '$$$+$$$' and call it $$$s_+$$$ and one for '$$$-$$$' and call it $$$s_-$$$ then each time you encounter a '$$$+$$$' you should pair it with back of $$$s_-$$$ if it's not empty otherwise you should add it to back of $$$s_+$$$ and same thing for when you encounter a '$$$-$$$'.

But again, why? We can use kinda inductive prove, assume that all pairs are correctly found before the i-th gap,
now without loss of generality suppose we are going to pair a '$$$+$$$' to a '$$$-$$$' at the back of $$$s_-$$$, this means that both of them must move towards each other and eventually meet somewhere in the middle so it's enough to prove that $$$F$$$ of our '$$$+$$$' is negative and $$$F$$$ of our '$$$-$$$' is positive.

We already know $$$F$$$ of our '$$$-$$$' is positive, because it is not paired with anyone on its left side, which means that the sum of its left side is a non-positive number suppose this number is $$$X$$$ then it means that $$$F$$$ of our '$$$-$$$' is equals to $$$(X - (0 - X + 1)) \times (-1) = -2X + 1 \gt 0$$$ ($$$X$$$ is the sum of its left and $$$(0 - X + 1)$$$ is the sum of its right and it comes from the fact that the total sum is $$$0$$$).

And now what about $$$F$$$ of our '$$$+$$$'. In fact, because everything we had between these two are paired together, so the number of '$$$+$$$' and '$$$-$$$' between them is the same, so we can ignore them while calculating $$$F$$$ of our '$$$+$$$', so it means that $$$F$$$ of our '$$$+$$$' is equals to $$$((X - 1) - (0 - (X - 1) - 1)) \times (+1) = 2X - 1 \lt 0$$$. $$$\blacksquare$$$