Блог пользователя halin.george

Автор halin.george, история, 8 лет назад, По-русски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Разбор задач Codeforces Round 381 (Div. 1)
Разбор задач Codeforces Round 381 (Div. 2)
  • Проголосовать: нравится
  • +48
  • Проголосовать: не нравится

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

Во время контеста я пришёл к следующему решению задачи E, но не смог его достаточно эффективно реализовать.

Создадим сеть с 4 + n вершинами: сток t, исток s, две вершины x и y, которые отвечают шарам разных типов, а также n вершин на каждого покемона. Проведём рёбра из s в x и y нулевой стоимости и пропускных способностей a и b соответственно. Из x проведём рёбра единичной пропускной способности во всех покемонов, со стоимостями ( - pi). Аналогично, из y проведём рёбра с единичной пропускной способностью и стоимостью ( - ui).

Мы хотим пустить поток величины a + b в сети, минимизировав стоимость. Заметим, что если в i-ого покемона выстрелить обоими шарами, вероятность того, что он будет повержен, равна 1 - (1 - pi)(1 - ui) = pi + ui - piui. Значит, нужно каким-то образом прибавить к общей стоимости piui в случае, если в покемона выстрелили обоими шарами.

Для этого из каждого покемона проведём в сток два ребра: одно пропускной способности 1 и стоимости 0, второе — способности 1 и стоимости piui. Оптимальный поток либо будет течь по верхнему ребру, если в i-ого покемона втекает единица потока, либо по обоим, увеличивая стоимость на нужную величину.

Стало быть, модуль минимальной стоимости максимального потока в такой сети равен ответу. В сети O(N) вершин и рёбер, поток есть O(N). Форд-Беллман получил TL, Дейкстра должна зайти.

UPD: Дейкстра зашла после замены long double на double. Форд-Беллману это не помогло...

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

Честно говоря задача "739A — Алёна и mex" очень запутанно написана. Не то что я не смог ее решить, я вообще не понял о чем речь.

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

    Я прочитал условие. Там всё хорошо написано. Мне кажется, это один из важных навыков, которые дают эти соревнования — сесть, напрячься и прочитать технический текст формально и максимально естественно. Поверьте, и техническая документация к требования ПО бывает сложной и в computer science есть много текстов, которые надо суметь прочитать.

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

      Я понимаю что немного запутать это часть соревнования. Меня сильно смутило это предложение.

      "Назовем подмассивом некоторую последовательность из подряд идущих чисел в массиве."

      Что значит подряд идущих чисел? Если числа просто рядом стоят разве это не подряд идущие числа? То есть под это условие по-моему подходит просто любые числа подряд идущие. Почему я не могу взять просто "10000 10000 10000 10000 10000"?

      Если кто-то мне объяснит как это понять буду очень признателен.

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

        Если числа просто рядом стоят разве это не подряд идущие числа?

        А в чем разница между "подряд идущими" и "рядом стоящими", кроме того, что первые "идут", а вторые "стоят", и как вы понимаете это относительно чисел массива?)

        Я понимаю, когда у новичков возникают проблемы с пониманием фраз "минимизировать максимум / максимизировать минимум", но такую проблему не понимаю.

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

          Видимо я не очень владею терминологией и не вижу различий. Если предположить что "подряд идущие" это возрастающая или убывающая последовательность, где числа идут одно за другим. "1 2 3 2 1"

          То как сюда вписывается пример "5 2 0 1"?

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

            Подряд идущие не значит возрастающие или убывающие. Это означает что мы берем подпоследовательность элементов без пропусков. То есть все элементы с i-го по j-й. Иногда в задачах идет речь о подпоследовательностях общего вида, то есть в такие подпоследовательности попадают элементы, которые не обязательно идут подряд (например, каждый третий).

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

