@ayush201 You could use a Map and store the count of each element. It should have the same complexity.
1 Like
Hi, let me explain the 4th problem. letâs make a couple observations:
1.If we have two connected segments that have a common part [a..b] [x..y], we can create two segments that have no common part with connections between their first and second ends respectively.
2.It gives us next idea(letâs sort our set, and divide it into connected groups), but if the size of a connected group \ge 4 we can split into two groups of sizes [group/2] and group-[group/2], the answer will be smaller, and every number will be connected.
3.Let we have order of set A[1..N], DP[1..i] - the minimal cost to connect prefix A[1âŚi],
DP[2] = A[2] - A[1]
DP[3] = A[3] - A[1]
DP[x] = min(DP[x - 3] + A[x] - A[x - 2], DP[x - 2] + A[x] - A[x - 1]),
we checking where to connect x \implies to x-1, or to x-2.
Letâs rewrite that DP, DP[i][j] denotes connection of the prefix 1..i, j=0 denotes that i is connected to 1..i-1, j=1 denotes that i should be connected to i+1.
DP[i][1] = DP[i-1][0], DP[i][0] = min(DP[i-1][0],DP[i-1][1])+A[i]-A[i-1], for i \ge 3.
But how to maintain add/erase queries? Letâs make one more observation we can keep DP for the segment l..r in a similar way:
DP[l..r][i][j] (r-l\ge1) denotes minimal value to connect everything in the segment l..r, if i=1, l should be connected to l-1, otherwise itâs connected to the segment l..r.
If j=1, r = should be connected to r+1, otherwise connected to the segment l..r.
For r-l==1 and r-l==2 better to recalculate DP with hands.
For r-l \ge 3, we can split segment into to l..m, and m+1..r, and recalculate DP[l..r][x][y] as min(DP[l..m][x][i] + DP[m+1..r][j][y] + (1 - i) * (1 - j) * (A[m + 1] - A[m])).
Only in one case we donât need to take A[m+1]-A[m], if A[m] is connected to l..m and A[m+1] is connected to m+1..r. We need to add some data structure for the solution, we can use cartesian tree/splay tree, but itâs very painful to write that, (I did it, I know what Iâm saying about 
)
Letâs use implicit segment tree(also, we can read all queries, compress the values and use normal segment tree) and for each node to save (min and max on the segment in the segment tree, dp[2][2] and other things), after that we can combine two segments into one, by operations as described above.
We have a solution with complexity O(Q log N) but with huge constant around (~log N). My solution with cartesian is very hard to understand, you can write yours, maybe my debugging solution will help understand whatâs going on: https://pastebin.com/PuFTvuNy
4 Likes
@arun_001 your solution for SMRSTR was almost correct except if input element becomes zero. Divide by zero canât be possible hence avoid dividing by input.Here is what I have changed slightly in your code and got A.C:
https://www.codechef.com/viewsolution/16377847
Hey misha, I edited your answer a little to give some formats (Decent formatting + Decent explanation= Profit 
). Please have a look in case you find concern.
2 Likes
@prince367 The A[i]'s are the keys of the maps. The way data is stored in maps is different. If I insert 10^9 into the map, it goes to the first instead of the 10^9 th position as it would do for arrays.
Youâre welcome 
1 Like
Btw, if youâll use https://en.wikipedia.org/wiki/X-fast_trie you can update your solution theoretically to O(Q sqrt (N log log N)), I donât how it goes practically, next and previous elements can be found in time O(log log N), but insert/erase in O(log N)
4 Likes
Done. Please have a look and verify
1 Like
@bazsi700 - https://www.codechef.com/viewsolution/16378208 i have implemented similar approach here, but it is timing out can you have a look why?
@divyansh_gaba7 The problem is you use std::lower_bound in query, which is O(N) on sets. You should use std::set::lower_bound which runs O(\log{N}), thus replace lower_bound(t[l].begin(),t[l].end(),m) by t[l].lower_bound(m).
I faced the same problem once, and posted a blog about it on CF, where I got explanation for it:
http://codeforces.com/blog/entry/55450
@lunchcook , firstly thank you for the reply, but it is clear that 1 ⤠Xi, Di ⤠10e9, how âwas almost correct except if input element becomes zero. Divide by zero canât be possible hence avoid dividing by inputâ is possible?
Probably the problem is with double precision. However you donât need to precalculate the division into a double, because you can perform standard division each time which takes floor operation anyways.
@bazsi700 , when I change the datatype to double, it is passing 1st test case but when I change it to long double it is passing only 2nd test case, why?(isnât first test case a sub set of 2nd) I just want to know whatâs happening behindâŚ
No, Rating are updated only upto November Cook Off.