Opencup — Northern Grand Prix: Обсуждение задач

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

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

Предлагаю обсуждать здесь задачи; контест был очень интересным, думаю, у многих есть вопросы.

У кого-нибудь были проблемы с 8ым тестом в H? У нас какая-то мистика — WA8, но если мы добавляем чекер в наше решение, он падает на 4ом тесте. Неужели у жюри слабый чекер? ну или у нас руки совсем кривые

opencup, andrew stankevich, fun

ilyakor
9 лет назад
31

Комментарии (31)

Написать комментарий?

fetetriste

9 лет назад, # |

Прошлый раунд Снарк просил пока не обсуждать. Может быть, с этим так же?

→ Ответить

ilyakor

9 лет назад, # ^ |

← Rev. 4 →

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

Upd.

Снарк говорит, что можно обсуждать.

→ Ответить

abistrigova

9 лет назад, # |

Как решать E?

→ Ответить

ivan.popelyshev

9 лет назад, # ^ |

← Rev. 7 →

Пусть есть матрица с единицами. Возьмём главую диагональ, и умножим все её клетки на какое-то простое число. Сдвинем по циклу, умножим ещё раз, и так N раз.

2  3  5  7 11
11 2  3  5  7 
7 11  2  3  5
5  7 11  2  3
3  5  7 11  2

Если N нечетное то можно сделать такой же квадрат для побочной диагонали но с другими простыми числами.

13 17 19 23 29
17 19 23 29 13
19 23 29 13 17
23 29 13 17 19
29 13 17 19 23

Если перемножить квадраты то все числа будут разные, т.к. каждое число однозначно определяется двумя диагоналями на которых оно лежит.

Для чётных N так не выйдет, поэтому в первом квадрате я сдвигал нижнюю половину матрицы:

i<n/2 : j=i
i>=n/2 : j = n/2 + (i-n/2+1)%(n/2)
2   3  5  7 11 13
13  2  3  5  7 11
11 13  2  3  5  7
5  7  11 13  2  3
3  5  7  11 13  2
7  11 13  2  3  5

После этого клетка опять однозначно определялась по двум диагоналям, а значит все числа были разные.

→ Ответить

abistrigova

9 лет назад, # ^ |

Ясно, спасибо.

→ Ответить

Prestige

9 лет назад, # |

Как решать L and N див2. Не обессудьте)

→ Ответить

vas.and.tor

9 лет назад, # ^ |

Положим в мапу все цифры со значением 1. Потом (n - 1) раз сделаем следующее: вынем каждое число из мапы, умножим на каждую цифру и положим обратно. Потом пройдёмся по всем значениям в мапе, возведём в квадрат и прибавим к ответу.

Код

→ Ответить

Prestige

9 лет назад, # ^ |

А как пояснить что число различных произведений растет медленно или может это число можно формулой выразить?

→ Ответить

vas.and.tor

9 лет назад, # ^ |

Всего у нас миллиард различных чисел. Причём, перестановка цифр в числе не даёт нового произведения.

Очень-очень грубо получается что-то вроде: $\text{[math]}$ .

Но пока я не написал код, для меня это было неочевидно. Даже когда Lo_R_D предложил написать это в начале раунда, я убедил его что это порядка 10⁹ операций.

→ Ответить

vas.and.tor

9 лет назад, # ^ |

← Rev. 2 →

Вроде такое должно работать:

Пройдёмся массиву от B влево и будем поддерживать разность (количество чисел меньше B — количество чисел больше B). Затем пройдёмся от B вправо поддерживая ту же разность. На каждом элементе прибавим к ответу количество раз, которое текущая разность с противоположным знаком встретилась пока проходились влево.

UPDATE: Наконец таки появилась дорешка. Это решение зашло. Код.

→ Ответить

HellKitsune

9 лет назад, # |

В задаче D нет решения только когда все буквы одинаковые, или когда все разные, верно ли это?

→ Ответить

Kaban-5

9 лет назад, # ^ |

← Rev. 3 →

+13

Решения нет только в случае всех одинаковых букв.

UPD. Иначе возьмём обычную цепочку и двумя разными способами заменим одно ребро на цикл (например, для cтроки aabb автоматы будут aa*bb и aabb*).

→ Ответить

HellKitsune

9 лет назад, # ^ |

← Rev. 2 →

А можно тогда пример для abcd, если не трудно?

Upd: ясно, спасибо.

→ Ответить

Kaban-5

9 лет назад, # ^ |

← Rev. 2 →

1 -> 2, a
2 -> 2, b
2 -> 3, c
3 -> 4, d
4 - терминальная, в 5 приходит огромное число рёбер