Кто-то может объяснить "Алёна и дерево" более подробно? Я понял что нужно найти высоту всех вершин, и что бинпоиском можно найти предков которые получат +1, но я не понял как заполнить эти +1 всем предкам?

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

    Допустим у нас есть массив (пусть изначально из нулей), и нам нужно обработать кучу запросов вида прибавить на подотрезке [l, r] величину x, и в конце вывести результирующий массив. Это можно сделать следующим образом: a[l] += x, a[r+1] -= x. Так обрабатываем каждый запрос, а в конце накапливаем префикс суммы a[i] += a[i-1]. В этой же задаче можно сделать аналогично, только вместо массива у нас будет стек дфса (в нем в каждый момент будут лежать все предки), и префикс суммы будем накапливать в обратную сторону.

    Еще это можно переформулировать немного иначе: ответ в вершине V равен сумме ответов ее детей минус количество вершин, для которых вершина V — первый предок, который не получит +1. Таким образом мы для каждой вершины бинпоиском находим первого предка, который не получит +1, и делаем в его ответе -1.

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

      Теперь все понял, спасибо!

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

      Для каждой вершины нужно делать свой бинпоиск? Если да, то я не совсем понимаю, на каком множестве?

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

        Да, для каждой вершины бинпоиск свой, это бинпоиск по всем предкам этой вершины. Если отсортировать предков по глубине, можно заметить, что чем выше находится предок, тем больше расстояние от вершины до него :) Поэтому можно бинпоиском найти самого высокого предка, расстояние до которого не больше a[x].

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

          В целом я понимаю, что бинпоиск надо делать по всем предкам)

          Но мы же не можем хранить для каждой вершины список ее предков явно. Или мы бинпоиск делаем прямо в процессе обхода дерева?

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

            Как вариант, можно поддерживать в дфсе стек вершин, которые мы посетили, но из которых еще не успели выйти. Легко заметить, что в этом стеке и будут храниться все предки, при чем уже отсортированные по глубине.

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

            Для каждой вершины надо хранить 1, 2, 4, 8 и т.д. предков. С этой инфой можно восстановить любого предка за логарифм.

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

              О, вот это очень интересно, спасибо за идею!

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

В задаче 739B можно построить эйлеров обход и находить кол-во вершин x, h[x] — a[x] <= h[v] в поддереве c помощью дерева отрезков.

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

Я придумал другое решение Div1C, оно мне кажется немного проще авторского.

Как и в разборе, сначала перейдём к частичным разностям и массиву +1/0/-1. Теперь заведём сет отрезков вида +1 +1 ... -1 -1, максимальных по включению (т.е. таких, что в них ничего нельзя добавить ни слева, ни справа). Кроме этого, будем держать мультисет длин таких отрезков.

Теперь при изменении одной позиции можно понять, в каком отрезке она сейчас лежит, и при необходимости разделить отрезок на два или склеить его со следующим/предыдущим.

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

    Второе авторское было таким же) Вот

    Но кода в нем получилось намного больше, и писал я его дольше, так что как основное авторское использовал решение с ДО.

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

Could someone please look at my code for 739B? I was getting WA on pretest 15 and am not sure why...

I store the 2^k ancestors and the distance to them in bparent[][] and bdist[][]. I then binary search for each node that controls the node that I am on and store the start and end segments in event[]. The function solve() dfs's through the tree, keeping track of how many nodes each node controls.

Thanks!

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

For problem D, how do we store the ancestors of all nodes in O(n)?

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

Can someone explain the approach for the problem 'Alyona and Tree'

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

    This is the binary search method that may not be the easiest, I recommend checking out zawini54's comment too!

    A few observations could be made:

    1. dist(v, u) = dist(root, u) - dist(root, v)
    2. for any vertex v, and its ancestors a1, a2, ..., ai,
      a1 being the furtherest ancestor (root of the tree) and ai the closest (immediate parent vertex),
      we can see that dist(root, a1) < dist(root, a2) < ... < dist(root, ai) < dist(root, v), a sorted sequence that is binary searchable.
    3. for each vertex v, we want to find the number of vertices u it controls, i.e.:
      dist(v, u) ≤ value(u) dist(root, u) - dist(root, v) ≤ value(u) dist(root, u) - value(u) ≤ dist(root, v)
    4. with #2 and #3 in mind, let's try to think of this problem in another way: for each vertex u, which vertices v could control u?
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ok, for each vertex u, I can find how many ancestor controls it, but how do I use this information to find out the reverse?

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

        this can be maintained using segment tree on the path from root to current vertex

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

      Let u is controlled by x vertices. Then the immediate x parents of u could control this vertex u.

      But a simple approach in getting the answer requires O(n^2) which would fail on the time limit. Can you suggest a better approach?

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

        Consider the array, A = [6, 1, 6, 9, 3]

        We can compute an array of differences between the neighbouring two elements, a difference array, D = [6,  - 5, 5, 3,  - 6],

        Note how we can reconstruct the array A from its difference array D,

        A[0] = D[0]
        A[1] = D[0] + D[1]
        A[2] = D[0] + D[1] + D[2]
        A[3] = D[0] + D[1] + D[2] + D[3]
        A[4] = D[0] + D[1] + D[2] + D[3] + D[4]

        If we can somehow first construct a difference "array" D for this problem, then we can reconstruct the answer "array" A from it.

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

