MikeMirzayanov's blog

By MikeMirzayanov, 9 years ago, translation, In English,

You may read complete rules here.

The text contains only preliminary rules of Codeforces contests — something surely will change. In particular, I hope to help the community to find the illogic in the rules. However, I have already discussed the format with programming contests dinosaurs and made unrated alpha contests — it seems rules are OK.

I think than the format 5 tasks x 2 hour is quite good. For this reason, in the near future we will not change it, but of course, experiments are possible.

1. Before the competition all participants are divided into rooms, each room contains about 20 participants. For now random strategy works, but after a while it will be somehow correlated with the rating.

Read more »

 
 
 
 
  • Vote: I like it
  • +23
  • Vote: I do not like it

By MikeMirzayanov, 9 years ago, translation, In English,

Hello!

Today will be the first alpha test of the new format of the competition. Registration will be limited - as soon as about 60 participants have register, I'll close it. Invited to participate, only those who have read rules draft. The document is in Russian, so I expect most participants from Russia. After some time we will translate the rules into English, and make this type of rounds really international.

In this round will be used folklore problems and the duration had to be reduced. For sure, it will be non-rated. Codeforces not guarantee that everything will work well - so be patient.

Many thanks to those who gathered to take part. I hope it will be interesting.

MikeMirzayanov

UPD 1. Contest duration changed to be 90 minutes.
UPD 2. In order to take part in contest, your browser should have installed flash player.
UPD 3. Contest will start on 19:30.

Read more »

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

By MikeMirzayanov, 9 years ago, In Russian,

Летняя студенческая школа по программированию

Второе информационное сообщение

За период предварительной регистрации мы получили большое количество заявок. Спасибо за проявленный интерес. Мы очень рады, что школа находит свою аудиторию.

С другой стороны, так как количество заявок в три раза превышает наши возможности по размещению, мы не в состоянии пригласить всех желающих. При составлении списков участников летней школы были учтены различные критерии: соответствие уровня команды учебной программе, возраст членов команды, география и др. Заметим, что мы смогли увеличить число приглашенных участников по сравнению с прошлым годом. Мы очень надеемся, что школа станет традиционной, расширится, и в будущем мы сможем приглашать большее число участников.

Приглашенные команды:

  • Петрозаводский ГУ (Басунков, Федулин, Филиппов)
  • МГТУ им. Баумана (Верхоглядов, Акользин, Егурнов)
  • МФТИ (состав уточняется)
  • МАИ (Зернин, Колесник, Кирилишин)
  • СпбГУ (Карпов, Соколов, Ненашев)
  • Пермский ГУ (Акимов, Шафер, Ошеров)
  • Московский ГУ (Золотов, Броварь, Таболин)
  • Российско-Армянский (славянский) ГУ (состав уточняется)
  • Ярославский ГУ (Делюкин, Быкова, Нефедов)

Индивидуальные участники:

  • Астраханский ГУ (Горбачев)
  • УрГУ (Мухаметьянов)
  • СпбГУ (Белоус)
  • Ковровская ГТА (Фомин)
  • Тюменский ГУ (Красноперов)
  • ИжГТУ (Гатин)

Руководители (тренера) вышеперечисленных команд и участников должны подтвердить приглашение до 26 июня по электронной почте

Если планируется безналичный перевод, то пришлите запрос на оформление счета. В случае если какая-либо команда (участник) не пришлет подтверждения, то она будет заменена в списке другой командой. Как только будут готовы дополнительные документы (договор, акт выполненных работ), мы опубликуем их на сайте.

Руководитель Центра олимпиадной подготовки программистов
Саратовского государственного университета,
тренер команд.
М.Р. Мирзаянов,
16 июня 2010 г.

P.S. Так как количество заявок в несколько раз превышает количество участников, то нами решалась сложная задача утверждения состава школы. Были учтены различные критерии, о которых написано выше. Просьба подойти с пониманием и не поднимать дискуссий по этому вопросу. Спасибо.

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By MikeMirzayanov, 9 years ago, translation, In English,

Guess when the contest began and ended :)

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

By MikeMirzayanov, 9 years ago, In English,
Hello.

