By MikeMirzayanov, 3 weeks ago, translation, In English,

Hello, Codeforces!

I'd like to invite you to join in Playrix Codescapes Cup for the both divisions that will be held on May 11 at 18:35 MSK. The round is rated and open for everyone.

Problems are prepared by KAN, Al.Cash, MikeMirzayanov and fcspartakm. Huge thanks to Playrix company for making this round possible. Hope you enjoy the round!

Playrix is one of the leading mobile games development companies in the world. Its distributed team consists of 450 professionals from around the world. The company has released three successful mobile free-to-play games – Township, Fishdom and Gardenscapes. All of the projects have consistently been among the Top 50 Grossing Apps for iOS and Google Play since their release.In 2016, Facebook named Gardenscapes game of the year.

Company is looking for Russian-speaking C++ developers.

Prizes from the Playrix company:

  • Top 1: iPadPro 9,7 + PowerBank + T-shirt with logo
  • Top 2-5: PowerBank + T-shirt with logo
  • Top 6-50: T-shirt with logo
  • (New!) Random 5 participants (not from top-50, submitted at least once): T-shirt with logo

Congratulations to the winners!

  1. tourist
  2. LHiC
  3. subscriber
  4. W4yneb0t
  5. enot110

The problem analysis is published.

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

»
3 weeks ago, # |
  Vote: I like it +49 Vote: I do not like it

why all of the jobs in codeforces are for Russian-speaking contestants?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +91 Vote: I do not like it

    I think it's a matter of the companies which hold contests on CF , not CF itself.

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Register again. Previous registration has been cancelled.

»
3 weeks ago, # |
  Vote: I like it +50 Vote: I do not like it

How many problems?

»
3 weeks ago, # |
Rev. 2   Vote: I like it -74 Vote: I do not like it

Tourist winning another round ? Hope he participates.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow very awesome!!

»
3 weeks ago, # |
  Vote: I like it +106 Vote: I do not like it

tourist will complete his set of apple products.

»
2 weeks ago, # |
Rev. 2   Vote: I like it +49 Vote: I do not like it

Posted time: 15:35 UTC

Actual time: probably 15:45 UTC

»
2 weeks ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

Hi, everybody.

The offer to organizers from the company Playrix

Considering that the Playrix is engaged in development of games, I would advise to bring some spirit of surprise in a contest :) For example, to add 3-5 small prizes (or T-shirts) which by a randomly method will get to participants outside the first hundred, and maybe the first thousand. It would stimulate attraction to a contest of players.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    would be fantastic, no newbies got a tshirt before.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Although I totally love the idea and also love to get a T-shirt, but I think keeping it for the first 50 is better. To encourage low-rate participants to do better and EARN the T-shirt.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      I don't urge to take away t-shirts at TOP-50 participants. ))) I suggest to give IN ADDITION 3-5 t-shirts for participants from the first thousand

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +84 Vote: I do not like it

    Great idea, thanks! Playrix will give 5 additional prizes to random participants not included in the top 50. I hope CF will help us with fair random algorithms )

    Best Regards, Trushkov Aleksey Playrix

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      Thank you for understanding. P.S. Понадобятся идеи, обращайтесь, на кетайщине их хватает ))

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

It would be great if you will announce such events more than a day before. Thanks.

»
2 weeks ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

Problem prepared by MikeMirzayanov! I'm not gonna miss it.

»
2 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

I predict there will be an obscure Geometry problem.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +31 Vote: I do not like it

    Given that Playrix is a games development company?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      Playrix is one of the leading mobile games development companies in the world.

»
2 weeks ago, # |
  Vote: I like it +135 Vote: I do not like it

T-shirt on girl is really great :D

»
2 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

I hope there won't be delay before the contest.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

T-Shirt <3

»
2 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

Dafuq happened to the right hand of the t-shirt girl?..look at those veins :O

»
2 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it
»
2 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope it's easy to understand all the problems, And all participants will enjoy the contest. :)

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

The T-Shirt Looks Nice

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

How does back of white T-shirt look?

»
2 weeks ago, # |
  Vote: I like it +62 Vote: I do not like it

Rating prediction,

Extensions:

Have fun & high rating:)

PS One guy wrote to me that he couldn't install extension. Does anybody else has the same problem?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have same problem :(

    "An error has occurred There was a problem adding the item to Chrome. Please refresh the page and try again."

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I think I got this message when I had slow internet speed

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

how many problems???

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

T-shirts very well

»
2 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Is my luck so poor?

