Codeforces Beta Round #42 (Div. 2, Codeforces format)

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3611
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	Radewoosh	3415
8	Um_nik	3376
9	maroonrk	3361
10	XVIII	3345

№	Пользователь	Вклад
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

Добрый вечер

Вчера вечером делегация Саратовского университета вернулась из Питера, с полуфинала чемпионата мира по программированию ACM-ICPC NEERC 2010/11. Если кто-то еще не видел результаты: все 4 саратовские команды получили дипломы, а мы (Saratov SU 2) вышли в финал. Команда Saratov SU 1 тоже попала в число выходящих в финал, что довольно круто для их первого раза, но не едет из-за ограничения "одна команда на один университет".

А еще мы подготовили Div. 2 раунд. За оперативную помощь спасибо Эдварду Давтяну, Геральду Агапову и Марии Беловой.

Всем удачи!

Артем Рахов и команда Codeforces

К сожалению, было обнаружено несоответствие авторского решения и условия задачи E. Приносим свои извинения всем участникам соревнования. Все решения, не получившие Accepted ранее, были перетестированы. Спасибо участнику xcr за обнаружение проблемы.

6 896922 8 295 313 551 122 299 965 189 619 139 566 311 427 47 541 411 231 5 743 210 82 451 921 124 792 397 742 371 7 173 247 608 603 615 383 307 10 112 670 991 103 361 199 2 190 209 961 892 2 821 870 186 982 5 563 456 293 568 247 955 134 787 151 877

33 OWQWCKLLF OWQWCKLLF OWQWCKLLF PYPAS PYPAS PYPAS OWQWCKLLF PYPAS OWQWCKLLF PYPAS PYPAS OWQWCKLLF OWQWCKLLF OWQWCKLLF PYPAS OWQWCKLLF PYPAS PYPAS PYPAS PYPAS OWQWCKLLF PYPAS PYPAS OWQWCKLLF OWQWCKLLF PYPAS OWQWCKLLF OWQWCKLLF PYPAS PYPAS OWQWCKLLF PYPAS PYPAS

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

Показать архивные | Написать комментарий?

okulov

15 лет назад, скрыть # |

→ Ответить

Rubanenko

GL&HF^^

Snipx

Что значит отказ тестирования?

MikeMirzayanov

15 лет назад, скрыть # ^ |

Уже исправлено :)

havi	15 лет назад, скрыть # \| 0 что значит ошибка представления?... → Ответить

Вероятно вы вывели лишние данные или вывели строку, хотя ожидалось число. Возможно, вы вывели недостаточное количество данных.

72VanVector_SevNTU

Касательно задачи С вопрос:

Будут ли билеты, склееные из кусков (например) (123 + 321) и (12 + 3321), считаться разными билетами??

RAD	15 лет назад, скрыть # ^ \| 0 Да, номера получившихся билетов могут совпадать. → Ответить

Сори

(перечитал условие)

---Grigor---

А разве можно взламывать решения участников, которые участвуют вне конкурса ?

AndreySiunov

← Rev. 2 →

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

SergeyLazarev

-7

Спасибо авторам за задачу D. Давно я так не веселился:)

caustique

Из-за чего веселье? Мне вот совсем не весело - меня по ней взломали.

Можешь подсказать, в чем угловой случай состоит?

ballon

1 2

У меня правильно обрабатывает этот случай. Проверил все маленькие тесты - не нашел баги.

Я даже забеспокоился, вдруг мой вывод 10000 чисел через System.out.println() медленно работает.

Вообще, в моем решении было 3 случая.

if (n % 2 == 1 && m % 2 == 1) {

строим один телепорт

идем змейкой до (n, m)

} else if (n % 2 == 0) {

идем по вертикали - потом змейкой

} else {

идем по горизонтали - потом змейкой

В чем я неправ?

}

Нашел ошибку, отменяется вопрос.

Если n=1 и m>2 и m%2=0, то телепорт строить все равно надо, хоть одно из чисел и четное.

Vaness

