Всем привет!
Новый, 79, раунд представляю вам я, Валерий Самойлов, выпускник СПбГУ. Сегодня вы познакомитесь с мальчиком Геральдом и поможете ему с честью выйти из самых разных жизненных ситуаций.
В обоих дивизионах разбалловка обычная: 500 - 1000 - 1500 - 2000 - 2500
Это мой первой codeforces раунд, надеюсь, задачи вам понравятся и их будет приятно решать.
Большое спасибо Артёму Рахову (RAD) за помощь в подготовке задач, Макару Краснопёрову (Connector) за несколько ценных советов, ну и, конечно, Марии Беловой за перевод.
Желаю удачи участникам обоих дивизионов!
Контест завершён, поздравляем победителей!
Дивизион 1:
1. RAVEman
2. ilyakor
3. ACRush
Дивизион 2:
1. SuperLight
2. xiaowuc1
Появился разбор задач.
Ваш Кэп.
У меня у одного CF так тормозит? Грузит страницы доолго и раза со 2го или 3го только. С другими сайтами нет таких проблем. Браузер Firefox.
Чудеса... Сейчас для прикола поставил Chrome, абсолютно те же глюки. Аватарки почти не грузятся, и страницы открываются раза со 2го-3го. Даже залогиниться не получилось в течении 10 минут (ибо Firefox перепосылает данные при обновлении, а вот Chrome, видимо, нет).
Значит все-таки я не один такой
Задача E была сделана по мотивам задачи F из SNWS-2011, Round 4?
Или это просто совпадение? :)
Nice contest. :)
What is the complexity of the intended solution for problem D div 2? O(m) ? O(m*log(m))?
I tried to implement a O(m) algorithm, but maybe there is a simpler one in O(m*log(m))?
Any help appreciated!
The main idea is:
If not, it's really weird. A lot of AC solution have complexity O(m log(m))...
Besides, I'm not a big fan of Java, but if it passes arrays around by copy, that's a huge overhead that you are not using class variables for the arrays...
Regarding java, I don't think it passes a new copy of the array. for objects more than the primitive data types, it passes the object as a pointer to the same memory location.
Call num[t] = number of ways from the position t (a bus stop or the value 0).
num[max_t] = 1 and the result to return is num[0].
the update rule at time t is:
num[t] = c*num[next_t]
where t is a bus final stop, and next_t is the next position where a bus stops.
and c is either r or r+1
with r = number of buses that start before or at t, and stop at exactly next_t.
c = r+1 if there is a bus that starts before or at t, and stops strictly after next_t,
c = r otherwise.
I see how to get the value r in O(log m),
but to determine efficiently whether c should be r or r+1, I'm at a loss.
Anyone knows? Or is there a simpler way to look at it?
Thanks for your help.
With that definition, num[0] = 1, obviously, and to compute num[t] for increasing values of t, we can do:
for each bus starting at s and ending t:
for s <= i < t:
add num[i] to num[t]
Of course, we must first compress the coordinates into a range O(M) so our num array is small enough. Additionally, to avoid an O(M) inner loop, we can keep track of the accumulated sum of num[0..i]; with that, we can compute sums of num[i..j] efficiently too.
If you can read C++, my commented solution shows the details.
By the way: don't feel too bad about not being able to solve this one. I thought it was a pretty hard problem, despite its point value. I'm rated red here, but I could not figure this out to save my life during the contest!
It's tricky to adapt the outer loop to include the computation of num[0..i] from num[0..i-1] in O(1).
- Можем прибавлять вектор C, повернутый на 90, 180 и 270 градусов
- В конце можем повернуть на 90 градусов несколько ра
А далее перебираем, сколько раз в конце повернули. После этого остаётся представить вектор B-A в виде суммы C и ортогонального ему. Можно разложить по координатам и проверить, что они получились целые (разумеется, не надо считать в даблах, а просто проверить, что делится).Еще есть случай, когда C равно нулю (чтобы не случилось делений).
Мой вариант - рассматриваю 4 случая (4 поворота вектора A). Решаю систему уравнений с двумя неизвестнымиxa+yb=x'
ya-xb=y'
x, y - координата x и y вектора С. x' y' - разница между вектором B и повёрнутым вектором A. Если b и a (неизвестные) получаются целыми - выводим YES. По сути своей система уравнений - попытка составить вектор B-A из сложенных векторов C и C, повёрнутого на 90 градусов (отрицательные a и b - значит вектор С стоило повернуть на 180 и 270 градусов). Отдельно случаи, когда координата(-ы) вектора C == 0
Косяк, то же самое, не сразу понял :)
This is convenient, because we can just try the four possible rotations of A and subtract them from B. Then the question becomes if we can express the resulting vector with integer coordinates in an orthogonal system with C and its rotation as axes.
So after we compute D = (B - roti(A)) for i={0,1,2,3} we want to check if there are integers x and y such that x*C + y*rot(C)=D. Since C and rot(C) are orthogonal, we can decompose D into independent components using scalar projection, and from there we can compute the value of x (or, in this case, just check if its integral). For example, x is integral iff C·D = 0 mod |C|2, where · is the dot product.
A different approach for the last part is to write the equation x*C + y*rot(C)=D as a system of linear equations (C, rot(C) and D are all known) and solve that using Gauss-Jordan elimination. This is a bit more work if you don't have code prepared for this, but requires less thinking if you do.
Жаль, упала E-div2 из за пропущенной проверки при C = (0, 0) ...
Как доказать, не знаю. Понятно, что примерно как-то так, но я сомневался, что надо брать полное время обхода, а не среднее время, если клад там. Хотя не исключено, что правильно и так, и так.
А если не секрет - когда и с чем это связано?
В итоге вместо занятого 175-ого места, я "занял" 213-ое, если судить по графику. Мягко говоря, обидно.
it should be %I64d instead in this contest ?
Both POSIX and ANSI C allow ll as a size prefix, but Microsoft doesn't implement either standard.
If GCC on Windows calls the printf() implementation in Microsoft's C library, then it probably behaves incorrectly too. The fact that it works on Linux is not thanks to GCC, but thanks to the GNU C library.
I think so. Let me check again.
Yes, I'm 100% sure. Why do you ask?
A little bit more seriously (sorry): My intention was to protect the poor twits who first click without understanding the text, and then think and use Google Tranlate.
I wish we were able to flag posts as spam, in addition to negative votes. Where is the right place to request the feature? :)
I don't think there are much people on this site that click on every link they see without understanding it.
Я, например, в начале каждого контеста все равно туда перехожу