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

Автор MikeMirzayanov, 3 недели назад, По-русски,

Добрый день!

15-го октября завершился Четвертьфинал Южного подрегиона NEERC (Northern Eurasia) чемпионата ICPC. В Саратове встретились 76 команд, многие из которых получили приглашение по результатам квалификационного этапа.

Сегодня в субботу, 27-го октября в 12:35 (МСК) состоится онлайн-зеркало 2019-2020 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, предпочтительно команды).

Надеюсь, вам понравятся задачи. Председателем жюри этого соревнования являюсь я, а над задачами работал дружный коллектив жюри экс-участников чемпионата из Саратовского ГУ и иногородние члены жюри. Спасибо всем!

Приглашаю команды ICPC к участию и просто индивидуальных участников соревнований Codeforces принять участие!

Конечно, соревнование будет нерейтинговое.

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

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

is this rated for division 3?

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

is this rated for div3?

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

Thank you for your efforts. Good luck to everyone!

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

how to solve E?

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

    It's kind of 2-SAT.

    Let's iterate over all pairs of necklaces. For each pair $$$p$$$ and $$$q$$$, look at the similarities of $$$p, q$$$ and $$$p, rev(q)$$$. If this pair can only exist when both are in the same direction, draw a white edge between them; if this pair can only exist when one of them is reversed, draw a black edge between them; if this pair can't exist either way, report a failure. After this reduction it is fairly similar to e.g. 553C - Love Triangles.

    We want to split the resulting graph into two parts $$$S$$$ and $$$T$$$, such that there are only black edges between $$$S$$$ and $$$T$$$, and only white edges within $$$S$$$ and $$$T$$$; also, we want to minimize the size of $$$T$$$ (i.e. the number of reversed necklaces). First check if there is a cycle with odd number of black edges, if there is, report a failure. Otherwise, we have a bunch of "bipartite" connected components. Put the smaller half of each component into $$$T$$$ and we have our answer.

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

    E had very odd bounds as it can be solved in quadratic time.

    For every pair of necklaces, we either get that

    1. Neither or both necklaces must be flipped (xor must be 0)
    2. Exactly one of the necklaces must be flipped (xor must be 1)
    3. The pair of necklaces imposes no conditions
    4. No amount of flipping makes them similar

    If 4 happens even once, answer impossible. Now knowing the orientation of one necklace in a connected component (with conditions as edges) determines the orientations of the rest. Just take the orientation that minimises flipped necklaces.

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

      Isn't it still O(N^2*M) for constructing the graph? For every pair of strings you need to iterate over them to count the similarity. After that it's just the coloring described by you. Is there a way of making the graph in a better complexity?

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

        You can compare the pairs of strings by simply taking their xor. If you store them as bitmasks, the comparison takes, in some sense, $$$O(1)$$$ time. I assume this is what he means.

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

          Thanks! I figured it out eventually. I find the bounds kind of odd now too.

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

    oh I'll check it. Thank you so much -is-this-fft- mango_lassi

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

How to approach B?

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

    you need at least k/2 buses and at most k buses since k<=8000 iterate on each k to find the optimal one

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

      Only elaborating this approach, since I find the problem quite interesting.

      Suppose we have the counts of all teams in a non-descending/sorted order. An important observation is that in an optimal solution, the teams that go alone in the bus forms a suffix. This can be proven with an exchange argument. Now, what is the best way to pair up teams in a prefix? We want to pair up teams so that the maximum sum of counts is minimised. Consider the largest team in the prefix. It is best to pair it up with the smallest team (again, can prove with an exchange argument). So we remove the first and last of the prefix and repeat the procedure.

      Finally, we iterate on each prefix of even length (say $$$2i$$$) — obtain the maximum of the remaining suffix, and obtain the maximum sum of pairs of elements that are equally distant from the beginning and end of the prefix. Here, $$$s$$$ is the maximum of the two, and $$$r$$$ is $$$i + (n - 2i)$$$. And for all such $$$i$$$, we take the minimum of $$$s\cdot r$$$.

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