I never get a random prize.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Well considering that 4500 ppl will participate in this round 50 for them will get prizes for sure that leaves 4450 the probability that one will get a prize is 0.0011235955.

    Your luck is not poor it's just math.

    :)

    PS: if you work hard enough you won't need luck cause your probability will be 1.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Actually, assuming 4500 people submit at least once, the probability that you win one of the 5 random T-Shirts is 0.003366496682134068.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      Still got a higher chance than finding our soulmate

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I wonder if the T-shirts in this contest will be distributed based on an adaption of the formula from the problem in the previous contest 807B - T-Shirt Hunt ...

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

i think that it will be a little bit tricky one and challenging too.....

»
2 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

What about scoring distribution?

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

The '#' took the perfect place in the picture.

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Expecting a 10 minute delay. xD

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How many problems? What's the scoring distribution?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    5 minutes before the contest: we're still waiting for more info

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

tourist registered. maybe he is going to be champion

»
2 weeks ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

Look at girl's right hand. What is that monster dude...?

»
2 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

wow.. no delays .. so unusual ..

»
2 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

hope to be in random 5 !!!

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

mikemirzayanov please give tourist a new color :O

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can't agree more :)

    Or just a choice of any color he wishes

»
2 weeks ago, # |
  Vote: I like it +288 Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

how to solve D?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dp[h][w] in map

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    Notice that for ai >= 3, you will need maximum of 11 items to increase alength from 1 to over 10**5. So you can brute over min(22, n) largest items to divide them into either Length/width. Incase the length is still less, then find how many no of 2's will satisfy Maintain a count of actual length increments done and find the minimum answer.

    Complexity: O(2**22 * 20)

    I thought this should pass. But this was very close to tle. 940ms first time for me. But after doing some bad optimizations, it passes pretest ins 499ms. (I lost around 400 points on this :|)

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      If reverse sorted a[] is like five 6, five 5, five 4, five 3, five 2, you can brute over x '6' to width and 5-x '6' to height. And so on for the rest of the unique values in a[]. I think a binary search is required at the lowest level as you may not need all of 5-x 'smallest-digit'. And we must also consider inverted the rectangle by 90degree. The max time this will take is 2*( 2^(2*10 + 2*log11) ).

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    if you sort in non-increasing order, you should not to skip some extension, answer is some prefix, so you can use dp[idx][pair(curW, curH)] with map 27034588

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is also possible to memoize only one of the parameters (h or w). The other one may be derived from the current index of the dp if you precompute the prefix product of the sequence.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      what is the time complexity of this approach? how many elements in the worst case will be added to the map?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In my solution , it's O(max(a,b)) — since there are sqrt(x) different x/y numbers for y belongs to integers. so sqrt(x)*sqrt(x) for the pair = O(x) = O(max(a,b)).

