Vovuh's blog

By Vovuh, history, 4 weeks 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  

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

good contest!

»
4 weeks 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.

»
4 weeks 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 ?

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Amazing! That's what I was looking for. Thanks.

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

.

»
4 weeks 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
...
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah I also used the same strategy.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i used this too, nice!

  • »
    »
    3 weeks 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.

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

    Yeah ! It is the simplest approach.

»
4 weeks 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.

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
4 weeks 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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm seeing a lot of these type of these comments these days...

    sigh... I'm going to have to make a blog about why putting math in problems is good.

»
4 weeks 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) :(

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

cumulative sum might reduce complexity for problem D :)

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone suggest some other approach for F2. Thanks.

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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

          • »
            »
            »
            »
            »
            »
            4 weeks 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.

»
4 weeks 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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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]