Автор Endagorion, история, 6 лет назад, По-английски

On Oct/04/2018 10:05 (Moscow time), the Codeforces Round 513 by Barcelona Bootcamp (rated, Div. 1 + Div. 2) will start. This is a special round for the Hello Barcelona Programming Bootcamp, in collaboration with Moscow Workshops ICPC. It is rated for all participants, everybody can register on it regardless of a rating.

Hello Barcelona Programming Bootcamp is sponsored by VTB and Indeed Tokyo, with the addition of team sponsors Phaze Ventures, Spark Labs and REMY Robotics.

VTB, the largest international bank based in Eastern Europe, continues to be an official partner of the Hello Programming Bootcamp series, adding further quality to the 3rd edition of the Hello Barcelona Programming Bootcamp by bringing their own participants, as well as by supporting top teams from around the world.

Indeed Tokyo is Japan's branch of the #1 employment website in the world, giving job seekers free access to millions of jobs from thousands of company websites and job boards. As they sponsor for the second year in a row, Indeed continues to offer the best job opportunities to the boot camp participants.

Wish good luck to all the participants!

There will be 8 problems, common for both division. Score distribution: 500 750 1250 1500 1750 2250 2750 3000.

The problems are prepared by me, Arterm and GlebsHP, with assistance from 300iq, ifsmirnov and vintage_Vlad_Makeev. Have fun!

  • Проголосовать: нравится
  • +220
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +188 Проголосовать: не нравится

A good time for Chinese!

»
6 лет назад, # |
  Проголосовать: нравится -51 Проголосовать: не нравится

Unfortunately, bad time for me because of school

»
6 лет назад, # |
  Проголосовать: нравится -84 Проголосовать: не нравится

A bad time for Indians!

»
6 лет назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

I forgot the contest time last time, so I may forget again. I don't want to lose a chance to get high rating!

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -91 Проголосовать: не нравится

Endagorion is there any chance that contest can be shifted one hour earlier or at standard codeforces contest time?? If possible please do so.

»
6 лет назад, # |
Rev. 5   Проголосовать: нравится -114 Проголосовать: не нравится

I am just sad about not getting to participate in the round i was waiting for over a week.

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится -39 Проголосовать: не нравится

LUL

»
6 лет назад, # |
Rev. 6   Проголосовать: нравится -53 Проголосовать: не нравится

two contests back to back.

»
6 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Thanks to MikeMirzayanov for polygon platform.

»
6 лет назад, # |
  Проголосовать: нравится +104 Проголосовать: не нравится

Please stop complaining about the inappropriate time of the contest for your country. Codeforces has to adopt different timings for other people. Not only for a specific country.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Right? Like, across US, India, China, and Russia, any time is going to be bad for somebody. What's the point in complaining?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Point of complaining as I think is that you cant participate cause of school/work. If contest would take place on weekend, people could even participate at night. But bad time + weekday is reason enough to complane

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I wasn't complaining. I am just sad to miss the round by such good author & also this contest is after a long time from previous one. Neither I upvoted any comments who asked to shift the contest.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    I wasn't aware "work" and "school" are specific countries, since that's going to be the main reason to skip this round for people in Europe, Africa and almost all of Asia. Then we have the Americas, where it's night. Ok, I guess it's a good time for New Zealand and Oceania.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +28 Проголосовать: не нравится

      It's also good for Japan, most of China, a part of Russia, South Korea and some other countries that actually does competitive programming. So it's a pretty good time for many people. About quarter of the earth can participate easily in any contest. It just depends in which quarter.

»
6 лет назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

good time for those like me who has a day-off on thurdays!!!!!!

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +232 Проголосовать: не нравится

bad time for me, i have to poop at 10:30 AM..

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -45 Проголосовать: не нравится

Please no

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

that's time to participate in this contest after 2 weeks!

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

After a long duration Codeforces contest. Codeforces really awesome.

»
6 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Great time for me, 4AM so I get to wake up, do this contest and not miss any classes!

