Kniaz's blog

By Kniaz, history, 3 years ago, translation, In English,

I'm sorry for a delay with publishing the editorial.

Tutorial is loading...

Problem author: MikeMirzayanov.

Tutorial is loading...

Problem author: MikeMirzayanov, Kniaz.

Tutorial is loading...

Problem author: MikeMirzayanov.

Tutorial is loading...

Problem author: MikeMirzayanov, Kniaz.

Tutorial is loading...

Автор задачи: Kniaz.

Tutorial is loading...

Автор задачи: MikeMirzayanov.

I want to thank Mikhail Piklyaev (PikMike) for translation of tutorial!

 
 
 
 
  • Vote: I like it
  • +70
  • Vote: I do not like it

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

What about the problems E and F?

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

    I think they should be published soon. You can also ask me if you would like some tips!

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

      can you help me with implementations of C and D ?

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

Can anyone explain C and D in a simpler language? That would be a great help. Thanks in advance!

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

    I am not sure about the approach of C in the editorial, but here's my O(n) approach:

    Observation: a[] can be converted into b[] by grouping a[] in non-overlapping segments.

    If we start from the left, it is obvious that the answer exists only if the prefix sum (the sum of the first few elements) is equal to b[0] since a[] only consists of positive numbers. This fact could also be inducted to other segments if we consider that previous segments were cut away from a[] and treat the next element as the start of the segment for b[1...n].

    Now the only thing we have to care is whether the monster could start the momentum by eating others. By greedy we will assume that we are starting the eating processes of each group from the largest monster (as there are no non-positive elements), if you can't start the eating process (note that the eating process is only needed when the size of the group is larger than 1).

    Remember to store the correct positions of the monster during the eating process as the editorial has mentioned.

    The editorial for D pretty much nailed it and I don't think my explanation could beat that. Perhaps you should take a look at other's code.

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

      For problem C:

      You should select one largest monster which isn't surrounded by two equal monsters.

      To avoid being bothered with changes of position, you may process from the last block to the first block.

      Check my code: 21929693

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

How to solve C in O(n)- challenge ?

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

    Like this. 21968223

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

    Not very different than what is explained in the editorial. For a group S that needs to get reduced to one monster, find a monster which has maximum value and doesn't have an equal neighbour(if there is no such monster, then no solution). Once he eats this unequal neighbour, he can eat everything else in any order. So you'll either eat everything to the left and then everything to the right, or eat everything to the right and then everything to the left. And this way it's easy to keep track of his position in the final array, without simulating the transformations on the array.

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

    try to use two pointers one starting at first of 1st array and other at start of 2nd array.

    first time traverse whole b array to check if solution exists.if doesnt exist print NO and exit

    else if yes traverse again second time through 2 nd array and print the solution.

    for printing the solution,follow a greedy approach finding the maximum in it and assume it eats all the others in that union

    here is the link to my solution of it:http://codeforces.com/contest/733/submission/21949174

»
3 years ago, # |
Rev. 3   Vote: I like it +19 Vote: I do not like it

Ooops.. looks like my solution was incorrect. Took us a while to figure it. Sorry to everyone who wasted time trying to figure it out. I'll think more carefully next time.

Check the last edit if you wanna read the incorrect solution.

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

    Can you prove its correctness? I'm not sure about this.

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

      I presume you are suspicious that the Kruskal is incorrect, now that edges change their initial values?

      Indeed, I see that I wasn't rigorous enough about it. Looking over the Kruskal proof, you can make it still hold if edges that you haven't added yet to the MST can only increase in cost during the algorithm(which is what happens in my algorithm. The edges of category 2 increase in value until they reach category 1, but we fix their cost if we add them to the MST before that).

      Later Edit: No, it doesn't work.

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

        Hi Mikester, I understood the following.

        For a tree with n — 1 edges, the dissatisfaction will be Sum(w(i)) — S/c where c = minimal weight of edges in the tree.

        Now, if I fix c, which is equal to weight of some edge, I need to minimize sum(w(i)), that is find the minimal spanning tree containing edge with the weight c and all other edges have weight >= c.

        Can you explain after that point? I mean how do I optimize it?

        Hmm, looks like I am close to the solution

        http://codeforces.com/blog/entry/9570

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

    I can't understand what exactly are you representing with extra[i] array.Can you please elaborate a bit?

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

      extra[i] is in this instance of the problem -S/c[i]

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

    It's incorrect. consider following case
    4 4
    0 0 1 10
    100 100 5 1
    1 2
    1 3
    2 3
    2 4
    10

    your solution gives sum 1 and selects edge 3, 1, 4, but the optimal solution should give sum 0 and select 1 2 4.

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

      Wow, you're right.. Good job! I thought I had a cool insight about Kruskal too. What I said about it was incorrect. My apologies.

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

Implementing E was really painful, and had so many errors. Finally felt peaceful after getting AC. After seeing many people using binary search, I thought that I was making the problem very hard for myself but it seems that the editorial explanation is exactly what I have done(not sure). I considered all the cases separately in query function, and always made sure that when I am calculating the answer for s[i], it is always U. Otherwise I find the answer in the inverse string, where it would be U.

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

    What's the approach using binary search?

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

