drinkless's blog

By drinkless, history, 4 days ago, In English,

After reading the editorial for RCC Elimination round problem E, I thought of an easier problem of merging two strings such that the result is lexicographically minimal. Formally, a merge of two strings a and b is a string s of length |a| + |b| such that there exist two strictly increasing sequences of indices i1, i2, ..., i|a| and j1, j2, ..., j|b| such that a = si1si2... si|a|, b = sj1sj2... sj|b| and each index in s appears exactly once in i1, ..., i|a|, j1, ..., j|b|.

The above mentioned editorial provides an algorithm for solving this problem that works in time and uses hashes. Actually, this problem can be solved in linear time. The solution works roughly like this: maintain current position pa in a and pb in b. On each step, lexicographically compare the suffix of a starting at pa with the suffix of b starting at pb, and take a character from the suffix that is smaller (actually, for this to work, it is necessary to terminate each string with a character that is greater than any character in the strings, so that if one of the suffixes is a prefix of the other, the shorter suffix is considered larger, not smaller). The author proposes to compare the suffixes by using binary search and hashing, which takes time. However, this can be done in constant time.

Actually, this is a well known Longest Common Extension problem. One of the constant-time solutions is as follows: construct a suffix tree from the strings, then preprocess it using one of Lowest Common Ancestor algorithms that can answer LCA queries in constant time. It is easy to see that the lowest common ancestor of two leaves in a suffix tree that correspond to two suffixes can be used to find the length of the longest common prefix of those suffixes. From that, performing lexicographical comparison is easy.

It is possible to build and preprocess a suffix tree in linear time, so the overall running time is O(n), but the algorithm is quite complex. Does anyone know of a simpler algorithm with the (asymptotically) same running time?

Read more »

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

By drinkless, history, 3 months ago, In English,

Finally, TopCoder announced the dates of TopCoder Open 2017 Algorithm and Marathon Competitions. Since it is not trivial to find this information on their website, I will reproduce it here.

TCO17 Algorithm Competition will have a usual structure with three online rounds and two onsite rounds. The location and the dates of onsite rounds have yet to be announced, but the dates of online rounds are already known:

This year, 750 top contestants will advance from each sub-round of Round 1, 40 will advance from each sub-round of Round 2, and five from each sub-round of Round 3. Also, 250 TopCoder members with the highest rating advance to Round 2 automatically, as long as they competed in at least three rated TopCoder Algorithm rounds in total and in at least one such round between January 1 and Marth 31, 2017.

In addition to these online rounds, there will be six regional onsite rounds. To compete in any of them, it is necessary to be present at the event. These events are currently planned:

  • Regional event in Austin, TX: April 29, 2017.
  • Regional event in Saint Petersburg, Russia: May 7, 2017 (third year in a row).
  • Regional event in Beijing, China: June 24, 2017 (second year in a row).
  • Regional event in Warsaw, Poland: September 2, 2017.
  • Regional event in Pittsburgh, PA: September 7, 2017.

Also, there will be a regional event in India, but its exact location and date will be announced later. From each of these rounds, 10 top contestants will advance to a special Wildcard Round, which will be held on September 16, 2017 at 16:00 UTC. From this round, two highest-scoring contestants will advance to the onsite round. So, in total, 12 contestants will advance to TCO17 Algorithm onsite round.

In TCO17 Marathon Competition, there will be three regular online rounds plus some number of Lightning Rounds. The dates for the regular rounds are as follows:

In each regular round, top 30 contestants will be awarded points based on their place. Lightning Rounds, of which none is currently announced, will award fewer points. Top ten contestants who accumulate the most total points will advance to the onsite round.

Read more »

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

By drinkless, history, 6 months ago, In Russian,

... испытываю я после второго полуфинала TCO16.
С одной стороны, я не прошёл в финал. Это плохо.
С другой стороны, я выступил лучше, чем tourist. Это хорошо.

Read more »

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

By drinkless, history, 11 months ago, In English,

TopCoder Open 2016 Round 2C starts today at 17:00 UTC. Top 40 contestants will advance to Round 3. This is the last chance to advance. Those who have already advanced will be able to compete in a parallel round.

Good news for those who participate in IPSC: TopCoder has apparently decided to move this round so that it doesn't clash with it. Don't forget to register in time, registration closes five minutes before the round.

Read more »

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

By drinkless, history, 16 months ago, In English,