»
6 лет назад, # |
  Проголосовать: нравится +115 Проголосовать: не нравится

Миша, когда лекции??

»
6 лет назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

Good time for those who skip classes for cf rounds

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

feeling happy :) ... hoping an interesting round :)

»
6 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Hi! Is contest duration known? :)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Codeforces — Indeed the best interface for competitive programming

»
6 лет назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

Bad time for me... had to compete Codeforces again...

»
6 лет назад, # |
  Проголосовать: нравится -42 Проголосовать: не нравится

Score distribution? Careless author.

»
6 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

What is the score distribution or is it acm style?

»
6 лет назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

Bad time for Martians

»
6 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

My last year's Barcelona Bootcamp contest. Wish me luck this time :>

»
6 лет назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

Can someone explain me solution for D, probably I am very stupid guy :)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    On seeing AC solutions, the idea is the answer should be a total of n terms.Also we know only a l can reduce a r or vice versa. So now we take max l (assuming max l is morethan max r) and it should reduce max r ,anything other is suboptimal. Now we have two people combined so we can solve the problem further similarly.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      So you want to say that since we can pair a "l" with every "r" as (a,b) and (c,d) can also be treated as (a,d) and (c,b) sitting on individual tables.

      and since we want to take the summation_of(max(l,r)) for every pair and now , as we are allowed to replace their "r" as mentioned above . So, we will simply sort list individually.

      Is this correct interpretation???

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +100 Проголосовать: не нравится

    D was pretty neat. Basically, imagine everyone is at their own table originally. it is clear that the number of chairs used for a particular person i is max(li, ri) + 1. Imagine if we put two people at the same table, and say their values are (a, b) and (c, d) respectively. Through some inspection, we can see that this is equivalent to two people (a, d) and (c, b) sitting at their own individual tables*. This implies that we can permute the r values for all the pairs. From there it should be clear that we can minimize the chairs by sorting both the l and r arrays individually and calculating the number of chairs needed if these new sorted people were all at their own individual tables.

    *To be more precise here, combining (a, b) and (c, d) results in 2 + max(a, d) + max(b, c) chairs, and leaving them alone results in 2 + max(a, b) + max(c, d) chairs. So the former case is equivalent to having two people of values (a, d) and (b, c).

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    You can say that answer is where pi is a person sitting next to i. Note that pi might be arbitrary permutation. Turns out, the best way to choose this permutation is make it so that lpi and ri are sorted in the same way.

»
6 лет назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

Nice problemset today (especially D), but the difficult from E to F is like from Div1B to Div1E...

How to solve it anyway?

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve F?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +64 Проголосовать: не нравится

    We iterate over every root and solve N problems independently. Let us call fixed root as r, and subtree of v as Tv.

    DP[$v$][$k$]: Probability of survival of r, subject to the last contracted edge between r and v is contracted between k-th and k + 1-th contracted edge in Tv

    We can calculate it by another DP. Total complexity seems O(N5), but like many tree DP, it is O(N4).

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why I failed in Pretest 2( the same as the 2nd sample), but I still got the penalty?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

    1) sum(b[i],i=1..n) <= n * max(b[i]) ~~ 2000*2000 = 4*10^6 ,

    2) let sb[z] — max( y2-y1+1), where sum(b[i], i = y1...y2) <= z. Precalc O(N^2)

    3) answer = max( (x2-x1+1) * sb[X / sum(a[i],i=x1..x2) ] ), x1=1..n, x2=x1..n. O(N^2)

    total complixity: O(N^2). with O(N^2) memory.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Is possible to solve C with binary search?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    The question can be converted into finding a subarray each from A and B such that product of sum of elements of those subarrays is less than or equal to x and the product of their size is maximum.

    Pre-calculate the minimum sum continuous subarray of array A of each size from 1 to N. For all those minimum sum subarray of size from 1 to N, find the largest subarray in B which satisfies the above condition. It can be done using two pointers. Code: 43769883

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    As JustAni pointed out: "The question can be converted into finding a subarray each from A and B such that product of sum of elements of those subarrays is less than or equal to x and the product of their size is maximum."

    Now, for both arrays we can calculate in O(n^2) the minimum sum achievable for interval sizes i=1..n, i.e. for array "a" we can calculate "a_min" as a_min[i] = min( sum(a[l]..a[r]) where r-l+1 = i), and the same can be done for array "b".

    Now simply try all possibilities, track the current maximum and try to update it to i*j when a_min[i] * b_min[j] <= x. The time complexity of this step is sufficient, as it takes O(n*m), and the previous step took O(n^2) + O(m^2).

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem D what is the answer to this test case : 2 10 10 1 1

