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

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

1. Одежда (A Div-2)

В этой задаче ограничения позволяли просто перебрать все возможные тройки i, j, k (которых не больше, чем 1003 = 1000000), для каждой тройки проверить, все ли элементы тройки подходят друг к другу, и среди троек, в которых все элементы подходят друг к другу, найти тройку с минимальной суммой ai + aj + ak.

2. Сумма цифр (B Div-2)

Изначально в числе не больше, чем 100000 цифр. Значит, после первого применения заклинания сумма цифр будет не больше, чем 9· 100000 = 900000, ее можно сосчитать простым проходом по строке из ввода. Значит, в нем будет не больше 6 цифр. После второго применения заклинания число станет не больше, чем 9· 6 = 54. То есть, число будет не более, чем двухзначным. Сумма цифр двузначного числа не больше 18, а сумма цифр числа, которое не больше 18, уже однозначна. Значит, Геральд сможет применить заклинание не больше 4 раз. При этом, чтобы первый раз посчитать сумму цифр нам понадобится 100000 сложений, а остальные действия незначительны.

3. Домашнее задание (C Div-2, A Div-1)

Для каждой буквы найдем количество раз, которое она встречается. Пусть 'a' встречается ka раз, 'b' встречается kb раз, и так далее. Наша задача --- выкинуть все вхождения как можно большего количества букв. Пусть мы выкинули какие-то x букв. Заметим, что если вместо этого выкинуть x самых редких букв, суммарное число выкинутых букв будет не больше. Значит, для любого числа x легко выяснить, можно ли удалить все вхождения каких-нибудь x букв. Соответственно, можно выбрать минимаьное такое x, для которого можно.

4. Автобусы (D Div-2, B Div-1)

Давайте для каждой остановки x от 0 до n посчитаем величину kx - количество способов на нее приехать. Рассмотрим i-тый автобус. Количество способов приехать на остановку ti на i автобусе, очевидно, просто равно количеству способов сесть в этот автобус. А сесть в этот автобус можно на остановке si, si + 1, ..., ti - 1. Таким образом, количество способов приехать на остановку ti на i автобусе равно сумме ksi + ksi + 1 + ... + kti - 1. Осталось заметить, что, чтобы найти общее количество способов попасть на остановку ti, надо просуммировать количества способов попасть на нее на каждом автобусе, у которого это конечная остановка.
Осталось решить две проблемы. Проблема первая: 0 ≤ n ≤ 109, поэтому все kx в память не влезут. Но, очевидно, нам понадобятся только остановки с ненулевым kx. Например, можно сжать координаты: создать список из всех встречающихся в условии остановок (а так же остановок 0 и n), отсортировать его, убрать повторяющиеся и заменить каждый номер остановки на его индекс в этом массиве. Тогда получится, что все остановки имеют номера в пределах 200001. Массив такой длины уже спокойно влезает в память.
Второе, если сумму ksi + ksi + 1 + ... + kti - 1 считать циклом, решение будет работать за O(m2), что не влезает в TL. Эта проблема тоже легко решается: можно создать и обновлять одновременно с массивом k[] массив sum[], в котором будем сумму элементов k до некоторого момента: sum[i] = k[0] + k[1] + ...\ + k[i - 1]. Иными словами, sum[0] = 0, sum[i + 1] = sum[i] + k[i]. Тогда количество способов доехать до остановки ti на i автобусе будет равно sum[ti] - sum[si].
Итого, сложность решения, O(m*log(m)) времени (за счёт сжатия координат), O(m) памяти.

5. Вектора (E Div-2, C Div-1)

Переформулируем задачу в комплексных числах.
Рассмотрим комплексные числа a = xA + iyAb = xB + iyB и c = xC + iyC. С числом A разрешается делать операции A → A + C и A → iA.
Посмотрим, что может получится из числа A при применении к нему этих операций. Поскольку i4 = 1, то полученное число имеет вид A· ik + aC + biC - cC - idC для каких-то целых неотрицательных k, a, b, c, d, или, иными словами, A· ik + aC + biC для k = 0, 1, 2, 3 и целых a, b. Поскольку k может быть равно только 0, 1, 2 или 3, достаточно узнать, можно ли представить одно из чисел B - A, B - iA, B + A или B + iA в виде aC + biC.
Осталось научиться понимать, представляется ли некоторое комплексное число D в виде aC + biC. Запишем в виде системы линейных уравнений:
a· xC - b· yC = xD
a· yC + b· xC = yD
Решить систему линейных уравнений - это уже стандартная техническая задача.

6. Замок (D Div-1)