Actually there's another solution that doesn't use binary lifting, but the merging sets technique. I think it's easier, because at first I thought of doing something with binary lifting but wasn't able to come up with anything. Check it out: 22490570

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

    Nice approach, btw are you making reference to the technique disscused at this post?

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

    I considered merging set approach during contest, but couldn't find a way to count the number of elements <= d in O(logn) using std::set, now I know it's unnecesary for this problem after reading you code.
    However, if the condition change to that v controls u if dist(v, u) <= a(v) (instead of a(u)), it seems we must have a way to count the number of elements <= d in O(logn) using merging set approach, and std::set doesn't satisfy this.

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

      Actually, I don't think my approach works with the harder version of the problem, since it relies on that fact that d(v) is monotonically increasing as you go down the tree. I think there should be a solution involving segment tree and coordinate compression, but I haven't thought about it that much. Please feel free to correct me on anything.

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

      But Ordered Statistics Tree does. Can't we use it instead of sets?

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

    An explanation please?

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

    Hi,your approach looks amazing, I just learned binary lifting through this problem and now you propose another way of doing the problem... Where did you learn this technique from, I want to learn this too,is there some blog post associated with it , or some source where I can learn the merging set technique,because I cant understand your solution , can you also explain it just a little..?

    Thanks a ton!

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

      For anyone looking for a binary lifting solution: here it is

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

        Explanation to the binary lifting solution:

        The base idea can be seen here. We just don't use the binary search over the ancestors of a node.

        We create the parent's DP, that is required to do binary lifting. I saw this video to understand binary lifting. You create an 2D matrix with dims: DP[N][HEIGHT], where DP[i][j] represents the parent of $$$i^{th}$$$ node at height $$$2^j$$$ from $$$i$$$.

        DP[i][0] is simply the direct parent of the node, already given in the question. For the others, use this:

        f(j,1,21) f(i,0,n) parDP[i][j] = parDP[parDP[i][j-1]][j-1] ;
        

        Where j is the height, and i is the node. If you're confused, watch the video.

        Now, we remove the binary search part, and instead do the search using the parent DP matrix we created.

        This can be done using:

        int s = node ;
            for(int d=20;d>=0;d--)
            {
                if(dist[node]-dist[parDP[s][d]]<=a[node])
                {
                    s = parDP[s][d] ;
                }
            }
        

        This is what I stole from yaksha. Thenks. What does it mean tho?

        It finds the farthermost parent of s, that satisfies the condition. Let's name it $$$\phi$$$. But we're iterating through the powers of 2. That is, it is possible that a parent at an height of $$$2^j$$$ from $$$s$$$, might satisfy the condition, but we didn't see $$$2^{j+1}-2^{j}$$$ elements between the two parents.

        So, we'll have to iterate through the parents of $$$\phi$$$. But do we have to start again? No. We know that $$$2^{j+1}$$$th parent didn't satisfy, whereas $$$2^j$$$ did. So, we have a gap of $$$2^{j+1}-2^j = 2^j$$$ elements. So, we look into the $$$j^{th}$$$ parent of $$$\phi$$$ this time. This gap closes as we progress towards d=0.

        Everything else is pretty much the same.

        Here is my submission, made from multiple code stealing activities.

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

    Beautiful solution!

    This question just keeps on giving :>

    So explanation on the DSU on tree method to solve this problem (Alyona And Tree):

    There's a basic HLD (heavy light decomposition) concept of light child and heavy child in a tree for each node.So, consider you have a node $$$N$$$, which has $$$\alpha$$$ children, $$$C_1,C_2,C_3,...,C_{\alpha}$$$. Now, the child, which has the maximum size of it's subtree, is the one which is called the big child or the heavy child. Every other child is called a light child.

    How is this concept useful?

    So, for a node, consider, you need to perform some query that needs information from the whole tree, then in that case, if you do a brute force operation, then you'll get a $$$O(n^2)$$$ time complexity. What we can do here, is store the information of the big child while the traversal is done, and for the rest of the children, we do whatever we did in the brute force method.

    How does that help us?

    Basically we're not going into the big child, but are going into the light children. Consider this, if $$$x=tree[lightchild].size()$$$ and $$$y=tree[bigchild].size()$$$. So, $$$y > x$$$, obviously. So, if I merge the subtree of the lightchild into the subtree of the bigChild, then it's size: $$$y+x > x+x = 2\times x$$$. That is, each merge operation will, at least, double the size of the bigchild subtree. So, we can do this doubling operation only until the total number of elements ($$$=n$$$) is reached. That is, $$$log(n)$$$ times.

    And since we have $$$n$$$ nodes in total, the total time complexity is $$$O(n log n)$$$.

    You can learn more about DSU on graphs, here and here.

    Steps for the algorithm:

    1. For a node, find the bigChild.

    2. DFS through the lightChilds, and do not remember their results

    3. DFS through the bigChild, and remember it's result

    4. Add the result of the current node, if possible.

    5. Add the values of the subtrees of the lightChilds.

    6. At this point, we have the result for the node

    7. Remove the values of the lightChilds if the current node is a light child, else do not delete them

    This is the procedure, I understood from the tutorial.

    Now let's try to analyze szawinis' solution. Here we are not keeping results in some variable array or something, therefore there is no removal of values at the end of the DFS. That is, we can keep the subtree information intact, while traversing the tree. So priority queue pq stores the $$$\text{distance from root}-a[v]$$$ value for the nodes that satisfy the condition. That is for the node node, pq[node] will have the mentioned difference for the nodes which satisfy the condition (d[child]-d[node]<=a[child]).

    In the big for loop, if we see a light child, we push all it's values into the current node's pq. Whereas, if we see a potential bigChild, we push all the elements of the current node into the bigChild's pq and then point to the bigChild's pq as the current node's pq.

    The point is, not to transfer the elements of the big child (which actually makes the algorithm run in O(nlog n)). Then we disregard the elements which do not satisfy the condition. If you think that's a problem, then think how many elements in total can you remove? So yeah this can, at max n elements, because only the elements that satisfy the condition for the current node, are percolated up as potential candidates.

    At this point, you can take the value of pq[node].size() as the answer. And then add the node itself in it's priority queue.

    I hope this helps.

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

