sort the array and print last element!!!

hey i was also using the same approach but didnt separate the case of m>n and my sol tled.Nice to see i was half right for the dp.Thanks

C using Digit DP 244113917

thanks and now going to die after this silly mistake...

234400632

I tried to do D with another approach but getting a wrong answer.

Approach->

1. Lets reconstruct the array by merging same consecutive elements to a single element. like for array 1,1,2,2,1,1,2 modified new array will be 1,2,1,2.

2. Let m be the size of the modified array

3.Now if m is even you can form every sum ranging from 1 to total_sum of array(proof is simple)

4.but in case m is odd we can separately check for for the first m-1 groups or last m-1 groups

5.how i checked for the last m-1 groups is if sum of last m-1 groups is >=s then ans is yes otherwise check parity of element in first group and the diff between s and sum of last m-1 groups should be same for yes(coz then you can add elements from 1st group..basically extend your subarray).

6.same goes for checking of first m-1 groups

7.also we have to maintain length of prefix starting with 1,2 and length of suffix starting with 1,2 (can be done either by segment tree or simple multiset which have index of 1 and 2 in the array)

I am getting wrong answer for this approach can anyone explain why??

234328583

1-2,1-3,2-4,3-6,2-6,4-8 ans of this should be 9 but your formula gives 15....am i missing something???

sorry for being such stupid....replaced a[i] with a[tin[i]] and accepted....thanks

4927

can anyone help in f...getting wa on 2..230657380

if it was one string then we would have done dp with kmp but writing 6 kmp functions(in worst case) dont see me optimal in this case...i am also curious for the approach

original problem

here

I was able to come up with a nlogn approach-> Lets create 3 prefix sum array for greater,equal and less....now first of all we check for prefix of length 1. Store the count of numbers index are greater than s[0] in the prefix sum array of greater than...for ex in the above testcase index 2,3,4 have character greater than s[0] so just increase the gretaer[1] by 1 and reduce gretaer[5] by -1 for b...same goes for c,increase greater[1] by 1 and greater[4] by -1 because this c cnt contribute in prefix length gretaer than 3(as we have atmax 3 after it) do it for all the characters gretaer than it....do the same for less than prefix sum array...now if we observe that once a lexicographically gretaer string will always be lexicographically gretaer so there is no need to change in greater and less but the equal character may be included in lesser or greater as we increase their length....so for equal charcaters find the first index where it diff from prefix(can be done in logn by hashing)...let it be of length i...increase equal[1] by 1 and equal[i+1] by -1...now if the next element is smaller than it goes to lesser otherwise gretaer...so you increase the corresponding sum in lesser or greater array

now do pre[i]+=pre[i-1] for all the three arrays

just print gretaer[i] equal[i] lesser[i] for all the arrays for the final answer of a i

Alternative Solution for C 1.First of all you only need to care about first two index.lets see how....there are only four possibility for these two index..either both pos ,both neg, first is pos second is neg, and first is neg second is pos...lets deal with all of them one by one but before that i am assuming that we have picked all the pos numbers which are at odd pos after 2nd index and there are only pos elements left at even index(after 2nd index)...now for the first case when both are neg we can always remove 2nd index neg and now all the even index pos after that comes at odd index so we can add the rest of pos....same goes for the second case when both are pos,you can pick first index and now all the rest pos....in the case of first pos and second neg...remove second index element(neg number) and now all the pos are at odd index....for the last case first is neg and second is pos,one thing is to notice that if you have to remove atleast one pos number to get the pos after it(because then they come at odd pos) now which pos to choose...obviously removing the 2nd index pos number is always favourable as now we can always add all the pos numbers after it...so what we observe that we will always take all the pos numbers after 2nd index and for these two elements we can check locally...see my submission 225272412.Thanks for reading upto here.

use map

Really Nice Problem....did it using hld on tree(made by using above mentioned concept)217554715...thanks for sharing these...learned something new as well as interesting

ya really cool...upvoted...maybe u can link this comment in your blog

In the question mentioned above by you...lets take the first testcase first example...how will you decide between adding (3,2) aur (3,6) as adding (3,2) will affect the answer...so that why i used the second node for sorting

In Case of equal weights of a.first and b.first....do we have to sort by weight[a.second]<weight[b.second]

here

nice approach....nice implementation part(that queue one thing was awesome)

Can anyone share the approach.. i tried to think that max length of subarray can be 900 and then iterating over all those 900 length continous subarray for checking..but it a tle

no finished today ig...it was oa of sprinkler

Real Constraints

i assigned priority by using a little trick lets make a jump array initialise jump[i]=i+1 now we will iterate for these m segments for the ith segment(li,ri) lets start from li so if it is not visited(make a boolean bitset) then we will assign the current_priority to it and increase our current_priority by 1 now make li=jump[li] and update jump[li] as max(jump[li],ri+1)

do these for all segments

what if increasing ai-2 by 1, ai-3 becomes equal to ai-2

got accepted by using unordered_set for the pair....this question has a very tight constraints...firstly i have to use two hash functions otherwise it was colliding and then this unordered set thing for pair...i didnt know that we have to use a custom hash function for using unordered_set.....overall learned many things from it

hey it is still giving me tle.Could you please tell me what am i doing wrongsubmission

ya i was also getting wrong answer due to collisions so just used two different numbers 31 and 67 with modulo 1e9+7 and it got accepted

could you please explain a little bit more deep

agreed

Can you please elaborate more.mainly on the brute force part how you are checking a valid set

very observational tasks....found c easier than a and b

Another approach to solve E 1)Let our initial answer be k itself. 2)Now count the no of numbers which contain 4 until k. 3)Add this count to k(our new ans). 4)Now count the no of numbers which contain 4 until our new answer and subtract this count by previous count(as prev count was taken into consideration at step 3). 5)update our value of ans by adding the count. 6)Repeat until our ans is not updating to a new value.

Basically a Gauss-Seidal Approach.

200812209

thanks....will try another approach

Ya i got the mistake , but could there be any third string along with these two such that ans will not exist for three of them. Coz i guess my ans will come for the third string

hey what about my rating??????????

same here

can anyone help me in my code.Here is my submission 158595810 1348B - Phoenix and Beauty Instead of inserting the element in array a i have printed them directly