What is test case 2 in J ?

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

-

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

Can anyone help me in explaining how to solve problem N (Wires) ? My solution is failing for test-case 7 :( Not able to figure it out

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

    You delete a bridge.

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

      I thought that I am already taking care of that. Looks like I am having a big or something. Thanks for that :)

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

    Iterate over components, run dfs.

    Then you can always delete the last vertex in dfs (Try to think why it is true). So connect any vertex from next component with parent of last vertex.

    You don't need to find bridges or something like this.

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

      Could you hack my solution?

      I add all the edges to connect the point, which is relabeled,using dsu and keep the sum of edge for each point.

      I check all the edges,if its Unicom block haven't been visit and one of its end is size of 1,I push it and its size-one point to a stack.

      If there is still some Unicom blocks haven't been visit, which means it's a circle.I got any of a edge with one of its point.

      I connect the 2~n element in the stack to element 1.

      I also WA on test 7.I have test many case and submit 10 times.

      I wonder whether my solution bugged or the SPJ bugged.

      below is my two tries https://codeforces.com/contest/1250/submission/63558169 https://codeforces.com/contest/1250/submission/63621689

      Thanks a lot.

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

      oh yeah! I am using algorithm to find all articulation bridges and made it complex. I see why choosing last node of the simple DFS works. I ll keep that in mind. Thanks for that :)

      Edit: Removing the code to find articulation bridges and just using last edge of DFS gave me an AC :)

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

According to the contests tab, it is "open hacking phase" now? Is there any actual hacking that can be done now? I.e. is there a reasonable chance that the test set (which was probably the same at the subregional) is not complete?

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

Should we wait for editorial or not?

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

How to solve problem C?

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

    For C, What I did was, start by sorting queries by their r value. then i created a segment tree which tells the maximum possible answer with some l value for fixed r. segment tree was range update and point maximum query segment tree which also tells the index of maximum. now the main problem was how to store answer in segment tree so for fixed right index =x the index x would have -k + sum of segments which lie in (x-1,x) and index x-1 would have -2*k + sum of segments which lie in(x-2,x) and so on. we can do this possible by iterating over r and updating the range (1,r) with -k everytime.

    Heres my code- https://www.ideone.com/g2j16q

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

    https://pastebin.com/UNyjNnuu

    Here hope this helps

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

    Key observation is that to reach row_index rb from ra all the elements lying between will be of same type(if element at ra is even then all elements will be even and vice versa)..same thing applies for column too... I am limited by my formatting skills otherwise I could have explained better

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

How to solve problem N:Wires?

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

    If the number of connected components in the graph is $$$c$$$, then the answer is $$$c-1$$$.
    Just connect all the other components to the first component. To join the component:
    1) If it is a tree, change any leaf-vertex's edge
    2) otherwise, change any edge that belongs to a cycle

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

      I was also trying to do this....but I couldn't hand the case
      3
      1 2
      3 4
      5 6
      My code was connecting 1 with 3 or 4 which resulted in 2 becoming isolated.. How can I handle this situation

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

        Vertices can be isolated.
        We just need to make sure the edges are connected.

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

          Oww!!!!of course...I guess I was overthinking after getting WA on test case 6...I was thinking about the vertices being isolated [Even sample case does that :|]....

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

      UPD : Got it!! I wasn't considering multiple edges between two nodes

      If the component is not a tree then if I change either any leaf node edge or cycle node edge, then will there be any problem
      63618975 Here I am trying to do that , but getting WA

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

