Today, 20:10 MSK
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
How to solve 500?
Динамика. Прошли i рек, оказались на такой высоте. Переходы либо на 1 вверх по суше, либо по морю. Это какой-то len^2*m. Осталось заметить, что работают два указателя, потому-что что-то выпукло куда-то.
Вечный вопрос: а как заметить что "что-то выпукло куда-то"?
Ну это же корень. Он всегда выпуклый. Дальше надо пописать какие-то оценки и увидеть, что если нам сейчас выгодно опуститься на 1, то в прошлый раз это было еще выгоднее. А еще почему эти коментарии на английском? Пошли в другую ветку.
Мое решение на чем сломал? TL?
Да. Просто вбил большой случайный тест. С учетом того что тернарник казалось бы вообще не работает, на чем-то бы свалилось.
// эта ветка — английская.
Сразу скажу, что сам не успел дописать задачу.
Я заметил это так: нарисовал карту, хочу пройти в точку (x, y) из (x - 1, 0). Тогда я могу в неё попасть тремя способами: пройти по острову x - 1 расстояние y, затем по воде (получается перпендикулярно) расстояние width[x - 1], пройти по воде перпендикулярно расстояние width[x - 1], потом по острову x расстояние y, причём эти два значения будут равны (думаю, что это очевидно), либо пройти по "гипотенузе" расстояние
. А потом вспоминаем, что в прямоугольном треугольнике длина гипотенузы всегда меньше суммы длин катетов, ну и интуитивно понимаем аналогию.
P.S. Понимаю, что сказал полный бред, но это были всего лишь мои мысли :)
Alternative solution. At first assume we got from 0, 0 to sumWidths, 0. Take this time as an answer. Then length times do following — increase difference between indices of source and destiantion ports on some river (or walk 1 segment anywhere). Choose river where such operation would lead to smallest increase of answer. Notice that for this river next increase would be bigger, so our algorithm is correct
А еще оказывается работает решение добавить подъем на 1 там где он меньше всего нагадит length раз. Видимо опять таки из за того что корень — очень хорошая функция.
Если быть точным, то потому, что в каждой реке это число увеличивается после операции
А почему из того, что для каждой речки это число увеличивается, следует, что такая стратегия оптимальна?
Потому, что мы тогда возьмем length самых маленьких чисел
Спасибо, понятно
Another alternate solution. This problem is equivalent to knapsack problem (we want to take L meters up). So we have width.size() + 1 of objects, width.size() of there is rivers and one is the object that correspond to moving up (his width is 0, and his speed is walk). So we can proof that it's possible to solve this problem in such way: For all objects put into array L values timeToGo(width, Y+1, speed) — timeToGo(width, Y, speed) (1 <= Y < L), than sort this values, and sum first L values from array.
So this sum is the answer to the problem without sum for all rivers timeToGo(width, 0, speed).
timeToGo(w, y, s) = sqrt(w*w + y*y) / s.
ну я и весельчак, написал решение 500 для непрерывного случая и вспомнил условие за 5 минут до конца.
как решать?)
UPD непрерывный = лодку можно брать в любой точке острова
UPD2 вопрос уже неактуален
А как именно надо писать 2 указателя в 500-ке? Я весь контест провозился, так и не заработало.
посмотрите решение 250-ки пользователя xOberon и результаты челенжей
Что за дурацкое 4 * 109?
райтер тонко троллит контестантов :)
Тролль 80-го левела
90-го левела... на java в 500 троичный поиск не проходит раза в 3 по времени, а на С — проходит (-челлендж); зато я придумал чит, после которого троичный поиск на java работает 1.1 секунду и проходит все тесты (хотя возможно, существует тест против него) — см. practice room :)
Ну это смотря как его писать. Я зачелленджил троичный поиск, написанный на C++.
Попробуй в practice room зачелленджить мой на java. Наверняка ж тест против него есть :)
Да может это и правильно для данных ограничений.
Ещё и Passed System Tests.
А чего оно так быстро работает на интах? Это фейл авторов, можно было и до 10^18 чиселки дать
Из-за чего оно прошло систесты?
Потому что числа 32-битные, язык C++, компьютеры мощные, а автор, как кто-то уже подметил, тролль 80 левела.
Вот кстати перед тем как челленджить, неплохо смотреть History :)
My solution (Java) with 1 * n * length sqrt calculations works appr. 2 seconds and was challenged (got TL). I suppose it would get AC written in c++. The question is, how to avoid such number of sqrt's? Am i missing something?
UPD. It got TL as I forgot to cast width[i] * width[i] so there was an overflow, and NaN values produced time limit on max test. With cast it works about 300ms, which is totally comrehensible.
Egor's solution requires only O(n + length) square root calculations for example.
Yes, and that solution is great. Mine dealt with two pointers, and I already found a couple of java solutions with almost the same code which passed systest, so anyway it's my fault.
Что теперь можно не боятся что 10^9 не уложится в 1 сек?
Да и раньше вроде укладывались. Это же TC.
Но не 4·109 же
Но не в секунду же? :) Тем более совсем простые операции
там TL = 2 секунды
Ну из того, что 109 × C < 1 не следует, что 4 × 109 × C > 2.
И всё это неплохо подтверждается на практике.
Напишите как решать 250
http://codeforces.me/blog/entry/411#comment-5627
а можно объяснить, с каких соображений береться мод 4?магические свойства четверки
Покажем, что xor всех чисел от 0 до 4k-1 равен 0. При k=0 это верно. Теперь посмотрим внимательно на 4 следующих числа: *00 *01 *10 *11 Нужно xor всех предыдущих чисел (т.е. 0), проксорить с этими 4-мя числами. Видно, что т.к. часть * одинакова, xor снова окажется нулевым.