awoo's blog

By awoo, history, 8 days ago, translation, In English

1680A - Minimums and Maximums

Idea: BledDest

Tutorial
Solution (BledDest)

1680B - Robots

Idea: BledDest

Tutorial
Solution (BledDest)

1680C - Binary String

Idea: BledDest

Tutorial
Solution (BledDest)

1680D - Dog Walking

Idea: vovuh and BledDest

Tutorial
Solution (vovuh)

1680E - Moving Chips

Idea: vovuh

Tutorial
Solution (vovuh)

1680F - Lenient Vertex Cover

Idea: BledDest

Tutorial
Solution (awoo)
 
 
 
 
  • Vote: I like it
  • +45
  • Vote: I do not like it

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone share his sliding window approach for problem C ?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Reduce the problem: find the lowest cost substring, cost = max(0's, total 1's — 1's)

    The cost of the final optimal substring will either be contributed by 0's or by 1's. Let's binary search on the best answer that can be contributed by 0's and then binary search again on 1's, then we take the minimum of the two.

    To check if an answer g is possible, we run sliding window. For example, let's say we are currently binary searching on best answer contributed by 0's. We can expand the window until we have more than g 0's in the current window. Then we can shrink it from the left until we have exactly g 0's again.

    here's my submission: https://codeforces.com/contest/1680/submission/157099290

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sliding window / two pointers approach without binary search, runs in O(n) time, in C.

    Let our window represent the string left after deleting the first i elements, and the size - j elements from the right.

    We know that for a window starting at index i, if we're increasing the window size, then the best cost we can get is when the number of characters 0 in our window is equal to characters 1 outside the window. This is because if we keep increasing our window size then the number of character 0 in the string will keep increasing, and a smaller window will increase the number of character 1 outside the string.

    Then we just iterate through i, the beginning of each window, and keep the maximum window we can get. When i goes to the next iteration, it will find the next possible window starting at the previous i's max (to keep it O(n)), while also keeping track of the minimum cost as well.

    Submission: https://codeforces.com/contest/1680/submission/157038960

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone share all the approaches to question C as mentioned in the tutorial? It will be nice to see them all at once and compare their complexities

Dynamic programming, Greedy, Two pointers

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone solved problem C with dynamic programming?

»
8 days ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Can C be solved using ternary search? If yes, can someone share their solution for the same?

  • »
    »
    7 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Here is my solution with ternary search.
    157125272
    I think the solution can be improved and may be done more clearly.

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I also tried it using ternary search but got WA as verdict , can you help me finding the test case where it is failing ? 157066350 For every index j in the string , I am finding the optimal i so that cost is minimum using ternary search .

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Binary Search Video Solution for C

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

green !

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I used a segment tree.I think I can replace it by a monotune queue.

»
8 days ago, # |
  Vote: I like it +31 Vote: I do not like it

Problem F looks very similar to https://codeforces.com/contest/19/problem/E

»
8 days ago, # |
  Vote: I like it +11 Vote: I do not like it

For problem E: a "state machine" approach works, without any DP.

The idea: same as in the editorial, we sweep all the chips from left to right. If we reach a column with a single chip, just move it to the right and add 1 to the answer. What if we reach a column with 2 chips (whether it's 2 chips that are already there, or 1 chip is there and another has been pushed in from the left)? In this case, we push the top chip down or the bottom chip up. But we don't have to consider both possibilities yet. Just put the chip in an "indeterminate" state and resolve the state when you reach a column with exactly one chip.

Of course, this doesn't save much in terms of runtime/space — the dp solution only carries around 2 integers. But I think it's a nice way of looking at the problem.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, can anyone help me with problem C. I've thought of a greedy solution whose basic idea was to remove the max number of zeros by removing min number of ones and repeat this till the string becomes empty from zeros.I tried checking with many edge cases but cannot see what is the mistake ive made. So plz can anyone help me I have commented the code for better understanding https://ideone.com/bBoj0b

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there is a typo in the editorial of problem E, because the transition $$$dp_{i, 1} \rightarrow dp_{i+1, 1}$$$ is considered twice. It's not really important though because it's easy to understand that the last transition is meant to be $$$dp_{i, 1} \rightarrow dp_{i+1, 0}$$$

»
8 days ago, # |
  Vote: I like it +2 Vote: I do not like it

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

»
7 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Finally an expert after this contest, really liked third problem

»
7 days ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

i really want to solve the problem c by myself but i am stuck for a few days. can anyone give me any insight to approach the problem

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, I iterate to [0,n-1] taking only the 'i'th character at each iteration as the first character of the substring, and for finding the last position of the substring, use the binary search. so how do we binary search it! first, compute the prefix of both '0's and '1's in the string, then use those prefixes to compute the max('0's present in the substring, '1's deleted from the substring). if('0's present in the substring > '1's deleted from the substring) then shift left=mid+1; else, shift right to mid. And then compute the minimum of answer and the substring computed up to left. https://codeforces.com/contest/1680/submission/157425332

»
6 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Problem F is very nice.

The final part can also be done with LCA. If you want to remove an edge in the tree, which splits it into two subtrees, the edge needs to be so the bad edges not in the original tree (ie. those non-tree edges that connect vertices of the same color) need to be in separate subtrees so we can flip the colors of one subtree.

Then the problem becomes: Given several paths on a tree, find an edge that lies on all of them. This will be the edge we remove. The intersection of two paths is empty, a vertex, or a subpath. It can be checked with a few cases using LCA whether the intersection is another path, and we repeat checking with this newer subpath.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, do you think you could help me understand solution to problem F? I understand when it says we need to remove one edge such that the remaining graph is bipartite but I don't after that I don't really understand anything about how we find this edge. Thanks.

»
5 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't understand how the dog walks in the second example of question D

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Now I understand,can't ignore the order of numbers

»
5 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Can anyone help finding which TC my submission fails on? https://codeforces.com/contest/1680/submission/157535516

Edit: Problem E

»
47 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please hack my program for D? Thank you in advance. https://codeforces.com/contest/1680/submission/157643976

»
15 hours ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I found a different simple solution for D.

Let $$$p[i] = \sum_{k \leq i} a[i]$$$ be where the dog is after $$$i$$$ steps.

Let $$$pre[i]$$$ denote sum of nonzero (known) steps in the first $$$i$$$ steps.

Let $$$cnt[i]$$$ denote the number of zeros in the first $$$i$$$ steps.

The problem is equivalent to maximizing $$$\max_i p[i] - \min_i p[i].$$$ Thus, for each pair of indices $$$(i,j)$$$ we check if we can make $$$p[i]$$$ the min and $$$p[j]$$$ the max or vice versa, and what optimal difference we can get with this pair. (Clearly if $$$a[i] > 0$$$ then it cannot be the min so we can ignore such cases, etc.)

We need the following inequalities to hold:

  • $$$ p[i] \in [pre[i] - cnt[i] \cdot k, pre[i] + cnt[i] \cdot k]$$$

  • $$$ p[j] \in [pre[j] - cnt[j] \cdot k, pre[j] + cnt[j] \cdot k]$$$

  • $$$ p[j] \leq (cnt[n] - cnt[j]) \cdot k - (pre[n] - pre[j])$$$

  • $$$ p[j] - p[i] \in [(pre[j] - pre[i]) - (cnt[j] - cnt[i]) \cdot k, (pre[j] - pre[i]) + (cnt[j] - cnt[i]) \cdot k]$$$

where the first two inequalities are obvious, the third inequality ensures that the dog can return to zero after reaching the maximum at $$$j,$$$ and the fourth inequality is that the dog can go from the min at $$$i$$$ to the max at $$$j.$$$

It can easily be checked whether these four inequalities hold, and find the optimal difference for this pair $$$(i,j).$$$ The overall runtime is $$$O(n^2).$$$