Roms's blog

Сodeforces Round 591 (and Technocup 2020 — Elimination Round 1) Editorial
By Roms, history, 5 years ago, In English

1223A - CME

Idea: Roms

Tutorial
Solution (Roms)

1223B - Strings Equalization

Idea: Roms

Tutorial
Solution (Roms)

1223C - Save the Nature

Idea: MikeMirzayanov

Tutorial
Solution (adedalic)

1223D - Sequence Sorting

Idea: Roms

Tutorial
Solution (Roms)

1223E - Paint the Tree

Idea: Neon

Tutorial
Solution (Ne0n25)

1223F - Stack Exterminable Arrays

Idea: Roms

Tutorial
Solution (Roms)

1223G - Wooden Raft

Idea: adedalic

Tutorial
Solution (adedalic)

1240F - Football

Idea: MikeMirzayanov

Tutorial
Solution (arsijo)
  • Vote: I like it
  • +112
  • Vote: I do not like it

Comments Comments (72)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +48 Vote: I do not like it

My solution of F:

Spoiler
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -83 Vote: I do not like it

    That is E bro

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

    We can build a bipartite graph with $$$2n$$$ vertexs.

    Here,we build an edge connect $$$x$$$ and $$$y+n$$$ if there is a match with team $$$x$$$ and $$$y$$$,$$$(x<y)$$$.

    we can try to find an edge coloring plan in the bipertite graph,which fix that for each vertex x,$$$\max a_{xi}-\min a_{xi} \leq 1$$$.Here $$$a_{xi}$$$ means the number of edges from x,which have color y.

    If there exist plan,then it can be an answer.Because in the original graph,the absolute difference between $$$s_{xc_1},s_{xc_2}$$$ is smaller then two times of the absolute difference between $$$a_{xc_1},a_{xc_2}$$$.So the plan is avaliable.

    There is already same problem on codeforces:Link,and it can be solved by using bipartite graph edge coloring or network-flow.

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

    You can prove that your solution is correct by bi-coloring the graph. If you can't color (u,v) with A in the end, it means the bi-partite graph has an odd loop, which is obviously wrong.

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

Can someone explain the dp part in problem D a bit more clearly.

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

    Here is my (very similar) approach, with identical DP part.

    Let $$$X$$$ = input array, and let $$$Unique()$$$ be removing all duplicates and $$$Sorted()$$$ be sorting. Here are the key steps:

    Non-DP part

    Formally, find the biggest sub-array of $$$Sorted(Unique(X))$$$ such that its elements stand in non-descending order in $$$X$$$.

    DP-part

    The answer is $$$|Unique(S)| -$$$(size of the biggest found sub-array). 62057262

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

    I had another solution, which is a bit slower and more complicated, but should pass TL. Actually we need to find something like LIS, but with two inserting cordinates.

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

      Can you add the link to your solution.

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

        it doesn't work, i've just checked (or bug maby)

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

In div 1 F, are these random solutions hackable? 62022214 62023134

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

What is the complexity of the model solution to F? Is it possible to prove that it has a reasonable time complexity, or is it just "No idea of the complexity, but it seems to work fast enough"

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

What is the time complexity of the model solution for F?

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

    Or maybe I should have started by asking: why does this algorithm always terminate?

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

      Let's calculate $$$P(coloring) = \sum_{v} \sum_{c} deg_{vc}^{2}$$$ where $$$deg_{vc}$$$ is number of edges of color $$$c$$$ incident to vertex $$$v$$$. One can see that $$$0 \le P(coloring) \le 2VE$$$ always holds, and this function strictly decreases after one transform (if something was bad in at least one vertex). Therefore, number of iterations is at most $$$2VE$$$, one iteration can be done in $$$O(V+E)$$$ time (finding euler cycle), and total complexity is $$$O(VE(V+E))$$$.

      If you assign colors randomly in the beginning, then for vertex of degree $$$d$$$ expected value of P (restricted to that vertex) is $$$d+d(d-1)/k=d^{2}/k+d(1-1/k)$$$ while theoretical minimum is $$$k(d/k)^{2}=d^{2}/k$$$. So, expected number of iterations is $$$O(E)$$$.

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

Solved 1223F - Stack Exterminable Arrays in a more straightforward way in $$$\mathcal{O}(n \cdot log^2(n))$$$.

