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

Hello everyone!

The second round of MemSQL Start[c]UP 3.0 will take place this Saturday, September 30, at 10:05am US/Pacific.

There will be an onsite round at MemSQL HQ and parallel online rounds that will be open for div1 and div2 participants. The online finalists (placed in top 500 in Round 1) will be given 100 MemSQL Start[c]UP T-shirts.

The onsite contestants will be participating from MemSQL HQ using their personal laptops. Breakfast will be served starting at 8:30 am, contest starts at 10:05 am and lunch will be served after the contest. The three winners of the onsite round will be awarded Amazon gift cards for $1000, $500 and $250. Please come early to set everything up.

Here is the list of people who agreed to participate: aandrew, al13n, Ali.Sh, architkarandikar, Belonogov, BIT-silence, chenmark, farmersrice, lewin, LiChenKoh, _M_, NgocHai, ntfoim, Paraboli4eskyHyperboloid, SaveVMK, scott_wu, sdya, SnapDragon, winger, Wo_oW, xiaowuc1, yum, yzyz.

If you haven't accepted the invitation yet or you think that we missed you, please message MikeMirzayanov or cerealguy.

We will update this post with more contest details later.

Good luck!

UPD: For onsite finalists: you are already registered for the corresponding round. You don't need to register anywhere else. For everybody else: choose the corresponding division round. All rounds will be rated for everybody, and we'll make special standings for the official participants of Round 2 (who placed in top 500 in Round 1).

UPD2: All online finalists will be registered in Div. 1 round automatically.

UPD3: Huge thanks to round testers: ashmelev, Errichto, cyand1317, gritukan!

UPD4: You will be able to see results of offsite finalists using this link.

Congratulations to winners!

Onsite finalists:

  1. scott_wu — $1000 Amazon gift card!
  2. Belonogov — $500 Amazon gift card!
  3. xiaowuc1 — $250 Amazon gift card!
  4. LiChenKoh
  5. sdya

Other finalists and div. 1:

  1. tourist
  2. Petr
  3. ksun48
  4. halyavin
  5. Arterm

Div. 2:

  1. laizenan
  2. PSMao
  3. lqs2015
  4. letsDoThatShit
  5. kr_abhinav
 
 
 
 
  • Проголосовать: нравится  
  • +192
  • Проголосовать: не нравится  

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

Round 1's announcement said "Only people who finished in the top 500 in Round 1 can participate." about Round 2. Now it says the online rounds are open for div1 and div2 participants.

So anyone can participate, or only people who finished in top 500 in Round 1?

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

    These two statements don't seem exclusive to me. It doesn't say the round is open to all div1 and div2 participants.

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

    what about offline round?

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

    if you dont know telavshi tovs and you can come with us for seeing tovli without any top 500 whatg do you think? p.s subscribe my YT channel "qurdi baxbaxa" and iqurde with me

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

I hope it is not open for everyone, it collides with Codechef.

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

Is this rated??

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

What? why is there a separation between div 1 and div 2? so how is the top 100 selected? Or does the t-shirt not really matter as Fcdkbear said

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

    Sorry if it was unclear, only those who placed in top 500 in Round 1 can win a t-shirt. They will be registered in Div. 1 automatically.

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

      Edit: I am registered in div1 indeed. Disregard content below.

      Thanks


      This is not true. I can't register in div 1 and I'm registered in div 2.

      I also think that the idea of separating the round is stupid, without separating top 500 in round 1 from the rest. It means you should have 4 contests or 3 if you join 25 onsite with 475 online.

      Otherwise I guess you will provide different problems for div 2 and how are you going to compare these participants in the official standings?

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

        Of course you can't register now because you will be registered automatically. Within a few hours.

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

          It will be my first div 1 contest while being in div 2 :P Maybe it was worth to do all these stupid mistakes during last contests, to make this historical event happen ;)

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

          You should also disable registration in div2 round. Otherwise it would be the first time I will participate in both div1 and div2 rounds at the same time. I wonder how will my rating be calculated in that case :)

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

            We will unregister everybody from top-500 from div2 closer to the beginning of the round.

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

