Editorial will be published.

Now we have to choose no more than K consecutive values in such a way that they cover as much elements as possible

Shouldn't it be

Now we have to choose no more than K consecutive values in such a way that they cover as less elements as possible

Could any one please explain (Div1 F) more clearly because I find it actually hard for me to get the proves for those observations.

also (Div1 D) the same thing.

any help would be appreciated.

thanks,

Isn't it better to use kuhn's algorithm for problem Div 1 E if we want to find max matching?

For div1 A doesn't the N change every time you compress?

My alternate solution for C:

Consider the DFS Trees of the connected components in the graph, we can pair the nodes in such a way that only nodes left unpaired are leaves by pairing each unpaired node with a random child, so in worst case we have got a matching of (3*n-x)/2 edges where x is the number of leaves. if (3*n-x)/2 >= n, output this otherwise x must >= n , so output any n leaves. Note that the leaves form an independent set because in DFS tree all non-tree edges go to an ancestor.

Are the top 6 solutions really of only of 3 — 4 lines and rest 6-8 lines or you did a huffman coding on them ?

very short. one can write editorials like : basically we can do it in O(n^5) by using our mind.

also it can be written as : AA! this is easy , look other solutions for it.

morover : It can be solved in O(N)

a step forward : you can use any langauge to solve this problem. solve it on your own

baby giant: see how radewoosh and tourist solved

finally : editorial is missing

Really no intention of writing editorial. wrote just for formality

in div1C/div2E can you prove the line : "Either matching or independent set has size at least n"?

I'm getting time limit exceeded on div1C, even though my solution is O(n+m) like the tutorial says. Is 1 second too short given the input constraints or am I missing an easy way to improve my solution?

Can someone plz explain for Div2/D How can we do it in O(n+q)?

I used another approach in div1-C / div2-E. I'm not sure if my idea is correct. Can someone give me a counterexample (or hack my solution) ?

Submission : 58029374

Idea : sort all the nodes with respect to their degree. First let's try to form an independent set. So we iterate through the nodes and if it isn't marked, then we add it to our list and marked all its neighbours. If the list has size >= n , we're done . If size < n , we do almost the same in order to find a matching. In the same order we iterate through the nodes and if it isn't visited we try to find a neighbour that is not visited. If we find such a pair, we add it to our list of matching and we visit both nodes. But I'm not sure if this matching has size >= n in all the cases.

@Um_nik Please provide code implementations of problems DIV 1:C,D,E.it would be 25 min work for you, but it would be of great help in understanding the code details of the solution.

1198B — Welfare State

Could someone explain efficient way of finding maximum of all x for queries of type 2 after latest query of type 1? I can't invent fast solution unless using sparse table. Thank you in advance.

May someone please explain how the formula was derived in Div2 B? Thanks.

The time limit + test size for 1198A — MP3 is really tight. My Kotlin solutions pretty much match the tutorial solution but this one didn't pass, and this one only barely passes (2 ms to spare!) after I switched to a TreeMap for the counts and an IntArray for the prefix sums. I wonder if anyone could pass this with something like Python.

Edit: And when I tried to bypass storing the values in an a List or IntArray and generate cnt straight away it won't pass test 13, with significant slowdown on test 12. Optimization is a fickle business...

F: Did you include complexity of choosing pair in the final complexity? In my solution, it raises a factor of $$$k$$$ in a determined way. If we are given such pair, mine works in $$$O(2^{2k} + kn)$$$. For each prime in at most $$$2k$$$ primes, choose an element that kills it and is not selected. Now we have at most $$$2k + 2$$$ numbers to consider. Simple bitmask results in $$$O(2^{2k})$$$.

Edit: It is wrong and test cases are weak :). There are $$$O(k^2)$$$ numbers to consider. Another way: $$$dp[mask]$$$ is the earliest time to reach $$$mask$$$ will result in $$$O(k2^{2k})$$$.

The editorial is too concise to be understood. It's perfunctory.

please anyone explain div1 D how take base condition and How do we perform transitionss?

For Div2E/Div1C, Can someone please help with a formal proof for always having at least n matching or independent set?

problem c did the same thing and got WA during the contest

div2D (div1B) is easier than div2C (div1A), and not only for me.

Um_nik, sir why there aren't any solution in the tutorials? I mean one could have a better understanding of the your tutorial after looking at a solution implementing the same idea as provided in the tutorial, I guess.

In Div1-F, You don't need to randomize the algorithm for choosing two numbers from different groups. If $$$n \geq 10$$$ and there is a solution, then there is also a solution in which the first number is in a different group from one of the next $$$9$$$ numbers, so you only need to check these $$$9$$$ pairs. This is true because otherwise, all $$$10$$$ numbers would need to be in the same group, but then you can just remove one of them because $$$k=9$$$.

For Div1 E, O(n^5) seems to be too expensive to pass. Can anyone explain why it would fit into the time constraint?

For problem 1198A — MP3: First, I sort the distinc numbers array and I use binary search to find out how many distinct numbers we should keep exactly. We know that these numbers must be consecutive so I use prefix sum to get the answer. https://mirror.codeforces.com/contest/1199/submission/58250549

I found this guy flashmt use an algorithm with $$$O(n^4)$$$ in this submission 58039307. I had a hard time finding out why it is correct, and finally, I found it could be hacked by this input

9
......###
......###
......###
.........
.........
.........
###......
###....#.
###......

The output should be $$$7$$$ while his output is $$$9$$$.

can anyone tell me in DIV2E/DIV1C how to greedily do matching stuff.

is there any algorithm which i need to learn in order to solve this.

Thanks for reading out :)