Soon my wife will have a business trip to China. She will be a week in Harbin. Is there anyone from this city?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By MikeMirzayanov, 9 years ago, translation, In English,

This post contains few words and many pictures. I decided to publish statistics on Codeforces visitors for the past two months. Why? I believe that it might be interesting. I took pictures from Google Analitycs.

Codeforces was born little more than 4 months ago. During this time, we held 16 contests (though one of them was non-rated). There are more than 4000 registered users, and every day we get about 30 more. There are 1797 coders participated in the contests, many of them participate in our contests regularly. The average number of registrations for one competition is growing, and I want to believe that soon it will conquer psychological barrier 1000 users. Also codeforces social network is popular: more than 400 posts, almost 6000 comments. The leader of the hit parade of posts is this post, has collected to date 184 comments. Bravo, SkidanovAlex! And of course I say thank you to everyone who helped make the project: those who help in the development, who make the problems, translate texts and write the alternative solutions, participate in community life, and just take part in contests. Thank you!

Below you will find a few more pictures and statistics, the total traffic of about 250KB.

Read more »

 
 
 
 
  • Vote: I like it
  • +14
  • Vote: I do not like it

By MikeMirzayanov, 9 years ago, translation, In English,

The first information letter


General information


From 2nd to 12th August 2010 Saratov State University runs an international student summer school in computer programming. Teams of three people and individual participants are invited to take part in it.

The school will take place in a picturesque place at one of Saratov resort centers on the Volga bank. The participants will be provided comfortable rooms for 2-4 people and meals three times a day. The resort center owns a beach and sport grounds.

The school curriculum includes lectures by Saratov state university coaches, joint trainings, problems tutorials and topical workshops. The curriculum is designed for younger university students who aspire to achieve high results at programming competitions.

The fees are 15000 RUR (~ 500 USD) for a person. Moreover, each team or an individual participant should bring a laptop with the support of WI-FI.

All interested participants and teams should register at http://acm.sgu.ru/sazanka-2010/ till 10th June 2010. Don't postpone the registration, as the number of participants we can take is limited.

You can get additional information by e-mail mirzayanovmr[symbol-at]gmail.com. As since the official language of the school is Russian, the registration requires knowledge of Russian. Also it is recommended to view this page in Russian.

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By MikeMirzayanov, 9 years ago, In Russian,
Для тех кто еще не знает, сообщу, что IPSC (Internet Problem Solving Contest) это ежегодное соревнование, которое проводиться братским народом - словаками. Интересно оно в первую очередь необычными правилами и задачами. В этом году соревнование будет проходить 6 июня, а регистрация уже открыта.

Соревнование длится 5 часов и на нем будет предложено 6-20 задач. Например, в прошлом году их было 13. По каждой задаче вы можете скачать два набора входных данных: упрощенный и усложненный. Отсылать на проверку надо только результаты (примерно как в Google Code Jam), за неправильные попытки начисляется icpc-like penalty (для простого теста 10 минут штраф за попытку, для сложного - 20). Бывает, что они дают не решаемую в общем случае задачу, но тесты содержат входные данные специального вида, то есть, посмотрев на них внимательно можно понять, что для данного вида тестов решение существует. Кроме того на этом соревновании обязательно бывают задачи-угадалки, в которые практически невозможно сдать с первой попытки, но каждая попытка дает новую информацию. Задача состоит в том, чтобы выбрать правильную стратегию, получив ответ за наименьшее число попыток. Отметим, что существует ограничение на число попыток на каждый тест равное 10. Настоятельно рекомендую написать пробный тур, чтобы ознакомиться с их системой сдачи решений.

В конце отмечу, что этот контест (2000 года) команда Saratov SU 3 (Эльтерман, Лазарев, Мирзаянов) считает своим днем рождения. Дважды мы делали себе подарок, одерживая победу на нем: в 2003 и 2004 годах :)

Результаты подводятся по двум дивизионам: школьный дивизион (детский) и открытый (взрослый). На настоящий момент чемпионом мира по версии IPSC является команда наших соотечественников Ural Fanclub of Ksenia Sobchak

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By MikeMirzayanov, 9 years ago, In Russian,