»
2 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Congrats tourist , i was spectating whole round lol

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Taking fountain with diamond + coin is easy. Then use two pointers\bin search for coin + coin, diamond + diamond pair.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Then use two pointers\bin search for coin + coin, diamond + diamond pair.

      Could you, please, explain how to do that? It looks like a knapsack for me.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        When we buy fountain for x coins, we still have c — x coins. So you can sort and find max prefix that you can buy with c — x coins, and find max beauty in that prefix with prefix maximums.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think that with this approach we can choose one fountain twice.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Nope, we just limit our prefix by i — 1.

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yeah, really, I didn't think about that, thank you!

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            not if you binary search corectly. you should make hi=i-1 and it is imposible to take fountain i twice

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I described that in my comment below.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Could you share your code?

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Here (might fail because of bugs)(don't look at the segtree, I haven't used it).

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              My solution is failing on test 4 . How to handle it ?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        well,you have 2 cases:you take two of the same type(2 coins or 2 diamonds) or you take one fountain with diamonds and one with coins.

        1 diamond+1coin: you take the most beautifull fountain you can afford for each type

        2 diamonds/coins: you take fountain i,and search for another fountain j,such that their beauty is maximal for i,and their cost is small enough

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          such that their beauty is maximal for i,and their cost is small enough

          I don't understand how to do that.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            you select a fountain i,and say "ok,i would like to buy this fountain and another one of the same type,but i would like to take the most beautifull one i can afford". so beauty[i]+beauty[j] is maximal,and cost[i]+cost[j]<=C(or D,depends on case)

            and res will be max of all this cases and case 1(1 diamond+1 coin)

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              We do O(n) steps to choose fountain i. For each of i we do O(n) operations to find j'th fountain. Right?

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                we find j in logN steps by sorting the array and binary searching after,but thats the tedious part,and its hard to explain.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  ... logN steps by sorting the array and binary searching ...

                  So, we sort by beauty or by cost?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  by cost

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  In this case, after sorting the array by cost and getting the position of the fountain with less or equal to (total coins — coins for selected fountain) coins, wouldn't one need to check for all fountains less than this found price as well? Then, will it still be logN?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                  Rev. 2   Vote: I like it +1 Vote: I do not like it

                  yes,because it would be something like max(beauty[1],....beauty[j]),which can be precalculated with another array,where V[i]=max(beauty[1],beauty[2],....,beauty[i])

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I have used the same approach but my solution is giving WA on test 4 .

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                  Rev. 3   Vote: I like it 0 Vote: I do not like it

                  Well,You did something wrong in the code than. Belive me,this approach is good,and i got accepted with it

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              "ok,i would like to buy this fountain and another one of the same type,but i would like to take the most beautifull one i can afford"

              But can it be a situation like we can choose 2 fountains in one currency without that fountain we chose in the first time?

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                Yes,thats why you take each fountain i from 1 to number_of_same_type,and after you do a max

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      @Reol , I have done same thing as you are mentioning. But was getting WA for 4th testcase... can't figure out what is mistake,,,

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Exact same case with me. I did binary search and keep getting WA on 4th test case.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          @hrushikesht, binary search ???

          I thought it was simple knapsack problem... where picking up 2 fountains was compulsory :| ... Can't say for sure...

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            well its pretty hard to do knapsack on this,considering you would end up with O(N*C*D) plus,you can choose a maximum of 2 elements,so that would be a costant of 2

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              @georgerapeanu

              What I mean by knapsack is that.

              firts of all split fountains which can be bought by only diamonds , and only coins,,, then given list of fountains which can be bougth by only coins,,, use knapsack for them ,,, and DP table size will be ,,,

              (number_of_coin_fountains * 2) same goes for number_of_diamond_mountains*2 size for other process... Since costs of fountains are within the 10^5 ,,, that was most preferable approach(in my opinion),,,

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                wouldnt it be O(C*number_of_coin*2)?

                because you should take care of the cost,and you are at index i,and you have selected k fountains so far

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

                  @georgerapeanu,,,

                  yeah , my bad,,,

                  it will be maximum 100000*2 ,,, and we can fill up the DP table in linear time...

                  but now, you must be getting an idea,,, which KNAPSACK I was talking about

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I used segment tree range maximum query to find the best pair

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please elaborate more on the approach?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it +2 Vote: I do not like it

        There are 3 cases: 1. Get 1 fountain with diamonds and 1 with coins, 2. Get both with coins, 3. Get both with diamonds.

        Case 1 is easy: buy the most beautiful ones that you can afford.

        For cases 2 and 3 you can use 2 separate segment trees: st[0 or 1][i] = most beautiful fountain that costs i coins (0) or diamonds (1). Iterate through all fountains. If you take fountain i, you have c — cost[i] coins left. Let this amount be x. Use range max query on first segment tree to find the most beautiful fountain whose cost is in the range 1...x and take the sum of current one's beauty and this one's. Then, store current fountain in the segtree. The same applies for diamonds, just use another segtree.

        From each case you get a value, answer is the maximum of these. Be aware of the situations when you can't buy two fountains.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Observe that you can either pay with coins only, diamonds only or both.

    Sort by Coins or Diamonds whatever the case and have a dp array such that dp[i] is the fountain with biggest beauty in the range [0..i].

    We can use binary search for any of the cases.

    In the last case, iterate through the coin array and use binary search on the corresponding Diamond array.

    I think all three cases should produce a best value.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was thinking about dp[i], but it can be that for some i1 and i2 that i1 + i2 <= d/c dp[i1] and dp[i2] will be the beauty of the same fountain, or did i misunderstood something?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        noeInadal states what I'm trying to say.

        So once you understand that there are three cases, you basically use binary search and sorting to achieve your aim.

        It is possible to code without duplicate creation.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are three ways of purchasing two fountains:

    • one of each type;
    • two of the first type;
    • two of the second type.

    In the first case, just consider, for every type, the maximum beauty among the fountains whose price is lower or equal to the number of coins of this type. Then, the maximum beauty is the sum of these two.

    Then, sort fountains separately according to their price, and precompute for every fountain the maximum beauty with a fountain whose price is lower of equal than this fountain. Then move from most expensive fountain to cheapest one and update the answer if you can.

    Complexity in O(nlog(n)).

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Unfortunately for me because I attempted and solved(pretest) C, I could not come back and solve my B on time. I hope my speed increases soon. :(

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did not solve it but those who find segtree easier than bin search can try this for the cases coin+coin and diamond+diamond. For every cost x, maintain two values, the two maximum beauty available and call them b1 and b2. If there is only one, set b1 to -inf and if there is none, set b1 and b2 both to -inf. Now build a segtree over the costs and every leaf node stores the maximum beauty possible with the given cost. If you select a fountain with cost x, replace in segtree with the second maximum beauty and query the segtree. Repeat this for every possible cost.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No binary search needed. Since the maximum possible price is not that big, it can be solved as follows.

    Let's compute fc[i] := (id1, id2) such that id1 is the index of the most beautiful fountain with the cost at most i coins, and id2 is the index of the second most beautiful fountains with the cost at most i coins.

    Similarly, fd[i] := (id1, id2) such that id1 is the index of the most beautiful fountain with the cost at most i diamonds, and id2 is the index of the second most beautiful fountains with the cost at most i diamonds.

    These two tables can be easily computed in O(n) starting from i = 1 (or O(n*log(n)) if someone is lazy) if you have fountains grouped initially by an exact price.

    After that, the only thing to do is to combine the results considering all the cases: you pay only with coins for both, you pay only with diamonds for both, you pay with coins for one and with diamonds for the other.

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think it's awesome how computational geometry problems can be so conceptually simple and yet so hard to solve in contest time (ok probably because it was the last question too).

What's the solution for E? (I get the strange feeling that some sort of clever gradual refinement might somehow pass, since it is almost a linear programming question.)

Edit: seems like modified mincost maxflow might work...

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest I liked the problems very much...C was a little bit tedious tho.

How to solve D ?

:)

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Since 2^18 > 1e5, you only need something like 60 items with best cost.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      2^17 > 1e5 and 34 items total I believe.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think so, but I hate tight bounds so I decided to take 55 elements :D

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    What is 4th testcase bro ? (for C question)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sort the array a, and then try all possibilities by having last k elements in use? I used multiset array to store variantions of h and w, for some k and then go thru all of them in (k-1) array and try to multiply. As the multiplicator is at least 2 the multisets size might not explode :D

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    C was easy to code using BIT. Not at all tedious. code

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      ankububble can you please explain your concept behind your code .... thanks

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Sure.
        Let dp(i) denote the max beauty when you have to pick 2 fountains from first i fountains and you are selecting the ith fountain. When I am calculating dp(i) , I need to iterate over all j<i, and select the fountain that passes the budget and has the max beauty. This is O(n^2). BITs are used to speed this up.
        I used BIT to compute prefix max. For fountain of price p and beauty b, I set bit[p] = b. To compute fountain with max beauty within price range <= K, we can take max from bit for prefix of length K.
        Hope this helps. Have a good day!

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Got it ... Thanks a lot and same to you :)

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    solved

