Um_nik's blog

Round #576 Editorial
By Um_nik, history, 19 months ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +65
  • Vote: I do not like it

Comments Comments (93)
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Editorial will be published.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
19 months ago, # |
← Rev. 4   Vote: I like it +10 Vote: I do not like it

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,

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ups I am probably wrong

    → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    It's not a bipartite graph and kuhn munkres only works on bipartite graphs. Plus kuhn munkres will probabably TLE. Correct me if I am wrong

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      "...we will build a bipartite graph "

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        We can not build a bipartite graph if the graph contains odd cycles...

        → Reply
        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          Left part — columns Right part — rows

          → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    The graph you are building is bipartite and what you want is indeed max matching, but when you compress vertices you turn $$$m$$$ edges going into $$$m$$$ equivalent vertices into a single edge with capacity $$$m$$$. So the problem you actually solve in the compressed representation really is maxflow and not just max matching.

    → Reply
»
19 months ago, # |
  Vote: I like it -9 Vote: I do not like it

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

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No, the n is the length of the array, not the amount of different values in the array.

    → Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

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.

→ Reply
»
19 months ago, # |
← Rev. 5   Vote: I like it +64 Vote: I do not like it

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

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it +19 Vote: I do not like it

    Let's do subset DP — our state is what primes are still alive. This solution has complexity O(n^2 2^k). __ what about transitions. You can write it like : No need to look at editorial, solve using dp.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      He explicitly gives you the dp states and the transition is just naive. He may assume that people who read this editorial have a basic sense of how dp works (bcs it's a Div1 pF), and the transition is just an (and trivial) exercise. If you really have no idea what he says, then do some exponential states dp problems first, or just simply ask for details here instead of complaining.

      → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    This is absolutely true

    I wanted to say exactly that

    → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Editorial is perfectly fine. He gave the crucial observation required for the recurrence(_Of course, we can cover all rectangle with itself for cost W. To get something smaller than W we have to leave at least one column uncovered — otherwise we pay at least sum of w over all rectangles which is at least W._). If you want everything comprehensively for the simple things, you just destroys that problem for yourself instead of gaining something from it.

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    You keep choosing edges for a potential matching, as long as there is an edge between two unused vertices. If the number of edges you find in this manner is at least n, you found a matching of at least n edges. Otherwise, you have used fewer than 2n vertices and there are at least n vertices remaining, which have no edge between any two of them. Therefore the unused vertices form an independent set of size at least n.

    → Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Update: Accepted when I added ios::sync_with_stdio(false);

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please explain what does this do

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Solution got TL on tests with large input, so the problem is how to read a lot of data fast. You can read how the thing above optimizes the time here: https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio (Using of printf and scanf usually fixes all the issues connected with input/output, so by using them you can protect yourself from stupid TLs)

        → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The time constraints do seem rather tight in this set given the input sizes and expected time complexity...

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You can use count sort and two pointers, but that wasn't needed. My solution is $$$O(q + n \cdot log(q))$$$.

    → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Loop from the last query to the first. If we get query type 2, save the maximum type 2 from the last query to the moment. Otherwise, if we get query type 1, update the value at index x with max(max_type_2_now, value from query) and flag it so we will never update it again.

    After the query done, loop through the entire array. If the cell is not flagged, update the cell with max(max_type_2, A[i]).

    → Reply
»
19 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

@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.

→ Reply
»
19 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    It is quite simpler than that, just maintain a suffix array lets call it maxSuff of size q and for each query of type 2 assign maxSuff[i] to x, where i is the index of that query

    and then run a loop through i from q-1 to 0 and assign maxSuff[i] to max(maxSuff[i], maxSuff[i + 1])

    solution for better understanding 58077496

    → Reply
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Note that the length of the flower will remain constant. When the flower was straight the length = depth of river(d) + H. When the flower is tilted then you can apply Pythagoras theorem where the hypotenuse= length of the flower.

    → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    First of all, you have to notice that green lines are equal.

    Pythagorean theorem for triangle: Ans^2 + L^2 = (Ans + H)^2

    Solve the equation above.

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How is the following solution wrong?

https://codeforces.com/contest/1199/submission/58065770