Надо сказать, что участвуя в прошлом году в TopCoder Open и Google Code Jam, я чувствовал себя значительно более уверенно, чем в этом. Дело в том, что последний год я совсем мало решал задач и участвовал в каких-либо контестах. Это разумеется отразилось и на результатах. Но как бы то ни было я собираюсь участвовать этих соревнованиях этого года и буду бороться до последнего (надеюсь, раунда).

Только что закончился Google Code Jam 2010 Round 1B, который я слил препозорнейшим образом, о чем сейчас и поведаю. Сразу отмечу, что задачи мне очень понравились, отличный отборочный раунд.

Результаты здесь


А вот и разборы задач.

A. File Fix-it

Я решал эту задачу явно строя дерево директорий. Для этого я каждый путь превратил в vector<string>, разделяя его символом слэш. Вот такая функция добавляла в дерево путь d[idx]->d[idx + 1]->…->d[d.size()-1] из вершины tree дерева. Так же она увеличивает глобальный счетчик z созданных узлов.

void put(const vector& d, int idx, int tree)
{
	if (idx >= d.size())
    	return;

    if (f[tree].inner.count(d[idx]) == 0)
    {
	    z++;
    	f[tree].inner[d[idx]] = p++;
    }

    put(d, idx + 1, f[tree].inner[d[idx]]);
}

Тогда задача сводиться к добавлению в дерево всех существующих путей, а затем (после z:  = 0) добавлению тех директорий, которые надо создать. Значение z после этого (т.е. количество созданных узлов на второй фазе) будет равно ответу на задачу.

B. Picking Up Chicks

Эта задача меня подвела. В первом абзаце я как-то умудрился прочесть, что при обгоне обгоняющая курочка скидывает с беговой дорожке обгоняемую, но продолжает двигаться со скоростью второй. Не спрашивайте меня как я это прочел…

После того как я понял условие правильно, то решил задачу следующим образом. Для каждой курочки я определил добежит ли она до финиша за время t если ей никто не будет мешать. Если таких курочек меньше k, то ответ IMPOSSIBLE. Если таких курочек равно 0, то ответ 0. А вот если таких курочек больше или равно k и k положительно, то выбираем k ближайших к финишу курочек и будем именно их использовать для составления ответа. Пусть это множество A. Для каждой из этих курочек посмотрим на такие, которые находятся правее ее, но не являются выбранными. Такие курочки не успевают добежать до финиша (так как не выбраны), и поэтому в них нельзя упираться. Значит всех их надо проскочить. Таким образом, ответ это сумма для каждого a из A количества курочек впереди a, но не принадлежащих A.

C. Your Rank is Pure

Задачу я решал методом динамического программирования. Пусть z[i][j] = количеству подмножеств {2,3,…,i} которые являются хорошими (в терминах задачи) и число i в них имеет ранг j. Тогда число j тоже принадлежит подмножеству и может иметь любой ранг от 2 до j - 1. Допустим его ранг равен t. Тогда на участке от j + 1 до i - 1 (включительно) нужно выбрать любое подмножество из j - t - 1 элементов, чтобы заполнить пропуск нумерации. Получаем, такую формулу:

.

Разумеется, все вычисления надо производить по модулю 100003 и предпосчитать таблицу биномиальных коэффициентов.

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By MikeMirzayanov, 9 years ago, translation, In English,
Today's round is not quite usual. The participants of the first division can register on it and to participate out of competition. This round will be some alpha-testing for this functionality, but for the next div. 2 round you can expect a stable version. 

This round prepared for you by: homo_sapiensJuliaNerevarKudryashovIA and me. 

I want a high-ranking 
MikeMirzayanov

Read more »

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

By MikeMirzayanov, 9 years ago, translation, In English,
There is known issue which sometimes leads to the fact that with the start of contest we have to restart the application (the same goes for the end of the contest). Please do not panic if it happens. In worst cases it will take 2-3 minutes. I’m resolving this issue, but at the moment it is not yet completely resolved. Thank you for your understanding.

Read more »

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

By MikeMirzayanov, 9 years ago, In English,
Hello again. I hope nobody has forgotten to register?