Will there be a place for everyone to plug in laptops? My laptop's battery is broken.

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

    I called up MemSQL and they said there is. Consider this resolved. :)

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

    We will have enough room for everyone to plug in their laptops.

    Don't forget your chargers, this round will be longer than regular CF rounds!

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

Number of problems ?

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

I am registered in both divisions right now. So, which division will be considered for me? :/

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

    Div 1, read KAN's comment above.

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

      Yes, I read that comment, but in that comment he didn't make it clear what would happen if we're registered in both divisions so I was confused. He cleared it later though. Thanks anyway :)

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

Why are there div2 participants in div1 registration list?

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

    because they placed top 500 in the first round of memsql

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

moejy0viiiiiv and tourist both register,Who will win?:)

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

23 : 05 , 22 : 05 are best time for contest Codeforces should take all contest is that time.

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

Why registration is completed for div.1?

Edit: Ok looks like I'm automatically registered. It's pretty unobvious.

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

Scoring?

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

I registered in Div. 2 round but it seems that there is a bug in Codeforces that considered me as Div. 1 round participant.

Now I can't submit my solution to Div. 2 round.

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

    You are in top-500 of Round 1, so you should compete in Round 2, which is a div1 contest.

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

18 minutes in and not a single Div.2 contestant solved more than A and B, this round is pretty bad tbh

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

Why second example in problem A div 2 return YES ??.

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

The fourth note for Div2A is so funny lmao.

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

Div2 C's test 7 is an immovable test case xD

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

    really ? I passed the problem without any problem . i had a first try compile too which is an strange thing for me .

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

How to solve Div2-C ?

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

Is E greedy?

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

How to solve Div2 E?

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

    Can we solve it with maximum matching?

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

      Will you please elaborate?

      I tried a greedy approach to match each small query with nearest and largest but got a runtime error.

      Segment trees can never make your life easy. :(

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

        I didn't solve the problem, but I've started thinking in the direction of graphs.

        When we choose to take some number ai, we need to find a pair for this number aj, such that j > i and aj > ai. The weight of the edge (ai, aj) is wij = aj - ai. When we choose an edge (ai, aj) that excludes all the edges which come into aj.

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

          Okay, I am being able to relate my idea with this idea.

          Can you tell what will be the best choice for an edge then such that it can be taken into count?

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

          According to my idea, I sorted all elements of array a and then start taking them one by one.

          In each iteration, my idea was to find the maximum value in the array from pos + 1 to n where pos is the actual position of that element in array a.

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

    Here's what I did for Div 2 E (without segment trees): Have two sets(multisets) of unsold and sold items respectively. Every day, when you encounter a new price, you may choose to do one of the following: 1. sell the smallest element in unsold. 2. insert the smallest element in sold to the unsold set, and replace it with the new price in sold set for better profit, or 3. insert this new price in the unsold set(when both cases bring negative profits.) This has overall time complexity O(nlogn). submission

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

I liked the problemset. Too bad it was too hard for me.

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

Can div1D/div2E be solved with treap + binary search? I came up with this, but there were too little time to code it.

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

How to solve C, D, E?

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

    C: My solution is to fix answer by binary search!

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

      I tried binary search but all I got was a "WA on pretest 7". Can u please elaborate your approach? :)

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

      Fixed the final answer by binary search, populated the DP table and verified my assumption at the end.

      Code

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

      Yeah, I also used this approach. I'm so mindblowned until now, :")

      The DP approach is kinda straightforward, where the state is DP(at_which_level, total_time_up_to_this_level). The answer is on DP(0,0), but the problem is it can be cyclic to call DP(0,0) again at some points.

      Binary search the answer is to fix a double value of X, which we think it is the answer i.e. DP(0,0) is X. So whenever the the DP call DP(0,0) on the recurrence, replace it with X.

      Calling the "real value" of DP(0,0) then compare it with X. If DP(0,0) is more than X, then the answer must be > X, vice versa.

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

        Nice!

        Thanks a lot.

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

        I accept that if we put X as the optimal answer R, then, indeed, dp00 will have the value of R after the recurrence. But how does one prove that by assigning X = Y such that Y > R won't make dp00 ≥ Y?

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

          First, assume the expression is simple, and doesn't contain min operations. So, basically it'll be like dp00 = a + bX.

          Of course this can be easily solved. But I want you to observe that in this special case, dp00 < Y.

          Proof:

          dp00 - R = b(Y - R)

          0 ≤ b < 1

          |dp00 - R| < |Y - R|,

          hence if Y > R, dp00 < Y.

          Try to generalize this proof to include min operations. If you couldn't, I can elaborate more.

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

    D: I passed pretest using segment tree (greedy approach).

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