Перенумеруем вершины так, чтобы стартовая вершина, в которой исходно находится Геральд, получила номер 0.
Подвесим дерево, о котором идет речь в задаче, за вершину 0, и рассмотрим прямых потомков этой вершины. Пусть Геральд начал свой путь, пойдя в одну из этих вершин - вершину x. Далее после этого он должен обойти все поддерево этой вершины и вернуться в нее - иначе его маршрут пройдет не по всем вершинами. Далее он вернется из вершины x в вершину 0 и больше никогда не вернется в эту вершину. Далее он пойдет еще в какого-то предка вершины 0 (если, конечно, они у нее еще есть), и обойдет поддерево, подвешенное на эту вершину; и так далее. Пусть мы посчитали искомую величину для аналогичных задач на поддеревьях. Попробуем исходя из этого посчитать искомую величину для всего дерева. Это даст нам возможность решать задачу динамикой по поддереву.
Пусть у вершины 0 n сыновей. Пусть в них k1,  k2, ...,  kn потомков (включая них самих).
Пусть всего в дереве N вершин.
Пусть Ti - это удвоенная сумма длин всех ребер в i-том поддереве, включая ребро, ведущее в вершину 0. Это величина - ровно то время, которое потребуется Геральду, чтобы обойти все поддерево, начиная из вершины 0 и вернуться в вершину 0.
Наконец, пусть ti - ответ для подзадачи в i-той поддереве. Сразу прибавим к этому времени длину ребра между вершиной 0 и ее i-тым предком. Таким образом, это будет среднее время для поддерева с учётом того, что надо ещё дойти до него от вершины 0.
Пусть мы обошли поддеревья в порядке 1, 2, ..., n. Каково среднее время нахождения клада?
С вероятностью клад окажется в первом поддереве. Тогда среднее время нахождения клада будет t1.
С вероятностью клад окажется во втором поддереве. Тогда среднее время нахождения клада будет T1 + t2.
И так далее. Таким образом, среднее время нахождения клада будет

Посмотрим, можно ли улучшить это время? Поменяем местами поддеревья номер i и i + 1. Тогда из суммы исчезнет слагаемое ki + 1Ti и появится слагаемое kiTi + 1. То есть, сумма изменится на kiTi + 1 - ki + 1Ti. Сумма уменьшится, если это изменение меньше 0, то есть, если kiTi + 1 - ki + 1Ti < 0, что равносильно .
Таким образом, среднее время нахождения клада уменьшить не удастся, если поддеревья отсортированы в порядке возрастания величины , иначе найдется пара соседних поддеревьев, замена местами которых приведёт к улучшению результата. Таким образом, надо отсортировать поддеревья по этой величине, и обходить их этом порядке.

7. Конфеты и Камни. (E Div-1)

Суть задачи в том, что есть доска n × m, на которой расставлены числа. И надо пройти от клетки (0, 0) до клетки (n - 1, m - 1), делая шаги на одну клетку вверх или вправо (то есть, увеличивая на 1 одну из координат) так, чтобы сумма чисел на клетках пути была максимальна.
Наша задача определить n + m - 1 клетку оптимального пути. Давайте начнем с малого: определим одну клетку этого пути, а именно среднюю. Пусть . Какие клетки поля могут быть k-тыми? Очевидно, те, у которых сумма координат равна k, то есть, это будет диагональ прямоугольника. Поэтому очевидно, что несложно динамикой за O(nm) в нижнем треугольнике под этой диагональю посчитать, какое какую максимальную сумму можно набрать, придя в каждую из клеток этой диагонали. Аналогичной динамикой в верхнем треугольнике (на это раз сверху вниз) для каждой клетки на этой диагонали посчитаем, какую максимальную сумму можно собрать, стартовав с этой клетки. Сложив эти две величины, получим, какую максимальную сумму можно получить, пройдя через эту клетку. Осталось найти клетку (x, y), в которой достигается максимум. Её мы и возьмем за k-тую клетку нашего пути. Заметим, что в течение этой итерации мы использовали O((n + m)2) времени и O(n + m) памяти.
Теперь рекурсивно перейдем к подзадачам, то есть, будем искать оптимальный путь от клетки (0, 0) до клетки (x, y), и от клетки (x, y) до клетки (n, m).
Осталось убедиться, что такое решение решение занимает ((n + m)2) времени.
Обозначим n + m за r.
На первом уровне рекурсии мы потратим r2 времени. На втором - два раза по . На третьем - 4 раза по , и так далее. Все будет потрачено времени . Таким образом, описанное решение занимает O((n + m)2) времени и очевидно, что оно занимает O(n + m) памяти.
Разбор задач Codeforces Beta Round 79 (Div. 1 Only)
Разбор задач Codeforces Beta Round 79 (Div. 2 Only)
  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

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