In this contest we will try alpha of our chat - if something goes wrong, we turn it off: please do not panic:)

Links:
Problemsetters: Дмитрий Матов и Игорь Кудряшов. Thank them for their contributions.

I wish you to advance to the first division.
Mike Mirzayanov.

Read more »

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, translation, In English,
Sometimes funny things happen on contests. On a recent training Ivan Fefer was unsuccessfully submitting one of the problems for a long time. After all he asked me. There followed this dialogue:
Ivan: - I have a question on the problem D.
Me: - What is the problem?
Ivan: - It is about a tree and requests.
Me: - So it's C.
Ivan: - ...oops... The question is removed ...

Do you have a funny story about something that happened to you during the contests?"

Read more »

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, translation, In English,
Welcome to Codeforces Beta Round # 9. 
The problems of this round prepared by Alex_KPR. Thank you, Alex_KPR. Also Nerevar participated in the contest preparation.

Julia, a special thanks to you for the excellent translations.

Wish you high rating,
MikeMirzayanov

Read more »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, translation, In English,
In case you are not familiar with the term, this the way of filling the site with content by the joint effort of the community. You might read a Wikipedia entry.
Basically, the idea to apply crowdsourcing to contests tutorials seems quite natural, but… it works badly. As you see, it is not the first time there has been no one willing to help the community. The question is: why and what is the way-out?

Let’s discuss it together. What should be changed/improved in order to make contests tutorials appear at Codeforces?

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, In English,
Welcome and good luck on the round! 

I'd like to remind that if you have any questions on the problems, the best way to ask them is to use the web interface on the problems page. 

Later in the same post we will discuss the round. 

Wish you high rating,
MikeMirzayanov.

UPD. For contest you may thanks team Saratov SU #5, namely, users FeferGerald and Polichka.

UPD2. And better late than never: the presence of English statements we are obliged only to Julia. Many thanks to her for 8 wonderful translations of 8 rounds.

Read more »

Announcement of Codeforces Beta Round #8
Announcement of Codeforces Beta Round #8
 
 
 
 
  • Vote: I like it
  • +22
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, translation, In English,
The contest is rescheduled to start on 19:45.

Thank you all for participating in Codeforces Beta Round #7. I hope you enjoyed it. You may discuss the problems and system in comments. Please express your opinion, especially if you notice any inappropriate behavior. And as always, I will read with interest the suggestions for improvement.

From today on both-divisions contests ratings will be updated separately for each division. I. e. ratings will be calculated as if two contests (one per division) have taken place on the same problemset.

Also I would like to see someone who wants to write contest tutorial. This must be done in Russian and English languages. Of course you must solve the problem on either contest, or in the practice. If you have a desire to do it - write in comments. Your post will be published on the main page and later available on special link available from the contest page.

Many thanks to the contest problemssetters: RAD and e-maxx.

Good luck.

Ratings has been updated. Solutions are available for view.

Read more »

Announcement of Codeforces Beta Round #7
Announcement of Codeforces Beta Round #7
 
 
 
 
  • Vote: I like it
  • +19
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, translation, In English,
Welcome to the Codeforces Beta Round #6.

It will be good to see your feedback and impressions in the comments.

Wish you high rating,
MikeMirzayanov.

UPD. It seems the problem D has some tricky issues around judge solutions. Judge solutions will be fixed and the problem will be rejudged. If it will affect many participants, the contest will not be rated.

UPD 2. We have reduced constraints in the problem D and made rejudge. No solution passed tests. So the rejudge affected significantly only 4 participants, who solved it during the contest. But all of them increase their rating if we will count the contest as rated event. So we decided to make it rated and put problem with lowered constraints into the practice.

UPD 3. And by the way, the round tutorial is waiting for a volunteer. The tutorial should be in Russian and in English. It will be published on the homepage and later will be available via special link from the contest page.

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, translation, In English,
Hello to everyone.

The latest news - now you are able to see the source code of the solution. During the contest you can view your own solutions only, but when the contest is finished you can view the solutions of any other participant. The table with the solutions is available via the problemset page, the solutions there are sorted by the program length. Pay attention, please, that you are free to change the sorting criteria using the option at the bottom of the table. 
There is another principle that gives you the chance to view the source codes of solved (during the contest or practice) solutions only. Personally, I regard the principle "everyone sees everything" as more suitable for our regular contests.  Am I right?

