Блог пользователя I_love_tigersugar

Автор I_love_tigersugar, 10 лет назад, По-английски

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.

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

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

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

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

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)

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

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

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

    Challenges work well for me.

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

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

      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! :(

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

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

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

          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).

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

          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).

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

Это ж надо так написать

res = min(solve(holeH, holeW, boardH, boardW), 
          solve(holeH, holeW, boardH, boardW))
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    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?

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

      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.

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

        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

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

          Same thing, but I have one more bug :)

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

          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.

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

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

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

    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.

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

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

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

      How to make the flow network ?

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

        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...

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

    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...

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

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

      my solution can't even pass pretests

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

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

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

          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.

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

            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.

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

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

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

        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

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

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

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

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

        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 :(

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

    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.

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

      This does not pass the last sample case.

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

      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).

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

    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.

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

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

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

FST!

:((

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

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

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

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.

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

    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

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

      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 ):

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

        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.

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

          ah, my line of thought was exactly this one:

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

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

    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.

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

    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].

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

      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!

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

Ребят, стыдно задавать такой вопрос, но все же, как решать 1000 див2?

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

    Если X/Y (округленное вниз) > 1, то можно моделировать. За один ход проскакивать количество дней равное количеству конфет, затем пересчитывать деньги и конфеты. При таком условии количество конфет из итерации к итерации будет расти экспоненциально. O(logZ).

    Если X/Y (округленное вниз) == 1, то можно моделировать. Заметим, что изначально у нас 0 конфет (после первого вечера). Через несколько дней остаток накопится (если X != Y, но этот случай совсем тривиален) и в некоторый день у нас появится 1 запасная конфета. Заметим, что теперь каждый раз, когда мы будем покупать конфеты у нас будет хотя бы одна запасная. Через несколько ходов уже не 1 конфета, а 2, 3, 4... За одну итерацию можно проскакивать все дни, в которых одно и то же количество запасных конфет (суммарный остаток должен в очередной раз переполнить Y, ..., какие-то вычисления на бумажке). Так как если у нас k запасных конфет, то и дней мы промоделируем хотя бы k, то в итоге за n итераций мы промоделируем 1 + 2 + 3 + 4 + ... + n = O(n2) дней. .

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

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]

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

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

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

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