reminds me of that round 1090

Bro don't speak Chinese on Codeforces

If the round announcement doesn't specifically say there will be interactive problems then there won't be interactive problems

Agree.

who ask bro?

skill issue, next

i have O(n) DP-like solution, working from right to left

Its simple DP. You have to compute a helper DP at indices where $$$a_i = b_i$$$, like if you both had watched that episode at that index then how much further segments they can still watch before you find a bad pair. And then use this DP later for smaller $$$i$$$. Sorry if explanation is bad but hope you get the idea.

At each index $$$i$$$, let $$$dp_j$$$ be the number of subarrays ending at index $$$i$$$ in which we've already watched $$$j$$$ movies ($$$j$$$ can be 0). Based on $$$a_i$$$ and $$$b_i$$$, we only need to update a few elements in the $$$dp$$$ array for the current $$$i$$$, and then we add all values from $$$dp_j$$$ to the answer. This can be done efficiently by keeping track of the sum of $$$dp$$$ at each point in time, making it $$$O(1)$$$ for each $$$i$$$ and $$$O(n)$$$ overall.

I think the easy way to think about this is that each $$$(i, i)$$$ determines what we are interested in next in $$$(i+1,i+1)$$$, $$$(i+1, x)$$$ or $$$(x,i+1)$$$. This creates a single outcoming edge. Having this sort of tree structure, you can just DP on it to know where the chain ends if you start in some $$$(1, 1)$$$.

375107486

Backwards DP. Let dp[k] be max day that Alice and Bob can reach if they enter the current day with k episodes watched so far. For each day i, if a_i = b_i (say =k) then the max day they can reach from state k-1 is the same to max day they can reach from state k, so dp[k-1] = dp[k]. Otherwise, they cannot even progress past the previous day, so dp[a[i]-1] = dp[b[i]-1] = i.

Answer is sum of dp[0] — i for each i. Time complexity is O(n) for each test case.

You can keep track of valid left points for every point i by storing their mex value if they survive till point i. When entering a position you can create a new starting position. If a[i] != b[i], all left points whose mex value are a[i] or b[i] dies at this point, so you just need to add all left points that are alive at every index i.

375130209

why so overkill?

notice that for a given person, we have 5 cases: (1) the optimal p is 0, and optimal c is 0, (2) optimal p is t+d, optimal c is 0, (3) optimal p is 0, optimal c is t+d, (4) optimal p and c are both t+d (5) the optimal uses the raw value of p+c

what can be done is to sort the values c[i] by the key p[i], and vice versa, then build suffix and prefix minimums on them. this allows us to efficiently query the first 4 cases, by asking for example "what's the minimal p-value amongst all i such that c[i] >= t + d?". you find by binary search the location of first c[i] where c[i] >= t+d, then use the suffix minimum to answer the query.

for the final case, we can just store a segment tree on the values of p+c, sorted by p[i]. then make a query in the range [t, t+d] for the minimum. why does this work, even though the minimum might use a c > t_c? it works because our other 4 cases will have caught that, so even though p+c ≠ I(p,c), it doesn't affect the answer as it is larger than the actual value and we are taking mins

Get a dp array at each i where a[i] == b[i] which means the right bound if we have already watched 1..=a[i] movies. The transition would involve cases like the next a[i]+1 in both a and b having the same index or not.

Then for each starting L, find the next position of 1 in both a and b, if they are the same index, ans += dp[ix] — i, else ans += min(ix_a, ix_b) — i.

If I understood your code correctly, it will TLE in an input of this form:

n
[1 1 1 1 1 .. (n/2) times] [2 3 4 5 ... (n/2)+1]
[1 1 1 1 1 .. (n/2) times] [2 3 4 5 ... (n/2)+1]

Since for each 1 you are going to the next largest integer, this code will take $$$O(n^2 \cdot \log n)$$$ time (for each 1, you are traversing the $$$\frac{n}{2}$$$ list of numbers from $$$2 .. n/2 +1$$$)

This is my O(nlogn) solution 375186318

To handle cases like [1 1 1 1 1 .. (n/2) times] [2 3 4 5 ... (n/2)+1]

Use: if(a[i]==a[i-1])curr_r = previ_r;

idk I did the same sol as u and kept screwing up on test case 2

For this test case 1 1 1 2 2 2 2 2 3 3 3 3 2

• count of 1 + count of 3 before the last 2 = 7
• count of 2 after the minimum index of 1 and 3 = 6
• if you remove first first 3 ones and last 2, cost = 4 and you still get a valid ordering.

Logically speaking, you are only considering 2 strategies: removing ALL ones & threes, or removing ALL twos. You are not considering any hybrid strategies.

I used the same idea and got WA2 :(

375152428

I spent too much time for B but can't solve it. Feel it's harder than C :)

And you didn't even participate.

me too :(

I've forwarded this issue to the admins, they are investigating it currently. Your submission will be rejudged

Try:

1
1121222

easily

i think its long queue thats why.my one solution is in queue but now i paste same solution that is accepted

with the amount of time system testing took I think you will officially be master next year

congrats dude

Same .showing as unrated for mine too though i participated as rated

what