DO NOT try to evaluate the difficulty of a task based on its point value. It's often inaccurate.

The same to you

I traversed the array and for every Ai , finded the maximum among Ai-d , Ai+d and added 1 to it in the dp array of size 5e5.

eg. 4 2
3 5 1 2

dp array = [0,0,0,0,0,0]
started with 3 , maximum in dp array among [3-2 , 3+2] = [1,5] is 0 add 1 to it and put it at dp[3] = 1;

dp array = [0,0,1,0,0,0]
for 5 , maximum in dp array among [5-2,5+2] = [3,7] is 1 add 1 to it and put it at dp[5] = 2;

dp array = [0,0,1,0,2,0]
for 1 , maximum in dp array among [1-2,1+2] = [1,3] is 1 add 1 to it and put it at dp[1] = 2;

dp array = [2,0,1,0,2,0]
for 2, maximum in dp array among [2-2,2+2] = [1,4] is 2 add 1 to it and put it at dp[2] = 3;

dp array = [2,3,1,0,2,0]
Maximum among this is 3, Hence 3 is the maximum subsequence

We can optimize a dp solution: dp[i] = longest subsequence ending at ith index satisfying conditions

the transition would be to consider all j < i such that abs(a[j] — a[i]) <= d but we notice that we only need to consider the last j such that a[j] <= a[i] and abs(a[j] — a[i]) <= d and the last j such that a[j] >= a[i] and abs(a[j] — a[i]) <= d

i used a segment tree to manage these indices

I will try to explain my approach. As the elements are less than 5e5, you can maintain a dp over the element values (not indexes). For a given element x and max adjacent difference d, the element just before x (i.e. the previous element of the subsequence, if any) can be between x-d to x+d. I used a segment tree over the dp array, where the query returns the max value in the range mentioned. Then for the current element x, the max length of subsequence ending at that point will the be max value in range (x-d,x+d) + 1. Iterate over all elements in array and take the maximum as answer. Here's my code for reference: link

you may solve it with tree

More like simulation really

https://mirror.codeforces.com/blog/entry/125434#comment-1112843

Define $$$dp_{a_i}$$$ is the maximum subsequence ends at $$$a_i$$$. Its contributor values are the $$$dp$$$ values that ends in element from range $$$dp_{[a_i - d, a_i + d]}$$$ so we want to find the maximum $$$dp$$$ value within that range and add it by $$$1$$$ (by appending $$$a_i$$$ at the end of it). To get the maximum values of these $$$dp$$$, we can use segment tree

Hints for E: Smooth Subsequence

Start with the first DP definition that comes to mind.

$$$dp[i]$$$ is the the maximum length of a smooth subequence ending at $$$i$$$.

Our desired smooth subsequence has to end at some index. Hence, the answer would be $$$max(dp[i]$$$).

How to perform transitions? Notice that the candidates for the second last element are $$$j \lt i$$$ such that $$$|a[i] - a[j] \leq d$$$. Hence, you can naively take contribution from all such $$$j$$$.

Submission

Now, If you're a beginner, most of the problems you might've solved so far would have applied DP on indices. However, it's possible to apply DP on values as well. Let's define an alternate DP definition.

At any point of time, $$$dp[val]$$$ is the maximum length of a smooth subequence whose last element has value $$$val$$$.

Suppose we insert elements one by one. What happens when you see the $$$i^{th}$$$ element for the first time. When an element enters, the subequences can be divided into 2 disjoint sets, one that ends at $$$i$$$ and the other that doesn't include $$$i$$$. By induction, we can assume that the for the subsequences not ending at $$$i$$$, their DP values would've been populated correctly. Now, how does $$$dp[a[i]$$$ vary? The possible candidates for the second last element are all $$$dp[old]$$$ such that $$$|old - a[i]| \leq d$$$. Hence, you can naively take contribution from them.

Submision

For the next part, if you are not familiar with Segment Tree, but understood the alternate DP definition on values, you can consider this problem as solved and come back to it later once you learn segment trees. There's no additional thinking required for the later parts, just blind use of template/library.

Next, notice that you are taking contribution from a continuous range. More specifically, you are looking for a data structure that can support point update and range maxima. Hence, you can use segment tree to optimize it.

Submission

But if the template scares you, you can also use Atcoder Library's Segment Tree.

Submission

I solve it with merge sort tree.

yes, link

Note that it can be solved in $$$O(n \log n + q \log n)$$$ with persistent segtree: initialize segtree with 0s. then set add each element to the segtree in their order (first 1s, then 2s, then 3s...). for querying you can find the latest segtree that has elements <= x and query that tree.

I solve it with merge sort tree. n * log n for build it. (log n)^2 for answer to each query.

Bfs and you need to keep track of both persons positions.

BFS, there are $$$O(n^4)$$$ nodes, each node represents the positions of both players. $$$dp[x1][y1][x2][y2]$$$ represents the minimum number of movees to get to a state where player 1 is at $$$(x1, y1)$$$ and player 2 is at $$$(x2, y2)$$$.

Code

each node is of form x1,y1,x2,y2 so make a 4d array

If $$$a \cdot b = c$$$, then $$$a \pmod{m} \cdot b \pmod{m} = c \pmod{m}$$$. You can select some prime numbers as $$$m$$$, and check if they are same under those modulo. The more prime number you choose, the chance of collision will decrease.

Multiplication is expensive in that problem. They made it less expensive by picking a random mod and did the same bruteforce algorithm but with smaller numbers.

I personally can't imagine the probability of collision but I assume when you have very big numbers, it's hard, when multiplied under same mod that their product will collide with some smaller number that you had in your array, given that you only have 1000 numbers in the array. You could probably force it to collide but not under a random modulus.

BFS on every state that two player can be.

the time complexity off this idea is the number of choose 2 cell of (n^2) cell.

Can Python get you through $$$10 ^ {1000}$$$?

Btw, I passed G in $$$O((n+q\log n)\sqrt{n})$$$ with Ofast, see here.

Just need to fine tune the block length.

For cpp you can use bigint in Nyaan's library. ac submission

You don't even need to break at any point after sorting, it still passes. My submission-code

we can even solve it with merge sort logic without persistent.

I see solutions based on persistent segment tree/fenwick tree and even wavelet tree.

The first G I solved during the contest

Agreeable

But I used some silly references on priority_queue which increased my debugging time (will post it later)

It cost much time that I have no time to solve F

But how to hack if you don't know the modulus he set? Even if he doesn't pass this question, he can change to a different modulus and submit and pass this question again.

It's meaningless to hack hashing algorithm in Atcoder contest, especially ABC.

I think problem D is 1400 problem E is 1900 just because it have data structure and segment tree problem G is 1900 or 2000 as well

I didn't solve it online, but I thought of a offline solution with a segment tree. You can sort the queries in descending order for the x values, and as you go through each query, insert the array values that are greater than the current x into the segment tree, then query the range of the segment tree to get the sum of elements in the range [l, r] that exceed the current x. Then you just take the sum of this subarray and subtract the sum of elements greater.

persistent segment tree/wavelet matrix/merge sort tree can solve it online, but when talking about offline query, you can just use a simple point add range sum query segment tree with sweepline to solve it

I've created a tutorial and practice contest to help you understand how to solve it efficiently if the queries could be answered offline.

I dont think so. I solved with DP + segment tree. and the segment tree used for findind maximum value of a segment of numbers so it cant be handle with Fenwick.

Take a look at Ticket 17334 from CF Stress for a counter example.