vovuh's blog

By vovuh, history, 6 years ago, In English

1118A - Water Buying

Idea: MikeMirzayanov

Tutorial
Solution

1118B - Tanya and Candies

Idea: MikeMirzayanov

Tutorial
Solution

1118C - Palindromic Matrix

Idea: MikeMirzayanov

I should mention this blog because it is amazing! This is a tutorial of this problem from MikeMirzayanov.

Tutorial
Solution

1118D1 - Coffee and Coursework (Easy version)

Idea: MikeMirzayanov

Tutorial
Solution

1118D2 - Coffee and Coursework (Hard Version)

Idea: MikeMirzayanov

Tutorial
Solution

1118E - Yet Another Ball Problem

Idea: MikeMirzayanov

Tutorial
Solution

1118F1 - Tree Cutting (Easy Version)

Idea: MikeMirzayanov

Tutorial
Solution

1118F2 - Tree Cutting (Hard Version)

Idea: MikeMirzayanov

Tutorial
Solution
  • Vote: I like it
  • +62
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

good contest!

»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

nice!f2 is a interesting problem,and i learned a lot from it.

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

What's the proof of optimality for D for given coffee distribution-strategy ? Is it just intuitive or we can prove it ?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes we can prove it.The approach is greedy. Consider the caffeine values 6 5 5 3 1 1 in order and consider the distribution for 2 days and in each day you are taking 3 cups.

    6 + 5 + (5 — 1) + (3 — 1) + max(0, 1 — 2) + max(0, 1 — 2) = 17

    If you consider this case 6 5 1 1 3 5 in order

    6 + 5 + (1 — 1) + (1 — 1) + (3 — 2) + (5 — 2) = 15

    This is because in the first case max(0, -1) + max(0, -1) hides subtracting 2 from the final output.

    Sorry for my bad example.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it

    If you can bear some algebra then you can better appreciate the proof. ;)

    So again let's sort it in decreasing order a0 ≥ a1 ≥ ... ≥ an - 1, and we consider the sum . Now there exists an m such that this sum is equal to : is strictly decreasing as i increases. In other words we can 'assume' that a0 through am - 1 are strictly greater than , and the rest at most .

    To show that this is optimally, let b0, ... , bn - 1 be a permutation of these ai's, and since we spread it over k days, at most k of the coffee cups are the first of the days (hence 0 penalty), at most k of them has penalty 1, and so on. Hence the sum is now at most . Choosing only those i's that are relevant, we see that this sum is also equal to .

    Now if p is the number of those i's satisfying , we can split the sum into two categories: the bi's contain at most m integers from a0, ... , am - 1 and the rest are not more than ; so . On the other hand, the sum (considering only those i's that are relevant) at at least so

    , as desired.

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

.

»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

E has another simple solution.
Traverse all pairs in increasing order (starting from (1, 2), (1, 3), ...) and print each pair followed by its flipped pair (not repeating any).

1 2  
2 1  
1 3  
3 1
1 4
4 1
2 3
3 2
...
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah I also used the same strategy.

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

    i used this too, nice!

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

    There is another solution where in we could start with say pair (1,2) and keep incrementing both the elements of the pair until the second element of the pair reaches k.

    After that, we flip the pair and keep decrementing both x and y until y becomes 1. Repeat this process and we get the correct answer.

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

    Yeah ! It is the simplest approach.

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone please explain me the tutorial of F1.

It would be of great help.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    I solved it in following steps:

    1. Suppose root of the tree is 1.

    2. Then by single dfs we find how many red and blue vertices are present in subtree of each vertex.

    3. Then we see each parent to child edge, if child's subtree contains 0 blue vertices and all red vertices(or 0 red vertices and all blue vertices) then this edge is good.

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think this contest have much tricky questions then previous div3 contest.

»
6 years ago, # |
  Vote: I like it -31 Vote: I do not like it

the contest was terrible and now seeing from this editorial you really didn't care about us. it's a joke, especially problem D. i'm at a loss of words trying to explain myself why you keep mixing math with programming. what connection do you see between the two? genuinely

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

In Problem B for n=1 ans should be 0, bcoz if there is only one candy, tanya will give that's one to his father, since now there is no candy she could not eat any day.(There is no candy). Shouldn't it be 0 ? (My soln got hacked just due to only this case which i made myself ans = 0 if n==1) :(

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

    No, because if dad eats the 1-th candy, sum of weights of candies Tanya eats in even days = sum of weights of candies Tanya eats in odd days = 0.

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

i've learned a lot from this contest, specially that i must read the entire problem set.

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

Can someone suggest some other approach for F2. Thanks.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hi, my solution is still similar to the editorial but maybe it can help.
    I first run a DFS to do a minimal merge of the components of the same color: I colorize the entire path between each vertex of color, and check for collisions. You only have to keep a count of number of components per color to know if the child has to give its color to his parent.
    Then instead of counting the ways of cutting, i count the number of valid colorings, where a color for a node is either "in subtree" or "not in subT". Then for the second DFS I just compute the possibilities for these two "colors". The formulas are similar to editorial.
    Solution in O(n log mod) runs in 0.5s, because I took modular inverse to obtain the product of "all but one".
    Hope it helps, my code here: 50352250

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

      Could You explain how counting works? I haven't really understood it from the tutorial. Although I understand all the rest.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Either you already have made # of colors in subtree cuts in this subtree or you have made this number minus one. In my case corresponds to "is this node color in the subree?". You can think of DP0 as "am i done here? = has color of parent" so naturally you can keep a color and get from color of child to color of parent but not the converse. Then like classical tree DP you sum possibilities of disjoint events (like choosing one children color) and multiply the ones for independent events (like choosing a color for each subtree). This is not an easy DP pb because you have to keep track of both. Try to get the intuition behind the formulae before looking at tricks for computing it faster.

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

          Okey, I think I am starting to understand it now. One more question. How do we know in our dp that we cut exactly k-1 times? No more no less?

          I will try solving some easier problems with tags (trees, combinatorics) and then come back to this one. Thanks

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            1: you checked there were no collisions during the minimal merging
            2: at each cut your separating the "top" color from the "bottom" one, the components stay connected. When you already cut it, a color disappears from the possibilities (DP1->DP0) and becomes a color not in subtree. DP0 means we are done w/ all colors of subtree, DP1 there is one left at the root of subtree.
            3: Since you want the root node to have a color from its subtree, you return DP1. Each color except this one has been cut -> K-1.

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

can anybody take a look to my post here

and help me to optimize my dp solution for the D1 to solve D2

thanks in advance

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

    Its painful to read code of other people sometimes. Let me know if you haven't understood from editorial.

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

      I can’t figure out the counting part. Logic behind dp[v][1] and dp[v][0]

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

1118D1 — Coffee and Coursework (Easy version)

Let the current number of days be k. The best way to distribute first cups of coffee for each day is to take k maximums in the array

How do you know that it's the best way to distribute? I don't get that

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Checking on samples and doing some casework and observations, It is better to use maximum values initially because they may get depleted later on.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Need help with the problem F2. What I've done is-

  1. For every color, tried to build $$$k$$$ same-colored subtrees. If not possible (collision occurs), the answer is trivially $$$0$$$.

  2. For simplicity, let's call uncolored vertices as black vertices. When an answer exists, there will be many (possibly $$$0$$$) subtrees induced by black vertices, whose leaves will have many colored components(sub-trees) adjacent to them. Let's call the set of these colored component/sub-trees $$$S_T$$$ and the black components $$$B_T$$$. Instead of cutting $$$k-1$$$ edges, I tried to color the black vertices in a way such that:

a. only the trees in $$$S_T$$$ get larger

b. no new subtrees form.

c. all the vertices get colored.

Clearly, doing step 2 for all the black sub-trees in $$$B_T$$$ will lead us to the result. The answer will be the product of $$$count(coloring_.a_.black_.component_.in_.B_T)$$$. So, all I need is to find a way to count the colorings of $$$1$$$ black component. It should be an easy DP but somehow I'm failing to grasp it. The tutorial did not help (sorry). Any help is welcome. Thanks.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The way Mike has explained F2 is remarkable. Thanks Mike and Vovuh.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem F2 I have an approach. However I am stuck at some part Please read this blog for my approach. Note: For good coders you will find one more interesting problem to solve.