Today, 20:10 MSK
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Name |
---|
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.
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.