Facebook Hacker Cup 2016 is starting soon. Don't miss the qualification round, which starts at midnight UTC and lasts for 3 days. To advance, you will need to solve at least one problem.

This year's finals will be in London, so this is another chance for those who missed GCJ finals in 2013.

You can enter the round using this link, but you need to log into Facebook first.

Read more »

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

By drinkless, history, 23 months ago, In Russian,

Недавно мне, как финалисту Яндекс.Алгоритма, пришло письмо с документом, который мне предлагается подписать (английская версия). Насторожило меня уже то, как выглядит этот файл в их же собственном просмотровщике:

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

Содержимое меня, однако, опечалило. Вы там в Яндексе вообще читаете то, что предлагаете нам подписать? Или думаете, что мы, финалисты, подмахнём, не глядя? А то уже в первом пункте:

1.я ознакомлен и согласен с Положением о конкурсе «Яндекс.Алгоритм-2015», размещенным в сети интернет по адресу: algorithm.contest.yandex.ru/terms/ (далее — «Положение»)

Ну предположим, что то, что предложения обычно начинают с заглавной буквы, можно на время проигнорировать. Кому они нужны, эти правила? Больше беспокоит то, что по указанному адресу находится страница с ошибкой 404. Согласен ли я с тем, что там написано? Не уверен. Продолжим:

а также с Правилами конкурса «Яндекс.Алгоритм-2015», содержащими условия и правила проведения мероприятия – конкурса «Яндекс.Алгоритм-2014», проводимого ООО «ЯНДЕКС» (далее – Организатор) в срок с 21 апреля 2015 года по 6 августа 2015 года (далее- «Конкурс») по адресу: algorithm.contest.yandex.ru.

Даже не знаю, что более странно: то, что правила Яндекс.Алгоритма 2015 содержат правила Яндекс.Алгоритма 2014, или то, что Яндекс.Алгоритм 2014 проводится в 2015 году?

3.В случае своей победы в Конкурсе (занятия одного из призовых мест, дающих, в соответствии с правилами проведения Конкурса, право на получение приза), я получу денежный приз, предусмотренный п. 10.3. Положения, в зависимости от занятого места.

Смотрим этот пункт:

10.3. Победители обязаны предоставить Организатору Конкурса указанные в п. 10.2 Положения документы в течение 14 календарных дней после определения Организатором Победителей конкурса в порядке, предусмотренном п. 7.3 Положения.

Не очень понятно, что за денежный приз он предусматривает.

4.Я осознаю, что денежный приз мне будет выплачен в российских рублях за вычетом налога на доходы физических лиц в размере _____, исчисленного в соответствии со ст. 224 Налогового Кодекса РФ.

Это вообще что, проверка того, знаю ли я налоговое законодательство? Кстати, в англоязычной версии ставку налога вписывать не нужно. Видимо, англоязычным финалистам для участия знать налоговый кодекс РФ необязательно.

В общем, повнимательнее нужно относиться к документам.

Read more »

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

By drinkless, history, 2 years ago, translation, In English,

This year's TopCoder Open includes, in addition to onsite final round, four onsite events, which take place in various cities around the globe simultaneously with the sub-rounds of round 2. As a result, the times for these rounds become known later than usual. The times for rounds 2A, 2B and 2D have already been announced, and now the time for round 2C is announced as well.

Round 2C will take place on July 18th in Tokyo, at the office of Dwango Co.

Kabukiza Tower

Like on the other onsite events, there will be a hackathon and t-shirts. Unlike the other onsite events, there will be round 2 explanation by iwiwi and rng_58. The event will begin at 11:00 AM local time, and the round itself will start at 3:00 PM (6:00 AM UTC). There will be a parallel round for onsite participants who didn't advance to round 2, as well as for everyone who have already advanced to round 3. If you plan to participate in the onsite event, don't forget to register, because just 100 participants would be able to do it.

As a reminder, all onsite events are optional. If you advanced to round 2, you can participate online.

Read more »

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

By drinkless, 2 years ago, translation, In English,

TopCoder announced the dates of TopCoder Open 2015 rounds 2B and 2D, as well as the details of the corresponding regional events. Round 2B will take place on June 20th in San Francisco, at MemSQL headquarters.

MemSQL headquarters

Read more »

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

By drinkless, 2 years ago, translation, In English,

