В четверг, 15 апреля, в 19:45 по московскому времени состоялся Codeforces Beta Round #10. В этот раз автором задач для контеста выступаю я. Хочется поблагодарить создателя Codeforces Михаила Мирзаянова за корректировку условий и Юлию Сатушину за отличный перевод задач на английский.
Сразу хочется извиниться за задачу D, потому как уж точно в моем авторском решении был баг. Более того, возможно, что эта задача вообще неразрешима за полиномиальное время даже при небольшом диапазоне чисел [0.255]. Хотя мне так не казалось:))) Надеюсь, что при любом итоге исследования этой задачи никто сильно не обидится.
UPD: Я уверился в палености своего рещения по D. Еще раз приношу свои извинения. Как сказал бы председатель жюри KPI-Open, задача получилось "с хитринкой", то бишь кривая. Никакого перетестирования решений, сданных на контесте, не будет. Задача будет изменена таким образом, чтобы в ней требовалось найти НОВП для двух последовательностей. Для такой задачи уж точно решение существует.
UPD: Задача D изменена так, как я до этого обещал.
Сразу хочется извиниться за задачу D, потому как уж точно в моем авторском решении был баг. Более того, возможно, что эта задача вообще неразрешима за полиномиальное время даже при небольшом диапазоне чисел [0.255]. Хотя мне так не казалось:))) Надеюсь, что при любом итоге исследования этой задачи никто сильно не обидится.
UPD: Я уверился в палености своего рещения по D. Еще раз приношу свои извинения. Как сказал бы председатель жюри KPI-Open, задача получилось "с хитринкой", то бишь кривая. Никакого перетестирования решений, сданных на контесте, не будет. Задача будет изменена таким образом, чтобы в ней требовалось найти НОВП для двух последовательностей. Для такой задачи уж точно решение существует.
UPD: Задача D изменена так, как я до этого обещал.
А возможно ли сделать чтение или с stdin или c input.txt и писать в stdout или в stdout?
Просто при тестировании, каждый раз вбивать тесты неудобно в консоль, а если забудешь убрать чтение с файла, то выдает РЕ.
#ifndef _DEBUG
freopen("input.txt", "r", stdin);
#endif
на компе у себя запускаешь как правило в дебаге, а на сервере выполняется всегда релиз. так что такое условие можно использовать почти везде
На сервере определена константа ONLINE_JUDJE ЧТО можно испольховать для не открывания файлов в на сервере и открывания на локальном компе. Кроме того в той теме люди предложли еще несколько вариантов.
Проэкт - Свойства - Свойства конфигурации - Отладка - Командные аргументы - "< input.txt"
Наслаждайся. =)
В какой теме? Не могли бы дать ссылочку, я бы прочитал и не парил мозги людям.
я решил что ее просто найти через мой блог.
No need to thank me for each contest. Frankly speaking, I feel embarassed, and... ashamed for the comment I made some days ago (hope, you know what I'm speaking about). Forgot to ask you earlier not to mention me. Moreover, one of the translations is yours))
We'll see how good the translations are during/after the contest ;-)
From the bottom of my heart I wish you all the best! It is such a difficult think to make a contest (now I know this for sure). So, you deserve only the best))
Thank you! =)
Forgot to say – it’s a difficult thing to make a contest, but it’s even more difficult to reconcile with the idea that you have to miss the contest and lose rating points… :-( For a programmer like you it’s hard… So, good luck one more time))
Кажись очепятка в задаче A:
"Через T1 минут после того, как Вася с последний"
Лучше не задавать длинных вопросов ;) .
For a slightly more objective assessment, it might be interesting to calculate the percentage of Russians amongst those who solved the problem, and compare that to the percentage of Russians in the competition.
Maybe the version you read was the Russian one?
Надо перенести в раздел "Смешное на контестах".И что ты хочешь сделать с тренером? Купить, арендовать, нанять или ещё что-нибудь?
Иначе потенциальному тренеру будет как-то странно — неизвестен ни уровень, ни опыт участия в олимпиадах, вообще ничего. Даже не прочитать ни одной строчки твоего кода. А вдруг ты на самом деле Петя Митричев или Гена Короткевич? Или пишешь принципиально только на INTERCAL-е? Тогда круг возможных тренеров резко сужается ;) .
For each pair <V, L> you save all ordered sets of n numbers such that you can find the common subsequence of length L that finishes in the positions from ordered set and has length L. Whenever you add new ordered set, you chould check if there exists a set that has the following properties:
1) For each sequence a corresponding number in it for this set is begger than in new set
2) Length for this set is less or equal to length of sequence ending in the new set
Every such set you should delete. Some other small optimisations are also requred.
The rest is just loop through all pairs<V,d> and all corresponding sets.
You can see my code in upsolving. Sorry in my English is not understandable enough
http://graal.ens-lyon.fr/~yrobert/algo/coins2.ps
Once I've heard some lecture where some guy was talking about a criteria
to check whether a knapsack problem is greedy solvable. I thought maybe this problem
is also has a known solution, so I went straight to google and started to search. And after
some time I've found this.
Hints are:
Full solution is:
And, if you can, leave feedback for my mistakes in English. :)
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.2394&rep=rep1&type=pdf
Personally, I thought the idea was to find this article, read it and implement during the contest.
Can somebody please write a tutorial for the updated D problem :)
In case of problem C, for N=4 why (1,2,2) and (2,1,1) is not among expected pairs?
Can someone tell me how to solve E?
Can Someone tell me how to solve problem D ?
we need to build a graph over the elements after co-ordinate compression, consider two elements i,j if i is present before j in both sequences and i<j then we add a directed edge from i to j , now the answer is to find the longest path in a directed acyclic graph
Editorial ?
No.