Let's use divide and conquer and count number of subarrays that are going through the middle of array. We can simulate process of elimination with stack for each suffix of left part and for each prefix of right part. We can notice that some left part matches with some right part if and only if they have the same stacks. We can use hashes to quickly compare stacks and use maps, hash-maps or merging sorted lists of hashes to count the result.

Not really optimized solution 62025172 works in $$$732 \; ms$$$.

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

    If we know We can notice that some left part matches with some right part if and only if they have the same stacks., we can just count the number of pairs of the same stacks by storing hashes in a map instead of doing divide-and-conquer. The complexity will be $$$O(n \log n)$$$

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

      In my solution I am building left and right parts from some middle point, that's why I actually need D&C to cover everything. But your solution just calculates all the stacks from the beginning and says that the answer is

      $$$\sum_{distinct \; stacks} \binom{number \; of \; occurences}{2}$$$

      That makes further observation that is "if we are at some position $$$l$$$ and we have added all elements from $$$a_{l \cdots r}$$$ and stack configuration did not change so $$$a_{l \cdots r}$$$ defines stack-exterminable subarray." So we can take any pair of positions with the same stack-from-beginning configuration as endpoints of correct stack-exterminable subarray. That is quite nice and simplifies things a lot. Thanks.

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

    That's what I did too, but without hashes. Instead, I store the sequence of all stack states when adding elements to the left as a trie and to the right as a second trie. Then, I just find the tries' intersection (e.g. by basic DFS), count the number of states from the left part and from the right part corresponding to each vertex of this intersection and get the sum of their products. It's completely deterministic and with the same complexity when I store the edges from the tries in a map (using a hashmap instead actually slows down the program).

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

      it gave MLE if the memory wasn't freed for the nodes(of trie). My question is, do you'll always free memory for nodes after its use? Since it is done on the expense of time...

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

        It's not at the expense of time unless you consider allocator/processor magic. For every malloc(), you need a corresponding free().

        Immediately cleaning up variables you don't need is a good thing for your memory (both computer and head).

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

Alternate approach for D. observations: which element will we choose if we were to perform only one left operation, we will definitely choose the smallest element. same way if we had only one right operation we will choose the largest element.

In general if we had x left operations we will choose the smallest x elements. Let us try to find out the minimum right operations needed if we could only perform L left operation. Let L be the number of left operations allowed and R be the number of right operations. We will find minimum of L + R where L will vary from 0 to N.

For 0 left operations(i.e. only right ops allowed), if there exists a number X in the array such that Y is a number greater than X but is to the left of X we need to move this Y to the right end and since we move this Y to the right end we need to move all elements larger than Y to the right end as well. Hence find smallest such Y and move all elements to the right end that are greater than equal to Y. We can find number of elements greater than equal to Y in logN time which will be required ops R.

Similarly for 1 left operation you may consider the same procedure only that the smallest element may be considered absent. for L left operations allowed consider 1st L smallest elements absent.

https://mirror.codeforces.com/contest/1223/submission/62028221

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

Hi all, my greedy idea for E was to simply sort the edges in non-increasing edge weight, then greedily take the largest edges as long as both of its vertices have enough in-degree to accept this edge. The intuition is similar to the greedy idea in Kruskal's MST algo. Can anyone poke a hole in this idea? I get WA on test case 3. (link to my code 62028517)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it 
    1
4 1
1 2 5
2 3 6
3 4 5

    The answer for this should be 10 but your code outputs 6.

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

In 1223F — Stack Exterminable Arrays, why $$$nxtX_{nxt_i + 1}$$$ will never be used again so that we can use swap?

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

    I'm pretty sure it's provable that no 2 indices will have the same R value.

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

P.S.: We decided to allow the O(Alog2A) solution which binary search x for each y to pass if it's carefully written.

It's not like you could stop that anyway. Good luck distinguishing between $$$O(A\log^2 A)$$$ and $$$O(A\log A)$$$ where the extra factor is binsearch — you can't even use huge $$$A$$$ without requiring insane constant factors from optimal solutions too. I implemented that and my solution runs in half a second without trivial optimisations like "stop binsearch when it's clear you can't improve the answer".

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

For 1223C/Div2C — Save the Nature, count(len) can be calculated in constant time by precalculating the prefix sum of sorted p. Then we don't need to do a binary search on the answer. This is my accepted solution https://mirror.codeforces.com/contest/1223/submission/62030690

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

