Golovanov399's blog

Codeforces Round #522 and Technocup 2019 Elimination Round 3 Editorial
By Golovanov399, history, 8 years ago, translation, In English

We are sorry that you were having troubles with access to Codeforces.

Problem A of elimination/div2
Problem B of elimination/div2
Problem C of elimination/div2
Problem D of elimination/div2 = problem A of div1
Problem E of elimination/div2 = problem B of div1
Problem F of elimination/div2 = problem C of div1
Problem G of elimination/div2 = problem D of div1
Problem E of div1
  • Vote: I like it
  • +101
  • Vote: I do not like it

Comments Comments (44)
| Write comment?
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Golovanov399 (previous revision, new revision, compare).

→ Reply
»
8 years ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

Very nice solution for the problem div2 G / div1 D i made exactly the same. 45972559

→ Reply
»
8 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

why can't we choose k = 3 and n = 12 in the second dummy test of problem E? *edit: nevermind i was dumb

→ Reply
»
8 years ago, hide # |
← Rev. 2  
Vote: I like it +5 Vote: I do not like it

For F, how to prove the "unique if and only if it's perfect" part? Update: got it.

→ Reply
  • »
    »
    8 years ago, hide # ^ |
     
    Vote: I like it +15 Vote: I do not like it

    Consider a graph G with a maximum matching M. If there exists node V in G where it has at least one edge incident on it in G but has no edges incident on it in M, you can choose any edge E incident on V in G (notice that any edge incident on V in G connects V to nodes which have incident edges on them in M, otherwise M is not a maximum matching). Let E be connecting nodes V and U. Add E to M, and remove the edge incident on U in M. This produces a new maximum matching. This proves that M with at least one unsaturated node is not unique.

    Now consider a tree T with maximum matching M where all nodes in M are saturated. If you decide to add arbitrary edge E (existing in T but not in M, and connects U and V) to M, you need to delete the edges incident on U and V in M. Now you will have two new unsaturated nodes (which were connected to U and V by the edges removed) in M. Let's call them U' and V'. So you need to add 2 edges from T such that they will be incident on U' and V' in M. Let these 2 edges were connecting U' and V' to U'' and V'' respectively in T. Now you need to delete the 2 edges incident on U'' and V'' in M. Two new unsaturated nodes appear and the process will repeat. The only thing that can stop this process and produce a new maximum matching is adding an edge between the 2 new unsaturated nodes in M, which means that the graph was cyclic (not a tree). This proves that a maximum matching of a tree with all nodes saturated is unique.

    → Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anyone explain problem C?

→ Reply
  • »
    »
    8 years ago, hide # ^ |
     
    Vote: I like it +7 Vote: I do not like it

    Imagine for some i we know all fingers by which we can play this note. Then

    • If ai + 1 > ai and we can play the i-th note by the j-th finger, then we can play ai + 1 by k-th finger for every k > j (after we played the i-th note by the j-th finger).

    • If ai + 1 < ai and we can play the i-th note by the j-th finger, then we can play ai + 1 by k-th finger for every k < j (after we played the i-th note by the j-th finger).

    • If ai + 1 = ai and we can play the i-th note by the j-th finger, then we can play ai + 1 by k-th finger for every k ≠ j (after we played the i-th note by the j-th finger).

    By storing all these things we can both determine if we can play the whole melody and which fingering we can use for this.

    → Reply
»
8 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

Can someone explain the dp transition for div2E/div1B?

→ Reply
»
8 years ago, hide # |
← Rev. 6  
Vote: I like it +29 Vote: I do not like it

Hi, I'm confused by the states of div2F, can somebody help and clear my thoughts? Thanks

Is it true that: dp[v][0] and dp[v][2] have intersection?

Then won't it be repeatedly counting when calculating dp[v][1]?