»
2 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

I told you we have much confidence on tourist winning the round. Now see he has won it by huge huge margin. On your face who gave me downvotes on my previous comments.

»
2 weeks ago, # |
Rev. 2   Vote: I like it +36 Vote: I do not like it

There are random t-shirts again, so we will use a similar algorithm to the one used several months ago. We have a pseudo-random generator based on testlib.h. The seed will be the winner score in the Tinkoff Cnallenge Final Round on Saturday. The printed integers are the winning places, the ties are broken by the time of last AC.

Generator
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    you use number_of_participants_with_positive_score while in announcement tshirt is for those who have at least one submission

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why do you use seed from the next contest?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    So winner score is 8876 and number_of_participants_made_at_least_one_submission is 3465,

    I get these five numbers: 903 935 1552 1591 2272

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +40 Vote: I do not like it

    The seed is 8876, the number_of_participants_made_at_least_one_submission is 3465. So the winners are

    Place Handle
    903 Acarus
    935 Xris
    1552 MashiroSky
    1591 orz010orz
    2272 Abuccts

    Congratulations!

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I need help in Problem D.

I need to solve this Subproblem.

Given an array A = [a1, a2, a3, ..., an] and an Integer X.

Get a Sub Sequence B = [b1, b2, b3, ..., bm] from array A such that b1 * b2 * b3 * ... * bm is >= X and as minimum as possible.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    Hint: Note that bi >= 2. So you need at most 17 elements to make their product > 10^5.
    Hint2: Suppose you are kinking K numbers. You will sort them in descending order and pick the first K numbers.

»
2 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

