KAN's blog

Playrix Codescapes Cup Problems Analysis
By KAN, 8 years ago, translation, In English
A: Carrot Cakes
B: T-shirt buying
C: Fountains
D: Field expansion
E: Aquarium decoration
F: Beautiful fountains rows
G: Cut the pie
  • Vote: I like it
  • +52
  • Vote: I do not like it

Comments Comments (30)
| Write comment?
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What a beatiful solution for D )

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

    What a beautiful solution for E

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

Someone plz explain me the solution for Carrot Cakes ?

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

    You can simulate the entire process on time ( Since constraints are low. The maximum time it would take to get 1000 cakes is 1e6)

    First situation : You only have first oven. Then calculate the time you need to get atleast n cakes.

    Second situation : From starting you have first oven. At time t = d , you have second oven too. Simultaneously calculate the time needed to get atleast n cakes.

    If time required in second situation is less than first situation , then it is reasonable to build the second oven.

    Code

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

      Your simulation seems a bit too complicated. Just forget about the second oven and check whether or not any cakes remain at time d: http://mirror.codeforces.com/contest/799/submission/27016758

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

        Won't your code go wrong as per this statement:

        If the time needed with the second oven is the same as with one oven, then it is unreasonable.

        I'm not able to format a test-case so just giving the description of a test-case: If cakes remain after 'd' time but time completion of both procedures is same.

        Please correct me if I'm wrong.

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

          Sorry, I got it! Ignore my above comment..!

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

    This is just for future readers,

    I don't know why the problem was tagged with 'Brute force' I see it's purely mathematical,

    You need to calculate how many cakes can he bake at the time of building an oven, if the remaining needed cakes are superior to the number of cakes that can be baked at the same time, then we need another oven.(since we substracted the calculated number of cakes (above), we assume that the oven is already built at that time).

    solution : [submission:https://mirror.codeforces.com/contest/799/submission/155534329]

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

Can you please explain the problem D bit more? Edit: I got it

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

First, we should find the intersection points of the line with the polygon, it is a known problem which can be solved in .

Could someone explain this algorithm?

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

For Carrot Cakes, can someone explain how do we get the value (n+k-1)/k*t ?

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

    You need ceil(n/k)*t because you bake k cakes every t seconds and that is the smallest time you need to bake atleast n cakes.
    ceil(a/b) is the same as floor((a+b-1)/b) or equivalently, (a+b-1)/b.

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

We don't need to use bin search in C if we precalcaulated two better fountains for each p <= c and p <= d (I named it C_dp[c+1][2], D_dp[d+1][2]). Then, first ans will be (C_dp[c][0] + D_dp[d][0]) if both of them are non-zero.

Another two cases — we will check each sorted fountain buying for C, and if its cost < p (we still have some money), trying to by second fountain C_dp[c — p][0] (if b of current fountain == C_dp[c — p][0], then we use C_dp[c — p][1]). Also checking if it is non-zero.

The same with D's.

Summary: O(C + D + C * log(C) + D * log(D)) (log for sorting). http://mirror.codeforces.com/contest/799/submission/27062024

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

    I don't know why minuses, it's a good approach. However you do not need to sort.

    Basically, split fountains into 2 groups {diamonds, coins} and calculate 2 best beauties for each price.

    You can do this in a similar way to prefix sum. Store each beauty for initial price (remember max 2 of them). Then go from smallest prices to largest: you have 2 best beauties for price p-1, add them to price p, and leave best 2 for price p.

    Then process every fountain f — you have to find the best match for f. You should choose either the best beauty for diamonds-price_in_diamonds(f) or coins-price_in_coins(f). You should store 2 of them, as the best one might be the same as f in which case you have to choose the second best.

    Time: O(maxPrice + n) — including coins and diamonds initially possessed.

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

      Ok, I see. We needn't sort because a[i] <= 10^5. Your solution is better, thanks.

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

Overtaking editorial for E:

  1. Take all the items which both players like or k of them, whichever is less.
  2. Take remaining items which only one of the players like to collect k items for each player.
  3. Take the best items to collect m of them -> remember how many additional items (more than k) each of the players got.

If we were able to get to this point, the answer clearly exists — now improve it.

Notice that if we have k items which both players like, then we choose nothing in 2. and we got all the best in 3. So we may remove some of the items taken in 1., to improve the result.

If we got less than k items in step 1, notice that we got all the best in 2. and 3. We obviously don't remove anything from 3. We also don't remove anything from 2 — we took all the best items, to meet the requirement that both of players have to get at least k items.

Which means that we can improve our answer by removing things we got in 1.

We do this in 2 ways:

A. Check the balance of each player. If it has more than k items, you can try to remove item liked by both. There are 2 cases, when you can remove: A.1. Both players have more than k items, then you can replace the current worst item collected in 1. with the best item not collected yet and decrease the number of items for both players.

A.2. If only one player (call him p1) has more than k items, the other has exactly k items (call him p2) but there are still some items which p2 likes (obviously we will not choose anything liked by both, as we selected all the best such items in 1. and now we remove them). We can remove item from 1. and get the best item which p2 likes. Decrease the status for p1 and nothing changed for p2 — it sill has k items.

B. Once we removed everything by A., both players have exactly k items and we can't decrease the status anymore. We still can improve the answer though. We need to remove 2 items taken so far. One of them must be from 1., so the other must not be liked by any player. We replace them with 2 best items: 1 of them liked by p1 and the other by p2. In this way we do not change the number of items which both players like (they still have k of them) and we keep the set of m items.

After A. and B. we finish with the best set possible.

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

"After that we need to calculate linear dynamic where di equals to maximum width which we got for the length i. Let's iterate through extensions in sorted order and recalculate d." I did'nt find this to be clear enough. Can someone please explain this ?

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

    Let dp[i][x] = the biggest height you can get with width x using i extensions

    to calculate next 2 states (multiplying width & height)

    dp[i + 1][x] = dp[i][x] * ext[i + 1] // multiply height

    dp[i + 1][x * ext[i + 1]] = dp[i][x] // multiply width

    the base case is dp[0][w] = h

    we can reduce the memory and use only 1D array and update states in decreasing order of width

    after each new state dp[i][x] = y, check if (x * y) can enclose the (a*b) rectangle

    27060296

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

      dp[i+1][x*ext[i+1]] = max(dp[i][x*ext[i+1]], dp[i][x])

      Could you explain, please, why dp[i+1][x*ext[i+1]] isn't just always equal to dp[i][x*ext[i+1]]? Can't figure whence have you got dp[i][x].

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

        The max height for width x * ext[i + 1] using i extensions can be less than max height for width x using i extensions, so we take the max of previous max height for that width (dp[i][x * e]) and max height for the width we are multiplying (dp[i][x])

        Also the previous max height can be zero

        For example: w = 2, h = 2, extensions {2, 2}

        i / w 0 1 2 3 4 5 6 7 8
        0 0 0 2 0 0 0 0 0 0
        1 0 0 4 0 2 0 0 0 0
        2 0 0 8 0 4 0 0 0 2
        → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

This worst case O(n2) solution for C has passed. It should not have if the test cases had been a little stronger.

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

Should be noted that for E you don't need any particular data structure (such as a stl set) to keep your data. You can just use arrays and remember the last index of pushed "must-have" elements so you can't push them on further steps (in order to mentain O(n)) steps. This way you get O(n) as opposed to O(n log n). Not much of an improvement but it's something.

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

I don't understand problem C's solution, why should we consider p1 equals p2? In fact, I accepted without considering this case (My code)).

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

Can you please explain the solution for D?

→ Reply
»
7 years 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://mirror.codeforces.com/contest/799/submission/27019364) Can somebody explain this ?

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

can anyone give a code with explanation for [problem:D].

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

Problem D:

I found this is the easiest soln to understand. Note this gets TLE...So first one gets AC just for optimization

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

Great solution for Problem D!

However, mine is different and I would like to share it.

We reduce the problem to the subproblem: given an array $$$arr[]$$$ and a number $$$X$$$, find a subsequence $$$b[1]$$$, $$$b[2]$$$, ..., $$$b[k]$$$ of $$$arr[]$$$ such that $$$P=b[1]b[2]...b[k] \geq X$$$ and the $$$P$$$ is the smallest possible.

To solve it, we use DP. Sort the array in decreasing order. DP state:

$$$dp[j][ceil(X/i)]$$$ is the answer for $$$arr[1...j]$$$. Then transition is $$$dp[j][ceil(X/i)]=min(dp[j-1][ceil(X/i)], dp[j-1][ceil(X/(iv[j])]*v[j])$$$.

That's it!

103627148

→ Reply