USACO December Contest - System Error (и обсуждение)

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

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

У кого-нибудь возникала ошибка System Error - Please contact contest administrator?

Что с этим делать? Обратиться к администратору (если да, то скажите как) или забить на это и просто решить и сдать задачи?

UPD. Участникам из Silver Division - в задаче umbrella зонтики могут пересекаться?

usaco, contest

valikluks1995
12 лет назад
14

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

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

aqua4

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

← Rev. 3 →

Я писал в пятницу, но возникалo только "Wrong answer on sample test" когда у меня на компе всё было правильно.

У меня тоже есть вопрос. Участникам из Silver Division - в задаче umbrella зонтики могут использоваться несколько раз?

→ Ответить

DaurenMuratov

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

Интересно, сейчас только у меня ничего не появляется после "Start the Contest!"?

→ Ответить

yeputons

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

У меня тоже.

→ Ответить

aqua4

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

Если кто-то решил задачу "photo" из Silver Division, можете объяснить задачу и решение?

→ Ответить

warrior_c

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

Я полагаю, что в бронзе была такая же. Как решал ее я (1 тест неправильный, ну думаю суть решения правильная). Нам даны 5 массивов, каждый из них образован таким действием: из первоначального массива i-ый элемент становится j-ым без нарушения, т.е. если представить как список, поменяется 3 указателя: у того, который был i-ым, который был j-ым. и у того, который стоял перед j-ым, для него теперь следующим элементом будет тот, который был для j-го. Также возможен вариант, что какой то из массивов совпадает с изначальным(который нужно найти), т.е. никто никуда не переходил. Как решать: не трудно догадаться, что если перед каким то элементом появлялся другой элемент только 1, 2 или 3 раза, то в этих 5-и массивах его потомком(следующим элементом) будет тот, который является следующим для него >= 2-ух раз. Например:

1 2 3 4 5 - изначальный

1) 1 3 2 4 5 - 3 на вторую позицию

2) 1 4 2 3 5 - 4 на вторую позицию

3) 1 5 2 3 4 - 5 на вторую позицию

4) 1 2 3 5 4 - 5 на четвертую позицию

5) 5 1 2 3 4 - 5 на первую позицию

2-ой 2 раза был потомком первого, значит в изначально массиве будет присутствовать кусок "...1 2..."

Что делать, если у какого-то элемента всегда разные потомки, т.е. перед ним вставали 4 или 5 раз другие коровы. Ответ прост и очевиден: хранить потомков второго поколения, очевидно, они и будут потомками этого элемента. (для последнего элемента будут >=2 раз потомком будет 0, т.е. если у какого то элемента >=2 потомком был 0, то этот элемент последний)

Почему это решение работает? Потому что каждый может только 1 раз перейти на новую позицию.

Какие могут быть подводные камни? Когда какой то из массивов и так уже изначальный. Тогда сначала можно просто проверить каждый массив на "изначальность", сделать это не трудно.

Но может быть такая ситуация:

1 2 3 4 6 5- 6-ой перешел влево

1 2 3 4 6 5 - 5-ый перешел вправо.

Здесь уже следует как то обработать это.

PS: я подозреваю, чо сейчас получу много минусов из-за того, что задачи были разные, просто названия увидел одинаковые, решил написать. Если что, извините.

→ Ответить

KADR

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

Зачем хранить каких-то потомков? Просто функции сортировки массива кормим свой компаратор, который для пары чисел смотрит, в каком порядке они чаще встречались на фотографиях. Это верно, потому что любые 2 коровы были в правильном относительном порядке как минимум на 3-х фотографиях из 5.

→ Ответить

warrior_c

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

Да, Вы правы, с оптимизацией мне надо поработать), но неужели это решение не правильно?

→ Ответить

KADR

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

Я не понимаю вашего решения. Ведь пара чисел идущих подряд в исходной последовательности может вообще ни разу не стоять подряд на фотографиях. Или же наоборот, стоять подряд 2 раза в неправильном порядке.

→ Ответить

warrior_c

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

Если нет повторяющейся цифры после какой-то более двух раз, мы обращаемся к потомкам второй степени. А чтобы 2 раза подряд была неправильная быть не может, т.к. каждая корова только по одному разу может переместиться.

→ Ответить

KADR

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

Почему не может? Вы же сами привели пример, где это возможно:

1 2 3 4 6 5 - 6-й перешел влево;

1 2 3 4 6 5 - 5-й перешел вправо.

→ Ответить

warrior_c

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

В своем решении я отдельно обрабатывал такие случаи) ну в общем, думаю нет смысла сейчас спорить, спасибо за Ваше решение, реализую, выложат тесты - протестю)

→ Ответить