Can anyone help me finding what's wrong in my code of Paint the Tree, https://mirror.codeforces.com/contest/1240/submission/62017811

It seems I was the only one who failed pretest 5, I did the same as mentioned in tutorial (just my notation is opposite, so dp[node][0] means node has taken atmost k-1 edges)

I take pair of child's dp[child][0] + edge , dp[child][1] , and sort them by (p.F — p.S) > (q.F-q.S)

then I iterate and take first k-1 pairs in both where x.F > x.S and one more for dp[cur][1],

If x.S >= x.F or i already took the required edges, i take x.S

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

    in C++, comparators should return false when element are equal !!!

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

      Woaah..!! It got accepted. I would never think that this can cause the problem. Can you please elaborate or give a link describing why it causes an error ??

      I used to think that when elements are same, it doesnt matter if comparator gives true or false. (If two elements have same order, it wont matter which gets placed first

      EDIT : Got it thanks for your help.

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

        Please tell why it causes an error.

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

          The compare function simply models a "less than" operator. Consider how the < operator works for primitive types like int:

          int a = 1, b = 2; a < b == true a is less than b

          int a = 2, b = 1; a < b == false a is not less than b, because a is greater than b

          int a = 1, b = 1; a < b == false a is not less than b, because a equals b

          Returning true means you want a to be ordered before b. So return false if that is not the case, either because you want b to be ordered before a, or because their order doesn't matter.

          If you return true when the arguments are equal, then you are saying that you want a to come before b and you want b to come before a, which is a contradiction.

          Copied from this link : https://stackoverflow.com/questions/45929474/why-must-stdsort-compare-function-return-false-when-arguments-are-equal

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

            Still confused.

            say a=b, and you return a<=b.

            so I want a before b. (or b before a. it wont matter, right? since a=b)

            what's the problem here?

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

D is really nice.

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

Can anyone explain more this part of the editorial of problem D ?

"For each integer l we want to find the maximum index dpl=r such that we can sort sequence a without moving elements in range l…r. We can do it with dynamic programming.

Let's consider all integers occurring in sequence a in descending order s1,s2,…,st (si−1>si for each i from 2 to t). If maxInd(si)<minInd(si+1) then dpi=dpi+1+1, otherwise dpi=1."

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

    Hello！ I would fain help you. (Sorry for my poor English.)

    First of all, the size of the specific value is meaningless.

    So we can reduce its value to $$$[1,t]$$$ and all the numbers in the $$$[1,t]$$$ appear at least once.

    The answer is obviously constructed as follows ：

    We can put $$$ l, l-1, l-2, ..., 1$$$ one by one at the beginning of the sequence at the cost of $$$1$$$.

    After that , We should put $$$ r,r+1,r+2,...,t$$$ one by one at the end of the sequence at the cost of $$$1$$$.

    If such a scheme is legal, then it must be guaranteed that the numbers in the middle are in order.

    However, the time complexity of such an algorithm is $$$O(n^3)$$$

    So, we can first determine the ordered interval in the middle, and then calculate the answers to the answers on both sides.

    We can define $$$dp[i]$$$ for each i.

    This means one of the biggest extensions length which let $$$ i-dp[i]+1 , i-dp[i]+2 ... i$$$ are ordered in the sequence.

    To calculate $$$dp[i]$$$ , we should calculate MinInd[i] MaxInd[i] ($$$i \in [1,t]$$$) .

    First of all , $$$ dp[1] = 1 $$$

    if $$$ MinInd[i] > MaxInd[i-1]$$$ then $$$ dp[i] = dp[i-1]+1$$$ else $$$dp[i] = 1$$$

    So , The answer is the minimum value of $$$t-dp[i]$$$ ($$$i \in [1,t]$$$)

    Now, the time complexity of the algorithm is $$$O(n)$$$

    My Code

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

It seems in problem D should be: "Let's consider all integers occurring in sequence a in descending order st,st-1,…,s1 (si+1>si for each i from t-1 to 1). If maxInd(si)<minInd(si+1) then dpi=dpi+1+1, otherwise dpi=1."

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

The editorial of problem Div2 D seems to have a mistake. You first call $$$dp_l$$$, the index $$$r$$$, s.t. we can sort the sequence without moving elements $$$[l .. r]$$$. But, in the recurrence, you have taken $$$dp_l$$$ to be the length of the sequence $$$[l .. r]$$$

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

    Roms can you please correct it? It might be a difficulty for people who try to solve this problem later by reading the editorial

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

For 1223C Solve the Nature, I am not satisfied with the fact that we need to check only if x>y.The terms a and b should also have a role.It can be that b is very small as compared to a.In that case even if x is smaller than y we would wish to allot greater ticket price to y% contributed tickets because they appear for every multiple of b which is very large as compared to a based on our assumption. I think in the solution suggested above it has been considered that a is smaller than b. Do correct me if i am wrong!

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

    Well, x>y or y>x, a>b or b>a, all this stuff does matter only for easier implementation. I'll try to explain the main idea in pictures. I think it's easier to understand.

    Let's consider the particular case:

    Data that we have

    So, let we already sold n tickets. Than we got m for the Nature and m is the maximum value.

    How to find the m?

    If our segment has a and b blocks, than put the most expensive tickets there. After that, put the remaining tickets into a if x>y or b if x<y and so on.

    Best distribution for fixed length, case(length = 7)

    Let function cont(n) = m The answer will be such n that cont(n) >= k and n is minimal. So we need to find cont(n) for every n in range len(tickets).

    In our case it's 7.

    cont(n) from 0 to 7

    Well, in this case the answer will be 4, becuse k=240 and cont(3)=200, cont(4)=250.

    But we can notice that cont(n) is monotonous, because as n rises cont(n) rises.

    That's why the array [cont(1), cont(2), ... cont(len(tickets))] will be already sorted.

    And we want to find such element that will be >=k and its index will be minimal, what is the best way to do it?

    Of course it's left binary search.

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

Hi,

In problem E — Paint the Tree, I don't understand why I can use dp[v][k] since v and f can be up to 3 * 10^5. The solution of the Tutorial would be O(n * k), wouldn't?

Thank you, Rosklin

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

    $$$f$$$ is boolean flag ($$$f \in \{0,1\}$$$). So, we have dp[n][2], where dp[x][0] is optimal painting of subtree $$$x$$$ not including edge to the parent, dp[x][1] is optimal painting of subtree $$$x$$$ including edge to the parent.

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

The editorial solution for D fails on this simple test.

1
2
5 6

Please change it.

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

    Your test is incorrect. All $$$a_i$$$ must not exceed $$$n$$$.

    → Reply
»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

sometimes i feel like a wet pile of crap

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

Here's my solution for D (lol, it took about an hour to figure this one out):

Firstly, in any legal sequence of operations all numbers moved to the left must be less than all numbers moved to the right (otherwise the resulting array is not sorted).

So let's fix a number k, such that all numbers moved to the left are less than or equal to k, while all numbers moved to the right are greater than k. Some numbers may not be moved at all, for example if part of our array is 3 1 4 2 and we move all of them to the left, then we only need to move numbers 2 and 3, in that order.

First we calibrate the array such that all numbers used are consecutive integers. Another way would be to declare arrays prev and next, and that's OK, since the numbers are relatively small.

Now, let's say that we've fixed this k, and we need to decide how many numbers we need to move to the left so that the elements 1, 2, ..., k are sorted. It can be noticed that if there exists a sequence k - c, ..., k - 1, k (in that order), we do not need to do any operations with those numbers, since they are already relatively sorted! So we only have to move numbers 1 through k - c - 1.

To find the longest such sequence (which results in the smallest number of elements that we need to move), we create an array up. up[i] — the length of the longest sequence of consecutive numbers (possibly, with intermediary ones) ending in i (sorted in increasing order). We can do this with a linear pass through the array.

So, given a fixed k, the number of elements we need to move to the left, given that elements 1 through k must be sorted afterwards, is equal to k - up[k].

We tackle the other case similarly. down[i] — the length of the longest sequence of consecutive numbers (again, sorted in increasing order) starting in i. So, the number of elements we need to move to the right, given that elements k + 1 through mark — the maximum number in the array must be sorted afterwards, is equal to (mark - k) - down[k + 1].

For a given k, we sum those two values and receive the local answer. There's one catch, if there is an occurrence of k later than an occurrence of k + 1, we have to sort one of the pieces of the array entirely. We simply choose which one gives the minimum number of total operations.

In this way, the answer is simply the minimum of local answers from 1 to mark - 1.

By the way, it's only 80 lines of code in Java :)

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

Div1 D can also be solved by creating, for each $$$x \in [1,n]$$$ a random vector $$$b_i$$$ in 3D, setting $$$z_0$$$ to a random 3D point, and then setting $$$z_{i+1}$$$ to be the reflection of the point $$$z_i$$$ along the direction of $$$b_{a_i}$$$. Then a segment (0-indexed) $$$[l,r)$$$ of the array is stack exterminable iff $$$z_l = z_r$$$. Code

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

I laughed very hard when i read this:

You are an environmental activist at heart but the reality is harsh and you are just a cashier in a cinema.

Maybe i'm already dead inside.

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

update: got it.

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

I solved Div-2 D with two pointer + BIT. Maybe it was an overkill, but quite intuitive, cause we need to maximize the range of numbers with no inversions between themselves.

Brief explanation

My solution: 62025259

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

Can someone summarize Div2 E? I can't understand the statement.

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

Can anyone suggest more problems like D?

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

Hi all! How can I accelerate my code? I think my input is very slow 62119639

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

My code showing correct output but on submitting the results change .Am i doing something wrong while input or is it something else. P.S-I am new here:) My code to 'Save the nature' https://mirror.codeforces.com/contest/1241/submission/62256956

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