At worst I would have got an TLE. I think I am doing something similar to the tutorial, simulating the entire problem.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is hard to understand your code. Can you explain your approach? Here's my submission where I just checked for every day in summer whether the rain is minimum on ith day as compared to x days before and y days after. Plz note that it may be possible that and can be i<=x or i>=n-y day since days before 0th day and after n-1th day are not a part of summer and hence will not be observed by citizens.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      From a position, i, I am checking if there are enough days to its left segment which are all greater, and to its right segment which are all greater. The first instance of such a situation is when I output i+1(i is 0 based) as a valid day. The two segment represent left x and right y positions form i for the condition in the question to be satisfied.

      Thank you.

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Note that for indexes i<=x it is enough to check that a0,a1,..a_{i-1} are all greater than ai. So, your segment can be of length less than x for i<=x and same goes for i>=y.

        → Reply
        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Look like that is where I messed up. Gonna sleep now. Will fix it taking into your recommendation into account. The editorial looked pretty similar to simulating the problem which I seem to be doing. Thanks.

          → Reply
»
19 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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...

→ Reply
»
19 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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})$$$.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Number of pairs to check is constant

    → Reply
»
19 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

yeah, Editorial won't be published, but there is a surprise when clicking the link:)

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain 1198A — MP3 in detail?

→ Reply
»
19 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm struggling to find the mistake in my code for problem "1198A — MP3" and my approach continues to fail on 13th test case. Here is the link to my code: https://codeforces.com/contest/1199/submission/58130722. Can somebody look over it please? Thanks.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Understood the mistake, no need for help anymore.

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
19 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
19 months ago, # |
  Vote: I like it -8 Vote: I do not like it

hi, can anyone help me with painting rectangle 1. i dont understand why there is x1,x2,y1,y2 and i saw alot of coder using recursive solution, i dont know where that came from.. thanks

→ Reply
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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$$$.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't need to, but it is faster

    → Reply
»
19 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use pragmas

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is it ok for u to elaborate more?

      → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$50^{5} = 3.125 \cdot 10^{8}$$$, how can it be TL? Moreover, it is divided by 6 because left border is smaller than right and similar things.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I would say that 10^8 is a pretty dangerous bound.... Plus is it ok for you to explain why this number is devided by 6? I know it is pretty intuitive for you but it is kindda hard for me to see.

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        $$$10^{8}$$$ is nowhere near dangerous.

        If we are trying all $$$x, y, z$$$ such that $$$1 \le x \le y \le z \le n$$$, there are ~$$$\frac{n^{3}}{6}$$$ such triplets.

        → Reply
        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for explaining, that helps a lot!

          → Reply
»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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://codeforces.com/contest/1199/submission/58250549

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Can you explain your code after you've assigned the n*ceil(log2(i)) to arr[i]?

    What is savNum? Can you explain that line?

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Any one give me the code for the problem A 1199A — City Day or give me any hint please?

I am not understanding this portion The mayor knows that citizens will watch the weather x days before the celebration and y days after. Because of that, he says that a day d is not-so-rainy if ad is smaller than rain amounts at each of x days before day d and and each of y days after day d. In other words, ad<aj should hold for all d−x≤j<d and d<j≤d+y. Citizens only watch the weather during summer, so we only consider such j that 1≤j≤n.

Thanks in Advance

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is wrong in my code it is giving wa on test case 9 ..in div2 c MP3 ...my submission is https://codeforces.com/contest/1199/submission/58339875

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

guys can soneone help me to understand the problems???I am a beginner

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could somebody help me understand my mistake in problem C-MP3 DIV2 ??

My idea

I choose the right K the number of distant elements in the vector that I shouldn't go beyond if I have already less in my vector ---> 0 Otherwise I sort the vector and I use a map to give me the number of occurence of each element I use two pointers i and j one from beginning and one from the end I compare between these two elements and I change the ones having minimum occurence 58923419 :))

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me welfare state problem in detail

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for MP3 problem, i am getting WA on test case 11, i can't find out the reason. can anybody help? my solution : https://ideone.com/nxUse4

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's probably too late. But I had made the same mistake and was stuck on it for about a day. If you are still curious, the problem will arise in the case where the number of elements on both sides are equal. Make a couple of cases and you'll get the issue.

    → Reply
»
17 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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$$$.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, my solution is wrong and it was already hacked here. Sorry for wasting your time trying to understand it :(

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Need help 1198A-MP3 in my submission

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Deleted

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for div2-C what wrong with my solution WA test case 11th 91696563,any helps ? the ideas: count occurence all element and sort them,then for K-th i calculate their log and compare with 8*I if we get first solution print it because it maximal profit

→ Reply