As a contestant, I will participate for sure.

div. 4 especially for turquoise who will not be able to perform well at the div. 3 and will become green

What are the problems?

tree!!

sir can you give the hint for the third question of contest how to think for the problem and the basic apporoach should come in our mind it will be greatful if you give me some guidance. Hope for the reply sir thank you

Me too(^_^)

looks like a dog to me lol :)

:(

Then make stronger solutions?

Is E really that easy for 2700+ (I am sure it would go above 3000 by the end of the contest) people to solve?
I can't think of anything at this point :')

Do I need to know dp to be able to solve E ?

Brute Force O(n*n*logn)

Note that the sum of each segment needs to be same. So given the total sum as $$$S$$$, we must partition the array into $$$P$$$ segments with sum $$$\frac{S}{P}$$$. Now we can bruteforce by iterating $$$P$$$ from $$$1$$$ to $$$N$$$. (remember to skip when $$$P$$$ cannot divide $$$S$$$)

Dichotomous answer and O(n^2)check. So it is O(n*n*log(n))

You can use DP.
Video Solution explaining the DP Solution.

how to solve E?

Same for me here, but with F. Got my submission accepted after the contest had already finished. It was tense.

look carefully , every element of array may/maynot have the potential of being the right/left endpoint indicating the length of a segment so from each element we can have at most 2 probable segments, so we can get highest 2*n segments ,then the problem comes down to figure out whether you can build an array of n elements using some of these segments which are non-intersecting ; you can do that through dfs which I did

For every element just check if it can cover the area to it's left and right. If it covers the area to it's left then update the value of that position (dp[i]) with dp[i-left-1] and if it covers the area to it's right then update the value of dp[i+arr[i]] with dp[i-1]. And check for dp[n] at the end. Here is my submission 175628640

Hi can you please explain your approach of problem F. Thanks

probably the last one

F or G

you have miscalculated the complexity, it's not n * n

Two nested loops is a naive approach and yeah too slow at O(n^2). But if you think about how updates to your dp table are happening there, you can massage inner loop's updates into the outer loop and have just a single loop for O(n) runtime.

Alternatively think of it as a graph problem, two edges at each index going back/forward, determine if start is connected to the end.

Really cute problem btw with cute simple solution.

just try setting n to 2e5 and all values to 1.

That's Why No of Accepted Submission Increases for Problem C-D

your code editing is a little bit ugly

why do you think it can be hacked?

The statement is perfectly clear, and illustrated with examples. I have also failed to read questions properly in the past and paid the price, but that is not the fault of the author.

Do not agree with that honestly.

Kinda cringe tbh

Yes, clearly.

Maybe you're just too good? Lol. There's only 351 solves atm

you can split the array in 2 parts every time. and you have to check that the elements in first part is always less than second part for every subtree. if not, increase the count and repeat the same process till the leaf of the tree.

Use recursion for solving the problem.

You can take reference from my code-> https://mirror.codeforces.com/contest/1741/submission/175603313

In one way, if you know merge sort, you basically know the solution for this problem.
Would recommend you to learn the idea of merge sort from GFG or someplace else and try it on your own.
Just for reference 175631361

Think of divide and conquer technique.

That's insane, do you think you can describe your approach?(I only managed to solved it with bitmasks)

Try think this way: there is no colors in this problem, task is the same but without segment colors.

let's assume that the segments are sorted in increasing $$$l$$$. You can split the problem into two parts -

i) find the greatest $$$r[j]$$$ ($$$j$$$ < $$$i$$$) among all $$$l[j]$$$ which are less than $$$l[i]$$$ and with different color than $$$color[i]$$$

ii) find the least $$$l[j]$$$ ($$$j$$$ > $$$i$$$) among all $$$l[j]$$$ greater than $$$l[i]$$$ and with different color than $$$color[i]$$$

Let's see how we can solve the first part. We can store an array $$$mx$$$ where $$$mx[k]$$$ indicates the greatest $$$r$$$ value for a given color $$$k$$$. Store this $$$mx$$$ array in a segment tree so that we can retrieve the maximum value of $$$mx$$$ with updates. Now, for this case, you may wonder why you would actually require a segment tree and not just maintain a set or something similar. The thing is, if we are at the $$$ith$$$ segment, the maximum $$$r$$$ value of any segemnt $$$j$$$ ($$$j$$$ < $$$i$$$) might be of color similar to that of the $$$ith$$$ segment. In which case, we have to find the max $$$r$$$ value of a color which is not that of the $$$ith$$$ segment color. Say the color of the $$$ith$$$ segment is $$$k$$$. We can do this by updating $$$mx[k]$$$ in our segment tree to some very small number and then finding maximum in segment tree and later resetting $$$mx[k]$$$ to what it was initially. Ie make sure that $$$mx[k]$$$ is ignored in our max segment tree.

Now, as we move through all $$$i$$$ in increasing order of $$$l$$$, we can easily figure out the maximum $$$r$$$ value of a different color using our segtree (explained above). Once we find this maximum $$$r$$$, we we can update the answer for this segment to $$$max(0,segment[i].l-max_r)$$$

The second part of our problem can be solved in an almost similar way, except we would require a minimum segtree to find the minimum $$$l$$$ value of a segment $$$j$$$ ($$$j$$$ > $$$i$$$) of different color. Alternatively,we could use the same segment tree (max segment tree) except store values in the segment tree as (-(actual value)), now, the abs of the max value will be the least $$$l$$$ value. Once we find this minimum $$$l$$$, we can update the answer for this segment to $$$max(0,min_l-segment[i].r)$$$ We'd also have to make some minor changes like redefining $$$mx[k]$$$ to minimum $$$l$$$ value for a given color $$$k$$$

submission

I think DP solution much easier to understand

But DP idea almost like DFS solution. So let me tell you the DP idea first and then DFS

1) DP solution. Let $$$dp_i$$$ be the True, if the array $$$b[1..i]$$$ can be build by array $$$a$$$ and False otherwise. Our base is $$$dp_0 = True$$$. Then, if $$$dp_{i-1}$$$ is True that means we can build array $$$b[1..i-1]$$$, that we have to do with $$$b_i$$$? Let's say it's the count of numbers in next subarray, we set the $$$dp_i+b_i = 1$$$. And if $$$b_i$$$ was the counter in previous subarray we need to check if we can build array $$$b[1..i-b_i]$$$. The answer is in $$$dp_n$$$ now.

2) DFS solution. Let's now say from index $$$i$$$ we can go to indexes $$$i+b_i$$$ and $$$i-b_i$$$. Because $$$b_i$$$ is count of numbers in next or previous segments. Let's call this edges and $$$i$$$ as nodes. We have to be able to move from node $$$1$$$ to node $$$n$$$. The answer is $$$dfs(1)$$$ or $$$dfs(n)$$$ now.

Its a MergeSort problem, you just have to keep track of the left and right part for each segment using a 2d array and then on each iteration see if you can merge i and i+1.

You can survive only by using dp.Memorization is also not enough if you use dfs.

I tried to submit it again and it is giving TLE now but in standings it is an accepted solution even after system testing :(

As far as I know, it should be rated for you.

As far as I know, in Edu Div2 rounds you get +100 points for successful hack and -50 for unsuccessful. So yes, in Edu Div2 you improve your score.

In Div3/4 I don't think that is the case, since it's not based on scores but amount of solved problems.

I think they find a general case which might hack some of the approaches, then check for that specific problem if it's implemented via the approach you know how to hack. Not certainly sure tho.