Yandex.Algorithm 2015 Qualification Round begins soon. It is the last chance for those who didn't participate in the warm-up round or haven't solved at least one problem to advance to the elimination rounds, which will take place on May 24th and 30th and on June 6th.

The round will last 100 minutes and will be a virtual contest: each participant will be able to choose start time in the period between May 16th 21:00 and May 17th 21:00 UTC. This means that some participants may potentially be competing until 22:40 UTC, so please don't discuss the problems until that time. To advance to the elimination round, it is necessary to solve at least one problem.

Read more »

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

By drinkless, 2 years ago, In Russian,

Два с половиной месяца назад прошёл Rockethon 2015, 150 лучшим участникам которого обещали футболки. И вот 21 апреля звонят мне из UPS и говорят, что меня ждёт футболка от Rocket Fuel. Ждёт на таможне. Чтобы её пропустили, нужно зайти на сайт, заполнить там форму, отправить скан паспорта, подтверждение заказа и прочие документы. Странно, ведь другие футболки я получал безо всяких сложностей — получаешь извещение, приходишь на почту и забираешь.

Сайт для отправки документов какой-то кривой: своё имя ввести не даёт, вместо этого предлагает выбрать из трёх вариантов (и все три неправильные). Судя по всему, все футболки были оформлены одним заказом, и там видны данные других получателей. Ну и пароль он почему-то не всегда принимает. Ещё там можно посмотреть список остальных футболок и кто там чего навводил.

P.S. Отдельное спасибо UPS за паспортные данные участников sexyprincess91, Milanin и Igor_Kudryashov, которые имели неосторожность эти самые данные ввести. Правильным путём идёте, товарищи!

P.P.S. Не успел.

Read more »

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

By drinkless, 2 years ago, translation, In English,

TopCoder announced recently that they are planning regional onsite events coinciding with TCO 2015 round 2. Now it is known that the first of these events, round 2A, will be held on May 31st in Saint Petersburg, Russia, at ITMO University.

ITMO University

In addition to the round itself, the schedule includes a hackathon with $5000 in prizes. The first 150 attendees will receive t-shirts (registration is required). The event will start at 9:00 AM Moscow time, and the round itself will start at 3:00 PM (12:00 PM UTC). Those who will not advance to round 2 will be able to compete in a parallel round. If you would like to participate in the hackathon, you will need to register no later than May 28th (Moscow time).

By the way, it is already possible to find the locations of the other onsite events: round 2B will take place in Tokyo, round 2C in San Francisco, and round 2D in Jaipur, India.

Read more »

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

By drinkless, 2 years ago, translation, In English,

Russian Code Cup 2015 WarmUp Round will take place today at 10:00 UTC. Results of this round won't affect subsequent participation in RCC 2015, so this round can be viewed as a training before the qualification rounds. The contest lasts 2 hours, problem statements will be in Russian. The qualification rounds will take place on March 28th, April 25th and May 31st.

Read more »

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

By drinkless, 2 years ago, translation, In English,

The third round of Facebook Hacker Cup 2015 will take place exactly one week after round 2: on January 31st at 9:00 PM UTC. The round will last 3 hours. Top 25 participants will win a trip to Menlo Park to participate in the final round, which will take place at Facebook office on March 6th.

Participants will be able to enter the contest using this link, and the scoreboard will be available to everyone here.

Read more »

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

By drinkless, 3 years ago, In Russian,

Два часа назад TopCoder разослал всем присутствующим на онсайте TCO14 письмо. Содержание письма не столь важно, а важно то, что в поле "Копия" перечислены e-mail'ы всех присутствующих на онсайте, в общей сложности 557 адресов. Спасибо тебе, TopCoder!

Read more »

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

By drinkless, 5 years ago, translation, In English,

Google Code Jam Round 3 starts today at 14:00 UTC. Top 25 contestants will win a trip to New York City for a final round (they will also get their T-shirts a bit earlier).

Read more »

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

By drinkless, 5 years ago, translation, In English,

ICPC Challenge will start today. ICPC Challenge is an additional contest for ICPC finalists where they have two weeks to solve a single game problem. After that, a double-elimination tournament will be held between the team's submissions. The results will be announced at the finals. The teams who take the top places will be awarded prizes.

Solutions in C++ and Java are accepted. Unfortunately, participating out of competition is not permitted. However, statements are available to everyone. ACM recently offered an open contest based on the last year's problem, but it is already over.

Read more »

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