Can someone please elaborate the binary lifting method for problem D?

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

    My Code 22652723

    easy to understand

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

      Instead of binary lifting, I think you're using binary search in here.

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

      For everyone trying to understand Sukeesh's solution, here is an explanation:

      Basic what we knows:

      1. $$$dist(u,v) = dist(root,v)-dist(root,u)$$$. We're given the condition: $$$dist(u,v) \leq a_i$$$, which can be written now as $$$dist(root,v)-dist(root,u) \leq a_i$$$ (where $$$u$$$ is an ancestor of $$$v$$$).

      2. If you're looking at vertex $$$v$$$, then it's ancestors' distances from the root, will be in strictly increasing order, starting from the root itself. That is, if $$$a_1,a_2,a_3,...,a_i$$$ are the ancestors of $$$v$$$, where $$$a_1$$$ is the root, and $$$a_i$$$ is the parent of $$$v$$$, then the distance of this series of nodes, from the root, will be in strictly increasing order. Thus we can do a binary search on them.

      So let's see the algorithm. We're doing a DFS here.

      Consider we're at the vertex $$$v$$$, and we have the information of it's ancestors saved in an vector $$$arr$$$. We're saving the distance of a node from the root in the array $$$d$$$, while we're going down while the DFS. So while we're at $$$v$$$, we have the distance of it's ancestors from the root already saved in $$$d$$$.

      Great.

      Now we look for the first ancestor $$$a$$$ which doesn't satisfy the condition:

      $$$dist(root,v)-dist(root,a) \leq v_i$$$
      $$$dist(root,v)-v_i \leq dist(root,a)$$$

      We can calculate the LHS of this formula for our $v$ boi, and then we can search for this value in $$$arr$$$. Let's say this value's index is $$$hi$$$. So, bringing partial sums in here fam.

      This part is good. So what do we have here? We can say that all ancestors of $$$v$$$ after $$$hi$$$ (including $$$hi$$$) till the parent of $$$v$$$ satisfy the condition, right?

      We're saving the partial sums in an array dp.

      So as done in partial sums, we do dp[par[v]]++ and dp[par[arr[hi]]--. You'll understand this is you know about partial sums. We increase the starting of a segment, and decrease after the end of it.

      Now we carry on to our DFS work.

      We do all this,and do complete our DFS from the root.

      Now we can compute the answer of each node, by using the partial sums we built during the first DFS (oh no, there's no second DFS, yet).

      So, we calculate the answer for each node, in the same way, we created the dp array(i.e. going through a DFS). So we calculate the dp value for the children first, and then use it to calculate the value of the parent, by adding the children dp values in the parent dp value. The function go is used to do that.

      void go(ll v){
      	for ( ll j = 0 ; j < adj[v].sz ; j ++ ){
      		go(adj[v][j].F);
      		dp[v] += dp[adj[v][j].F];
      	}
      }
      

      Why is this working you ask? Consider a positive value is encountered. This means that this is a starting point for a segment of nodes which have some node $$$v$$$ for which the needed condition is satisfied. Thus we increase our dp value. If a negative value is encountered, we know that some segment has ended, and we decrease our dp value.

      Hope this helps someone.

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

In 739E — Gosha is hunting, The editorial writes "Not hard to prove that in group Y we should throw Poke Balls to Pokemons with greatest u - p." I think that we want to maximize PokeBalls probability when we throw PokeBalls. So shouldn't we throw pokeballs to pokemons with greatest p-u?

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

    That is not correct. Let me clarify a part of the editorial's proof for archival reasons.

    Assume that the pokemons have been sorted in descending order of $$$u_i$$$, therefore $$$u_0 >= u_1 >= u_2 >= .... u_{n-1}$$$. Now, let $$$i$$$ be the index of the last pokemon to be thrown an ultraball.

    Claim: For all pokemon in $$$[0, ... i - 1]$$$, we throw a ball at them (or perhaps two).

    Proof: Assume that there was a pokemon, say $$$x$$$, where $$$0 <= x < i$$$, and we don't throw a ball at $$$x$$$. But note that we do throw a ultraball at $$$i$$$. What is the total change if we throw that ultraball at $$$x$$$ instead?

    Case 1: We do not also throw a pokeball at $$$i$$$:
    — Loss in not throwing the ultraball at $$$i$$$ = $$$u_i$$$
    — Gain in throwing the ultraball at $$$x$$$ = $$$u_x$$$.
    Since $$$u_x >= u_i$$$, we can throw the ultraball at $$$x$$$ and not be worse.

    Case 2: We do also throw a pokeball at $$$i$$$.
    — Loss in not throwing the ultraball at $$$i$$$ = $$$(u_i + p_i - p_{i}u_{i} - p_i) = u_i(1-p_i)$$$
    — Gain in throwing the ultraball at $$$x$$$ = $$$u_x$$$.
    Since $$$u_x >= u_i >= u_i(1-p_i)$$$, we can throw the ultraball at $$$x$$$ and not be worse.

    Hence Proved

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

      Can you explain the Loss in case 2 proofbycontradiction? Does it mean that (ui + pi) -> either ultraball catches the pokemon or pokeball catches it. and (uipi + pi) -> either both types of balls catches pokemon or pokeball catches it.

      therefore (ui + pi) — (uipi + pi) -> ultraball catches the pokemon but pokeball does not.

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

    Yeah, I also think so

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

In Div1-A or Div2-C Why not to just fill the whole array with the maximum available value which is 10^9-1 and the maximum minimum mex becomes 10^9 ?

You didn't mention anything like : the array(or subarray) elements need to be unique !

What am I getting wrong here ?

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

    "The mex of a set S is a minimum possible non-negative integer that is not in S."

    if you fill array with max value your ans will be 0