Submitting problem A and passed pretest: YES! I did it! I'm the f**king genius! Let's check the dashboard. WTF?! tourist solved problem E already?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    We know he is a legend :) But he solved E after 41 minutes while you solved A after 22 minutes.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      22 minutes: Submitted. 22 minutes ~ about 26 minutes: In queue. I checked dashboard: he got '-1' on problem E So, you're right. It should be 'He has submitted problem E already' exactly.

»
2 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

Due to technical reasons the system testing and the rating update will probably be delayed a bit.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Why people vote this comment ://////

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      my question too ... !

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        because he is the codeforces co-ordinator.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          I think you should better look the message than the writer of it:/

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Because he is informing the community so most people don't start expecting immediate system testing. This in my opinion is a respectful thing to do.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    systesting started fairly fast...guess rating change is going to be a bitch.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    I removed cheaters and recalculated the ratings.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi:

I understand that the contest is finished, but is there a way to still submit my code, just to test for myself..?

Cheers

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Usually the problems will be added to the problemset, you can upsolve them there

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, after the contest is completely finished, you can submit your code for a problem or run a virtual contest for you. Cheers

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After system test finishes

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can upsolve after system testing.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest is over but I am not able to see the submissions of other users. Why is it so?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For C, I separated coins and diamonds. Applied knapsack on both of them individually. Then I just checked the maximum 2 values that can be generated taking care of if 2 fountains cannot be generated. Is this method wrong?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    TLE and MLE Unless you did one hell of an optimization.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank You. I missed to consider memory limit completely.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 4   Vote: I like it +4 Vote: I do not like it

    there are 3 choices :

    1) 1 cois + 1 diamond

    2) 2 coins

    3) 2 diamonds

    the first is easy , the second and the third are the same

    you have a vector of pair for each type { price , beauty } sorted in ascending order

    try the first fountain to be v[i] with price p1 and you have coins-p1 left

    the second one will be from range [ 0 , min(i-1, upper_bound(coins-p1)-1 ) ]

    now take the one with max beauty ( precalculation )

    something like that ...

»
2 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

In some last minutes, I used brute force way with O(n^2) for problem C and passed the pretest. So the pretest is weak and it is the chance for some cheater who passing it by this way, then open other solution in the same room to find the "real" solution.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, it doesn't make a difference, does it? He/She cannot resubmit his/her solution. And it was more or less obvious from the constraints that an O(n^2) solution would time out, so he didn't necessarily have to look at an optimal solution to figure that out.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Someone can have fake account and see others' solution with locking in fake account, then write in his real account.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That can also be done if doesn't pass pretests...

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Yes but then it requires solution that passes pretests with intended complexity. This is harder, thus making cheating harder, which is a good thing.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        How do you think XD

»
2 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Why was the memory limit so tight in C? I got memory limit exceeded with only 2 segment trees and total memory of around 12 * 105. My contest got ruined because of this :(

By the way, how much memory can I declare when 256 MB is the limit?

Edit: Nevermind, memory limit wasn't tight. I'm just stupid.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same problem )=

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    No there will be a different issue. 12*10^5 easily fits 256 MB.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I got same error, the problem was in my build function, say if count of 'C' is zero, u shld take care of this in ur build(1,1,count(C)) in the segment tree for C(Coins)

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Oh god! I think you're right! I'm so stupid -_-

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes. That's it. I wasted the entire contest on that. Lesson learned I guess.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Your contest got ruined because you are used to use segment trees everywhere, even if there is much simpler solution.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      Nothing wrong in that :P. segment trees is not "complex"

»
2 weeks ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Hats off for strong pretests. Update: I meant in D mainly, and I didn't see many hacks in general.

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Someone know why MLE here http://codeforces.com/contest/799/submission/27036789 I only use 10^6 integers or where am I wrong?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can't see others' submissions before systest. Can you pastebin it?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Sure, it's a little ugly

      code
»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Were there pretest on D that needed rotation before answering? Its sad that after trying optimization to fit into tle , i forgot this part and now i will get WA...

»
2 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it
Why my solution Memory limit #4

