chrome's blog

Topcoder Single Round Match 687
By chrome, 9 years ago, translation, In English

Hi there!

Tomorrow at 14:00 MSK will be held Topcoder SRM 687.

Let's discuss problems after contest.

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

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

Starts in less than an hour.

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I forgot about it :-(

→ Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Spend half an hour trying to compile my code using Arena.

Now I can't even try to challenge anyone. 'Your request timed out'.

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

How to solve the Div-1 500?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Maybe cgy4ever has one of his crazy simple solutions, but notice that if a graph exists, then a tree exists. min-cut from u to v in a tree is simply smallest edge in the path from u to v, so you can greedily add the edges in the matrix from largest to smallest weight as long as the graph remains a tree (no cycles are formed).

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      This tree is called Gomory-Hu tree :)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +27 Vote: I do not like it

        And the algorithm he described is called Kruskal.

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

          I did exactly like that (kruskal for max spanning tree), but failed systest. Just noticed that the problem need connected graph, (we can add edge with weight = 0), at first I think the problem only reject empty vector (if the flow matches the given input). Next time I should to read problem more carefully :X

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

        Yup. Figured that out with 2 minutes to spare, sadly couldn't code it up in a way that accounts for the possibility of no solution (if a solution were guaranteed, you just return a copy of the row containing the largest element, with a single zero removed).

        Basically I'm pretty sure the answer is look for the largest element (or rather any one of them), construct a bidirectional edge from the row index to the column index (it is evident that the largest edge must be on the very end). Then from now on look only in that row. Look for the largest element (remember, only in the chosen row) whose index hasn't been added yet (you can do this very naively). Now add an edge from the last added index to that index, with the given weight. Continue until every vertex is accounted for. Do a modified Floyd-Warshall (with max instead of min, and min instead of add) on the resulting graph. Change all i,i values to zero because the problem says so. If the result is the exact same as your input matrix, return a copy of the row, minus the i,i element. If it's not, then return -1 since this means there is no solution.

        Does that sound right?

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

          Just found a counterexample... so I guess instead you could do the following. Find the largest value... that edge is still in the tree. After that, find the largest value in the whole matrix that contains at least one vertex that hasn't been added yet. Add that edge. Continue until you've added n-1 edges. Now do the modified Floyd-Warshall check I mentioned above, but instead of a row, return the added weights.

          → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      What is the proof that if a graph exists, then a tree exists?

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

        the proof is Gomory-Hu tree. As mentioned before.

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

500 div1: https://www.e-olymp.com/ru/problems/5468

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Why every sample in medium that results in a graph results in a star graph with center at zero? Was that intended?

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

    Wasn't answer to pretest 2 a triangle? (Although it could be also a chain of length 2, which is indeed a star graph)

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

How to solve div2-1000 ?

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

How to prove that greedy strategy works for Div 1 250?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Let's assume greedy works for every number between 2 and N - 1.

    Let's define Ai as the biggest number in the sequence s.t. Ai = N or Ai < N - 1. The number N - Ai is smaller than N and is not 1, so for it a greedy strategy works.

    The only thing left to show is that the greedy solution for N - Ai does not contain Ai and therefore no number is duplicated. (Obviously, it will not contain numbers bigger than Ai). Let's assume the opposite. Then N - Ai ≥ Ai, then N ≥ 2 * Ai ≥ Ai + Ai - 1 - 1 = Ai + 1, which contradicts our definition of Ai.

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

      Thanks!

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

      Hey , I think you missed out Ai = N - 1.

      We can still show in this case too, there always exists an answer:

      Ai - 1 + Ai - 2 - 1 = N - 1. that implies:

      Ai - 1 + Ai - 2 = N ( For all i > 2)

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

        It is a question of definition of Ai. Look again at mine — I don't define it as a largest element of sequence not exceeding N, I say that Ai is never N - 1, which implies that when largest element of sequence Fx not exceeding N is N - 1, I instead use Ai = Fx - 1, and so N = Fx - 1 + Fx - 2.

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it 
      2, 3, 4, 6, 9, 14, 22, 35

      Let's say N = 10

      According to your definition of Ai, Ai = 6. Here N is in fact >= Ai+1 which is 9, so how does it contradict your definition of Ai?

      I don't think I got that proof properly

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

        Yes, according to my definition, Ai = 6. Which is exactly why according to the strategy I described we will choose the solution (6, 4), instead of trying (9, ???) which won't work.

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

    Using induction method

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