What is the solution for "Buy high sell low"? This looks like a very well known problem with failing greedy... or not?

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

    I did a simple greedy that passed but no proof

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

    It is like that http://codeforces.com/problemset/problem/391/F3 but different a bit.

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

    It is like searching for "max-cost matching" with edges of weights c_i-c_j (where i > j) in complete graph. However, I don't know how to do it effectively enough...

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

    I passed pretests using this. I always choose the lowest available stock. Then buy the highest possible "valid" stock. To check valid, I maintain prefix sums in segment tree, then I execute a range max query on some suffix of the array to find the selling point.

    UPD: Got AC. :D
    Code

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

      Does it passes :- 4 1 10 5 12 by your algo u should pair 1 and 12?

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

        Yes, it passes. Answer is 16.
        Yes, I pair 1 and 12 first. Then I buy 5 but after that, 10 is valid selling point as after buying 5, the prefix sum array is [1, 1, 2, 1].

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

          sorry i dont understand how are u choosing the range for valid stock. I understand that it will be some suffix of array but how to find where does that suffix starts?

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

            I maintain prefix sum in a segment tree. I find leftmost index such that no point to its right has prefix-sum 0, using binary search on segment tree. When I buy a stock, I do +1 range update and when I sell a stock I do -1 range update.

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

    I have pretest passed with this greedy algorithm: https://ideone.com/HPBkr4
    I iterate from the last object to the first, and push to the priorityqueue all the items with a flag if it was sold to a item with higher price (and greedily adding this difference). If this item appears at the top of the pq it means that if I bought it at Y and sold at X, and now I'm buying at Z with Z < Y < X, then I can change it to buying Z and selling at X, and being able to sell at Y when I encounter another item.

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

How to solve Div2 D ?

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

div2 B is div1 A !!!!!

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

My approach for C was to sort the array by a'i and b'i then to search for number of pizzas of type 1 with ternary search and greedy. But I could not debug for two hours! Please tell me that is wrong approach or I' gonna cry :D

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

I tried problem E with a greedy + segment tree based solution but was getting runtime error in pretest 3?

Can anybody tell me the mistake in algorithm or code?

Code — https://pastebin.com/MPQHs8eb

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

Thank you all for participation, I hope you enjoyed the problems!

The system testing will be delayed by about one hour, because onsite finalists need to have some rest and talk before they will be ready for the results revealing. Hope for your understanding!

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

    Can we at least look at other people solutions?

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

    onsite finalists need to have some rest and talk before they will be ready for the results revealing

    no we do not

    systest already please

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

      Agree — I also do not understand wtf?

      How systest is preventing them from talking and resting?

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

How to solve Div2-C ? I Wrong answer on pretest 7.

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

