chrome's blog

Single Round Match 633
By chrome, 10 years ago, In English

Today will be held Single Round Match 633 at 19:00 MSK.

Let's discuss here problems after the contest.

UPD: Contest delayed to 15 minutes

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

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

SRM 633 — Brought to you by Google :).

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

Anyone's going to compete in Div. II ?

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

    Most of Div2 users will compete in Div2 :D

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

      Glad to hear it :D I asked, because I have only seen Div.I problems discussed in this posts (most of the times).

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

Is there anyone facing problem with launching arena or doing registration? I can't launch my arena. I have downloaded the latest one. it shows a lot of exceptions when I try to launch it :(

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

Contest delayed 15 minutes :((

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

Good job Topcoder!

numerOfScrewedUpContests++;

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

    I considered this contest a good one for me. Happy to go back to yellow. :)

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

      He meant that some contestants weren't assigned a room, contest was delayed and challenge phase was delayed even more.

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

Awesome problems! How to solve 600? I've tried iterating over the node which is then called "root" in both trees, taking "tree1 + inverse_arcs(tree2)" and solving "max-weight strongly connected subset problem" there. It seems that this should somehow be reduced to max-flow, but I didn't figure out how :(

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

    Is is possible to solve "max-weight strongly connected subset problem" in poly time?

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

      I don't know about general case. But in this case, it is apparently possible, because (as pointed out below by azizkhan and Petr), if we also reverse the arcs of the first tree, we'll get max-weight closure problem.

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

    After you fix the root, the problem is finding the max weight subset which contains that root. Now you have 2 rooted trees. Let's build a network as follows: For each vertex v add a directed edges from it to its parents with infinite capacity in both trees. For each vertex v, where score[v] >= 0, add an edge from S to v with capacity score[v]. For each vertex v, where score[v] < 0, add an edge from v to T with capacity -score[v]. It can be shown that the answer is sum of positive scores minus minCut between vertices S and T.

    P.S. My solution is failed because I have a bug in MaxFlow algorithm

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

    After we've picked the root, then our condition boils down to: if we take a vertex, we need to take its parents in both trees.

    If we have a set of conditions "if we take X, we must take Y" we can apply min-cut by adding an infinite edge from X to Y — this way if we take X, we must take Y :) The only remaining part is choosing weights for edges from S and to T so that the weight of the cut is const+answer.

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

Woah, I just finished first in Div 2, had to share this somewhere.

I solved 250 and 500 (but not very fast), and then in the challenging phase I noticed a guy has only return "Solution exists" in this code. One guy tried challenging him, but accidentally entered a "solution exists" test and got a wrong challenge. I did that mistake too, but I was faster for the second challenge and got 25 off him. Then I noticed his 500 was also a return, I challenged it, and for the 250 he tried entering all possibilities manually, but only did it until 19, so I challenegd that one for a total of 125 from that guy.

Then I found two more wrong 500 solutions (one timed out, one had a flaw) for 100 more points.

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

    Did you advance to Div. 1 ? I spent most of the time debugging my 250 and got only something like 100 points for it and then there was no time left to solve 500...

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

      I sadly didn't. My first SRM was a complete blowout (two wrong solutions with very dumb mistakes and two wrong challenges) so I started with 300-ish rating. I advanced from 771 to 1136 this round.

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

        That's quite a jump anyway, congrats :D I'm like much more stable, my rating is always >= 900 && <= 1100.

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

I wonder which is Div 1 Easy which has the least % accepted. I remember Nickolas' AgeEncoding had very low acc rate.

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

Would anyone like to explain the problem of DIV-2 ,500 POINTS, 1000 POINTS how to solve both of these problem ?

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

    Div 2 500 :

    Let's look at the first test sample : We need to get to (5,4) with steps of distance 2 and 5. Using Euclidean distance we find the distance from the goal (5,4) to the start (0,0). In this case, the distance is 6.4. We also take a sum of all the steps. In this case, the sum is 7. If the sum is less than the distance, then you are not able to reach it in any way. Also, if the sum is equal to the distance, you are 100% able to reach it (just jumping directly towards the goal). Otherwise, we have this situation :

    We try to represent the path as a triangle, one side is the distance, the other sides are the steps you have in the input. For triangles, there's the following rule:

    a < b+c

    b < a+c

    c < a+b

    Otherwise stated : Every side of the triangle must be smaller than the sum of all other sides. If this is valid, then you return "Able", otherwise you return "Not able". This "theorem" is also valid for all other polygons. For example, if we had 4 sides, it would be :

    a < b+c+d

    b < a+c+d

    c < a+b+d

    d < a+b+c

    So you just have to check this theorem. Here's my solution.

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

      thanx add1ctus

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

        There is another way to think about this problem.

        If all reachable points after k jumps are a filled ring (true for first jump which is a circle). Where do all reachable points after k+1 jumps lie? Answer: A ring with a bigger outer radius (enlarged by k+1 th jump) and a smaller inner radius (diminished by k+1 th jump but not smaller than 0). And they also fill this ring completely.

        I don't have a strict mathematical prove though (I used a sheet of paper and circle to get the idea)

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

          oops, left out something crucial: The above is only true if jumps are in diminishing length.

          But one can convince oneself that the order of jumps doesn't matter so we can start with the largest jump. Again no proof (just pen and paper to get the idea)

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

      I was looking on similar solution all the Challenging, but I had no idea how it should work. Thanks a lot for your explanation!

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

      I am always confused about this one.Can you tell me while you are comparing sum and distance why are you doing this

      abs((double)sum-distance)<0.00001

      and not this

      abs((double)sum-distance)< numeric_limits<double>::epsilon()

      How can one decide that factor while comparing two doubles?

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

      We know, a triangle is valid, if
      a < b+c
      b < c+a
      c < a+b
      so, triangle with length {1,2,3} is not valid, as 3 < 1+2 isn't true. So in general, if a side is equal to summation of other side of a polygon, then this polygon isn't valid. Right ?

      Now in your code:

      double temp=sum+distance;
        for(int j=0;j<jumpLengths.size();j++)
            if(temp-jumpLengths[j]<jumpLengths[j])
                return "Not able";

      Here, why you don't need to check if temp-jumpLengths[j]is equal to jumpLengths[j] ?
      I coded like this comment(I returned "Not able" if temp-jumpLengths[j]<=jumpLengths[j]), but there is a input {1, 0, {100, 101}} for which my code returns "Not able", but judge says, "Able". From (0,0) to (1,0) distance is 1. If I think the input is a triangle with the length of {1,100,101} then 101 < 100+1 isn't true. So output should be "Not able". Shouldn't be it ? Please, clear me...

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

        Woah, this is actually a mistake on my end, and a lucky one (because if I didn't do that mistake, my answer would have been wrong).

        The problem with that theorem is that it is only valid for valid triangle. In the case of sides 1, 100 and 101, we have two angles of 0 degrees and one angle of 180 degrees. That is an invalid triangle, but it is a valid jump sequence. Removing the '=' will make sure that you count those jump sequences as well.

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

          Humm got it... Thanks... :)
          But it was really a tricky one and most probably the cause of too many system test failure is this case... :/
          how lucky you are !!! :P :)
          congratulation for division 2 winning ... :)

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

Rank 3 goes to egor in both the divisons :)

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

Div1-1000pts after considering each prime individually boils down to that problem
Is there an assignment for a[1], ..., a[n] such that some constraints of form max(a[i], a[j]) = c and min(a[i], a[j]) = d are fulfilled? If for particular vertex those constraints are contradictory, we return "NO". If not, then we can fulfill max edges with lowest label ot min edges with highest labels and we create a boolean variable for this. What is left to do is to check whether 2SAT is satisfiable (which can be very easily done since contraints are small — just check if there is vertex v such that there exist paths v->!v and !v->v)

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

Arena is not opening :(

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

How to solve Div 1 250?

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

    If you are in a jump n : You need to check if exist a polygon with sides of length jump[ 0 ] ,jump[ 1 ] , ...jump[ n] and the side with length x.

    So your answer is the minimum value of n.

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

Where can I see results of the round? Arena is down, topcoder.com is also down. Maybe someone has a copy of results. Please, share.

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

What is the solution for the Div2 1000 problem? Any hint anyone?

→ Reply