Now the hard question comes: How to solve div1Hard? The only thing I noticed was that the negative difference was not a problem, because if we have an answer a0, a1, .., a(N-1) we can substract the minimum, obtaining at least one 0, guaranteeing the existence ofpozitive maximum difference for each allien, but I'm not even sure if this observation is usefull.

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

    There was a thread in Russian UI about it already. The solution is as follows. Let's solve weighted-matching problem (in graph with weights  - wij) together with its dual (most algorithms provide dual solution — potentials in Hungarian algorithm, potentials for Dijkstra inside min-cost-max-flow). Then just take  - πi where i is a destination, and possibly adjust all of them so that they're non-negative.

    Proof. Dual problem for weighted matching is as follows:

    find weights ws, wt for all vertices, so that:

    • For each edge s - t, ws + wt ≤ ws, t,

    One can notice that for an optimal solution of dual problem, every optimal solution of weighted-matching problem uses edges with ws + wt = ws, t. I.e. if we can adjust both skiers and destinations, we can adjust them with πi, and get a graph where there is a full matching on edges with adjusted weight 0, and all other edges have adjusted weight  ≤ 0. This would be enough for us, but we cannot touch skiers. Fortunately, if we just ignore them, relative order of their edges preserves, and potentials of destinations still give us a solution.

    → Reply
»
9 years ago, # |
  Vote: I like it +52 Vote: I do not like it

Hello everyone. I was the author for this round, and this is my 11th SRM. To be honest, this is probably not one of my better rounds because div1 med/hard were standard problems, but I had thought before they were not too standard, so I hope you still enjoyed seeing them.

Here are some solutions:

div2: http://pastebin.com/Qg6gSjyc

div1: http://pastebin.com/JJvhwVbA

Quorum — sort the array and take the sum of the first k numbers

Quacking — Greedily spell quack until string is empty. Also, you can see the solution that I linked.

Queueing — Instead of the probability distribution, we can say a cashier with experience p has probability 1/p of successfully processing a customer at any particular second. So, we can write a dp[i][j] -> prob that first cashier finishes if there are i people in the first line and j people in the second line. See the code for how to compute this dp table.

AlmostFibonacciKnapsack — Greedy works (i.e. choose largest a[i] <= x), except when a[i]+1 = x, but in that case a[i-1]+a[i-2] works. You also need to show that indices will be unique, but I'll leave the proof up to the reader.

AllGraphCuts — It's tempting to google and find Gomory Hu tree. But that is too complex for this problem. Instead, this problem is almost exactly like: http://mirror.codeforces.com/contest/632/problem/F. We can show that a solution exists if and only if the diagonal is zero, the matrix is symmetric and x[i][j] >= min(x[i][k], x[k][j]). If this condition is satisfied, then you can find a maximum spanning tree to get the actual graph.

Comments: I felt this was a fairly standard problem, and I originally set the difficulty as div2 hard. However, I thought it was also ok as a div1 med. It has shown up on a previous contest before (based on comments above), so I apologize for that.

