I_love_tigersugar's blog

TopCoder SRM 629 — Long time with no SRMs
By I_love_tigersugar, 10 years ago, In English

Tomorrow, SRM 629 will be held at 11:00 EDT. This SRM is 3 weeks after the previous one (SRM 628 was on Jul 22, my birthday :D ). 3 weeks without TopCoder (except TCO14 Round 3), I'm sure that many people and I miss TopCoder too much! A sad fact that the number of SRMs is decreasing recently. After some months with 4 SRMs each, July has only 2, August has 3, and it's still not sure about next months. I don't know the reason, but it will be a great pity if there aren't any more SRMs.

I like some SRM rules. The one I like most is that the ratings will change if we open a problem. This forces us to try our best to solve problems, or our ratings will decrease much (we can't keep our ratings unchange by not making any submissions). The next one is value of a problem starts decreasing when we open it (not from the beginning of the contests). We don't have to choose which problem to solve first, and next. I also prefer to have coding and challenging phase separately, since the cost of challenging will be reduced.

I hope there will be more SRMs in the future, as many as recent months. Wishing you a wonderful SRM and high rating. Don't forget to share your thinking about TopCoder and discuss the round problems here AFTER CONTEST ENDS.

Thank you.

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

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

So long time with no SRMs, and now we have just two SRMs ;)

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

Actually I like Codeforces challenge rule more, because 1. You need a good "sense of hack" — that is, to notice some problems have some tricky point, if you lock problem early and start hacking you can get a lot more opportunity; 2. If someone else hacks you then you still have a chance to correct it (Of course lost some points, but better than nothing :p)

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

just after coding phase ended, the arena went dead and now it is not opening for challenge phase.
is anybody else having this problem?

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

    Challenges work well for me.

    First time competing on TopCoder, lost 50 points from challenging correct codes. -.-

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

      i had a good test case ready to challenge Div-1 250, and my friend just told me that there were 7 successful challenges in my room.
      how unlucky for me! :(

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

        I think it happened for all people of our college . My arena went down during challenge phase too .

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

          My arena did not go down. I tried challenging my own solution as I realized it was wrong(but it was not allowed, of course).

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

          firstly, i am not in college at the moment.
          secondly, i'm not sure about "all people of our college". Zzyzx (the same friend i mentioned) is in college now, and he told me that everything was working well for him during the challenge phase (albeit he hadn't registered, and was just watching).

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