У меня такие случаи обрабатываются отдельно, но мое решение все равно завалили, хотя оно полностью идентично решению caustiQue. Печально.

Увидел пост ниже. Вопрос исчерпан.

bubnov

Меня взломали на таком - 2 1 (ну или 1 2)

Выдать нужно

1 1

2 1

А у меня телепорт строился =) Но я быстро исправился.

Один из случаев - это 1 2 или 2 1. Очень многие считали, что если одна из размерностей равна 1, то телепорт обязательно нужен. Это верно только если вторая размерность больше 2.

Salat

черт=) все ща снимут значит...

ant.ermilov

Действительно, фантастика, я считал, что моё решение неверное с первого взлома и до конца контеста.

Теперь дошли руки проверить и оказалось, что эти угловые случаи обрабатываются...

pkhaustov

Спасибо авторам за контест.

Задача D мне ужасно не понравилась. Тупо всех ловили на частных случаях. Не самая достойная задача для D на соревнованиях такого типа. Хотя на ACM такое бы сошло на ура.

Можно пожалуйста претест 4 к задаче Е?

Nyatl

Мне не понравилось то, что если я решу за час все задачи, я не могу уйти. Я должен всё оставшиеся время сидеть, нажимать "F5" и высматривать новые посылки. На минуту отвлёкся - 300 очков потерял, например.

На TC такого нет: 30 минут покодил, ушёл, вернулся, почеленжил минут 5, ушёл.

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

hydrastuff

извини, но в первом дивизионе такого скорее всего не будет)

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

Контест за деньги, что за чушь?

что-нибудь вроде Codeforces World Finals 2014

Пиши чисто, и твой результат не будет зависеть от времени сдачи другими участниками. Что вобщем-то выполняется и в ТС.

gen	15 лет назад, скрыть # ^ \| 0 Если бы я всегда мог решать за час все задачи, я бы был счастлив. Ну а вообще что поделать, таков формат, человеку нравится — участвует, не нравится — не участвует. По крайней мере так обычно происходит. → Ответить

muriloufg

Someone can paste the Pretest #6 for the problem D?

I can't figure what is the problem with my solution...

slycelote

Try 1 2 and 1 4

flashmt

He means pretest?
1 2 and 1 4 are used for hack.

Ah, yeah, sorry

У меня бага в 1 4 оказалась. Айайай как обидно, что во время контеста не догадался его вбить.

L.I.S.

задача Е решается инверсиями?

На трассе будет всего NK событий. Делаешь массив событий, сортируешь хронологически, а дальше решение в целых.

AlexErofeev

Можно про решение в целых немного поподробнее?

Все свои решения описал в разборе.

http://mirror.codeforces.com/blog/entry/905

Постарался объяснить задачу E как можно более подробно.

/ a.out

./a.out

1 4

1 4 1 1

1 3

Try these tests: 4 4 , 4 5 , 5 4 , 5 5 (all the rest cases).

P___	15 лет назад, скрыть # \| ← Rev. 2 → 0 I wonder if it wouldn't be better to have a possibility to lock the problem and start hacking without passing pretests, even without submiting it. → Ответить

OleGG

I think it wouldn't be better, because in your case contestant can use 2 accounts: one for stealing solutions from another, second - for submitting stolen solutions. Now for getting solutions from competitors, even cheater have to write solution which passes pretests

MciprianM

How do I prove for problem D that when both n and m are odd, we can't find a required path without using teleporting gates?

Well, let's look at board painting. Every turn we change color of cell, in which king stays. So, for odd n and m cell at n*m turn will be black. n*m+1 turn must follow us to (1,1), which is also black. So we're used to place at least one gate.

roll_no_1

8 лет назад, скрыть # ^ |

In the above comment, the board painting refers to visualizing the board as a chess board with the cell at (1, 1) being colored black.

tarbaytas

6 лет назад, скрыть # ^ |

Another way to prove this is by noting that the graph is bipartite.

slavik

Не могли бы вы подсказать тест 8 задачи E и тест 11 задачи D?

RAD

Тест 8 в E:

Тест 11 задачи D:

1 100