What's the idea for the solution of Div 2-B?

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

    If a = 1, just print 1 1 1, else if we have only 2 and 1 denominations, answer for some n will be n / 2 + 1 (can be easily proved), so for some a we print 2 * (a — 1) 2 1 2

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

    You can get any number of combinations by using the set of coins D = {1, 2}.

    We can use the formula for Combinations With Repetition to calculate the number of combinations.

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

      I've read the wikipedia. But "You can get any number of combinations by using the set of coins D = {1, 2}. ", it's still not clear to me. Can you please explain a little more? :(

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

        Sure!
        It's good that you've asked. I've read my comment again and I see that it's not good =)

        Yesterday I have started with a Diophantine equation x1 + 2·x2 = k and came to a - 1. This equation just stuck in my head and was thinking that there is a small mental step to multichoose(n, k), but looks like I was wrong =)

        Do you understand how to get to a - 1?

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

          No, it's still not clear to me. I've just started combinatorics from a few days ago. I know the basics. But I am not able to relate those with this. I can catch up only if you explain. Would you please? Thank you.

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

            Suppose we have to make k cents from a set of 1 cents and 2 cents. let k=1,then possible states are (1,0) (1 coin of 1 cent and 2 coin of 2 cent) i.e 1 way if k=2 then states are (2,0),(0,1)---2 ways if k=3 then states are (3,0),(1,1)---2 ways if k=4 then states are (4,0),(2,1),(0,2)--3 ways if k=5 then states are (5,0),(3,1),(1,2)-- 3 ways if k=6 then states are (6,0),(4,1),(2,2),(0,3) --4 ways so,there for k=n, there are (n/2)+1 ways. In the question,we are given ways and we have to find k. So,it will be 2*a-1 where a are given ways

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

              Okay, it's clear to observe now. Thanks a lot :)

              But did it came just from observation finding pattern or there's a theory that helped you which can be used for a different variation of this type of problem?

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

                [user:codeforces.com/profile/Pixar]helped me to understand.

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

                I drew it out and saw basically:

                1 = 1 = 1 combo

                2 = 1+1 or 2 = 2 combo

                3 = 1+1+1 or 2+1 or 3 = 3 combo

                4 = 1+1+1+1 or 2+2 or 2+1+1 or 4 = 4 combo

                5 = 1+1+1+1+1 or 2+1+1+1 or 2+2+1 or 5 = 4 combo

                6 = 1+1+1+1+1+1 or 2+1+1+1+1 or 2+2+1+1 or 2+2+2 or 6 = 5 combo

                You see a pattern that for each combo amount, the number that makes the combo amount is floor(num/2)+2 (ex: floor(5/2) + 2 = 4). So you "reverse" this because they give you the combo amount, making it (combo-2)*2 (ex: (5-2)*2 = 6). This way, you can make the given combo amount made up of numbers 1, 2, and (a-2)*2.

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

The Div2C problem left the same impression as GCJ problems. I like it a lot =)

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

    can u explain your solution please

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

      Split all the people into 2 groups: A, B.
      A = { people who prefer pizza A}
      B = { people who prefer pizza B}

      S(A) — the number of pizza slices needed for group A.
      S(B) — the number of pizza slices needed for group B.

      Now the best thing to do is to feed group A with pizza A and to feed group B with pizza of type B.
      We can do that almost always.

      Some pizzas of type A will be completely eaten by group A, but there may be needed some more pizza slices to feed the group A, but these slices do not form a complete pizza.

      Consider the remainders of pizza slices:
      R(A) = S(A) mod S — pizza slices needed for group A, without forming a complete pizza.
      R(B) = S(B) mod S — pizza slices needed for group B, without forming a complete pizza.

      If R(A) = 0 or R(B) = 0 or R(A) + R(B) > S, we can buy new pizzas of correct type and give them to corresponding groups. So in that case everyone will get the pizza slices from pizza that he wants.

      There is only one case when we need to feed some people from group A with pizza of type B (or the other way around). This is when R(A) > 0 and R(B) > 0 and R(A) + R(B) ≤ S. In this case we need to buy only one more pizza and we check two cases: 1. This pizza is of type A, 2. This pizza is of type B. In each of these cases we do greedily calculate max pleasure and choose the largest between the two.

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

        "In each of these cases we do greedily calculate max pleasure and choose the largest between the two."

        How do we do that? Pixar

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

          If you have two people that like pizza A more than B. Suppose that the first one likes A = 15 and B = 14 and the second one likes A = 5 and B = 1.

          If you have to chose one of them to feed using pizza B (because you don't have pizza A anymore), which one you would you chose? It's easy to see that the first one is better because you would lose less than if you chose the second (15-14 < 5-1).

          So if you have to change someone take the one whose difference between A and B is minimum.

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

Short but funny statements :D

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

DIV-1C. Why this idea is wrong (fails on sample 3)?
Let's Tprev is one of the possible expected total times to complete n-1 levels.
In order to surely complete level N in Fn seconds, required time delta is: Fn + (Sn + Tprev) * (1 — Pn) / Pn (including reset progress cost)
In order to surely complete level N in Sn seconds, required time delta is: Fn * Pn + Sn * (1 — Pn) (there is no reset progress cost)
Submission 30885018 (GetAns() function)

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

    Fn * Pn + Sn * (1 — Pn)

    The above one doesn't calculate the expected time ending at some 'X' second . If fn is chosen you complete earlier than 'X' by Sn — Fn seconds. Later this propagates wrongly for Fn case.

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

      Thanks, got it!
      Do you see any way to tune this formula? Or idea "DP by completion time from level to level" is completely wrong?

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

D is too hard for undestand

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

"The position of the boxes within the basket matters"

Didn't see this sentence in G, and gave up.

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

Problem C remind me my first participation of ICPC Regional in Asia Kuala Lumpur site 9 year ago... There is a problem containing a step with same idea(UVa12164).

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

No Hacks this time !! :)

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