There are so many successful challenges. The problem B is too hard for me. Are there any ideas about B?

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

    I have no idea why we can't buy 6 candies of the 0th shape and 11 candies of the 2nd shape. Can somebody explain, please?

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

      If you buy 6 candies of the 0th shape, they might all be of flavor 1 and thus you don't have anything for flavor 0.

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

        Should have been replace cost[i] = Math.min(Number1[i], Number2[i]) + 1 with cost[i] = Math.max(Number1[i], Number2[i]) + 1 T_T

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

          Same thing, but I have one more bug :)

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

          Lol, it is much more complicated than that xd. You need to consider also "left cost" and "right cost", but my solution also hasn't passed xd.

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

            Sure, but it made me to stare at the sample like for 15 minutes. The things could go much better without this bug)

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

    I made a graph with costs ( edge from type1 <-> type2 with cost min(number1,number2)+1 ) and tried to add and replace edges increasingly by cost.

    I have no idea what is the good abordation. Maybe some DP. I am not even sure I got the statement right.

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

    i tried doing it with MCMF, but got successfully challenged ): the guy who challenged me did some DP i couldn't understand

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

      How to make the flow network ?

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

        i did this steps:

        • put edges from source to tastes with cost=0 and cap=1

        • put edges from tastes to target with cap=2 and cost=0

        • put edges from tastes to sizes with cap=1 and cost=amt of the other type of candies +1

        • (Tricky part here, probably where I got it all wrong) i've created a dummy vertex for each size and assigned edges from tastes to this w/ cost=0, cap=1, and from this vertex to its taste with cap=2 and cost=max(num[i],num[j])+1

        EDIT: I realize now that it wouldn't work...

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

    For each candy with the same shape, You have four options, get T1 flavor with cost N2+1, get T2 flavor with cost N1+1, get T1 and T2 flavor with cost max(N1,N2)+1, or get nothing, knowing this we could build a graph with edge (T1,T2), with special properties that each component will have exactly one cycle, which could be solve using dp tree.

    Unfortunately, i didn't have enough time to debug my solution during the contest :(

    EDIT : just realize that each component will be a simple cycle... which means it could be solved using linear DP :( , got mixed up with with another special case graph where each vertex have exacty one outgoing vertex...

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

      Well I thought we must buy max(N1,N2)+1 or nothing, but that was wrong...

      my solution can't even pass pretests

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

        We can buy 0, min(N1, N2) + 1, or max(N1, N2) + 1;

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

          I missed that point min(N1,N2)+1. Then I reduced the problem to vertex cover of set of cycles. But actually it's possible only to choose one vertex(by min(N1,N2)+1), so it got WA.

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

            Yes, Vertex cover doesn't work here, because if we buy min(N1, N2) + 1 then there is a one condition must hold to another shape.

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

      what would be the answer on this graph? I didn't get that.

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

        it was to compute minimum vertex+edge cover of the graph.

        for each vertex v, the weight was minimum cost to get flavor v

        for each edge u-v, the weight was minimum cost to get flavor u and v

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

      Why is that ? ( "each component will have exactly one cycle" )

      EDIT : It's ok. Saw andreyv's comment. ( and read again the statement )

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

        because all vertices in the graph have two degree, but i don't really know to prove it

        EDIT : i was wrong, it will be a simple cycle :(

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

    I had this idea. Consider a graph where the vertices are shapes, and two vertices are connected if both shapes can have the same flavor. Then notice how each vertex has exactly two neighbors, and thus the graph is a collection of simple cycles. Consider one such cycle. We need to choose some of its vertices so that each edge is connected to at least one chosen vertex. If we choose one cycle's vertex as first, we can run linear DP from it: on each step i we either take the vertex i and DP value from vertex i - 2, or we don't take the current vertex and use DP value from vertex i - 1. Then there is some trickiness at the end, when the last vertex is connected to the first. And the cost of taking each vertex is max(Number1[v], Number2[v]) + 1.

    I couldn't finish the solution in time, so I don't know whether it's correct.

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

      This does not pass the last sample case.

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

      This is correct, except that you have to take into account one more thing.

      If you buy Number1[v]+1, you are guaranteed to get at least one candy of type Type2[v]. In your graph, you can treat this as self-edges and modify the DP accordingly (the recurrence is very similar).

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

    Observation:
    Let's flavor i connected with shape a and b. shape a also connected with flavor j, b also connected with flavor k. Let's denote W(a, i) -> number of candies of shape a and flavor i.

    When we may not buy flavor of type i?
    When number of bought candies of shape a <= W(a, j) because we can buy all flavor type of j and When number of bought candies of shape b <= W(b, k)

    For every shape a, there are two equations mustn't hold:
    Assume they are:
    a <= i && b <= j
    a <= k && c <= l

    So possible values of a: 0, min(i,k)+1 and max(i,k)+1

    Graph can be divided into several circles, because every vertex has exactly two children. We can do dynamic programming on that circle.

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

Waiting for editorial of 950-problem. Maybe MinakoKojima will help me?

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

FST!

:((

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

how to solve Div 2 1000? No one in Div 2 got it :(.

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

I would like to know why my solution for 550 div 2 works. For each person, I take his density d = weight[i] / Volume[i] and calculate the sum of the differences with this density . I take the minimum of this sums. At the end, I got Accepted and I saw a lot of solutions with the same idea. Why is this a correct idea? I thought about the average density at first but It didn't work. Thanks in advance.

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

    I used the same approach and it worked( don't know why), but first I approached it with minimizing sum of squares ( to minimize this-> |a1-d*b1| + |a2-d*b2| ... I tried to minimize this function-> (a1-d*b1)^2 + (a2-d*b2)^2) like it is done in linear regression using differentiation, but it did not work. Can somebody also explain why this approach was wrong? Thnx

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

      did the same thing here... this is what i am trying here:

      (weighti - d * voli)2 = weighti2 - 2 * d * voli * weighti + d2 * voli2, so

      If we call , , , we have a parabola:

      a * d2 + b * d + c

      This function will never be negative, since it's just some algebraic manipulation from a sum of squares, so it must be convex and it's critical point must be it's minimal. we just have to derive a * d2 + b * d + c and equal it to zero to find the density to which it's minimal:

      I wish someone would point out what's wrong with this ):

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

        Your problem is on the very first line. It is simply not true that minimizing the sum of the absolute values is the same as minimizing the sum of the squares, and I wonder why you thought that.

        Example: the minimum for the sum f(x) = |2 - x| + |3 - x| + |10 - x| is 8, which happens for x = 3.

        The minimum value for the sum g(x) = (2 - x)2 + (3 - x)2 + (10 - x)2 is 38, which happens for x = 5. We can see g(3) = 50 is not optimal.

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

          ah, my line of thought was exactly this one:

          If , I can just ignore this root and work with the square.

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

    We have to minimize function f(x)=sum(i=1..n, abs(x*volume[i]-weight[i])). So, we have to find its extremum. One easy idea of proof if graphical =) If you draw this function, you can see that it consists of segments connecting points (d[i],f(d[i])), where d[i]=weight[i]/volume[i], i=1..n. On each interval between these points our function is linear.

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

    A possible thought for this problem:

    Expand |ax + b| to |x + b/a| + |x + b/a| + ... + |x + b/a| (a items) For example, |2x-3| + |3x-6| + |x-7| = |x-1.5| + |x-1.5| + |x-2| + |x-2| + |x-2| + |x-7|

    In a result the question become to find the median of {1.5,1.5,2,2,2,7} (assume you may know the fact). So the best value of density will occur among weight[i] / Volume[i].

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

      Best explanation. Thanks! I had this intuition that it has got something to do with the median. I took the coefficient of x out but did not know what to do then.(Though I got it accepted by working out the answer from the test cases).

      Maths is awesome!

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

Solution of Div.2 hard problem:

First, if x =  = y, then obviously answer is 0. So assume x > y

Let rem = money left on day t, cur = candies left on day t (both taken at noon);

Initially rem = xmody, cur = xdivy.

Then, since x > y, after cur days Alice buys another cur candies, her money left will increase cur * (x - y), and let diff = cur * (x - y); Notice that if rem + diff ≥ y, Alice will actually buy more candies.

We will split into two cases then:

  1. if rem + diff < y, Alice needs period = ⌈(y - rem) / diff⌉ times to iterate cur days until cur increases. In such case, cur only increases by 1 after period * cur days;

  2. if rem + diff ≥ y, cur immediately increases after cur days, and because diff could be very large because cur will increase, we need modulars here. After cur days, Alice will get rem + diff additional money if she still buys only cur candies, so cur will increase by (rem + diff)divy, and rem = (rem + diff)%y.

The first case takes period * cur days, and second takes cur days. If days left < days to be taken, we should calculate the final result and terminate. The result is trivial: in first case finalResult = rem + (daysLeft / cur) * diff + (daysLeft%cur) * x, in second case it's just rem + daysLeft * x. If days left  ≥  days to be taken, we will keep iterating the process.

Complexity analysis: Both cases can be done in O(1), so we just care about number of iterations. After one iteration cur increases by at least 1, thus after k iterations days passed = Ω(k2), so running time for one test case is , enough to pass all tests.

Code in C++

PS: This is the first time that I try to write a solution with

Unable to parse markup [type=CF_TEX]

and I was reading AoPS LaTeX tutorial while I was writing this solution... BTW, I think that tutorial is very great to someone who don't know how to use

Unable to parse markup [type=CF_TEX]

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

someone can provide an explanation of div 1 500?, thanks.

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

And now there are only two SRMs in month... I like SRM competition (also I like CF), so I think we will be happy if there are more (like 3 or 4 SRMs in month).
But I think the quality of problem is improving much :P

→ Reply