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

Автор MikeMirzayanov, 4 года назад, По-русски

Добрый день!

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

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

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

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

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

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

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

is this rated for div3?

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

Thank you for your efforts. Good luck to everyone!

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

how to solve E?

  • »
    »
    4 года назад, # ^ |
    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +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.

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

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

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

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

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

How to approach B?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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

    • »
      »
      »
      4 года назад, # ^ |
      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$$$.

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

What is test case 2 in J ?

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

-

»
4 года назад, # |
  Проголосовать: нравится 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

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

    You delete a bridge.

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

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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.

    • »
      »
      »
      4 года назад, # ^ |
      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 :)

»
4 года назад, # |
  Проголосовать: нравится 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?

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

Should we wait for editorial or not?

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

How to solve problem C?

  • »
    »
    4 года назад, # ^ |
    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

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

    https://pastebin.com/UNyjNnuu

    Here hope this helps

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -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

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

How to solve problem N:Wires?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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

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

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          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 :|]....

    • »
      »
      »
      4 года назад, # ^ |
      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

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

How to solve D, I, M?

  • »
    »
    4 года назад, # ^ |
    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.

    • »
      »
      »
      4 года назад, # ^ |
      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?

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

        Thank you but the solution can't be viewed.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +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$$$

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

          How to solve K? qwq

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 4   Проголосовать: нравится +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), and 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 $$$f(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

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

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

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

      Can you please provide your implimentation if you have it.

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

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

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

      I think it should be " R = set of indices y with bit i=0 and y+1 also has bit i=0." instead of " R = set of indices y with bit i=1 and y+1 also has bit i=0.". Am i wrong?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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
»
4 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

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

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 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.

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

Does this competition have any influence on ratings?

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

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

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

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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

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

      can u provide link to your solution.. Thanks for replying..

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

          Thanks for providing the solutions, it help me a lot...

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

          Can you explain why your solution works. You have explained your approach and I understood what you have done. But I can't really understand how we can restrict possible values for "Maximum capacity of single ride".

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

          Thanks, nChurgulia! Can you explain what's the magic is here:

                  if(arr[i] + rem < c){
                      rem = arr[i];
                  }else{
                      rem = (arr[i] + rem)%c;
                  }
          

          Why this does not work:

          ans += (arr[i] + rem)/c;
          rem = (arr[i] + rem)%c;
          
          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Because difference of heights can not be greater than 1, in this case you are accumulating rem

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

            If you set rem = (arr[i] +rem)%c, there are chances that you will have soldiers of three different heights in a single row and you don't want that to happen. So, it is mandatory to check whether (rem+ arr[i]) >=c. If (rem+arr[i]) < c and you still carry on with making the row, then this row will have soldiers of height (i-1 i.e. rem) && (i) && (i+1) which are three different heights.

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

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

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

Can you please make all sources visible?

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

How to solve G?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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})$$$.

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

How to solve L ?

  • »
    »
    4 года назад, # ^ |
    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.

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

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

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

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

»
4 года назад, # |
  Проголосовать: нравится +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)?

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

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

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

How to solve problem K ?

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

Can anybody please help me in solving the F problem?