| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
Добро пожаловать на Codeforces Beta Round #18
Авторы задач сегодняшнего контеста: Михаил Мирзаянов, Эдвард Давтян и я. Спасибо Дмитрию Матову за помощь в подготовке условий и Юлии Сатушиной за перевод задач на английский язык.
Всем удачи!
Заслал на Java. Полное решение 660 мс 41436 Кб
I like them all.. :)
Well, when will the tutorial of this round
announced?
Problem A - Geometry with *many* possible solutions including Pythagoras's Theorem, checking for perpendicular line segments, using trigonometry to test angles...
Problem B - Simulation, with modular arithmetic to speed things up
Problem C - If you keep track of the sum to the right of a point, and the sum to the left of a point, you can compute the new left-hand and right-hand sums by just subtracting one number from one sum, and adding it to the other. In this way, you can try all possible cuts in O(n)
Problem D - This can be done as a Weighted Interval Scheduling DP, though as a friend pointed out, 2^x > 2^(x-1) + 2^(x-2) + ... + 2^0, so you can just take the largest intervals first, greedily, because they will be worth more than all other intervals that they conflict with.
Problem E - Row by Row DP. Determine all possible chequerings for one row, and get the cost of using that chequering (which can be done in constant time, not O(n)!). Then for the next row, try all possible chequerings and see which ones are compatible with the row above. Take the minimum cost of these. This is ~650x650x500 which is just a *bit* too slow. But if you sort the results of the previous row by cost, you can get an answer closer to 650*500.
because testdata are hidden..
example(as suggested by RAD)
0 0 1 0 4 1
Thanks RAD
like 0 0 0 1 0 3
I pass #31 test when add checking the S of triangle
I'm a rookie about algorithm, i just interested in the Weighted Interval Scheduling DP method, can somebody offer me more information about that? thx a lot! :)
There's also an O(n log n) algorithm, but it's a bit more complicated: http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec3.pdf
The UVa online judge has a list of Dynamic Programming problems: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114
I can't recall any UVa problems that are Weighted Interval Scheduling though... but solving DP problems will help you with other DP problems because they all have important similarities.
thank you so much!
i never expect somebody may answer such a primary question so detailed!
thank you very much!
I have never heard of Weighted Interval Scheduling DP before. Thanks for sharing your resource. You sir, are awesome! :D
Here, I found another source:
www.cs.cornell.edu/courses/cs482/2007su/dynamic.pdf
This contains both N^2 and NlogN idea.
Как работать с длинной арифметикой, в задаче D, например? Разрешается ли пользоваться заготовленным кодом?
Я считаю, что заготовки нельзя использовать и разрешать (конечно нельзя отследить никак, но все же), так как таким образом человек может просто скопипастить любой стандартный алгоритм.
Так что задачи на длинную арифметику - абсолютное зло
Что собственно все и делают, потому что это нормально.
Идиотизм-то как раз таки по 200 раз писать один и тот же алгоритм.
Например я давно для себя сделал штучку типа skidanovalex.ru/ahelper.html, чтобы не зависимо от того, откуда я пишу, все нужные алгоритмы были со мной :о)
"I'm a computer programmer. I like coding a lot, and not so long ago I was one of the best tough-algorithms coder in the world.
Here's the list of my selected achievements. Some of the scoreboards..."
Русская версия - Если в двух словах - я программист и металлюга :о)
И дальше по тексту... :)
у кого нибудь в задаче Д были проблемы с 4-м тестом?
можете привести контрпример или вспомнить в чем была ошибка?
не понял?
идею сюда написать? или имеете в виду что я не отправлял решения?
ЗЫ если второе то будьте внимательнее у меня и во время и после контеста есть отправленные решения
Участники должны быть в равных условиях. Видимо, это означает, что единственно верный вывод - разрешить любые заготовки. Кроме всего прочего, это более естественно.
I have a question though. How am I supposed to include the BigInt class in my solution? I'm writing in C#.
Thanks!
and is it enough to hold 2^2000?
In .NET 4.0:
using System.Numerics;
BigInteger a;
Then you can use it as a regular integer number. All the operators are overloaded, so you can easily do something like that:
BigInteger a = BigInteger.Parse( Console.ReadLine( ) );
BigInteger b = BigInteger.Parse( Console.ReadLine( ) );
BigInteger c = a + b;
But AFAIR this server doesn't support .NET 4.0, so anyway you will need to implement big integers by hands if you want to solve that problem using C#.
2) что за 16-й тест ? :)