AlienSkiSlopes — Suppose there isn't a perfect matching. Then, by Hall's theorem, there exist a subset of aliens S, such that their neighborhood to destinations T is smaller than S. Then, we increase all the heights of destinations until someone in S wants to choose something outside of T. Note that this may destroy some edges from aliens not in S to destinations in T. However, we can show that a modification of this process will terminate. (this is modified from cgy4ever's logic) Namely let's choose S,T such that D=|S|-|T| is maximized, and if there are still ties then find one with |S| minimized. You can show that D will increase, or D will remain the same and |S| will increase. To see this, even if we remove all edges from non-S to T, for each subset A of non-T: |adj(A)| >= |A| (otherwise let (S + A) be the new S, we will get a larger |S| — |T|).

You can also use this to show an answer always exists. Suppose that aliens can choose destinations with negative height differences. Then, if X is a solution, then adding any constant to all elements of X is also a solution. So, we can shift them until one of the entries in X is zero. Now, the maximum height difference for all aliens is nonnegative, so this is also a valid answer for the original problem.

Comments: I knew about the Hungarian algorithm, but I didn't actually understand how it works. It seems most competitors found a solution using the potentials computing during the Hungarian algorithm, so this reduced to a standard problem. I need to study my algorithms more.

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

    Sorry, I read your code but just can't know exactly how div2 1000 works. Assume q1 as the probability cashier1 finishes this second, q2 as the probability cashier2 finishes this second. dp[i][j] = dp[i-1][j]*q1*(1-q2) / (1- (1-q1)*(1-q2)) + ... so this means that one of the possiblity that c1 processes i people quicker than c2 processes j people contains: c1 processes (i — 1) people quicker than c2 processes j people, and now, c1 processes 1 more person but c2 doesn't, and this probability is divided by the prob that someone has processed a person. So how does this solution take care of the situation that c1 processes more quickly and even if c1 stops for a while, it could still be quicker than c2? Thanks. I just don't quite understand the solution. And would someone kindly provide a more detailed description of this solution?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      It might be easier to restate the problem. Let's say we have two people. Person 1 has a coin that comes up heads with probability 1/p1=q1, Person 2 has a coin that comes up heads with probability 1/p2=q2. Let X be the random variable representing the number of tosses person 1 takes to get len1 heads, and Y be the random variable representing the number of tosses person 2 takes to get len2 heads. We want to compute the probability X<Y. This is equivalent to the original problem.

      Now, the dp works as follows. At a particular second, person 1 still needs to toss i heads, and person 2 needs to toss j heads. Now, four things can happen. Person 1/2 can toss heads/tails. So we can compute dp[i][j] = dp[i][j]*P(TT) + dp[i-1][j]*P(HT) + dp[i][j-1]*P(TH) + dp[i-1][j-1]*P(HH). The base cases are dp[0][j>0] = 1 and dp[0][0] = 0.

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

        It seems dp[i][j]*P(TT) didn't include in your codes. Could you tell me why? Thanks

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

          Note that the recurrence is circular, so evaluating as is isn't correct.

          Instead, write it as dp[i][j] — dp[i][j]*P(TT) = X => dp[i][j](1-P(TT)) = X => dp[i][j] = X/(1-P(TT)), where X = dp[i-1][j]*P(HT) + dp[i][j-1]*P(TH) + dp[i-1][j-1]*P(HH).

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

            Hello, why the base case i.e. :

            Probability to make 0 heads by person 1 and j > 0 heads by person 2 is exactly 1?

            For eg: dp[0][1] represents that the second guy has exactly 1 Head and first guy has no Heads yet. How can the probability of this happening be 1?

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

        Thanks! I think I understand how that works. Still another question, why would the original probability that

        P(p, k) = (1 / p) * (1 - 1 / p)k - 1

        be equivalent to at any particular second one process a customer successfully with a probability of 1/p ?

        Is that: At any particular second, assume the probability is P, then, a cashier would end up this second if he started 1, 2, 3... seconds ago:

        (which is wrong but i can't figure out how.)

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

    Could you please add a detailed editorial also to the TopCoder problem set analysis? http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis

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

Could anyone explain solution of Div.2 C, please?

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

Could someone explain to me the implementation of Div-2 500 ? Understand the idea but not the implementation. Thanks.

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

    At each step keep deleting multiple subsequence "quack" that donot coincide in string a. If in the end you found a non empty string in then answer is -1 else it will be a positive integer.

    Problem lies here -> While searching for subsequence you need will delete terms in string but what if in the end you didn't find "quack" in it?

    Example -> quackq

    We delete first quack then we delete q thinking we will find subsequence in it.

    This is not what we want.

    So we will save from where we start assuming that we will find a subsequence. And if we don't find it then add the remaining part of the string.

    Code

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

    div 2 medium. solution idea

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

DIV — 2 1000, anyone ??

→ Reply