1 -> 2, a
2 -> 3, b
3 -> 3, c
3 -> 4, d
4 - терминальная, в 5 приходит огромное число рёбер

Очевидно, автоматы ab*cd и abc*d.

→ Ответить

zeliboba

9 лет назад, # |

У нас тоже что-то неясное в H, но мы по ходу переполняем long long. Может вы тоже?

→ Ответить

ilyakor

9 лет назад, # ^ |

У нас biginteger, так что вряд ли.

→ Ответить

zeliboba

9 лет назад, # ^ |

← Rev. 3 →

Ну мы в общем застряли на 19м тесте еще на контесте, видимо дальше без длинки пролезть нельзя. А что там может быть помимо длинки не знаю.

UPD. Написал внутри решения жадность по выбору строки и столбца и зашло

→ Ответить

ilyakor

9 лет назад, # ^ |

Ну меня сильно смущает, что наш чекер не согласен с чекером жюри. А можешь выложить ваш код — может стресстест найдёт, в чём проблема?

→ Ответить

zeliboba

9 лет назад, # ^ |

https://ideone.com/mXgJCV

→ Ответить

AlexFetisov

9 лет назад, # |

← Rev. 2 →

А как решать А и J? Мы без монитора решали и почему-то по этим двум не было разумных идей. Сейчас смотрю на standings и кажется, что мы что-то упустили.

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

← Rev. 2 →

В задаче А весьма приятная геометрия — благодаря ограничению "никакие 3 точки не лежат на одной прямой" не вылазит никаких корнеркейсов. Фиксируем форт, для него сортируем все башни и дроны по углу, дальше два указателя. При фиксированном форте и фиксированной левой башне второй указатель говорит нам о том, где оканчивается валидный отрезок башен (т.е. какая последняя башня такая, что стена между этой башней и левой башней будет перед фортом, а не позади него), а количество подходящих пар "дрон-башня" на этом отрезке можно вычислять за О(1), если предварительно посчитать различные частичные суммы вроде числа башен на префиксе, числа дронов на префиксе, числа дронов перед башнями и т.д.

→ Ответить

AlexFetisov

9 лет назад, # ^ |

Да, вроде понятно. Спасибо! Вопрос по J еще открыт :)

→ Ответить

Sinner

9 лет назад, # ^ |

← Rev. 2 →

+10

Мы J не сдали, но есть следующая идея — не знаю верная или нет:

Что такое ответ для точки (x, y)? Это минимум из максимальных расстояний(под расстоянием понимается количество поворотов) для следующих случаев:

вначале мы движемся по строке x(горизонтально)
вначале мы движемся по столбцу y(вертикально)

Как найти необходимое количество поворотов, чтобы посетить все точки, если вначале двигаемся по строке x? Заметим, что за один ход мы можем дойти до любой точки, принадлежащей столбцам на отрезке [left[x], right[x]]. На следующем ходу можно дойти до любых точек строк из отрезка [up, down], где up и down — минимальный и максимальный номера среди строк, инцидентных текущим столбцам. Повторяем, чередуя строки и столбцы, до тех пор пока не окажется, что мы не посетили все столбцы или все строки. Количество итераций и будет ответом для строки x. Осталось обновить ответ для всех ячеек, принадлежащих строке x. Для поиска минимальной и максимальной инцидентной строки/столбца на отрезке можно выполнить предподсчёт.

→ Ответить

AlexFetisov

9 лет назад, # ^ |

← Rev. 2 →

Да похоже на правду.. Спасибо! Только там вроде максимум из минимальных расстояний.

→ Ответить

winger

9 лет назад, # |

У нас в дорешивании зашел код с чекером. Можешь показать ваш код?

→ Ответить

ilyakor

9 лет назад, # ^ |

Ну, если в нашем коде чекер срабатывает, а у жюри нет, это не значит, что правильное решение не зайдёт. Это скорее значит, что мы иногда выводим неправильный ответ, который принимается чекером жюри :)

Наш код: http://ideone.com/KzB2UD

→ Ответить

dragoon

9 лет назад, # |

How about the rest of the set? B/C/H/I? Also I was wondering if different teams have different solution to F?

→ Ответить

pavel.savchenkov

9 лет назад, # ^ |

The task is obviously redused to the following: we have some string S, how many ways to add x characters to it and get borderless word?

Let's calculate the same thing for not borderless words and then subtract it from 2^x.

To do it one can iterate over L — the minimal length of such suffix that corresponds prefix. Now we need to know that there will be no such suffix with less length -- it's exactly our initial task with less x.

→ Ответить