»
6 лет назад, # |
  Проголосовать: нравится +84 Проголосовать: не нравится

10 second... give me 10 second to submit F...

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

Probably I'm the only one who assumed C to be dp problem :(

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +36 Проголосовать: не нравится

    If you have path between two nodes in tree (a, b) equal to len, after adding extra edges in the tree it will be . So, for even paths it will be same as , for odd paths it will be for 1 bigger, i.e (). So, final answer will be , where s is the sum of paths in the tree and o is the amount of odd paths in the tree.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I understood it.Thanks!

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you simply explain why it turns out to be (len+1)/2 after adding some extra edges?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It's easy to convince yourself of this by making a few trees on paper (calculating sum of paths before/after extra edges and comparing).

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How to count s?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        let's say for an edge there are 'a' nodes on one side of the edge and 'b' nodes on the other side of edge also a+b=n, now this edge will contribute to a*b paths(think ) do this for every edge and add them finally you will get s. Now to find the o(i.e count of odd length paths in a tree ) we can use dp on trees .

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

        In addition to allllekssssa's comment

        1) Calculating s: First, you calculate subtree_size array, where subtree_size[i] is how much nodes do you have in a subtree rooted at "i" (or equivalently, number of descendants of node "i" + 1). You can calculate this array by first setting all values in array to 1, then computing the postorder traversal of the tree, and then iterating through nodes in postorder order updating that node's parent subtree_size with it's own (subtree_size[parent[node]] += subtree_size[node]).

        Now, we can easily see that each edge is used exactly the number of times which we get by multiplying number of nodes on both sides of the edge. If we have the "subtree_size" array mentioned, we can simply traverse all the nodes except the root and update the "s" as follows: s += (n — subtree_size[node]) * subtree_size[node]

        2) Calculating o: The path between two nodes will have odd number of edges iff they are on levels of different parity (level being the distance from the root). So, to calculate "o", calculate the number of odd-level nodes and the number of even-level nodes, and multiply them.

        3) Solution = (s + o)/2

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      can you explain how the final answer will be (s+o)/2.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        yeah overall ans seems to be (s/2 + o) but this will give error because of integer division property

        firstly we know that(considering integer division) a/2 + b/2 =(a+b)/2 fails when both a&b are odd, and it works when both or at least one is even and for float division it is always true.

        a/2=a/2-0.5(left side integer div , right side float div)

        a/2+1=a/2+0.5. let divide paths into two sets s1(even length paths), s2(odd length paths) no problem is there when we combining the numerator of s1's terms but there is a problem with s2.

        for s2 to combine terms of s2 we need to take effect and must add 0.5 for each term after combining,it become overall addition of 0.5*o.

        hence it become overall s/2+0.5*o==(s+o)/2

        you can check each property

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was pretest 9 in problem C?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    I don't know what was the pretest, but after five WA at 9th pretest this is what I did and I passed it. "If you can take sum=10 with X ways then you can take every sum more than 10 with X ways as well. This means that you need to update your array like this arr[i] = max(arr[i], arr[i — 1])"

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      My approach was completely different than yours, so can you explain in more general terms.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        My way was to precalculate all possible sums for array A and B. Now lets say X = 10. If we get sum from array A equal to 5(let say from elements 2 and 3), then we need to get a sum from array B equal to X / 5 = 2 or less. So the key here is the word "less". You don't care only for the value X/sum, but for all the values that are less than that.