I have a (possibly dumb) question about Problem F: Why would it be optimal, given a fixed selection of main roads, to reduce the dissatisfaction value of just a single road? Would that still hold if the budget is not divisible by the unit repair cost of the selected road? In that case, would it be more optimal to distribute the budget over multiple roads whose total repair cost could make better use of the budget?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    That's a dumb question indeed :P . What you are saying is like this .. 19/3 can be greater than 15/5 + 4/4 . just because you are using all the money it doesn't provide you with more number of dissatisfaction units(because the cost is also high). Mathematically it goes like this.. a*x + (a-1) = Sigma(Bi*Yi). where each Bi is greater than 'a' implies Sigma(Yi) <= x. It's easy to prove :) . However my submission was giving wrong answer on test 75. can anyone please check ? what's special about testcase 75? here's my submission- [submission:21965336]

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

    Even if S % c[i] != 0, floor(S/c[i]) is maximized when c[i] is minimal.

    There's a simple argument: Assume you allocate some budget to road j such that c[j] > c[i]. Note that this budget could be moved to road i at no loss (indeed, possibly at a gain).

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

    Thanks @Artemis_Fowl and @OMGTallMonster for explaining! That was indeed dumb.

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

    I was also confused about that one.

    The OP says that fix an edge to be reduced and find MST corresponding to that edge.

    Now, it would be correct if the cost of that reducing edge was minimal. But what if there was an edge with smaller cost of reducing in that same spanning tree. Then we could reduce the dissatisfaction by reducing that edge. So I thought this, fix a road, find a MST containing that road, where all edges have cost of reduction >= c, where c is the cost of reducing dissatisfaction of the edge we initially chose. But it turns out I don't have to do actually that. What we need to do is that if there are multiple spanning trees of the same weight, then for all those spanning trees, we should choose the tree containing the edge with smallest reducing cost. So, we select an edge P, find MST corresponding to that edge. Suppose w(P) > w(Q) (w(p) = cost of reducing dissatisfaction of the edge p) for some other edge in the MST, then we know that MST(P) >= MST(Q)(either MST(P) = MST(Q), or at least one edge is different with smaller weight, so MST(Q) < MST(P) ), therefore we know that when we finally find MST corresponding to Q, the answer is obviously better and hence no need to find MST with weight >= c.

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

Really liked the problem C.
Need more problems like this.
I didn't think that it would be that easy.

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

Problem F should add this case:
5 6
3 3 3 3 4 9
100 100 100 100 2 1
1 2
2 3
3 4
4 5
1 5
1 5
7
The answer is 10. But my solution got 11 and passed all system test cases.

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

    They should put more corner cases in the System test... We don't expect weak test cases from Codeforces

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

problem F : Precalc takes ? or for Binary lifting ?

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

Thank you for such intersting problemset! The problems(especially E and F) worth thinking & solving :)

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

Can someone help me in finding the bug in my submission for problem C . I followed the same approach in the editorial but I'm getting a WA at test 64 . The checker comment is Wrong answer Can not eat not less . Since it's a large input I couldn't find the bug.

I would be very thankful if someone could help me out.

My submission with comments : LINK

UPDATE : I managed to find the bug and solved it.

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

I think I'm missing something in the complexity argument for F. How do you add an edge to a tree and delete some edge in the cycle without paying O(m) to reverse the links in the path between the added edge and the deleted edge? (The links are directed, and thus must be reversed, based on the LCA binary lifting article elsewhere in the blogs.) Which would raise the total time complexity to O(n log n + m^2).

Example: Tree rooted at A, with a child B. C is a descendant of B at depth O(m) [since this is an unbalanced tree]. Leaf D with depth O(m), not in B's subtree. Need to add an edge between C and D: LCA is A; suppose the heaviest edge in the cycle is (A,B). Then we need to reverse links on path B..C with total cost O(m).

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

    You don't have to do the whole operation. Instead, you just find the LCA to identify the unique cycle that will be created in log time, and then use binary lifting to identify the best edge to be removed.

    (When you create the binary lifting lookup table, you lift it in the way that the edges are directed to the parents, that's the way you want to do it anyways, you don't need to reverse it everytime you lookup the table then.)

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

      I got all that, and now after typing a long reply explaining my question better I think I was actually confused about something else =)

      I thought that after you found the edge to delete, you actually needed to store and use the new MST with that edge "forced", and having new binary lifting tables for the new MST. That would mean throwing away all the precomputation work you did before because it's invalid; that's the parent/child reversals I was talking about. Obviously that would be O(m) precomputations which is no good.

      But I think I see now that you don't store the new MST (well, you might store the minimal one); you just have a single MST you reuse over and over with a "hypothetical" delete/insert at every step.

      I think part of my confusion was that the time bound given seems achievable with LC trees supporting path reversal ("evert" operation in Sleator and Tarjan), which would allow you to actually modify the tree over and over.

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

Sorry, maybe I don't understand problem B(div2) but in 3d sample which is 6/ 5 9/ 1 3/ 4 8/ 4 5/ 23 54/ 12 32/ "/" means new string We can change places of 23 and 54 and we'll have optimal answer(then suml=80 and sumr=80) So why answer that we can't do anything? Please help in understanding problem!!

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

Can anyone prove the correctness of given solution for F ?