Hi, Here's the editorial.

Please note that not all the codes presented below belong to me. (It's a combination of codes from our problemsetters and testers) -- And I borrowed AKGMA's account since I wasn't able to link to my own submissions somehow!

Note: It seems that the Codeforces mark-up is not functioning. To see a submission go to: http://www.codeforces.com/contest/282/submission/submission-number

A: Bit++

Just use a simple loop. (Take a look at the Python code)

GNU C++: 3314442, 3314464

GNU C: 3314471

Python: 3314475

B: Painting Eggs

This one can be solved by a greedy algorithm. Start from the 1st egg and each time give the egg to A if and only if giving it to A doesn't make the difference > 500, otherwise give it to G.

To prove the correctness, one can use induction. The base case is trivial. Suppose that we've assigned the first n - 1 eggs such that the total money given to A is S_a and total money given to G is S_g. We can assume S_a ≥ S_g. Now we must either add g_n to S_g or add a_n to S_a. If we can't add g_n to S_g, then S_g + g_n > S_a + 500, so  - 500 > S_a - S_g - g_n, adding 1000 to both sides gives us the inequality 500 > S_a + (1000 - g_n) - S_g which is exactly what we need to make sure that we can add a_n = 1000 - g_n to S_a.

GNU C++: 3314480, 3314484

GNU C: 3314488

Python: 3314492

C: XOR and OR

First of all, check the length of the two strings to be equal. Then with a little try and guess, you can find out that the zero string (00...0) can't be converted to anything else and nothing else can be converted to zero. All other conversions are possible.

GNU C++: 3314503, 3314504, 3314509, 3314512, 3314514

D: Yet another Number Game

For n=1, everything is clear. If a₁ = 0 then BitAryo wins, otherwise BitLGM is the winner.

For n=2: define win[i][j] = (Whether i,j is a Winning position). It's easy to calculate win[i][j] for all i and j, using a loop (Checking all possible moves). This leads us to an O(n³) solution.

For n=3: Everything is similar to NIM, With the same statement of proof as for NIM, i,j,k is a winning position if and only if (i xor j xor k)  ≠ 0.[Don't forget the parentheses in code :) ] Complexity: O(1)

One can also solve this case using DP. We define lose[i][j]= (Least k, such that i,j,k is a losing position) ,lose2[i][j]=(Least k, such that k,k+i,k+i+j is a losing position) and win[i][j][k] just as the case with n=2. As in the codes below, one can calculate all these values in O(n³).

Using the same DP strategy for n=2 and the O(1) algorithm for n=3 and n=1, leads us to a total complexity of O(n²) which was not necessary in this contest.

GNU C++: 3314578, 3314580, 3314585, 3314588

E: Sausage Maximization

Can be solved using a trie in O(n log (max{a_i})).

Start with a prefix of size n, and decrease the size of prefix in each step. For each new prefix calculate the XOR of elements in that prefix and add the XOR of the newly available suffix (which does not coincide with the new prefix) to the trie, then query the trie for the best possible match for the XOR of the new prefix. (Try to get 1 as the first digit if possible, otherwise put 0, then do the same thing for the second digit and so on). Get a maximum over all answers you've found, and it's all done. [By digit, I mean binary digit]

GNU C++: 3314616, 3314619

We hope you enjoyed the tasks.

I think virtual contest must end as soon as all problems are solved.

It's quite unfit for it to continue while the user can do nothing more.

Итак, языком этого раунда является Io. Io (первая буква — заглавная i) — скриптовый, чисто объектно-ориентированный язык программирования с динамической типизацией. Язык был разработан Стивом Декортом (Steve Dekorte) в 2002 году. Реализация является кросплатформенной, открытой (лицензия BSD) и рассчитана на лёгкость встраивания в качестве скриптового языка (из Wikipedia). Версия, установленная на Codeforces — Io-2008-01-07 (Win32).

Одна из основных особенностей языка — минималистичность синтаксиса. Код знаменитой программы "Hello World!" на этом языке выглядит так:

"Hello World!" println

А вот пример решения задачи "A+B" (числа заданы на разных строках):

a := File standardInput readLine asNumber
b := File standardInput readLine asNumber
c := a+b
c println

Вы можете скачать интерпретатор отсюда и следовать инструкциям из дистрибутива для установки. Также дистрибутив доступен по ссылке. Пароль — f0ca4da70e5c5f80

Дополнительную информацию можно прочесть в Wikipedia, а документация доступна на официальном сайте здесь. Вы можете найти больше еще информации, используя Google. Удачи и веселого вам контеста!

Во время контеста, вы можете пользоваться вкладкой "Запуск", но мы не гарантируем ее работоспособность при большом ажиотаже. В таком случае будьте готовы установить интерпретатор локально.

Обратите внимание, что так как интерпретатор Io всегда возвращает код возврата 0 и не имеет возможности проверить синтаксис программы до запуска, то вердикты "Ошибка компиляции" и "Ошибка времени исполнения" будут отображаться как "Неправильный ответ".

Задачи не отсортированы от простой к сложной.

Для предварительной загрузки доступен зашифрованный по паролю архив. Контест задерживается примерно на 10 минут. Пароль будет доступен примерно за 1 минуту до начала контеста.

[Вольный перевод оригинального поста]

Всем привет!

Unknown language round #1 был проведен 21-го февраля и мы решили повторить этот эксперимент.

Он будет проведен по правилам обычного ACM-ICPC контеста. Единственная особенность раунда - задачи на нем можно будет сдавать, используя один-единственный язык программирования. Какой именно это будет язык? Пока - секрет! Мы надеемся, что вам придется его изучить во время контеста, а сам язык будет анонсирован примерно за одну минуту до начала соревнования.

Участие в этом раунде не повлияет на рейтинг - это такой веселый эксперимент. Задачи будут в большей степени ориентированы на умение писать код, чем на применение каких-либо алгоритмов.