Welcome all to Codeforces Beta Round #13, which will be held on Thursday, 6th of May at 18:00 MSK. I am an author of the problems.
I would like to thank Mike Mirzayanov who made this contest possible, Roman Iedemskyi and Andriy Maksay for helping to test authors solutions and Dmitry Matov for the translation of problem statements into English. Hope you will like the problems.
I hope that number 13 would be lucky for you!
UPD: Congratulations to Ivan Metelsky who became the winner, having solved all 5 tasks!
You can view the tasks here.
You can view the results here.
UPD2: I've added an editorial.
Some personal information:
I am a student of the first course of Kyiv National Taras Shevchenko University. I started training olympiad programming more or less seriously at the end of 10th grade (out of 11) after failing the national school olympiad and I don't want to give up now. After a year of practicing I've got gold on IOI 2009. Now I want to feel myself on the other side of barricades being an author instead of contestant. I'm glad to take part in the life of such a great resource as Codeforces.
You can discuss the problems here in the comments after the end of the contest.
Overall, the problems were nice. Thanks for the round!
I think (and this is a question to Mike) it would be nice to have a kind of standard for setting time limits at Codeforces. For example, time limit must be at least twice the running time of the reference solution implemented on the slowest available language (or something like this).
The slowest language here would be Ruby or Python (or maybe php?) - and they are pretty slow. 2x Ruby speed allowance might sometimes make slower C++ pass.
The slowest language here would be Ruby or Python (or maybe php?) - and they are pretty slow. 2x Ruby speed allowance might sometimes make slower C++ pass.
In this case, it would be nice to define the subset of allowed languages such that each problem is guaranteed to be solvable on each of these languages. Then the limit can be set based on the reference solution written on the slowest language from this subset. I'm not sure if it's a good idea to include only C/C++ in this subset.
Anyway, I don't really mind how the time limits are set. It just would be nice to have a common publically available standard to set them.
Ещё раз повторюсь, что в идеале надо так тщательно подгонять размер входных данных (или даже корректировать формулировку задачи!), чтобы алгоритм с плохой асимптотикой не проходил даже при сколь угодно хороших оптимизациях.
1
0 10 0 5
0 10 0 0
0 2 0 7
Rejudge will be dishonest.
So, ignore contest results?
F(position,value) - number of steps you need to do in order to obrain a non decreasing sequence starting at 1 and ending at position, when the number in position is equal to value.
F(1,value)=abs(a[1]-value), where a[1] is the initial value at first position.
F(P,V)=min(F(P-1,W<=V)+abs(V-a[P])) for P>1
The second key observation was that it is not optimal to change value of a[i] to value that hasn't been in the initial sequence. F(P,v1), F(P, v2), .. and so on can be computed in linear time by updating value of minimum on each step and the whole complexity is equal to O(N^2).
5 5 1
I've seen a similar problem at BOI'2004: http://www.boi2004.lv/Uzd_diena1.pdf (third problem). The main two differences: the limit on sequence length is 1000000, resulted sequence must be strictly increasing. I've been thinking for quite a lot on that problem and still don't have any working ideas. If anybody has clues on how it can be solved, could you please post.
This property leads to O(N^3) solution and this is the best I was able to come with so far. Of course, something much faster is required...
The ones on the left and the ones of the right of the fixed element.
- For example, If you consider the elements at the right of t[k]:
If you consider the vector c[i] = t[i+1] - t[i] - 1 for each . Increasing an element j by 1 implies increasing c[j-1] by one and decreasing c[j] by one (and the same thing happens when you decrease element j). You need to modify all values such that c[j] >= 0 subject to 'k' being fixed. You can compute this by means of DP considering k (the element you fix) goes from n-1 to 1.
You can compute the result by doing two passes one for the elements lying at the right and left of the fixed element.
I don't know if this is correct yet but I will try to explain myself later.
Thank you for the reference, even with google translator it was a very good source of learning. But I couldn`t find the specific article in the magazine page, if you know how to get it in PDF or something like please tell me or Maybe I`ll just e-mail Filip Wolski xD
My solution is same but getting WA in #6.
My solution is same as maksay described but getting WA.
F(P,V)=min(F(P-1,W<=V)+abs(V-a[P])) for P>1
What's W<=V ? What's W ?
I know this blog entry has been inactive for quite a long time. However, I recently heard there is an O(N log N) solution to problem C. Can anyone explain it?
EDIT: Here's a link: http://codeforces.me/blog/entry/18424#comment-234171