→ Reply
  • »
    »
    8 years ago, hide # ^ |
    ← Rev. 7  
    Vote: I like it +25 Vote: I do not like it

    I think I have some new thoughts trying out some small examples, let me put it here.

    I think the confusion can be cleared by distinguishing these two properties: 1. Is it connected to some edges? 2. Is it matched with its parent or children?

    Suppose we are looking at v. If we are constructing a tree, our decision will be whether to connect v to its children to's or not.

    dp[v][0] means the answer: number of ways to split the tree such that in the resulting perfect matching v is:

    • a) matched with one of its children, or
    • b) isolated (absolutely no edge connecting it).

    Also, every component has a perfect matching, for a subtree rooted at v without any constraint

    dp[v][1] counts: v is matched with its parent and it should not match with any of its children. Note in this case, the edge from v to its children may or may not be present.

    dp[v][2] counts the way in which v matches one of its children (and thus the edge is there).

    Let's start with dp[v][1], so in this case we force v to be matched with its parent. For each of its children to, we want either:

    • a) there's no such edge (v, to), or
    • b) there is an edge (v, to), but this edge should be forced non-existant in the perfect matching.

    For case a) is dp[to][0] and case b) is dp[to][2] because we want to to be matched with to's child instead of v.

    Then let's come to dp[v][2], so now we want to force v to be matched with one of its child to, and to should not be matched with its children (dp[to][1]), for v's other children to', either we don't want the edge (v, to') (dp[to'][0])or we want the edge but also to' should be matched with its children (dp[to'][2]).

    And finally, for dp[v][0], either we want to isolate v (dp[to][0]) or we want it to be matched with one of its children (following the logic of dp[v][2]).

    Interesting problem, thanks.

    → Reply
  • »
    »
    8 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +11 Vote: I do not like it

    So to answer this question, do dp[v][0] and dp[v][2] have intersection?

    Yes.

    But when you add them in a parent, they account for cases where either you have the parent edge or not.

    So there won't be double counting.

    → Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What is the definition of unique maximum matching? I'm confused now..

→ Reply
  • »
    »
    8 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Matching is something for bipartite graphs, trees are bipartite graphs.

    Supose the graph with 3 nodes and the edges: 1 2 and 2 3

    In this graph the maximum matching is not unique. The maximum matching is 1 and the chosen edges can be either 2 1 or 2 3

    → Reply
    • »
      »
      »
      8 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I don't understand the "unique" part of it. When the matching is unique?

      → Reply
      • »
        »
        »
        »
        8 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        The matching is unique when there is only one subset of the edges that gives the maximum matching.

        I just gave you an example of when it is not unique. Here its an example of when it is unique: A graph with 2 nodes and the edge 1 2. The maximum matching is 1 and the only choice is choosing the only edge 1 2.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          So how is it that the anwser is not just 0 or 1?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            Tree with n + 1 vertices and edges: {1, 2}, {1, 3}, {1, 4} ... {1, n} has n maximal matchings, but no perfect one.

            → Reply
»
8 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

In Div2C, when I first read the problem, I could only think of a greedy approach.

Could someone help tell me what observation led them to thinking of a DP approach? How'd the idea of applying DP come? Was there a specific part of the question which made you think "This can be solved with DP."

Any help is welcomed! I'm trying to develop the thought pattern and could use some help in doing so.

→ Reply
  • »
    »
    8 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Look, the choice for any finger depending on the previous one as example for fifth one the choice depend on forth one, for forth choice it depend on third one, for third choice it depend on secon done and finally for second choice it depend on first one. Here there is only 5 chice for first number and 4 or less choice for remaining numberes. so u can try by taking all possible way depending upon the condition. for example put 1 in first number and try with putting 2,3,4,5 on second number and if it is not possible to put any number on it then go back to forst one and put 2 on first number and try by putting 3,4,5 on second number if the second number is bigger else try by putting 1 and so on for next numbers.

    And for more convenience there is only 5 choice for each number and you can try by putting all the possible way whice tend to dp.

    → Reply
  • »
    »
    8 years ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    Actually the problem has a greedy approach which I used.

    The main idea is that if ai + 1 > ai, then the next finger should be at least 1 greater. However, if ai + 2 < ai + 1, then it’s better to choose 5, because in the worst case there will be 5 consecutive numbers in decreasing order and 5 will give you a possible answer in the future.

    You can apply the same idea when ai + 1 < ai and when ai + 1 = ai. The most important part in every case is that checking at the value of ai + 2 allows you to make the optimal choice.

    The code: 45938901

    → Reply
    • »
      »
      »
      8 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Thank you, I didn't think of looking past the immediate element :)

      Thanks for making time for my query and linking your code! :)

      → Reply
»
8 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

Just wondering, is the machine in Div1E Turing-Complete?

→ Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can any suggest more problems like C. Playing Piano for further practice ?

→ Reply
»
8 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

can someone explain the solution for problem D/div2.

thanks in advance.