Tonight, I'll dream of a pizza containing 100000 slices :D

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

How to solve Div1 E, F, G? I tried to solve G using matrix powers, but my solution is too slow.

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

    The answer is the constant term of series

    .

    Let M = max ci. So the answer is

    .

    Subtract the remainder from the numerator, and substitute x=0. You can get the constant term of the quotient.

    You can find the remainder using polynomial division only. So the time complexity is .

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

      So this problem is only about knowledge. Once, you know, just write and get it. Not much thinking.

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

        Yes... I thought the hardest problem in the memsql cup should be unsolvable (like 457F). So I skipped this one during the contest.

        However, I think this one is much easier than E and F for me :(

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

      I got your solution but don't know how to compute remainder. can you plz explain or provide some source where I can learn it

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

    My solution to F (which hopefully will sneak under TL and ML):

    First, don't end the game when one person eats R raw eggs. Then if one person ever gets at least R+1 total raw eggs, that person is guaranteed to lose. Therefore we can only consider the cases when each person eats exactly R raw eggs and C cooked eggs, and we want to minimize |# scenarios in which A wins — # scenarios in which B wins|, out of a total of (R+C choose R)^2 total scenarios.

    Now look at a sequence of A and B as path on an (R+C) by (R+C) grid. The number of scenarios in which A wins is the area under this path (grid segments will have length not 1 but (x choose r-1) ). We can use dp with a map to keep a list of which areas under the path are possible at each points in the grid, as well as how many paths attain that area.

    Finally, we need to use a meet-in-the-middle to speed this up. For me, the best choice for "middle" in the case where R = 10 and C = 20 was the first 38 turns vs last 22 turns.

    To speed this up, I also precalculated the optimal difference for each R,C and hardcoded this into my program.

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

      Close to intended solution, however if you notice that the first R-1 rows and columns in the grid have zero area, you only need to meet-in-the-middle on the remaining 2*(C+1) moves.

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

        I think my solution implicitly uses this (which gives the choice of split at 38/22). It is very tight at the time limit, though.

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

    E: first, let's try all possibilities for which of the positions have "carry" when the subtraction happens. Now we know for each position the difference between the numbers. The sum of all those differences must be zero (this cuts down the number of possibilities from 2**13 to C(13, 6)).

    Now let's look at the cycles of the permutation of the digits. Each cycle must have at least one zero digit (otherwise we can decrease all digits to get a smaller number). So we can assume that we have just one big cycle, since they can be joined using the zeros.

    Now we need to build this big cycle. Let's build it starting with its zero, and then each next digit is given by the current digit plus the difference in the current position (which we already know from the first paragraph). So we can do dynamic programming where the state is the set of positions we have already placed, and which remembers the smallest number formed by digits in those positions. In order to find the next digit to be placed, we just sum the differences of the already placed positions.

    Overall running time is around C(13,6)*14*2**14 which is 400 million.

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

When will system test start?

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

came after 1 hours to see standings! still pending system testing!

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

Just start the system test already. I can't wait to see whether I become blue or not

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

WA on test case 60 on C. Disappointing!

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

sorry but i was stupid, and problemsetters were not stupid.

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

When will we be able to submit?

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

Never in my life did I imagine my name will be in contest announcement. Thanks cerealguy

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

First one to solve Problem C. Rank 1 for 5 minutes. Great feeling :D

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

    can u pls explain your solution, basically when p1 % s + p2 % s <= s in your code?? tia

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

      if (p1%s + p2%s <= s) then we can make 1 pizza of remaining slices from both pizzas. So, we'll try both the cases. First add remaining slices of first pizza to second pizza starting from the slice whose difference between first and second pizza is lowest. Second is add remaining slices of second pizza to first pizza starting from the slice whose difference between second and first pizza is lowest. Then the maximum of above two cases is the answer.

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

    Hey, Can you explain How you solved problem C ?

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

When will the editorial be posted ?

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

For Div2 B / Div1 A, can someone explain tourist's code? 30874326

Why do we need to build max(1, 2(n-1)) using 1 and 2 coins to achieve n possible combinations?

Any insights would be appreciated c:

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

    Each number has a certain number of twos. These twos can be made either of the coin value 2 or two coins value 1. So each time you increase by two, you are increasing the result by one possibility. Therefore it's 2(n — 1).

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

      Thanks man, that's really helpful.

      Welp, this made me realized I probably don't belong in codeforces contests until I practice more.

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

Hey Please Give me the approach to solve Ordering Pizza :(

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

    First try to allot everyone the slices they prefer (max(a[i], b[i]), ignoring the restriction of buying minimum number of pizzas.

    To fit into the restriction of buying minimum number of pizzas, you will have to give some participants slices they do not prefer. To minimize this 'regret', you will want to disappoint the people with least (a[i] — b[i] or b[i] — a[i]) values. In case of a tie, you want to disappoint the one who eats less slices (s[i].

    Create two groups, people who prefer pizza of type 'A' over 'B' (a[i] > b[i]) and others (a[i] <= b[i]). Let's call these groups group-1 and group-2. Try to disappoint participants from one group by storing pairs of (a[i] — b[i], s[i]) (eg for group-1) for both groups.

    Sort these vectors of pairs and greedily disappoint participants of both groups independently. Your final answer is (max_happiness_ignoring_restriction - min_regret_of_the_two_possibilities)

    You can look at my solution for details 30902595

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

http://codeforces.com/contest/867/submission/30902968 plzz help, why i m getting runtime error on testcase 6?

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

when will the editorial be out?

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

    The editorial is available since one hour, but the contest announcement hasn't been updated yet, so here's the link

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

When can we expect Editorials? Other's solutions too hard for me to grasp :/

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

can anybody explain me Reyna's solution in D/Div 1 ? 30879284

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

has it editorial or analysis?

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

Can anyone explain div2 C?

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

How to prove that binary search can be applied to Div2D? I solved this problem but I can't prove it.

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

please publish the editorial

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

I just see that Problem Div 2B is so entusiactic. :D

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

Where are editorials of this round? I am looking for the editorial of 'Ordering Pizza'.

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

I really liked your article , your article is very petrified me in the learning process and provide additional knowledge to me, maybe I can learn more from you, I will wait for your next article article. Thanks a lot for providing this much informative stuff is perfectly excellent. color switch

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

So are there any updates about the T-shirts(tbh, I only care about this year's...). I hope there is still hope.