When you run a contest within your private community, you'll be able to set up your own principle for viewing solutions (or to switch off this function at all). But this functionality is under construction now. 

Wish you high rating,
MikeMirzayanov

UPD. Standings page is improved. You may double-click into a table cell (or use Ctrl+click) to view the submissions history.

Read more »

 
 
 
 
  • Vote: I like it
  • +14
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, translation, In English,
Welcome and good luck on the round! 

I'd like to remind that if you have any questions on the problems, the best way to ask them is to use the web interface on the problems page. 

Later in the same post we will discuss the round. 

Wish you high rating,
MikeMirzayanov.

Read more »

Announcement of Codeforces Beta Round #5
Announcement of Codeforces Beta Round #5
 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, translation, In English,
Hello, everybody. 

At this point we have already decided on the date of Codeforces Beta Round#5: it's Saturday, March 20. The exact time is still unknown. I do want to find the best time suitable for most participants. Please, express your ideas in the comments - of course, you should not come up with the time that suits only you, but suggest the most suitable time for the majority.  

Wish you high rating,
MikeMirzayanov

UPD.  Thanks to everybody who wrote comments - I've read them all. The venture proved to be useful. Without your help, I wouldn't have been able to take into consideration all those factors which can affect the number of participants.  After much thought, I've made a decision to schedule the round for 19:00 (Moscow time) - I think this option is convenient for most users of the site. It does not mean that we will not experiment with time in future - we will try morning contests, but I can't promise about 5:00:).

Read more »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, translation, In English,
I propose to discuss here the issues and troubles associated with Codeforces Beta Round #4.  On our side, we identified three difficulties: 
  • Slow judging - apologize for the large queue, to the next round, I assume significantly increase the speed of judging;
  • Runtime errors on Python solutions - apparently the decision they want to load some library, which is prohibited by security reasons;
  • Sometimes incorrect runtime errors - apparently the result of the antivirus on testing servers, they will be turned off on the next rounds
Also express your impressions about the round.

P.S. And by the way, the round tutorial is waiting for a volunteer. It is desirable that it will be one of the leaders of today's competition. The tutorial should be in Russian and in English. It will be published on the homepage and later will be available via special link from the contest page.

UPD. The ratings have been updated.
UPD 2. Thanks to KudryashovIA for his help in making contest.

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, translation, In English,
In email notification (in Russian) I've made a typo. The phrase "It starts on March 12 (Friday), 2010, 12:00" should be read as "It starts on March 12 (Friday), 2010, 15:00".

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, translation, In English,
I propose to discuss here all that concerns Codeforces Beta Round #3. Of course, during the competition it is forbidden to write anything about the solution of problems and similar things  

For the time of this contest, we turned off the chat server. This does not mean that it will not operate in future - I think it is a convenient and efficient way to communicate during the competition and you may expect it in the future.  

Also I'd like to announce Codeforces Beta Round #4, which will be held next week. It will be for participants from the second division (non-rated users or those having less than 1500 rating points). We will try not to delay Codeforces Beta Round #5, which will be opened for all. 

Wish you high rating,
MikeMirzayanov

Read more »

Announcement of Codeforces Beta Round #3
Announcement of Codeforces Beta Round #3
 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By MikeMirzayanov, 10 years ago, translation, In English,

It seems everyone is in the know that Codeforces Beta Round#3 didn’t take place in the appointed time. Seemingly, it happened because of the increased popularity of the site, on the one hand, and some of our bugs, on the other. For sure, it’s a pity that things went in such a way. On the other part, if everything had failed during the contest, it would have been worse. The contest is rescheduled for Sunday, 15:00 (Moscow time). Please be sure to check here for the start time in your time zone: http://www.timeanddate.com/worldclock/fixedtime.html?&day=07&month=03&year=2010&hour=07&min=00&sec=0&p1=179

I’d like to remind you that the project is in Beta yet, and we’ll work on the problem and try to fix it.

Thanks for your understanding,
MikeMirzayanov

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it