Действительно, вы очень хорошо поработали - классный набор задач и качественный понятный разбор. Спасибо за это.

С нетерпением жду разбора задач D и E.

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

В задаче D Геральд уже в вершине 0, там не надо перенумеровывать :о)

Единственный комментарий -- в задаче А для второго дивизиона ограничение в 40 было бы более оправданным, чтобы проходили решения на python, ruby и других. Это кажется более чем разумным -- делать задачи А и В решаемыми на всех языках.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    простите, я не знал, что 100^3 - это много для некоторых языков о_О эта задача вообще оказалась статистически второй по сложности - не потому ли?
    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      Да, на руби и 10 в пятой не всегда входит :о)
      10^6 на питоне похоже что проходило, потому что есть несколько решений в дорешке, но у меня есть знакомые, которые не протолкнули А на контесте на питоне :о)
      А так как второй дивизион пишут, в том числе, и люди, далекие от спортивного программирования, надо делать, чтобы А и В в див2 всегда сдавались на скриптовых языках. Тем более, что в формате здешнем даже не понять, что ТЛ -- потому что претесты маленькие.

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Может не в тему но:
D:
Как считается обьём использованой памяти на якыках MS C++ и 
GNU C++ ?
Просто у меня один и тот же код на MS C++ АС, с ML=~20 Мб...а на GNU C++---чистый МL(
Или в чём ещё может быть проблема ?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    На студии STL по-другому реализован. Например, в GCC вектор каждый раз расширяется вдвое при достижении лимита, а в студии - как-то не понятно, но меньше чем вдвое. Отсюда и потребление памяти меньше.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Ого! Спасибо...буду знать :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      В студии примерно в полтора раза расширяется, покрайней мере в 2010.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто сможет объяснить в Автобусах, при нахождении ответа, видел такой вариант. (немного адаптирвоал)

a[i] = (s[t] - s[f] + (v[i].second == 0) + mod) % mod; // Вопрос, зачем тут + mod
s[i + 1] = (s[i] + a[i]) % mod;

Элементы всех контейнеров int, mod = 10^9+7, то есть 2 * mod помещается в int.
Все s[i] считаются по модулю mod. Они не будут больше mod. s[i] положительные, причем s[t] > s[f].

Вопрос, в чем разница между
a[i] = (s[t] - s[f] + (v[i].second == 0) + mod) % mod;
и
a[i] = (s[t] - s[f] + (v[i].second == 0)) % mod;
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Затем, что отрицательные числа во многих языках программирования берутся по модулю не по математическому определению: (-5) % 3 == -2. Соответственно, чтобы нормально взять по модулю, достаточно прибавить некоторое количество раз mod, пока число не станет неотрицательным.
    В данном случае (видимо) s[t] - s[f] >= -mod, посему достаточно прибавить mod один раз.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      >> достаточно прибавить некоторое количество раз mod

      Тогда лучше (a%m+m)%m

      • 13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Это вторая ступень познания дзена.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Если гарантируется 0 ≤ a, b < m, то  - m < a - b < m, и тогда
        res = (a - b + m) % m;
        работает корректно и быстро (одно взятие по модулю вместо двух).

        Ещё быстрее будет так:
        res = a - b;
        if (res < 0) res += m;
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Неправда, что s[t]>s[f], т.к. это у нас не числа, а остатки по модулю => s[t] - s[f] + (v[i].second == 0) может быть отрицательным.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    дело в том, что неверно, что s[t] > s[f]. Они же считаются по модулю.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Nice questions :)
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

вопрос по задаче В: ведь можно считать ответ динамикой "с конца": считать для каждой остановки, сколько способов доехать от нее до конца? Переходы: отсортили в обратном порядке автобусы по конечной остановке. Берем автобус - у него конечная Ti, начальная Si. Тогда для остановок от Si до Ti (не включая Ti) в дереве отрезков с модификацией на отрезке прибавляем количество способов добраться от Ti до последней остановки. (Все ответы хранятся в дереве отрезков)
Где может быть баг в таком решении? WA 51

если кто хочет помочь - посылка 587332
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I have somewhat different approach to the last problem. In fact one can say I have implemented the most straight forward solution. 

If it weren't for the reconstruction of the path it is easy to write dynamic solution of the problem. We iterate all values of n 1...n and calculate the best gain we can get for every possible value of m. The values for some n1 depend only on the values of n1 and thus we consume only O(n) memory and it took O(n * m) calculations for this part of the problem.