I don't undertstand
About my memory MX=1e5; two (int,int)[4 * MX] = 2*4*4*4*MX = 128*MX two int MX = 2*MX all 128 * MX + 2 * MX = 130 * MX I think int array[1e6] = 4 Megabyte I tnink **** **** **** ******My memory about 50 Megabyte + (void with other) <= 256 Megabyte**

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve A? xd

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    We can iterate through time and compute the number of cakes that we can do in that time.

    for (int time = 1; true; time++)
    {
      int cnt_cakes1 = ...; // Number of cakes WITHOUT second oven.
      if (cnt_cakes1 >= needed_cakes)
      {
        cout << "NO";
        return 0;
      }
       
      int cnt_cakes2 = cnt_cakes1 + ...; // Number of cakes WITH second oven.
      if (cnt_cakes2 >= needed_cakes)
      {
        cout << "YES";
        return 0;
      }
    }
    
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved it like this: First, I calculated time needed for oven 1 to bake all the cakes. t1 = ceil(n/k)*t

    Then I do t1 — t which is the time the last batch of cakes were put in the oven. If it is less than equal to d, there is no need to build another oven.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if (d // t) * k + k >= n then answer is NO, else answer is YES

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if ( ceil ( n * 1. / k ) * t — t <= d ) cout << "NO" ; else cout << "YES";

»
2 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Can someone tell me why my approach for C is wrong?

First, I try to match 1 fountain of C with 1 fountain of D. In that case it will be the most beautiful of each one that I can afford. The other case is to get 2 fountains of C or 2 fountains of D.

So I sort them by cost, and build a segment tree of maximum beauty within range. Then, for each fountain, I take its cost and binary search the most expensive fountain that I can afford (which will give me an index j in the array the segment tree was based on). Then I just query the segment tree for the range (i+1, j). Then take the maximum of every iteration on both types.

Code: https://ghostbin.com/paste/ogevq

Wrong Answer on pretest 4.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What if the fountain of maximum beauty lays in the range from (0,i-1) ? It doesn't look like you account for that

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      well, then it would have been found on an early iteration. I always take the fountain i with the fountain returned by the query. If the best fountain to pair with i (let's call it j) is before i itself, then in the iteration of j the query would have returned i.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why aren't others solutions visible?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just wish I am lucky enough to get a T-shirt, please :)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any help in B please?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    here's my code it's long but very easy to understand.

    Note: SF(x) means scanf("%d", &x)

    Code

    :)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I used set of tuples: (color1, price, color2). It contained each t-shirt twice: (front, price, back) and (back, price, front). So on queries i choose the cheapest t-shirt of given color using upper_bound and erase it from set twice( (front, price, back) and (back, price, front) ). If there's no t-shirts of such color, answer is -1.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Short solution : code

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I made sorted vector of (price, color_front, color_back, is_sold) and three pointers.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My Solution CODE

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved B using set in O(mlogn) but my solution didn't care about number of colours, though it was limited to 3. So now I wonder whether it can be solved in linear time or not?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why WA11 on E? Can somebody help me?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is the general solution to fit some 'both like' decorations + minheap on the rest of the decorations?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why TLE on B 27019672. As far as i know the erase function returns number of elements deleted.

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

My solution to problem C got WA because I was comparing a price with a beauty by mistake, the idea was to compare two beauties. After the contest I fixed that and I got AC. How could the first solution have passed the damn pretests!?

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

WA on 27 in D. ARGHHHHH!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably failure to consider rectangle rotation? I also WAed 27 of D by forgetting to swap variables: "if ((curr >= a && area/curr >= b) || (curr >= a && area/curr >= b))"

»
2 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

The Magic returns again Random_shuffle (: http://codeforces.com/contest/799/submission/27038984

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Sometimes I think maybe try random but never have enough confidence to really try it

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    I believe this shit is the reason of KAN's comment about that the results are not final :D

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

So weak pretest on C. Jesus, there was only 10 tests and all of them were soooo simple. Nice trap)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B-: link-: http://codeforces.com/contest/799/submission/27030194

Can any one please have a look at my code it gives Runtime error on pretest 9 ??. i can't figure it out why..??

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code assumes that front and back sides of a T-shirt are TWO DISTINCT T-shirts.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No,not really that's why why i have deleted the price of current buyer from all color consist of set of price (ie v[i],i=1,2,3) here v[i] is the set of color i.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I_hate_my_color please have a look at my code ?? got frustrated ..why got runtime error ??

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You should store (*it) in a variable then delete it from various sets. Consider x=1 and v[1].size()=1. You first delete it then use (*it) for i=2, and i=3 which is invalid and cause run-time error.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks it works...But both way of doing it is same but OH MY bad luck solution is correct but due to this error it got runtime on 9. Bad day..

»
2 weeks ago, # |
  Vote: I like it +157 Vote: I do not like it

You know you are legendary when you fail E on system tests but you are still the first

»
2 weeks ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

27040141

this submission should get wrong ans

printing -1 for this case

100000 100000 1 1 4

99999 99999 99999 99999

»
2 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

c 27040159

what is the problem with this?

»
2 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

The results (and rating change) are not final yet, the final results will be within several hours.