»
6 лет назад, # |
  Проголосовать: нравится -47 Проголосовать: не нравится

I think this guy have cheated yuanmaoheng.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    With whom? And how you got this info??

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -58 Проголосовать: не нравится

      Let see his submissions in the past and compare it with this contest. Seem like he have known all the problems. 5 submits and got 5 ACed. Wow!?!

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

        This is not a sufficient reason.
        1. Especially when first 5 problems had ~500 submissions.
        2. No extra lines are added in his code. And his code is Accepted not skipped which proves that his code does not match with someone else.

        By this logic, tomorrow If I will solve 5 questions in Div2, then you will point me as a cheater.

        I'm not commenting If he cheated or not. But the reason you mentioned is not at all sufficient to doubt if he is guilty.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +7 Проголосовать: не нравится

          Fyi, Skipping solutions (ie Plagiarism detection) takes place after system testing.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        There are many reasons for submissions of several problems in quick succession, like power-cut, network-dropdown or something.

        You can still think without power/network coverage, please.

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

When the next Div.3 round is going to be?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

my level of regret for trying D instead of C is over 9000

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Is it legal that leave a special case for hacking. http://codeforces.me/contest/1060/submission/43777486

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

I made a very funny bug in D. Instead of an easy solution with sorting both arrays independently I overdid and created two sets with pairs (one ordered by first component and the other by second component). As in easier solution I considered maximum of first components and maximum of second components. But when considering two pairs (l_max, r_not_max) and (l_not_max, r_max) I wrote a code removing both them from sets and inserting an element (l_not_max, r_not_max) (like we placed two people with corresponding segments alongside). Of course, if two pairs are the same we don't have to insert anything — we just remove this pair from both sets.

When checking if actually two pairs are the same I did stupid mistake and wrote an always-true condition.

if (ppl._2 == ppl._2) {
	stl.erase(stl.begin());
	str.erase(str.begin());
} else {
	// manipulate with sets
}

But it appeared that this mistake didn't ruin the solution. When we simply remove maximal elements from both sets we have a situation similar to a one with two independently sorted arrays (as in easier solution). After the contest my friend showed me this mistake and I was upset because didn't realize that easier solution works. But surprisingly it got AC, and now I understand why :)

»
6 лет назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

Even though I did not perform well today, I will probably remember this round as I hacked a solution with an anti-quicksort testdata.

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится -175 Проголосовать: не нравится

Today Chinese guys did so great. There were 4 Chinese in top 5, 7 Chinese in top 10 and 13 Chinese in top 20. How do you guys train?

sunset TLE whzzt fateice AwD xumingkuan ugly2333 yhx-12243 yfzcsc Tommyr7 orbitingflea zhangzy cz_xuyixuan