The thing is that the memory is not enough to store all the actions we took to get to this result. This is why when I do this calculations I store the actions taken only for the upper quarter of all ns. Then I can resotre the last quarter of the sought string. But when I restore it I can also formulate smaller problem to be solved (with smaller values of n and m). In it I do the same and again consider the actions taken only for the last portion of ns corresponding to the quarter of the original n. When I repeat this 4 times I have all the whole answer. 

This solution fits in both memory and time.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Asymptotically your solution is take up time O(nm), but really, I think, it will work too slow, becouse you are repeat dynamic four times...
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      The thing is that with this time restirctions you can afford recalculating several times. Memory limits impose that, but as soon as the dynamic can be done in O(n * m) it is not a problem. 

      The greatest slow down is that you still have to optimise your memory quite a lot and this is why I store every action I take in only single bit. This adds on some more actions you have to take for every read and every write operation. 

      And something I forgot to mention: as with every other time in which I post my solution, I have passed the problem in codeforces, beforehand.
      • 9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I think you are right.^_^

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

        so the space is still O(nm), but you split it in half (or a quarter), so that it takes 25MB, and then compute the rest? Feels like the recursive solution, but you split it only once or so and the dp is simpler (its not a diagonal row). I'm not sure if i get your idea.

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

    I came up with a very similar solution. First I find all the cells of the middle diagonal and then use DP to find the cell inside the diagonal that also belongs to the optimal path. Then using DP and a bitset<200000000> I find the optimal path from the upper left corner to the cell in the diagonal (this is the first half). I do the same thing to find the optimal path from the cell in the diagonal to the lower right corner (this is the second half). I join both halves and the full path is totally recovered. Here is my submission: http://codeforces.me/contest/101/submission/31324561

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

tkae should be take

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

tkae should be take.

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

I think this is the Smallest Solution for the B problem

#include<bits/stdc++.h>

using namespace std;
string s ;
int main(){
    cin >> s;int ans = 0;
    while(s.size()!=1){
        int n =0;for(int i=0;i<s.length();++i) n+=s[i]-'0';
        s = to_string(n);
        ans++; 
    } cout << ans << endl;
    return 0;
}
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Nice solution... a little way to make it faster is by adding ths line before for loop :-

    s.erase(remove(s.begin(),s.end(),'0'), s.end());

    This helps in removing the unwanted '0' from the string which dosent add to change the sum

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

what is the use of subtracting v from the lower_bound iterato vector<pair<int,int> v ; int l = lower_bound(v, v + i, pii(v[i].second, 0)) — v;

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

I keep running into problems where I hit a wall because the input is too big for what I know how to handle in Java.

Question B is one of those problems. I am using longs and they still aren't long enough for the digits in the input.

Is this a sign that the answer has to be found with another language or is there a technique I don't know about?

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

I am not getting problem D.

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

I am not getting problem D.

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

    Im also finding the solution very difficult to understand

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

      Here is how I solved:

      Let dp[x] be the number of ways to get to stop x. dp[0] = 1. So, for every bus i, you can do: $$$dp[t_i] = \sum_{s_i \leq j < t_i} dp[j]$$$. But we have a problem here, since $$$1 \leq t_i \leq 10^9$$$. You can use coordinate compression to handle this. You also can't compute this sum naively. I did it with a segment tree. Here is my submission for details.

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

i'm pretty sure that the time compelxity on problem E can be reduced to O(nm) (which is less than O((n+m)^2) when n>>m or vice versa. The reasoning is that you split n and m to n/2 and m/2 respectively. In terms of the contest this is not required because n and m have the same upper bound of 20'000. If the problem statement had said something in the terms of n, m <= 1e5 but n*m <= 1e8, then this would be necessary.

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

i'm pretty sure that for problem E, we can reduce the time complexity to Θ(nm) which is less than Θ(n+m)^2 when n>>m or vice verca. Because the constraints of n and m are independent, its unnecessary. The problem statement could say "n,m <=1e5 but n*m<=1e6". The reasoning is that the diagonal dp row, can be wider (have a different ratio, not 1:1), which is weird to implement. This way, with the recursive calls we can divide independently the 2 dimensions (n/2, and m/2 for the first division). Space compelxity is still Θ(nm).

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

242922518 my approach to the problem was to create a string consisting of integer characters, and adding the integer value of them to the variable called sum and after the summation is finished, converting the sum to the string and go on while the string.size() is bigger than 1 since the number we want is one digit.

sorry for my bad english, I hope this solution helps someone someday. Gl to all on their journeys.

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

I like the B problem easy implementation but i strugled to find the solution

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

can anyone provide the solution for Homework (C Div-2, A Div-1) i am a beginner to CP but this question looked interesting for greedy algorithm. i am having some difficulty in implementing it. Answer to this will help me a lot, Thanx:)