My solution for C:

Make an array a of n vectors where a_i contains all the painters who paint the ith panel. Find 'total', the total number of painted panels using all of the painters. Then, we make a 2D array 'count' that is initialized to 0. Here, 'count[i][j]' is 'the number of sections that have no one painting them if i and j are removed.

So, loop over all elements of a. If a[i].size()==2, then count[a[i][0]][a[i][1]]++ and count[a[i][1]][a[i][0]]++. If a[i].size()==1, then for all j ≠ a[i][0], perform count[a[i][0]][j]++ and count[j][a[i][0]]++.

Then, simply find the minimum value of count[i][j], and subtract that from total to get your answer. Solution works in O(n²).

This took me an embarrassing amount of time to figure out, and, in addition to my A getting hacked (due to a REALLY embarrassing careless mistake which wasn't caught in the pretests), my rating really took a hit this contest :'( Which is such a shame because I got F pretty early and I thought this contest was gonna be one of the good ones... from 3rd place to 900something, lmao. Someone play Viva la Vida.

Third question is little bit more tricky from last div2"s third question.

Can someone explain problem F with example, I am not able to understand the dp state

My solution for E:

Notice that if the total sum is bigger or equal than W, the answer must be between W-8 and W. So I approached the total sum to between W and W+8 by greedly removing the itens and then I checked if I could remove the difference between the actual sum and the answer, this could be done using smaller knapsacks as the difference would be no more than 16 (W+8-(W-8)).

Could someone please explain me why did my code get accepted? (I have no idea O.o, i thought that a pseudo brute force should work but i'm not sure why or maybe there are weak test cases, idk)

My code

Thanks in advanced.

I am not able to understand the solution of E .can some one elaborate it,please?How the equation could be written like this ? Thank you in advance.

I solved C in something like O(nlog(q) + q^2).

Keep two prefix sums of how many segments are covered by exactly 1 and exactly 2 painters respectively. You build these in O(nlog(q)) with a sweep line over the n segments keeping track of how many painters are in each. Also keep just a single integer keeping track of how many total segments are covered by at least one painter.

Now iterate over each pair of painters and for each pair take the number of segments covered by any painter and subtract from this number the number of segments which only 1 painter (this painter) covers. Then if they intersect subtract the number of segments with exactly two painters covering it (exactly these two painters). This can all be done in O(1) because of the prefix sums built before. In my code I also added back in the number covered by exactly 1 in the intersection but as I'm writing this I see that it's of course always zero as two painters are intersecting, so it's redundant.

code: https://mirror.codeforces.com/contest/1132/submission/50838090

there is a typo in the tutorial of F:clear the string. It should be s_i = s_l.

In C,my thought process was in the following direction. Sort all the pairs according to their interval length and then iterate over each interval along with maintaining a boolean array to mark which sections are painted.Can we reach the solution using this approach,if yes how?

Can C be solved using segment trees? If yes, then can someone please share an efficient solution?

В разборе F опечатка: во втором переходе в формуле должно быть "минимум по всем позициям i, таким что l<=i<=r и s[l] == s[i]", а не "s[i] == s[r]"

My solution For G:

dsu on tree

https://mirror.codeforces.com/contest/1132/submission/50995547

Why is G not Increasing subsequence problem? can someone elaborate the what does the meaning of the problem G in simple way.

G: Managed to squeeze HLD O(n * log^2(n)) with Fenwick tree and binary search 51106103
Solution shortly : go from right to left and keep multiset of possible ending of sequence, add and delete nodes as you go. While deleting node, erase it from multiset, and add it's children to multiset. While adding node, find highest parent which you can improve with HLD & binary search. After finding this node just do += 1 from added node to it.

In the editorial for G, what makes a vertex marked?

Is it "if it has a node that points to it in the current subsegment"?

Can anyone help me. I find the test when a parsed program for problem G gives an incorrect result.

6 6 3 29 5 5 28 6

True answer : 3( a[0], a[2], a[5] )

Answer in program: 2

Or i have mistake?

Can someone provide a test case where this solution of E fail or provide a proof of its correctness? https://mirror.codeforces.com/contest/1132/submission/50862512

Can someone explain problem B ? I am not able to follow the tutorial.

//Solution: DIV2 — C

Simple Bruteforce Solution:

https://mirror.codeforces.com/contest/1132/submission/54590211

In problem F, the recurrence according to the editorial is
f(l, r) = min f(l+1, i-1) + f(i, r)

But since we are combining s[l] with s[i], can we not have a recurrence like:
f(l, r) = min f(l+1, i-1) + 1 + f(i+1, r)

the +1 coming from combining s[l] and s[i] and we start the 2nd recursive call from i+1 instead of i. How are the two different?

Alternative solution for problem D

Binary search the answer. Suppose that you are checking the charger with power $$$x$$$. At the beginning, consider each laptop separately and charge it as late as possible, and keep an array $$$c$$$ with the number of laptops that should be charged each minute. There are two cases:

• $$$x \geq b[i]$$$: in this case, it would be optimal to charge the laptop iff its current power is $$$< b[i]$$$. This is easy to simulate in $$$O(\text{number of charges})$$$.
• $$$x < b[i]$$$: in this case, it would be optimal to charge the laptop only in a suffix of minutes (because the power of the laptop is always decreasing).

Of course, if the total number of charges becomes $$$\geq k$$$, we can just return false.

The problem with this approach is that we are not considering that we can't charge more than one laptop in a minute. However, we can consider the total number of laptops that should be charged until each minute by taking the prefix sums of the array $$$c$$$. The condition is easy: the charger with power $$$x$$$ can be used iff $$$c[i] \leq i + 1$$$ for each $$$i$$$.

Submission: 90456305

For C, https://www.youtube.com/watch?v=4GNUt5unEnM

Can someone please help me figure out why O(N^3) solution for Problem-F is getting accepted ?

Since N is 500 , N^3 should give TLE .

Who would have thought this will be the first question in Cisco's Online Assessment

in the tutorial of F in the last line in formula,Si=Sl not Sr

Added some hints and thought process for F. Clear the String on CF Step.

Essentially the same as the editorial, but also talks about different ways for DP transitions that might not really work, but are the first ones to come to mind during a contest.