PROBLEM LINK:Author: Ramazan Rakhmatullin DIFFICULTY:Easy PREREQUISITES:Two pointers PROBLEM:You are given 2 arrays $W = [W_1, W_2, \ldots, W_N]$ and $C = [C_1, C_2, \ldots, C_N]$ with $N$ elements each. We say that a range $[L, R]$ is unique if all the elements $C_L, C_{L+1}, \ldots, C_R$ are unique. The goal is to find the maximum possible sum $W_L + W_{L+1} + \ldots + W_R$ for a unique range $[L, R]$. EXPLANATION:First of all, notice that in both subtasks, values of $W$ are up to $10^9$, which means that the final sum can exceed $32$bit integer range, so you should use $64$bit integers to represent the sums. Subtask 1In the first subtask, there are up to $100$ test cases to solve, but we know that the sum of $N$ over all these test cases doesn't exceed $10^4$, so we can apply the following quadratic time approach. For all $L = 1, 2, \ldots, N$, let's iterate over all $R \geq L$ such that a range $[L, R]$ is unique and update the result during this iteration. The key observation here is that if for some $A$, the range $[L, A]$ is not unique, i.e. there exists two indices $L \leq i < j \leq A$, such that $C_i = C_j$, then any range $[L, B]$ for $B > A$ is also not unique. In order to track uniqueness of elements in a range during iterations, we can use a hashtable, or even better, after noticing that values in $C$ are nonnegative integers less than $N$, we can use a simple boolean array for this purpose. The following pseudocode illustrates the above appraoch:
The total time complexity of this method is clearly $O(N^2)$ for a single test case, which is sufficient in this subtask. Subtask 2In the second subtask, there are also up to $100$ test cases to solve, but now the sum over $N$ over these test cases doesn't exceed $10^6$. Thus we need a faster approach, ideally a linear one. The key observation is to notice that values in the array $W$ are nonnegative, which means that if a range $[L, R]$ is unique, and we can extend it in any direction, then we can always do that. It follows, that if we have a unique range $[L, R$], we want to extend in both directions as much as it stays unique. This leads to the following approach: Let's start with $L = 1$. We are going to use a boolean array for tracking already seen elements in the current range  similarly as in the solution for the first subtask. Now, let's find maximum $R$ such that the range $[L, R$] is unique. It means that either $R = N$ or value $C[R+1]$ appears in range $[L, R]$ in array $C$. We do this by simply iterating from $R = L$ until we find this maximum $R$. Now we know that $[L, R]$ is a unique range and we can update the result with its sum, which can be computed while iterating. Now comes the second key observation. If $R = N$ we are done, because there are no remaining elements to the right. Otherwise, in order to extend the current range to the right, we have to find the minimum $i \geq L$, such that $C[i] = C[R+1]$, update $L$ to $i+1$ and start extending the right endpoint of the range from $R$ while it remains unique. We repeat this process until $R$ becomes $N$. The following pseudocode illustrates this approach:
The time complexity of this approach is $O(N)$ for a single test case because both $L$ and $R$ can be updated at most $N$ times in the loops and the total complexity is dominated by the loops where these values are updated in every iteration. This method is often called "Two pointers" approach and it's useful in approaching many problems, even very advanced ones. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 24 Jun '17, 04:08

it seems to me that my solution is more ergonomic, and works for O(N) here is the link : https://www.codechef.com/viewsolution/14333217 the main idea was : 1) in 2) due to 1 ≤ N ≤ 1000000 , 0 ≤ Ci < N, we are able to have a mask array with Nranged size and keep in the 3) the last movement was :
for each test we do:
answered 25 Jun '17, 07:03

I think my solution is easier to understand and the code is also simple. answered 25 Jun '17, 11:05

Could you please tell me where I went wrong? This is the link to my code https://www.codechef.com/viewsolution/14336038 answered 24 Jun '17, 23:25

I think my approach was the same. Just instead of a boolean array, I kept checking elements with a set, which is less memoryconsuming I think. Still, the code couldn't pass the second subtask because of TLE. Can anybody point out the mistake? answered 24 Jun '17, 23:26

If someone has some test cases cant they please help me out? My code (https://www.codechef.com/viewsolution/14336258) got WA I'm not able to understand why. Thank You answered 24 Jun '17, 23:41
1
(25 Jun '17, 01:07)
Thanks a lot siddharth bro :)
(25 Jun '17, 14:27)

I think i have also used a O(n) approach but i am getting a wrong answer.Could anyone help me out what is wrong in my code or for what test cases it is giving wrong output? Here is the link to my code:https://www.codechef.com/viewsolution/14336093 answered 25 Jun '17, 11:33

is really second approach is O(n).. i can see that, its O(n^2)...is i m right? there exist last while loop as well which is as follows
here it is somewhat taking extra time than o(n)... can anyOne explain what exactly time Complexity of second approach.. because here loop inside loop exists which suggests its O(N^2) answered 25 Jun '17, 12:22

@hemant_dhanuka Regarding time complexity in second approach answered 25 Jun '17, 13:45

can somone please tell where i went wrong? answered 25 Jun '17, 13:47

Can anyone help why one is giving runtime error and other AC runtime error : https://www.codechef.com/viewsolution/14342187 AC : https://www.codechef.com/viewsolution/14342108 what am i doing wrong for runtime error solution? answered 25 Jun '17, 18:32

I don't understand why this is showing Wrong answer..
answered 27 Jun '17, 11:21

In subtask 1 How is O(n^2) Approach possible??? Time Complexity is O(n^2 * T) answered 27 Jun '17, 19:24