Abra	15 лет назад, скрыть # \| 0 Give me 23 test for E, please → Ответить

RAD	15 лет назад, скрыть # ^ \| +2 Big random test with 99 cars, and 100 segments for each car. → Ответить

Abra	15 лет назад, скрыть # ^ \| 0 thanks → Ответить

ondrah

What's final test 25 at problem D? Thanks..

Hedayet

← Rev. 8 →

I don't know. But I can assure you that if your code passes the following types of inputs, it should pass all the inputs,
odd even
even odd
even even
odd odd
1 2
2 1
thanks to HackSon.

Hackson

I think "1 even" and "even 1" are not precise enough...

1 M

N 1

where N, M > 2.

it's unnecessary to check "1 M" and "N 1" when N or M odd since it same as "odd odd"

I have it done more complicately, so it's giving me Time exceeded.. but i think it should handle it for every 1<=n, m<=100

RAD	15 лет назад, скрыть # ^ \| 0 99 99 → Ответить

Deamon

Сижу ломаю голову над А. Можно 15 тест?

Hapuk

и 30 тест пожалуйста!

RAD	15 лет назад, скрыть # ^ \| 0 99 голов, из которых 49 забила одна команда. → Ответить

Нда... Пора делать перерыв) Спасибо

Можно 6 тест в задаче С?

никак не пойму.

RAD	15 лет назад, скрыть # ^ \| 0 6 94861402 89285133 30745405 41537407 90189008 83594323 ответ: 1 → Ответить

astrovsky

я чего-то непойму почему в задаче С во 2 примере ответ 1?

Там ведь можно собрать 123 231 1023 2310. Или я ошибаюсь?

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

спасибо за объяснение.

Zhandos

Будет ли опубликован разбор задач?

iman_MC

Hi to codeforces team

why you don't put test case's and problem's(in PDF) after each contest ?

it's usefull for every one ....

thanks for attention

PAG	15 лет назад, скрыть # \| 0 И всё-таки какой тест №6 в задаче D? → Ответить

trulo_17

Congrats on making into the finals!! 9 Problems done, that is pretty impresive.

Today I participated "out of competition". I have 2 questions:

-My solution got hacked by another div1 contestant. So....does this mean I'm able to hack any other div1 competitors? Cause I didn't see any one in my "room".

-Am I able to see the case that got me hacked during competition?

Thx in advance

To see other "out of competition" contestants in your room you should check box, that doing it (in top right corner).

Hack protocols availible at "Hacks" tab by link in "Verdict" column.

If you participate 'out of competition', then when you enter the contest you appear in room number 1 instead of the room you were assigned to. (It's a bug.) To move into your room, select it from listbox in top right corner, it's marked with a star.

hungamaboy

Can anyone explain me problem C, I couldn't program it and ended up getting -2, how about a contest analysis after every contest?

Let C[i] = # of integers in A_1...A_Ns.t. A_k = i (mod 3)

Then answer = C[0]/2 + min(C[1], C[2])

P___	15 лет назад, скрыть # ^ \| +1 Previous explanation is for problem B. As regards C you just have to pair numbers a, b when: a % 3 = b % 3 = 0 or a % 3 = 1 and b % 3 = 2. In such cases (a + b) % 3 = 0. → Ответить

Akramjon

Не могли бы вы подсказать тест #9 задачи D???????

xcr	15 лет назад, скрыть # \| +8 Не все "полные решения" по задаче E проходят следующий тест: 2 5 3 2 1 1 1 2 1 3 1 1 2 1 1 2 Правильный ответ - 0. Некоторые решения выдают 1 Тест корректный? → Ответить

yeputons

Да, корректный.

xcr	15 лет назад, скрыть # ^ \| 0 Да, мы уже достаточно коллективно с этим согласились. Если считать, что на такой тест правильный ответ - 0, то решение получает WA23. То же решение с 1-кой по такому тесту у меня получило Accepted → Ответить

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

daftcoder

-6

Ждём раунд 43.

maksay

Несколько странно, что проходило решение D за L*N*(b+f), при чем за 50мс..

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