»
2 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

what is problem of this code

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    First thing to do when you get RTE: Check the arrays bounds!!

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks it works

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey I was also getting runtime error on Case 9 this but as soon as I did del = *it and then used this del to erase then it got passed this but I am unable to understand why this is so ??

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why they made pretest in D so that you don't need to swap(a, b) in no way ant it still passes pretests, when after real tests it fails :/ My solution

»
2 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

D was such an amazing problem indeed

I guess my solution is a bit odd but it takes 78ms to finish

My idea was to deal with the easiest two cases separately, that's when the answer is 0 or 1

For the general case:

We are told that the smallest ai value is not less than 2, which means that in worst case we need 17 elements for each side a = b = 100, 000, w = h = 1, n = 100, 000, that's 34 elements at most, cool isn't it

Well that number 34 makes it seems like it's dynamic programming with bitmasking, hmmm maybe but I couldn't utilize this fact much

Anyway let's take a look at the worst case, we have 34 elements and we need to choose a subset of these numbers, multiply them together with one of sides, then multiply the complements of said subset with the other side and check if we can enclose an a * b inside

But 34 is a big number, I would gladly do something like that if it was something like 17, but hey, what if split it into 2 halves, each of which is at most 17 elements, that's 217 subsets -- we can sort the second one in descending order and then loop over each subset in the first half, for each one I want to find the best match in the second sorted half, we may add with each subset the value of its compliment, do something like partial sums over them such that subcomplement[i] = Maxi: subcomplement[0..i]

Now we can do for each subset in first half a binary search over the range of subsets, if we can satisfy:

w * subleft[i] * subright[l...r] >  = a and check if h * subleftcomplement[i] * subrightcomplement[r] >  = b or when w,h are swapped and a,b are swapped i.e. four cases then there is a solution using 34 elements

We can try to reduce the count to the half and repeat the process around log2(34) times

Basically we are doing binary search over answer (count) and using meet in the middle technique to check it quickly

Not so sure about the big-O though, may be O(2m / 2 * log2(2m / 2) * log2(m)) and m <  = 34

Anyway here is the link

27042867(Submission link)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I believe the expected solution was along these lines. I was trying to do something similar during the contest time. However, I am still not sure how many people got a simple bfs like solution to pass this constrains. It seems like they are actually exploring a tree with a branching factor of 2 (either multiply the current number to w o h) and the shallowest solution can be upto depth 34. Obviously many branches can be easily pruned but why was this optimization so significant?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      For a fixed set of extensions, let the final area of the field after applying all of them be A. Then if A/(a*b) > 100000, there must be a solution (Consider moving field extensions from the width to the height 1 at a time).

      So A < 1e15. Notice that all states we have are divisors of A, and that no number below 1e15 has too many factors (cannot remember how many, but it's way way less than 2^30). Thus pruning is very effective.

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

        Wont there be multiple states corresponding to one divisor of A.Could ou please elaborate on the proof.

        • »
          »
          »
          »
          »
          9 days ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          This is similar to the knapsack problem https://en.wikipedia.org/wiki/Knapsack_problem. Here the value and weights are the same. Consider the following solution:

          Number the items 1 to n. Consider the set S={0}. For 1 to n, do:

          Update S' to be S union {S*w_i}. That is, we add to the set S the new possible values that we could form with items up to n. To do this, we just need to add at most |S| values, i.e. the size of the already existing set. The pruning of repeated values keep the size of |S| small.

          If |S| is bounded by 100000, then we require at most 100000 operations per iteration of the for loop, which is still a lot less than 2^30, and hence runs in time.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have done the same. Forgot to swap h, w and perform it again. I used set for those 34 elements. When for a particular mask, I select some of those 34 elements, I remove them from mask and give it to h, then to make w >= b, I greedily reverse iterate on the set till I make w>=b. code

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I also thought subsets are 2 power 34 . So dynamic programming might time out. But if u observe states are not distinct unless all a[i] are distinct . The states will keep repeating(and 17 is possible only if all a[i] are two). So as 10! is less than 10^5 . Total states will be around 2^20 or so (this is just intuitive). So this is the reason why dp works

  • »
    »
    44 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please explain the part where we take complements of the sets .Suppose I choose a particular subset and then do binary search in the other set for the height.Then how do I do for the width.DO we have to try all complements of the chosen subset or one full complement of the chosen subset?

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem C, any case just as test 4 but simpler ?

UPD: AC .. sorry for inconvenience.

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve problem E? Thanks.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Denote set of decorations liked by both to be A, set liked by Arkady only to be B, set liked by Masha only to be C, and set liked by neither to be D. Sort these sets in ascending order by cost and keep their prefix sums.

    We fix the number of decorations we pick from set A to be x. Then we need at least (k-x) items from set B and set C, and (m-x-2*(k-x)) (call this number KK) remaining items from any set. The (k-x) items from set B and C we can just optimally pick the cheapest items. For the rest, we need to pick the cheapest KK items from any of the sets B,C,and D. Call this final optimal set of KK items to be S. We can binary search for the maximum value M in S (look for the minimum M such that the number of items <= to M in sets B,C,D sum up to more than KK). To do this for each set B,C,D we binary search again for number of items less than M and sum them up. If the minimum such M gives us L items that are <= M, then we subtract (L-K)*M from the prefix sum since all the over-counted items will have cost M.

    Loop through all possible values of x (0 to |A|) and get optimum answer.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had a similar idea.But I saw many people solve it with segment tree. Can someone elaborate on that?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        After fixing x, we are trying to solve the following problem:

        Find sum of z cheapest items in the union of the following arrays:

        • Some suffix of B
        • Some suffix of C
        • All of D

        We can keep a segment tree to tell us this quantity. Note that as x increases, we keep looking at larger suffixes of B and C, so we can keep two pointers for B and C and maintain all the candidate values in a segment tree, and report the optimal sum in .

        Ugly Code

        By the way, did anyone else think that problems A-E were sort of standard logically, and focused more toward implementation? I think there is a huge jump in difficulty from E to F. E isn't really difficult to solve on paper but tricky to code quickly..

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot for the help!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this problem can be done greedily by using 2 min heaps and 1 max heap. In one heap we will keep all the decorations with weight(cost) for common to both and 2*weight for dec that is liked by exactly one.Second heap for minimum common decoration not yet picked(after all buckets are filled).Third for costliest decoration(belonging to exactly one) which has been picked.If we've not filled all the m decorations we remove from third heap and insert from second one.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

B.Submitted

Can anyone say why my source code takes 280ms (in n=1.0*10^5) and takes over 3000ms in n=2.0*10^5)? I think it's time complexity is O((m+n)logn)... I guess why the program works slowly is that I used std::deque...?