→ Reply
  • »
    »
    8 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +3 Vote: I do not like it

    I had a pretty simple approach.

    To get from point A to point B, there are countable number of ways -

    1. Go the manhattan route -- completely ignoring the given line.

    2. Go from A to the given line parallel to the Y-axis, then traverse along the given line, and then go to B from the line vertically, when you're at the same X-coordinate as B.

    3. Go from A to the given line parallel to the Y-axis, then traverse the given line and move horizontally when you're at the same Y-coordinate as B.

    4. you'll go from A to the line parallel to the X-axis, traverse along given line, exit line and travel along Y-direction when you're at same X-coordinate as B.

    5. You'll go from A to the line parallel to the X-axis, traverse along the line, exit line and travel along the X-direction when you're at the same Y-coordinate as B.

    So overall, 5 cases to check — manhattan, X-line-X, X-line-Y, Y-line-X, Y-line-Y.

    Your answer is the minimum of them!

    Here's my accepted solution — https://codeforces.me/contest/1079/submission/45935081

    Corner case is to just check if either 'a' or 'b' in the line equals zero and if so, return infinity as the result along that direction. :)

    → Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

For Div1D, the editorial mentions using a sparse table, but I was only able to make the sparse table approach fast enough after many submissions. Did the writers actually expect people to use this approach? And did anyone else use this approach?

46016077

→ Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone please explain to me one case in problem G?

The third input contains 100 entries in total and entries 48-52 look like: ... 5 37 2 53 28 ... The judge answer for 50th entry is 2, and I am curious why.

I think the parrot on entry 2 will spread the message to the shown subarray of five elements in the first second. In the next second we have at most 3+37+53 parrots talking. What am I missing?

→ Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anyone provide the recursive solution for Div2 C.

→ Reply
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I tried implementing the editorial solution for Div 1 D, but I keep getting WA on Test Case 9. Can someone please provide a break case or find a bug in my code?

https://codeforces.me/contest/1078/submission/55229631

→ Reply
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In div2-E time complexity is O(n^4) but still it works, can someone explain how ?

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

In problem B, many contestants use this:

for (int a = 1; a <= 5; a++) 
    int b = (n + a - 1) / a;
    if(b <= 20) {...}

instead of iterating through all values of a and b like the editorial. I'm a beginner, can you please explain how this works?

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

In 1078E - Вычисления за отрицательное время, I'm having trouble because the solution I think is correct is not getting AC. According to the judge results, even the sample case "123456789 + 987654321" is claimed to be wrong.

For the case "123456789 + 987654321", the smallest program I feel is being judged incorrectly is as follows:

"d0luuu1ddd0s10usususttttttl1l0l0l0l1l1l1l0l1l0l1l1l0l0l0l1l0l1l1l1l0l0l0l1l0l0l0l0l1lr"

https://codeforces.me/contest/1078/submission/332313390

In the test(){} function of my submission, there is an explanation regarding this output, so if anyone can take a look, that would be helpful. If I insert "1" right after "tttttt", the program gets AC for sample 1, so this part seems suspicious.

I evaluated the outputs of many AC submissions using the simulator I implemented, and they all returned AC, so from that angle as well, I haven't found any obvious mistakes in my problem interpretation or simulator implementation.

I've also had this output independently verified multiple times by generative AI, and it claims my output is correct. (Of course, I don't think AI's opinion is inherently more trustworthy than the judge program's.)

I'd be happy if someone could help me. Thank you!

→ Reply
  • »
    »
    14 months ago, hide # ^ |
     
    Vote: I like it +10 Vote: I do not like it

    Hey!

    Sorry for that, it seems that the checker indeed had a bug (when time traveling, the first rollback didn't update the board, although the coordinates were reset properly).

    I hope not many people were affected by this, although this feels crucial. The tournament results wouldn't have changed because the round was unrated.

    I fixed the checker, you can use it locally now. I can send you the testlib version, if you want. I have updated the checker in polygon as well and rebuilt the packages for the problem, but I don't know if whatever contests use it are going to update or if I need to rebuild their packages too. I also cannot find the technocup round or its mirrors in my "view contests" polygon page.

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

      Thanks a lot for your quick response and the fix!

      Please let me know once the fix is deployed to the judge as well. I'm not sure how CF contests handle these updates either, but maybe contacting Mike or KAN could help if needed?

      In the meantime, it might be good to add a note to the problem page mentioning the checker issue.

      → Reply