How to solve D, I, M?

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

    I: my solution was the weirdest solution I've ever came up with

    First to make it simpler we'll take the complement of the set, so we'll order by lesser size and greater sum and the restriction goes from SET <= K to SUM — SET >= K.

    Now, let's try and get TLE with a bruteforce solution like bf(i, remaining that need to be taken, current sum) + ordering the values before bruteforce.

    Here comes the trick, if we compress a tree to not have any internal nodes with degree 2 then it has O(N) leafs and O(N) nodes, using this fact we can compress the segments that we don't have a choice but to choose the values by using a binary search to remove that segment.

    This isn't enough since it might have values mixed in that are smaller than what should be the last value, so we do a binary search to find the largest value that doesn't use all M things and then do a special iteration to get some value that's exactly what the last should be.

    Complexity is something like O(N * logN * logV) or something like that lol.

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

      Alternative solution for I:

      Let's suppose we fix $$$K$$$ as the number of people in the subset $$$S$$$ and the people are sorted in increasing order of awkwardness.

      Obviously, the first set that we should output is $$$v_1, ..., v_K$$$. The main idea is how to transition from this set to potentially other sets while iterating through them in order of total awkwardness.

      It turns out that we can do that by two operations. Consider a pointer that initially points to $$$K$$$ and represents to the position of the $$$K$$$-th person in the set. We now consider two operations: - increase the position of the pointer by $$$1$$$ - fix the position of the pointer and grab a pointer to the previous person in the set.

      Basically, for set $$$1, 3, 5$$$ we can do these operations: $$$1, 2, 3 \rightarrow 1, 2, 4 \rightarrow 1, 2, 5 \rightarrow 1, 3, 5$$$.

      Essentially, we start increasing the second pointer only when we fixed the value for the first pointer.

      Two aspects here are essential: that the sequence of operations is unique for a given target set (we don't end up at a target set in two different ways), and that the intermediary sets are of increasing total awkwardness (the cost of transitioning is always positive).

      Therefore, the state space with these two operations is actually a rooted tree, and edges are always of positive weight. In fact, all edge costs are of form $$$v_{i + 1} - v_i$$$. That means that we can traverse the tree in order by simulating Dijkstra algorithm on this search tree.

      In order to reach the good complexity, we need to keep for each node in the tree a state of form: (maximum remaining sum, where current pointer points to, where is the fixed element to its right, how many elements are before it). Then we can transition from a state $$$(s, pos, npos, idx)$$$ to $$$(s - v_{pos+1} + v_{pos}, pos + 1, npos, idx)$$$ if $$$pos + 1 < npos$$$ (incrementing) or $$$(s - v_{idx + 1} + v_{idx}, idx, pos, idx - 1)$$$ if $$$idx > 0$$$ (fixing + incrementing). Each state determines the values $$$ptr_0 = 0, ptr_1 = 1, ..., ptr_{idx - 1} = idx - 1, ptr_{idx} = pos$$$, and the positions greater than $$$idx$$$ are determined by its path in the search tree.

      The rest is just reconstruction bonanza.

      Total complexity is $$$O(k \log{k})$$$.

      Solution

      How to solve D?

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

        Thank you but the solution can't be viewed.

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

        solution of D:

        First we can imagine all the persons as 2-dimensional point $$$(L,R)$$$ with color $$$c$$$. If a person who located at $$$(x,y)$$$ is unhappy, then all person who located in the upper-left of $$$(y,x)$$$ should be in the same color(think about when two intervals don't intersect). So you can enumerate all the persons and see:if he is unhappy, what the color will be in the upper-left rectangle or we don't know the color yet.

        we change the problem to this:give some points with color(or don't have any color yet),and some upper-left rectangles with color(or don't have any color yet). you should choose rectangles as many as possible and make sure:
        1.give colors to all rectangles and points which don't have colors yet.
        2.all points in a chosen rectangle should have the same color with the rectangle.

        we can run a dp in $$$O(n^2k)$$$. for the first step,sort all rectangles according to its right boundary(from right to left).then define $$$dp[i][j][k]$$$ as "after considering the first $$$i$$$ rectangles, all useful points whose y-coordinate is larger than $$$j$$$ are already colored the $$$k-th$$$ color,how many rectangles you can choose at most?".
        some explanation about it:
        1.after discretization, there are only $$$O(n)$$$ y-coordinates;
        2.definition of useful points:you can imagine all the chosen rectangles, the figure of them is something like “stairs”. Obiviously only the points in the left of the leftmost stair are useful(because the rectangles are sorted).

        there are more details:
        1.precalculate the color/number of points in all rectangles(I use bitset)
        2.color the rectangle. and in the process of dp you need the information precalculated in the first step.

        the dp details are a little bit complicated but easy to think.

        At first I'm afraid this solution is not efficient enough, but after coding carefully, my solution runs in only $$$140ms$$$

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

          How to solve K? qwq

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

            Suppose that we fix a way of distributing the ordinary projectors to seminars. Then there's a way to distribute the HD projectors iff for any integer $$$t,$$$ the time $$$t+0.5$$$ is not contained within more than $$$x$$$ intervals corresponding to seminars or lectures which do not already have a projector. (condition 1)

            It follows that we don't actually care about the exact intervals spanned by lectures. For example, $$$[1,4), [2,3)$$$ is indistinguishable from $$$[1,2),[2,3),[3,4),[2,3)$$$ or $$$[1,3),[2,4).$$$ Thus, we want to create some sort of flow graph with the seminars (not the lectures) as edges.

            The way of distributing the ordinary projectors must satisfy the following condition: Suppose that at time $$$t+0.5,$$$ exactly $$$X$$$ lectures and $$$Y$$$ seminars are happening. Then $$$X\le x, X+Y\le x+y,$$$ and at most $$$\min(y,x+y-X-Y)$$$ ordinary projectors are not being used at time $$$t+0.5$$$. (condition 2)

            Now let's construct a graph for the ordinary projectors. Create a vertex for each (compressed) time in increasing order from left to right. The source (left of all other vertices) has an edge to the first time and the last time has an edge to the sink (right of all other vertices). There will be edges for each seminar with capacity one and edges between every two adjacent times with capacities determined by (condition 2). All edges are directed from left to right. Then there will exist a distribution satisfying (condition 2) iff the max flow from the source to the sink is equal to $$$y.$$$

            If (condition 2) is satisfied, then (condition 1) will be satisfied as well, so after distributing the ordinary projectors we can distribute the HD projectors greedily. (Nice problem!)

            Code

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

          I have another interesting solution for D.

          First we can sort all persons by $$$r$$$ (departure time) in increasing order. For the $$$i$$$-th persion, consider who he will meet during the conference. We can define it as a set. $$$S(i)$$$ means the set of persons that the $$$i$$$-th persion will meet. For simplicity, we let $$$i \in S(i)$$$.

          According to the colors, there are 4 types of sets.

          1. The set contains at least two different nonzero colors.
          2. The colors in the set are the same, a nonzero color.
          3. The set contains two different colors, one is 0 and the other is nonzero.
          4. The colors in the set are all 0.

          When $$$S(i)$$$ is type 1, person $$$i$$$ is impossibe to be upset. When $$$S(i)$$$ is type 2, person $$$i$$$ must be upset.

          So we can preprocess these two types of sets and ignore them in the following solution.

          So the problem can be changed to this: we can select some sets (to make the corresponding persons upset), amd assign a color to each set (For set of type 3, we can only assign the existing color). And this assignment is valid if and only if it doesn't exist that two sets are assigned different color but intersect with each other.

          Since $$$r$$$ (departure time) for everyone is increasing, we can describe $$$S(i)$$$ in a simple way. We can define $$$p(i)$$$ as the smallest $$$x$$$ that satisifies $$$r_x \geq l_i$$$.

          Then for all $$$p(i) \leq x \leq i, x \in S(i)$$$. And for those $$$x$$$ greater than $$$i$$$, $$$x \in S(i)$$$ if and only if $$$p(x) \leq i$$$. Hence, $$$S(i)= \{x|p(i)\leq x \leq i \vee p(x) \leq i \}$$$

          $$$S(i)$$$ consists of two parts, the first part of which is $$$\{x|p(i)\leq x \leq i \}$$$, a consecutive interval; the second part is $$$ \{x|x>i,p(x) \leq i \}$$$, which may be some isolated points.

          Then we consider when will two sets $$$S(i)$$$ and $$$S(j)$$$ intersect. Suppose $$$i < j$$$, there are 3 types of intersection.

          1. The first part of $$$S(i)$$$ intersects with the first part of $$$S(j)$$$, if and only if $$$p(j)\leq i$$$.
          2. The second part of $$$S(i)$$$ intersects with the first part of $$$S(j)$$$, if and only if $$$\exists x, p(j)\leq x \leq j \wedge p(x) \leq i$$$.
          3. The second part of $$$S(i)$$$ intersects with the second part of $$$S(j)$$$, if and only if $$$\exists x, x>j \wedge p(x) \leq i$$$.

          (It is impossible that the first part of $$$S(i)$$$ intersects with the second part of $$$S(j)$$$ since $$$i < j$$$.)

          We can combine the conditions for the second and third types of intersection to $$$\exists x, x \geq p(j)\wedge p(x) \leq i$$$. We can define $$${\rm minp}(i)=\min_{x\geq i}p(x)$$$. Then this condition can be rewrited as $$${\rm minp}(p(j))\leq i$$$.

          Next, we can define $$$f(i) = \min(p(i), {\rm minp}(p(i)))$$$. Then $$$S(j)$$$ intersects with $$$S(i)$$$($$$i < j)$$$ if and only if $$$f(j) \leq i$$$.

          This is an elegant conclusion. After we get it, we can work out a dp solution. Define $$$dp(i)$$$ as the maximum number of unhappy persons when we only consider the first $$$i$$$ persons.

          After calculating $$$dp(i-1)$$$, how to get the value of $$$dp(i)$$$? First, we set $$$dp(i) = dp(i-1)$$$, then consider the maximum number of persons upset if we make person $$$i$$$ upset. We can enumerate the color $$$j$$$ assigned to $$$S(i)$$$, and then enumerate $$$k(0\leq k < p(i))$$$, which means the sets among $$$S(x)( k<x\leq i)$$$ that are selected will be only assigned color $$$j$$$, and the sets among $$$S(x)(x\leq k)$$$ are free to select.

          Which sets among $$$S(x)(k<x\leq i)$$$ can be selected in this case? Those sets can not intersects with the sets $$$S(y)(y\leq k)$$$. So the condition is $$$p(x) > k$$$ and the color of $$$S(x)$$$ is $$$j$$$ or 0. We can use Binary Indexed Tree to maintain the amounts.

          This editorial is so long and I have written it for a long time because I'm not so good at English. But this approach is very easy to implement. I finished the code within 20 minutes.

          The time complexity is $$$O(n^2 k\log (n))$$$, where $$$k$$$ is the number of total colors. In the problem, $$$k=200$$$. Since we shouldn't enumerate all colors when $$$S(i)$$$ is type 3 (have a specific color), the complexity is far from reaching the upper bound. My solution runs in $$$93ms$$$.

          Here is my code.

          solution

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

            For the reason that the number of add operation is $$$n$$$, so with prefix sum, the time complexity is $$$O(n^2k)$$$.

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

    M is nice.

    For each bit $$$i$$$, let L = set of indices $$$x$$$ with bit $$$i = 0$$$, R = set of indices $$$y$$$ with bit $$$i = 1$$$ and $$$y + 1$$$ also has bit $$$i = 1$$$.

    Similarly, for each bit $$$i$$$, let L = set of indices $$$x$$$ with bit $$$i = 1$$$, R = set of indices $$$y$$$ with bit $$$i = 1$$$ and $$$y + 1$$$ also has bit $$$i = 0$$$.

    Now, we used 26 sets.

    Observe that only pairs $$$(x, y)$$$, with y = 01111...1 (the string of 1s is nonempty) and x = 1 such that there is at least one bit 1 in the suffix, are uncovered.

    Thus, it is sufficient to make $$$12$$$ more queries that cover all y of the form 0111...1 for a fixed 1-suffix length and then put all x that can be matched on the left hand side.

    In total, my solution uses $$$38$$$ queries.

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

      Can you please provide your implimentation if you have it.

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

        ps. Thank you zscoder. It's a nice solution.

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

    Simpler solution for I:

    Sort all values. We loop through the number of elements from N to 1. Let's say now we are considering the ways to choose k elements. Start with the smallest k elements. We build our solutions progressively using 2 types of steps: Consider a pointer starting at the largest element. Each step consists of either increasing the current element to the next possible element, or move the pointer lefft and increase the current element to the next possible element. We can push the current sum, current position of pointer, position of previous element, position of current element into a priority queue to simulate this expansion. To restore the solution, just create an ID for each state and keep track of which move is used to reach the current state, and we can backtrack at the end.

    Complexity: $$$O(M\log M)$$$

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

MikeMirzayanov codes are still not visible, will it be fixed or it will remain like this ?

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

    In fact, codes of a problem in this contest will be visible after you solve it.

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

      For me visible are codes of problems which I solved. If you see codes of all problems maybe it is because of coach mode.

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

        It's the same to me. I can't see the solutions of problems I haven't upsolved. If you want to find a solution of a problem in this contest, you can search tutorial in this blog. Other users may have posted their own solutions. If the tutorial of the problem is not posted, you can ask about it. I will try to help you.

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

          Thanks, can you tell the solution of C and N.In N I came up what is the main idea, but I don't know how to implement it easily.

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

Does this competition have any influence on ratings?

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

Is there any solutions to these problems ? Officially or unofficially.

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

Can anyone provide a link to there submission for problem B and J. Thanks

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

    in J you should binary search the amount of soldiers in one row. in B you should sort teams by size and consider you put 1st and last together, then 2nd and last-1 ans so on for each capacity you must check amount of rides and minimal capacity*number of rides among them will be the answer

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

Please write the blog for editorial, it will help in upsolveing the problem. Thanks

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

Can you please make all sources visible?

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

How to solve G?

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

    Enumerate on the position of last Reset operation, then we can use binary search to determine if this is possible. Also we need to know at least how many Reset operations we need to do before this one, which can be preprocessed using dynamic programming. The transition can be done using either binary search or two pointers. Time complexity should be $$$O(n\log{n})$$$.

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

How to solve L ?

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

    Just find the answer with a binary search.

    We can assume that $$$a \geq c$$$ because they are symmetric, then for an answer $$$k$$$ wee need to check whether we can satisfy the condition.

    Suppose we have all $$$a$$$ in set $$$A$$$, $$$b$$$ in set $$$B$$$ and $$$c$$$ in set $$$C$$$, then we need to adjust it.

    If $$$a \leq k$$$, obviously $$$c \leq a \leq k$$$, we only need to check if we can put some person b to $$$A$$$ or $$$C$$$.

    If $$$a \geq c > k$$$, we failed, otherwise we put $$$a - k$$$ person a in $$$B$$$, and we can take at most $$$b$$$ person b from $$$B$$$ to $$$C$$$, just to find out whether it is possible.

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

Нижний Новгород идет на золотые медали? По сборам, по четверти, например, похоже.

Ну и проход в полуфинал чумовой, конечно.

P.S. Посмотрел состав... ну, похоже, что одни из фаворитов

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

I am wondering if everything is ok with checker for task I.

During contest I've submitted solution. After contest with some assertions it turned out that test 9 is maxtest ($$$n, m = 10^6, k = 10^{18}, a_i = 10^{12}$$$). So I asserted to check if my answer is correct and I got wa instead of rte.

To check if I haven't made any mistake (in asserts etc) I took accepted code from comments and with diff checked on my laptop that I calculated answer correctly. Now I have no idea what's wrong with my code/output, can someone investigate this (maybe I made a mistake, but I just can't see where)?

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

Can anyone provide a solution for L? It will help me a lot... Thanks!