cf) I used struct to save p,a,b and saved that structs(t-shirts) at the deque(one,two,three) and sorted and when the buyer want to buy t-shirts, I used "pop_front" and "erase" to erase one t-shirts.. I think "erase" is cause of TLE...

please help me

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess that your idea may be right.

    Complexity Linear on the number of elements erased (destructions). Plus, depending on the particular library implemention, up to an additional linear time on the number of elements between position and one of the ends of the deque.

    quote from:deque::erase

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, you are right.. If I use priority-queue(min_heap).. I think I can solve it faster :) Thanks a lot! have a nice day!

»
2 weeks ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

I think the final tests for C are too weak. I got AC in the contest 27031840 , but now I realize that I made some mistakes when I decided to reduce the execution time. ex.it will WA on the data below

2 10 0
5 3 C
6 3 C

Now I have fixed the mistakes.27044385 [If you guys can find other mistakes, please tell me. thx!]

Sorry for my poor English.XD

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D is also solvable with Meet-In-The-Middle.
Here is my code 27046475

»
2 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

When will the editorial be available?

»
2 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

when will the random 5 participant who get tshirt be posted .

»
2 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

When will be the editorial uploaded?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I have TL in my solve: 27047914. It s very strange

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem C

is it ok to sort by bi/qi and then use binary search?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i did that, sorted by bi then binary searched over bi.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      i mean sort on (bi/qi)(devide :D)

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        No, you can't. Cause worst case is O(n^2), like you picked most quality thing, now you have only 5 c it doesn't mean, what you should buy most expensive thing, cause it can have lower quality then cheap. Sry for me english)

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I meant that the binary search is useless in this situation

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

What is the intended solution in F? I've accepted solution with no more than 24n queries to the segment tree in upsolving but had some troubles fitting it in time limit. I've seen some solutions without this data structure, maybe someone can share his approach?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I've posted the problem analysis. My code is 27058630, it uses no more than 2m + 6n queries to segment tree.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why this solution fails on C?

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

MikeMirzayanov KAN, When will you announce the five random T-shirt winners ?

»
2 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

Why so serious?  My corrently account is sina-ss you send me whats your problem

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I have seen solutions of C using fenwick tree( also called Binary Indexed Tree or BIT) such as this one : (http://codeforces.com/contest/799/submission/27019364) Can somebody explain this ?