Всем привет.
8 и 9 декабря в Саратовской области пройдет муниципальный этап Всероссийской олимпиады по информатике. Мы решили, что будет интересно, если задачи с олимпиады будут решать не только саратовские школьники, но и все желающие. Поэтому я рад сообщить, что в ближайшие выходные состоятся сразу два раунда для участников второго дивизиона (олимпиада проходит в два тура, поэтому и раундов будет два).
Первый из раундов — Codeforces Round #154 (Div. 2) — состоится 8 декабря в 14:00 MSK.
Второй — Codeforces Round #155 (Div. 2) — пройдет 9 декабря в 14:00 MSK.
Это будут обычные раунды по правилам Codeforces, но с одной особенностью:
Ввод-вывод во всех задачах будет файловый: чтение нужно осуществлять из файла input.txt, а выводить в файл output.txt.
Разбалловка будет объявлена незадолго до начала каждого из раундов.
Участники из первого дивизиона, как обычно, могут поучаствовать вне конкурса.
UPD По ссылкам содержатся примеры решений с файловым вводом-выводом для некоторых языков:
- C++: 2366378
- Pascal: 2454867
- Java: 2366738
- Python: 2387503
- D: 2436251
- Scala: 2385341
- Haskell: 2378010
- C: 2519130
- Ruby: 2375494
- PHP: 2381582
- C# 2716641
UPD2 Разбалловка в 155-м раунде будет стандартной: 500-1000-1500-2000-2500.
UPD3 Появился разбор задач раунда 154.
UPD4 К сожалению, в первой половине контеста было обнаружено, что чекер по задаче C не проверяет лексикографическую минимальность выведенного участником ответа. Мы приносим свои извинения за эту ошибку. Поправив чекер, мы провели расследование и обнаружили, что изменение чекера повлияло на 53 участников из второго дивизиона. Мы считаем, что справедливо будет сделать данное соревнование для таких участников нерейтинговым. На всех остальных участников эта неточность никак не повлияла.
UPD5 Появился разбор задач раунда 155, уже на русском:)).
По поводу файлового ввода-вывода. У многих кто пишет на C# возникают с этим проблемы. Например недавний контест: http://mirror.codeforces.com/contest/234/status. Достаточно выбрать в фильтре: Любая задача, Любой вердикт, C#. Решена ли эта проблема? Если нет, то будет ли она решена? Или придётся опять перестраиваться на лругой язык? Спасибо.
Проблема в использовании Console.SetIn() и Console.SetOut(). Попробуйте открывать файлы без перезаписывания стандартных потоков, вроде бы все будет работать нормально.
http://mirror.codeforces.com/contest/234/submission/2364370 http://mirror.codeforces.com/contest/234/submission/2365483 Вот парочка решений без использования Console.SetIn() и Console.SetOut(). Результат тот же, к сожалению.
http://mirror.codeforces.com/contest/36/submission/159163 Данный код зашёл 2 года назад. http://mirror.codeforces.com/contest/36/submission/2716641 Но сейчас не заходит.
Спасибо, исправили.
Оффтоп: а почему у вас нет дня перерыва между турами? Это сейчас так правила поменяли или у вас перерыва никогда не было?
Муниципальный этап в некоторых городах вообще в один тур...
Когда я учился в школе, перерыва не было.
a typical comment:
wish you all luck !!
Two contests on two days :D. I and a part of CF Users will have two sleepless nights :D
Haha, but I have enjoyed those two contests in the daytime, cool enough!
I am happy to hear it. Thanks for your kindness!
Why At This Time ? That's Too Bad
Any time you choose for contest will be good for some people and bad for other. And there is no way to do something with that.
Два раунда подряд, ещё и в 12:00 по Украине! Супер!
Ну и почему так супер ? В субботу в это время учеба, а в воскресенье — региональный этап(ну, в Хмельницкой области так).
В субботу не учусь, областные и вовсе пойдут лишь на втором семестре
Хех =) Везет Вам ) Удачи на контесте.
Спасибо за новость! Контесты лишними не бывают:)
Will these rounds be rated?
yeah it will be rated
div1?
read the post completely and then ask your questions :)
Participants from Div1 can take part in rounds out of competition.
For the others div2-contests, participants from div1 can take part too, but as non official (non rated). The question is still valid. I would be interested by an official answer.
Oups, sorry, double fail. Didn't seen the end of the sentence ><
Жаль, что раунд будет проходить одновременно с тренировкой на neerc.ifmo.ru/school. Придется выбирать =(
Кажется, что для школьников выбор очевиден.
И каков же очевидный выбор для школьника? Уровень контестов примерно один и тот же.
at this time i have math :(
Time of the contest is too bad! Couldn't it be taken place at usual CF rounds' time(19:30)?
It is a school contest so the online contest has to be at the exactly same time.By the way,I think it isn't a bad time,at least for Eastern Asian constants,who have to stay up midnight for contests at usual time.
I come from IRI; is IRI in eastern asia?
I can't agree with you more
By the way, I'm the only who likes the time of these contests? :)
No, I like it too =)
and exactly after finishing Codeforces Round 154 we should switch to UVA for ACM ICPC:: Dhaka Regional Semilive! what a busy days, full of contests and programming! but i like being exhausted by contest-based days !
And don't forget Topcoder SRM 563 ;)
http://community.topcoder.com/tc?module=MatchDetails&rd=15185
It starts 10 minutes after the ACM ICPC:: Dhaka Regional Semilive contest. So 2 + 5 + 1.5 hours full of fun!
It seems some new experiences are waiting for us ;)
Wouldn't be a good idea to put sample A+B problem at least for C++ an Java languages, for those who are not familiar with I/O from files?
On C++ just add this code
and after that you can use you favorite read/write methods (cin/scanf, cout/printf)
I think you made mistake "stdout" in second line
yeap, you are right
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");
int A,B;
in>>A>>B;
out<<A+B<<endl;
return 0;
}
Неплохо было бы примеры с файловым вводом и выводом запилить для такого случая. Многие из новичков же не умеют
коммент выше — пример на с++
Боюсь что на кф не только плюсы
Спасибо за соревнования!!! А то соскучились по ним....
Russians should practice English a more lot. 30% WAs are due to their problem statements in English. They should check the statements by a native English man.
We will be very happy to have such an opportunity. But I also think that some green coders from Bangladesh should practice solving programming tasks a lot more. The rest 70% WAs are due to their poor skills.
Well this was offensive from both of you. It is not good to have such situations on programming competition site.
I join this site because hear about this contest... :)
and the example code of I/O is very helpful, thanks...
In c++ freopen's are allowed but everytime i was sending a code in java with
System.setIn(new FileInputStream("input.txt")); System.setOut(new PrintStream("output.txt"));
runtime error was coming everytime! Why is that not allowed in Java?
Самую первую не выложили. А пятая похожа на сложную реализацию.
пятая в кф контесте. на онсайте — шестая_)
Я правильно понимаю, что в E бинпоиск по возможным приоритетам, их O(n), а внутри эмуляция с помощью PriorityQueue за O(n*log(n))?
Да. Я так и не смог победить WA5. После контеста заметил, что мое решение допускает приоритет равный нулю. Также надо внимательно отследить, чтобы не было такого же приоритета, как и у какого-то другого задания.
Похоже, у меня где-то там бесконечный цикл... Я сначала думал, что тупо по времени не заходит, но потом посмотрел на расход памяти — видимо 5-ый тест все-таки маленький.
Чуть не повесился, когда увидел, что неправильно написал бинпоиск и проверял size-ый элемент в листе возможных приоритетов. К счастью, была еще одна принципиальная бага. Теперь Accepted.
Да, бипоиск прошел. Изменил левую границу с нуля на единицу и тут же в дорешке зашло. Примерно 900мс из 4000мс. До меня только сейчас дошло, что можно бинарить не тупо от 1 до 109, а просто сгенерить в массив все приоритеты вида Pi - 1 и Pi + 1 и бинарить по ним.
Да, но решение за O(n·logn) тоже есть. Просто мы решили, что пусть O(n·log2n) тоже заходит.
Contest is over, help me, please, with problem C. Did anybody wrote something besides BFS?
Yes
The idea is: Go from r1 to some intermediate row i and then go from that intermediate row i to r2 (using ups or downs), after that get to the right column(using lefts or rights).
подскажите как решалась задача D и E? Я думал в задаче D хранить для каждой клетки вектор подходяших клеток справа и снизу. И потом идти с конца первого вектора и просматривая какие нам подходят. Проверяя пару клеток с помощью массива dp[n][m], где dp[i][j] -это кол-во букв "а" в прямоугольнике (i,j) (n,m).
Задача С Пусть i — какая-либо строка текста. Сходим, используя только клавиши "Вверх" и "Вниз" от r1 до i и от i до r2. Потратим на это t1 нажатий. Возможно, наша позиция в строке изменилась из-за разности длин строк, по которым мы ходили. Пусть эта позиция — q. Теперь курсор находится на строке r2, нужно добраться из позиции q до позиции с2, потратим t2 нажатий. Для данного i ответ будет (t1+t2). Итак, за O(n) переберём все возможные i и выведем минимум.
Норм у тебя перебор за О(1)
O(n), конечно же. Опечатка, спасибо.
Enormous speed of system testing makes me happy :D
Also very good problems
Yeah, really good problems. But much more difficult than the same school olympiad in Novosibirsk :)
Если бы каждый раз так быстро тестили Я наверное мог бы и выспаться
Хороший контест, D и E очень понравились.
I got Runtime error in system test, but I can get the right answer in custom test.... why can this thing happened?
While。。。 It's my fault, I haven't seen that the data was read from input.txt....:-(
I sent the first problem, got TLE (because I used no file) and lost rating. I was thinking failing in test case 1 didn't count as a submission, so I abandoned the contest. :\
EDIT: I would like to ask someone why this happened, since from contest rules:
"If the result of the judging is Compilation Error, Denial of judgement (or similar) or if the solution didn't pass the first pretest, then this solution won't be considered in calculating results."
Did I get it wrong?
You do not get -50 for such submission, but it still counts as participation.
Only integer and int64, and I have failed problem D :(
Weirdly, there's no %lld warning on this problem.
2724941 :D somebody solved D using 2000ms
Looking at the constraints, i thought BFS would TLE for Problem C but i got AC'ed in practice ( 234ms ) :(
I am getting TLE in div2 C with bfs. Can anybody tell why? Here's the link to my solution — http://www.codeforces.com/contest/253/submission/2728384
HashSet? ArrayDeque? Point? Objects, objects everywhere! Of course, it's TLE!
k, seems OOPS is not the way 2 go!
I think your skill isn't good because i got AC in 468 ms
2724998
ok! we've all understood that your programming is very good!
finally AC, had forgotten to override hashcode()!!
Why File I/O style was used in this match? I think that the unusual format only mislead people. Please tell me the reason.
I think, all school olympiads testing systems use file I/O, but, I afraid, the reason of this is unknown
Is it possible to get some more specific details about Compilation Error? My code compiles well locally, but when I try it here it gives Compilation Error without any good explanation of what could've mistaken.
Me too. I tried to submit "Boys and Girls" (#154 Div.2 A) just now. I got 2 "Runtime exceeded" on Test #1 and 1 "Compilation Error". But I put those 3 codes onto the "custom test" provided and input the test case #1 (3 3). It is ok. Can anyone tell me what mistakes I have made?
oh. I have understood already. Because I haven't read the instructions of this contest. Sorry.
в примере на D ввод-вывод не буферизован, что может привести к, ну вы поняли. Надо использовать сишные функции:
Эээх жалко, что соревнование проходит именно в это время.Ведь практически в это же время будет Биатлон (2-й этап, Хохфильцен, Австрия. 4 х 7,5 км эстафета (М)).Теперь не могу выбрать , на чем же остановиться?
Если у вас есть юридические обязательства перед сборной своей страны, вам придется все же принять участие в эстафете. Нельзя вот так просто взять и не явиться на старт
Please somebody tell m why i am getting time limit exceeded in the following code,while i could run the exact same code on code::blocks, http://mirror.codeforces.com/contest/253/submission/2723001
"Problems will require file I/O: you have to read data from input.txt and write data to output.txt"
My bad..they have mentioned it in the contest post...:(
The score distribution for the round #155 will be the same with #154 ?
Until is not specified differently we suppose is the same.
You did't notice UPD2.
Скажите, пожалуйста, второй тест в задаче E
Ждать окончания систестов чтобы посмотреть его — не комильфо?
Что там было в Е? Пытался написать динамику, но показалось, что слишком муторно
E жутчая.
как решались задачи D и E в 155 раунде? Я думал в D какой нибудь жадняк запуская бфс из каждой точки где стоит мышь и помечая клетки. И в конце если в местах где стоят мыши всего 1 или 2 различных значения то мы можем так взорвать гранату в противном случае не можем.
Я не успел дописать D и правильность гарантировать не могу, но вот идея: т.к. d<=8, то если самые далёкие друг от друга мыши стоят друг от друга на расстоянии, большем 4*d, то взорвать всех мышей мы точно не сможем. Поэтому достаточно рассмотреть наименьшую часть поля, которая включает в себя всех мышей, а она будет достаточно мала, максимум (4*d)^2.
это не так: предположим у нас очень большое поле, 2 мышки по углам, чего нам стоит прям по ним запустить по гранате, ведь у нас их тоже 2?
можно же при считывании просто добавить счетчик, и если крыс две или меньше, вывести координаты мышей+любые пустые клетки(если мышей меньше 2х). а иначе решать как написано в комментарии Lapenkov
ну так всеравно не пройдёт мы можем хоть по 5 мышей в 1 угол и 5 мышей во 2 и расстояние между 2 из них максимальное будет > 4 * d. И решение Lapenkov будет выдавать -1. А на самом деле мы с лёгкостью уничтожим 2 гранатами этих мышей
а, ну, да=)
Контест прошёл хорошо, без багов и задачи вполне нормальные. Осилил А и Б. Когда разбор?
непонятно, зачем было добавлять в Е восстановление ответа? идейности это не добавило, зато извращения да.
ага, я написал подсчет рейтинга за 5 минут до конца контеста, и еще 6 минут писал восстановление, и, как результат, не успел залить=)
Простое, понятное и, что самое главное, не работающее решение.
Почему не запускают системное тестирование?
Насколько вчера быстро прошли сис. тесты, настолько же сегодня они долго начинаются
И умудряются ведь укладывать ровно в тайм-лимит.
2737877
Решение "зависло"? Да что это вообще за вердикт-то? 2736757
System testing isn't going to show us surprising speed today :)
I'm wondering why the system testing hasn't begun yet? thx~
^-^
^-^
Can anyone tell me how to solve 155 problem C? I stuck in that problem..
Although I did not participated in the contest, But for me solution seems like this.
First you can decide that minimum no of changes part easily. So if you fix min no of changes. Let call it z.
Then for the lexicographic part , Go from sorted order of characters in t , and try doing the change in corresponding character in s , If you can do the change , Then do it. Continue this until you have done z changes.
Although things explained are very high level , But you should try to go into more depth yourself.
"чекер по задаче C не проверяет лексикографическую минимальность выведенного участником ответа" учитывая, что ответ однозначный, где же нужно было ошибится, сравнивая два токена?
видимо проверяли только кол-во изменений над первой строкой(первая строка в выводе)
Поставить стандартный wcmp слишком легко, лучше написать собственный неправильный чекер!
Just saw my ranking go down from 304 -> 252 even before systests has started.
What happened?
look UPD4
Thanks man
There is a typo in UPD5.
Nice editorial, I had the idea of E but didn't implement it, I went to hack 4 people instead.
UPD4 Does it mean that this competition should be unrated for me? Bad luck... I solved four problems.
Once again — you didn't solve problem C. Actually you had wrong answer on pretest 9, but system told you invalid response that the solution passed it. It affected only 53 participants (including you).
Oh...Sorry...Next time I will check my solutions more carefully...Thank you...
На контесте сдал задачу А, претесты засчитались. Сейчас пошло финально тестирование и у меня не прошел тест 9 из-за тл. Насколько я понял, 9ый тест был в претестах(например вот это решение — http://mirror.codeforces.com/contest/254/submission/2738151). Как такое могло получиться(решение у меня как в разборе)?
С чего Вы взяли, что 9 тест был в претестах? Насколько я знаю, в претесты не дают большие значения, в том числе макс. тесты (как 300 000 тут).
вообще-то в претестах как раз и был 9 тест это макс тест. Так что это какая-то ошибка, что SharpBlade оно вначале прошло а потом выдало ТЛ
с того что я приложил вам ссылку, где решение валится на 9ом тесте, и там написано, что это претест. более того, я залил такое же решение в дорешку и оно получило AC. http://mirror.codeforces.com/contest/254/submission/2734441 — контест http://mirror.codeforces.com/contest/254/submission/2741882 — дорешка
Всё, понял, увидел, что претест. Но это в любом случае вина не тестирующей системы, а Вашего решения, которое работает «впритык». Невозможно точно замерить время работы, вот в одном случае решение и влезло, а в другом не успело. UPD: Кстати, во время дорешки нагрузка ниже, и вполне возможно, что именно поэтому оно и зашло во второй раз.
опять вы говорите не очень внятную речь. Если решение прошло претесты с самого начала, то на финальном тестировании оно как минимум эти же претесты должно проходить.
тут проблема основная не в этом. вот я открываю задачу А, пишу ее, заливаю. она попадает в очередь, я смотрю очередь, там передо мной еще куча непроверенных решений, соответственно я открываю след. задачу и начинаю уже решать ее(потому что задача А простая и я был уверен в общем-то в правильности+ ранее имел проблемы с тем, что ждал вердикта и не успевал заливать решения).
где-то чеерез 25 минут, я заливаю след. решение, бросаю беглый взгляд на А, и вижу AC. опятть очередь, опять не жду, читаю след. задачу. Решив след. задачу, заливаю, вижу, что пред. свалилась(по А так и висит АС), возвращаюсь к ней, правлю и сдаю.
затем контест заканчивается, начинаются систесты и моя А задача берет и падает на претесте, хотя она должна было упасть на нем еще на 5й минуте, когда я залилвал, тогда я бы потратил езе 2 минуты и перезалил. Итого потеряв бы 50+4+6+8 очков(примерно). а в итоге я потерял всю задачу А. про потрянные очки из-за очередей я уже ничего не хочу говорить.
ТЛ в А задаче у меня вообще впервые, я думал, так не бывает :D
Это особенность работы чекера. У Вас решение A в одном случае прошло, в другом — нет. Оно могло и в первый раз упасть, но ему повезло, и чекер за TL «срубить» не успел. А могло и пройти оба раза. Так устроена тестирующая система, от погрешностей защититься не получится, особенно с решениями, работающими вплотную к ограничениям, вроде Вашего. В принципе, с 26 по 34 тесты идут тоже по 300 000 чисел, и Ваша программа, даже если бы прошла 9 тест, наверняка свалилась бы на каком-то из них.
Challenge Master
Wrong language sorry
Why I'm out of competition?
По поводу UPD4: а на самом муниципальном этапе чекер тоже неверный был?
Там оффлайн соревнование, по-этому когда тестировалась школьная олимпиада, то все было уже нормально.
А ето нормально что у меня на А место РЕ выдавало ВА и ТЛ
РЕ и ТЛ довольно сложно отличить особенно если вы на Сишке сдаёте. так что да впринципе нормально, главное что выдавало ошибку
" UPD5 Tutorial is available for round 154. " Shouldn't it be round 155? Or i make a mistake?
why I am out of contes?I register the contest before and solved 3 problem during the contest.
Моя С-ка прошла финальное тестирование, но в таблице мне показывает, что у меня решены только 2 задачи. Что не так?
Она почему-то повисла у меня в "Попытках" на 1-ом тесте. Что за черт?
Провелил реджадж. Теперь все нормально. Спасибо
Why I am out of contest? I register the contest before and solved 3 problem during the contest.
Look at UPD4
В B надо было ограничения побольше. А то я что, зря сканлайн туда пилил?)
Да, зря :)
Таки да, веселый и интересный контест.
Спасибо контесту за новый цвет!
Поздравляю!=)
Спасибо)
Может и мне как-нибудь повезет...
I'd still have managed a rating increase inspite of the Problem C issue. Bad luck! :D
У многих линия рейтинга стала похожей на вертикальную?
))))А есть такие, у кого она стала горизонтальной???)))
My rating went up and then dropped back to the previous value, however my color has not changed? What happened?
Ok it seems it is back to normal now, thank you! sorry about that.
Can somebody help me, please?
I am div 1, and i send sources for problems A and C at round 155. For both of em i get WA1.
Now i send the solutions again, and i can't see my answer .. This is my sol for A .. http://mirror.codeforces.com/contest/254/submission/2742588
you have to use files instead of standart input\output
You are using iostream You need to read from a file (input.txt) and output to a text file (output.txt) I suggest you use fstream, comment iostream and just add the following lines: ifstream cin("input.txt"); ofstream cout("output.txt");
Ohh .. i just saw the input and the output :(
Sorry .. I thought that was just like in the older CF-s .. with stdin.
I think 28th line isn't funny.
I checked if it writes sth .. :( Sorry ..
the test# 4 in problem E my output is : 17 3 1 3 4 0 5 1 6 8 5 1 6 8 2 7 4 1 6 7 5
i calculate it by hand is correct , but the check log said "wrong answer impossible to feed friend 5 at day number 3."
Why a submission is judged TLE in a test case that passed in the Pretests?
See: 2735059 Passed pretest 9 --> TLE in test 9
Are the same input data?
The exact TLE output depends on the load on the server as well as your code. You should be safe if you actually go for the intended complexity bound of the solution. In this case it is O(n) and yours I presume is O(nlogn). Here luck plays some role.
Неправильно показывается мой рейтинг в "рейтинге друзей" :( Я написал 27 контестов, тут почему-то не учитывается последний, сегодняшний контест. У всех так?
У меня то же самое. Непорядок.
UPD: уже нет, теперь норм.
Почему это решение http://mirror.codeforces.com/contest/254/submission/2734808 прошло 9 тест, а моё аналогичное не прошло. И даже когда я сдал абсолютно такое же решение, то всё равно было TLE
магия сервера)) Вроде моё решение за линию работает чего ему ТЛ-ится? Учитывая что решение работает за 460 мс, то возможно ошибка у вас в коде поэтому оно и ТЛ-ится?
Так я потом скопировал это решение и отослал, поэтому ошибки быть не может. И много других пройденных решений я уже посылал и всегда TL на 9. Я не могу понять, что происходит, у кого какие мысли по этому поводу?)
Специфика компиляторов=)
Вы отправляли решение на MS C++, а astrovsky на GNU C++.
Сама суть такой разницы, по-моему, в медленном потоковом вводе-выводе в MS C++. Так что рекомендую впредь использовать scanf/printf.
in round 155 (Div 2) for the problem B why is the greedy algorithm wrong ??
How did you use the greedy algorithm? It's just the maximum number of jurors that have to work at one time.
I got WA in the problem D on the test 57 but I don't know why, and the test data is too huge.. Here is my code 2745258 . :D
Thanks.
Oh..I find my mistake in the "bfs2"... I'm curious about that the code can pass 56 test datas :P
hey why was the server down again???????!I don't wanna waste my time seeing the home page again & again.
I have solved the Physics question and I'm getting the right answer even when I run it under the "Custom Test" tab.. However, I'm getting a run time error or wrong answer error when I submit the solution. What is wrong?
http://mirror.codeforces.com/contest/253/submission/2822370
Note the trap: input.txt, output.txt.