K
Join algorithms chat to ask questions about scrollbars
Size: a a a
2021 January 03
AM
Matthew Good
thanks ^~^
Happy to help xd
RR
Кееек
ПК
https://codeforces.com/problemset/problem/331/C1
Как решается эта задача?
В разборе написано что-то не очень понятное:
"Для решения подзадачи C1 можно либо посчитать динамику, либо жадно вычитать наибольшую цифру — несложно доказывается, что всегда требуется вычитать именно наибольшую цифру. Для подзадачи C2 достаточно посчитать динамику для первого миллиона, разбить мысленно число на две группы цифр — старшие разряды и младшие — и выполнять не одно вычитание, а целую серию вычитаний, чтобы мгновенно минимизировать младшие разряды. Для решения подзадачи C3 необходимо уйти от желания хранить в параметрах динамики само число, а хранить лишь количество разрядов."
В комментариях к разбору попытались объяснить подробнее, но мне всё равно непонятно, что пытаются сделать авторы:
"Let me try. First of all, in C2 we can do what's written in the editorial: split the number in two parts(6 digits each), now while the first part is fixed, all we need to know about it is the biggest digit. So we calculate two arrays: cnt[dig][n] — how many operations we need to get to negative number if we can subtract maximum of dig and biggest digit of n, and decr[dig][n] — what is the first negative number we reach this way(here 0 ≤ dig < 10, 0 ≤ n < 106). After that, we can decrease first part by one in O(1) time and that's it.
C3's solution is almost the same, we calculate arrays cnt and decr again using memoization, but we split the number into the first digit and remainder."
Как решается эта задача?
В разборе написано что-то не очень понятное:
"Для решения подзадачи C1 можно либо посчитать динамику, либо жадно вычитать наибольшую цифру — несложно доказывается, что всегда требуется вычитать именно наибольшую цифру. Для подзадачи C2 достаточно посчитать динамику для первого миллиона, разбить мысленно число на две группы цифр — старшие разряды и младшие — и выполнять не одно вычитание, а целую серию вычитаний, чтобы мгновенно минимизировать младшие разряды. Для решения подзадачи C3 необходимо уйти от желания хранить в параметрах динамики само число, а хранить лишь количество разрядов."
В комментариях к разбору попытались объяснить подробнее, но мне всё равно непонятно, что пытаются сделать авторы:
"Let me try. First of all, in C2 we can do what's written in the editorial: split the number in two parts(6 digits each), now while the first part is fixed, all we need to know about it is the biggest digit. So we calculate two arrays: cnt[dig][n] — how many operations we need to get to negative number if we can subtract maximum of dig and biggest digit of n, and decr[dig][n] — what is the first negative number we reach this way(here 0 ≤ dig < 10, 0 ≤ n < 106). After that, we can decrease first part by one in O(1) time and that's it.
C3's solution is almost the same, we calculate arrays cnt and decr again using memoization, but we split the number into the first digit and remainder."
ПК
А, понял, в этой задаче нужно решить только первую подгруппу, мда...
2021 January 05
U
можно тупенький вопрос?
U
как отсортировать по критерию "родительский-дочерний"?
U
если у меня связи только от дочернего к родительскому, а не наоборот
U
то есть мне грубо говоря нужна топологическая сортировка, но ребра идут в обратном направлении
DP
построй полное дерево (обратные связи) пройдя по всему
U
хм, я чёто тоже про это как раз подумал
EZ
то есть мне грубо говоря нужна топологическая сортировка, но ребра идут в обратном направлении
Разверни ребра?)
DK
Реверс топологического порядка со связями сын-родитель будет топсорт для родитель-сын!
2021 January 06
P
Ребят, а можете подсказать какие-то идеи решения задачи ниже методом divide and conquer?
Наверняка, решение можно нагуглить, но мне нужны какие-то подсказки.
Есть арифметическое выражение из чисел и операторов.
Нужно вернуть все возможные уникальные результаты вычислений этого выражения после добавления скобок.
2-3*5/4 = x1
(2-3)*5/4 = x2
2-(3*5/4) = x3
((2-3)*5)/4 = x4
...
Не понимаю, как делать merge частей, если мы поделим исходное выражение по операторам до количества <1.
Наверняка, решение можно нагуглить, но мне нужны какие-то подсказки.
Есть арифметическое выражение из чисел и операторов.
Нужно вернуть все возможные уникальные результаты вычислений этого выражения после добавления скобок.
2-3*5/4 = x1
(2-3)*5/4 = x2
2-(3*5/4) = x3
((2-3)*5)/4 = x4
...
Не понимаю, как делать merge частей, если мы поделим исходное выражение по операторам до количества <1.
DP
Ребят, а можете подсказать какие-то идеи решения задачи ниже методом divide and conquer?
Наверняка, решение можно нагуглить, но мне нужны какие-то подсказки.
Есть арифметическое выражение из чисел и операторов.
Нужно вернуть все возможные уникальные результаты вычислений этого выражения после добавления скобок.
2-3*5/4 = x1
(2-3)*5/4 = x2
2-(3*5/4) = x3
((2-3)*5)/4 = x4
...
Не понимаю, как делать merge частей, если мы поделим исходное выражение по операторам до количества <1.
Наверняка, решение можно нагуглить, но мне нужны какие-то подсказки.
Есть арифметическое выражение из чисел и операторов.
Нужно вернуть все возможные уникальные результаты вычислений этого выражения после добавления скобок.
2-3*5/4 = x1
(2-3)*5/4 = x2
2-(3*5/4) = x3
((2-3)*5)/4 = x4
...
Не понимаю, как делать merge частей, если мы поделим исходное выражение по операторам до количества <1.
скобки могут менять только очередность операций
сделай функцию которая меняет очередность операций и игнорируй само понятие скобок
сделай функцию которая меняет очередность операций и игнорируй само понятие скобок
P
скобки могут менять только очередность операций
сделай функцию которая меняет очередность операций и игнорируй само понятие скобок
сделай функцию которая меняет очередность операций и игнорируй само понятие скобок
🤔🤔🤔
P
Интересно, не подумал. Спасибо
CD
Интересно, не подумал. Спасибо
Ты слышал что любое выражение это дерево?
P
Ты слышал что любое выражение это дерево?
+