There must be a secret technique. ;)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone will tell me the approach for problem B ? thanks in advance .....

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

    Any digit (except for the first one and any nines that may appear) in the number n can result either from simple addition (d1 + d2 = dn) or addition with "carrying" (d1 + d2 = 10 + dn. So one possible solution is to check all bitmasks from 00...00 to 11...11 where 0 denotes that a certain digit is produced by simple addition and 1 that it was produced by "carrying" with taking care to discard masks that have 1 in a position where there''s a 9 followed by a 0.

    However, simply adding to seems to work.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    For a,b what matters is the sum of digits (and not the number itself) and for max sum have as many 9's in a as possible.

    So number of number that a can be 10 * (number of digits in n).

    Permute through all a's such that a < n and b = n-a and the find max(S(a)+S(b)).

    Link to my solution:43764388

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Though there were easy number theories for this problem, don't know why the idea of digit dp hit my mind. My solution using digit dp was not very complex though. Just construct every number a less than n and store maximum s(a)+s(n-a) in the dp table.
    My solution: 43766071

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    First sort l[] and r[]. Then iterate from reverse direction — if(l_i and r_i are of different person) then add max of them to answer because we can place them on adjacent places and left of one will be right of other. if(l_i & r_i are of same person) then form new group and add max of l_i and r_i to answer.

»
6 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

I wonder if there will be a tutorial? Or has it not come yet?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    I have been refreshing this blog page since last two hours to check for Tutorial update. Don't tell me there will be no tutorial.

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

where is the editorial?

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Problems were good. Eagerly waiting for the Editorial for some up-solving.

»
6 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Could you tell me where i can get the editorial? I can't understand the O(n^2) algorithm of C.

PS:It seems that D is much easier than C.I use skytyf this account in this contest and get 3 problems except C. --Sorry for my poor English :)--

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    It seems that if you could not solve D quickly, then it would be really difficlt... I solved A to E except D :( For me, the algorithm for C is more familiar.

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Problem D is great! But I was too stupid to solve it in the contest:(

»
6 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Could you share the tutorial?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

How does D work? I still don't understand the solutions. Will there be a formal proof for this sorting method? For some reason I can't convince myself that it's correct...

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    Not a formal proof but it's how I visualized it and maybe you can at least convince yourself:

    Imagine at the start, every person's a bead with a LHS end and a RHS end, and that we're linking the people together, one link at a time, into chains (that eventually links its ends together into cycles). From now, we MUST perform exactly N links to join all the unpaired ends and minimize the cost.

    Let's take the guy with the highest unpaired RHS or LHS cost. Let's say that it was a RHS cost that was larger than everything else, and let's call the cost V (if it was LHS it will be symmetrical). This person's RHS MUST be linked with somebody's LHS (maybe even his own). He can be linked with any available LHS, but who should he be linked with? Since V is >= any LHS cost, any linking is going to cost V anyway. So, you might as well pick the guy with the highest LHS cost, to "absorb" the biggest cost possible. It's the best choice, since if we picked a different LHS, the remaining links we must do would be EXACTLY the same except now one of the LHS elements is more costly, which is clearly less desirable. Now again consider the largest RHS or LHS cost of the remaining unpaired ends, and repeat the linking process.

    If you visualize this, you will see multiple chains that start growing and joining, and sometimes the chains close into cycles when the RHS of a chain links with the LHS of itself.

    Clearly, to implement this method, you will just iterate through the sorted lists of RHS and LHS costs one by one, linking them.

    To think of it another way, the final result is a permutation, P(i) = j where the i'th person has the j'th person on the right hand side. Look at what happens when you start at a person and go left to right, following the permutation — the circles of the seating are the cycles of the permutation.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +105 Проголосовать: не нравится

My solutions to some of the harder problems:

E: recursive DP. If the distance from u to v in the original was d, it is now ceil(d/2). Within a subtree, keep track of

  • sum of distances to all descendants at odd depth
  • sum of distances to all descendants at even depth
  • number of descendants of odd depth
  • number of descendants of even depth

With this information, one can link a new subtree to a parent in O(1) time. There are four cases, and in each case you can compute the sum of lengths of all paths through the new edge, as well as how much to add to account for the ceil().

F: we'll solve separately for each query (fortunately N is small to we don't need to be too careful about efficiency). Place the query node at the root. Now consider some subtree. For the first few shrinks, it won't matter which label is chosen, but at some point this subtree will be rooted at the root of the whole tree and then any shrink involving the root has to pick the root label. So we can use DP to answer this question for each subtree and each K: if the first K shrinks are "safe", what is the probability that the shrinks won't eliminate the root? We start from the leaves, and build up a tree using two operations; 1. Add an edge above the old root. To answer this, we need to consider each possible position this new edge can have in the sequence of shrinks of the subtree. 2. Join two trees together at the root. In this case the events in the trees are independent, but he have to consider all possible partitions of the safe shrinks between the two trees.

H: I had an algorithmically correct solution to this, but just ran out of time debugging it (I wasted a lot of time before reading that the other cells contained 1, not 0). Since we can add numbers, we can multiply a number by any constant, and we can do it in log time using the same trick normally used for fast exponentiation. That also means we can divide by a constant (just multiply by the inverse mod p), we can construct 0 (multiply anything by p) and negate numbers (multiply by -1).

We can compute xd, (x + 1)d, (x + 2)d, ..., (x + d)d, and express each as a linear combination of 1, x, x2, x3, ... xd. The resulting matrix can be inverted to allow any xi (0 ≤ i ≤ d) to be expressed as a linear combination of (x + j)d (0 ≤ j ≤ d).

This means that we can square numbers, and since xy = ((x + y)2 - x2 - y2) / 2, we're done.

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +94 Проголосовать: не нравится

    A few different solutions for problems E and H:

    E: Each path of length d becomes a path of length . This means the total sum of paths is equal to (sum of all path lengths + # of paths of odd length) / 2.

    Sum of all path lengths can be computed quickly by noting that each edge is crossed exactly sizeleft * sizeright times, where sizeleft and sizeright are the sizes of the two subtrees on either side of the edge. Number of paths of odd length can be computed similarly -- it's just nodd * neven where nodd and neven are the number of nodes with odd and even depth from the root, respectively.

    H: Consider the polynomial (a1 + a2 + ... + aD)D. It contains the term D!a1a2...aD as well as lots of other extraneous terms. Inclusion-exclusion on the D-th powers of each subset sum of ai leaves just this D!a1a2...aD term (since it's the only term that encompasses all D elements ai). Now apply this idea with a1 = x, a2 = y, a3 = a4 = ... = aD = 1 and you're done :)

    Really interesting to see this strategy in H of obtaining x2 from x. From looking at a few other contestants' solutions it looks like most people followed this route -- curious how you all thought of the idea!

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

      Nice solution to E.

      On H, I wonder if your solution was the intended one — it would explain the very low constraint on D, since your solution takes operations, whereas mine takes . As to how one thinks of it, I started with (x + y)d as the obvious way to get products of x and y, and then saw that as long as d=2 it would work out easily.

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      No, O(2d) solution was not expected, could you describe it? (I see you already did.) The constraint for d was kinda random.

      You can came to x2 idea by setting x = y. The reason we made no samples was to hide this idea, because it's quite apparent even from case d = 2, p = 3.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      For E is it possible to do ceil(ans/2) instead of counting odd and even? Thanks in advance.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Nope, let's say there are 3 paths of length 3 in the original tree, after adding the edges they would become 2, so 6 in total. ceil(9/2)=5

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    How to proof that the coefficients of xd, (x + 1)d, ..., (x + d)d are linearly independent under modulo p?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      That's a good question. It's something I remember (at least for the real numbers, and I just trusted it would also work out in the field mod p), but I can't think of a proof at the moment.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      If you look closely at Lagrange interpolation formula, you'll see it works while d < p.

      Alternatively, if you put coefficients in a d + 1 × d + 1 matrix , one can see it is (almost) Vandermond's matrix, and its determinant can be calculated directly.

»
6 лет назад, # |
  Проголосовать: нравится +65 Проголосовать: не нравится

Where is the editorial?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +95 Проголосовать: не нравится

The editorial is very funny.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i am new to BST. can anyone tell me the source or links for basic questions on BST for practice ? thanks in advance...

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    BSTs are usually asked in Interview questions rather than competitive programming.

    I think Hackerrank here has a really good collection of BST questions.

»
6 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

Well I've waited for the editorial for a whole day...

»
6 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

When you see this comment,you have wasted lots of time waiting the dead editorial.

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Does anybody know where the tutorial is?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    I think there won't be. Because last year's round by Barcelona Bootcamp doesn't have tutorial.

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

where is the Tutorial? I'v been waiting for several days!

I want to know how to solve F and H!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Do we have the editorials yet?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is there no tutorial?