In Div1 D, instead of swapping the maps $$$nxtX_i$$$ and $$$nxtX_{nxt_i+1}$$$, it is also possible to move $$$nxtX_{nxt_i+1}$$$ to $$$nxtX_i$$$ using std::move in $$$O(1)$$$ time by doing nxtX[i] = move(nxtX[nxt[i] + 1]).

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

Hello,

In problem E (Paint The Tree) is there any benefit to using a DP array? I was able to solve it without one, in this submission https://mirror.codeforces.com/contest/1223/submission/62262784

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

D is very similar to AtCoder Grand Contest 24 — B: [](https://atcoder.jp/contests/agc024/tasks/agc024_b)

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

Hello,

Can anyone help me with 1223C? Here is my submission. What I'm doing:

  1. Sort the ticket values in non increasing order
  2. Create prefix array preSum

  3. Create a function check that takes $$$preSum,x,a,y,b$$$ and the number of tickets to sell $$$n$$$.

    Working of check : Find an : number of tickets within n that have the x% scheme Similarly, find bn for the y% scheme. cn for the tickets that have both the schemes applicable. Tickets with max values should be placed at positions which have both the
    schemes applicable. Their contribution would be the presum of first cn items * (x+y) Then assuming that allocating the higher tickets to ath positions will yield a better result, we can find (presum of $$$a_n$$$ items — presum of $$$c_n$$$ items) $$$\times (x)$$$ (as cn items are already taken from an). The rest is allocated to bn by: (presum of $$$a_n+b_n-c_n$$$ items- presum of $$$a_n$$$ items) $$$\times y $$$ (as we only need $$$b_n-c_n$$$ items next to the already used $$$a_n$$$ items. Then doing the same assuming $$$b^{th}$$$ positions will yield better results as compared to the $$$a^{th}$$$ positions.

The maximum of these two + $$$x+y$$$ contribution is returned.

$$$Finally$$$ a binary search is done over $$$[1,n]$$$. For the middle element, we use the check function, which yields the maximum sum for the middle element. If the sum is more than or equal to k, then it is saved in the variable ans. Once the search is complete, ans is printed.

I do not understand where am I going wrong in here. Any help is appreciated!

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

Div 2D and E are just amazing!

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

can anybody tell me C

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

Problem C can also be solved using number theory. So, (number theory) tag can be added to the problem

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

To anyone(from the future) who is looking for Problem D's solution, I have a much easier logic for this problem.

Hint 1: It is mentioned that in one operation we can take all occurences of a particular element and place it in beginning or the end. So does it really matter to actually do this operation?

Key observation: We can reduce the problem to a longest increasing subsequence problem ,and if we know the longest ascending subsequence we can just subtract it from distinct elements to get the answer. Note: here we will actually look for the just previous element while making the longest increasing subsequence .eg: lets say we have 2 3 4 in our array in some order ,so we while we are at 4 we will just take 3 into account for updating our ans .

After the above observation we can easily do this problem by using map data structure.

https://mirror.codeforces.com/contest/1241/submission/144912141

→ Reply