Автор AlexSkidanov, 12 лет назад, По-русски

MemSQL с радостью сообщает о проведении второго ежегодного соревнования по программированию Start[c]UP 2.0. Start[c]UP 2.0 проводится на платформе Codeforces и состоит из двух раундов.

Раунд 1 состоится онлайн 27 июля в 21:00 мск и будет проведен по стандартным правилам Codeforces. На нем будет представлено пять задач, сложность которых сопоставима со средним раундом на Codeforces, раунд является рейтинговым и длится 2.5 часа. Для участия в первом раунде допускаются все желающие.

Раунд 2 состоится одновременно онлайн и онсайт 10 августа в 21:00 мск и будет проведен по стандартным правилам Codeforces. Будет представлено шесть задач, сложность которых, по нашей оценке, превосходит средний раунд на Codeforces. Раунд является рейтинговым и длится 3 часа. Во втором раунде могут участвовать только участники, занявшие первые 500 мест в первом раунде. Лучшие 100 участников второго раунда получат футболки Start[c]UP 2.0.

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

UPDATE: в первом раунде будет предложено шесть задач, а не пять, как было объявлено ранее

  • Проголосовать: нравится
  • +592
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +25 Проголосовать: не нравится

Note that July 26th is also the date of TCO round 3A — it'd be good to avoid collisions as early as possible.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

Round 1 follows regular Codeforces rules and consists of 5 problems. For this round, the complexity of the problems will be comparable to a regular Codeforces round.

Division 1 or 2?

»
12 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится -37 Проголосовать: не нравится

Deleted.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

sorry if this seems like a stupid question, but what does the [c] in Start[c]UP signify?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

"**The top 100 in round 2 will receive a Start[c]UP 2.0 T-shirt.**" I like it :)

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

No unofficial participation in round 2 for those who didn't finish in top 500 in round 1?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -37 Проголосовать: не нравится

where can i get the competition

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -20 Проголосовать: не нравится

July 27th??!! That's the first day of NOI~~!!

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is it rated??

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

It is said that both round will follow regular Codeforces rules, while first will last 2,5h and second 3h, I think you should mention this in an announcement.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

When is the final round? I wish if you can announce this as early as possible. I live near to San Francisco, and I was invited to the final last year but I couldn't make it because I was outside the US at the contest's time.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

So late in such countries as China or Japan... The previous rounds are interesting. What a pity!:(

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

OMG! It is 1 a.m. Monday in China...:D end at 3:30... rating updated at about 4... then go to bed... And at 7 a.m I should go to the railway station and go to school. The train will cost me 8 hours... Monday is too busy for me to have a rest! Amazing Monday!

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Oh No~ 10:00AM PST, 1:00AM BEIJING

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -50 Проголосовать: не нравится

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

#include<iostream>
using namespace std;

int main()
{
  int a, b, c; cout<<"Vedite a b c";
  cin >>a; cin >>b; cin >>c;
	if(a>0)
	{
		if(b>0)
		{
			if(c > 0)
			{cout<<"a b c > 0";
			else
			{
			cout<<"c < 0";
		}
		}
		else 
		{
		cout <<"b < 0";
	}
}    else
		{cout<<"a < 0";
	}
	return 0;
	system("pause");
}
»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

What is the programming language I can use in this competion?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Wow I have always wanted a Start[c]UP 2.0 t-shirt! Very intriguing prize! Good luck to all participants as I am at camp and will not be able to participate.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

the complexity of the problems will be comparable to a regular Codeforces round

Regular Div1 or regular Div2?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

I tried to register for the MemSQL constest but I got an exception "The contest does not allow self registration". Can anyone register me?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Registration is running, but it's "Private Registration" !!! What's going on!?!??! :D

»
12 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

When I try to register it says — "The contest does not allow self registrations".
Edit: Thanks, it is fixed.

»
12 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится -21 Проголосовать: не нравится

Пацаны, а как же ДК Ворскла?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -27 Проголосовать: не нравится

Неужели тут нет поклонников украинского футбола?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Can people in div 2 participate in this contest and be qualified for round 2 if they come in top 500 ??

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Раунд будет рейтинговым для обоих дивизионов?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Just noticed that logo of memsql is very similar to that of Mumbai Indians, one of the Indian Premier League teams.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is this for DiV 1 or DiV 2 ?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

we are muslims we will be having breakfast as it is the last day in holy Ramadan :) 27th

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

The contest will be rated for both div1 and div2 participants?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +22 Проголосовать: не нравится

ВКонтакте недоступен, видимо, его разработчики тоже хотят футболки :)

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Anyone can tell score of problems?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

This contest start at the same time of (Iftar)
It will add another 2.5 hour to 16 hour without eating :D :D

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -12 Проголосовать: не нравится

I don't think will have ocasion to continue with round 2

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

contest is not simple !

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

На чем ломали B? И как решать С?

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    У меня сломали B на не разобранном отдельно случае Y == 0.

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    С http://pastebin.com/8XiqfxpL прошло претесты, идею могу объяснить, но еще нет вердикта финального тестирования.

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +11 Проголосовать: не нравится

      Ну еще бывает n=1=m, а так правильно

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        Эх, первое решение было другое, на нем все это тестил, на втором ощущение протестированности осталось( Спасибо.

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
        Rev. 2  
        Проголосовать: нравится +8 Проголосовать: не нравится

        А чем плохо решение вида посчитать, сколько комбинаций с K нужными картами, поделить на количество комбинаций с хотя бы одной нужной картой, умножить на K/M и прибавить к ответу? То есть оно выдаёт неправильный ответ на 4 4, например, но я не понимаю, почему.

        • »
          »
          »
          »
          »
          12 лет назад, скрыть # ^ |
          Rev. 3  
          Проголосовать: нравится +10 Проголосовать: не нравится

          http://mirror.codeforces.com/contest/452/submission/7274849

          Решил чем-то схожим с описанием выше.

          Ну суть казалось бы очевидна. Пусть выбрана карта X. Вероятность того, что в выбранных n картах, есть i карт, таких что, их тип совпадает с картой X равна .

          Правда, во время контеста рассуждал несколько иначе, и почему-то тоже выдавался неправильный ответ на тест 4 4. Считал ту же самую вероятность но по иной формуле.

          P.S. Буду благодарен, если кто-нибудь объяснит, почему последняя формула неверна. Казалось бы, это обычное выражение вероятности появления двух событий, через условную вероятность (второй множитель).

          • »
            »
            »
            »
            »
            »
            12 лет назад, скрыть # ^ |
            Rev. 2  
            Проголосовать: нравится 0 Проголосовать: не нравится

            Горе мне, я неправильно прочитал условие и подумал, что выбирается одна карта из каждой колоды. Что же, спасибо за объяснение!

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    В В ломали на тесте 2 2

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Ну у меня один взлом — человек думал, что всегда выгодно делать 3 линии около 1 диагонали, а на самом деле иногда (2 1000) нужно сделать "конверт" (2 диагонали + сторона)

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +7 Проголосовать: не нравится

      Удивительная задача. Ведь не нужно было даже думать, чтобы ее решить. Очевидно предполагаем, что точки должны быть распиханы по углам прямоугольника. Берем несколько точек из окресностей углов. Потом за O(k^4) ищем ответ

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

How was problem C to be solved?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

How to solve problems B, C, D, E, F ?

  • »
    »
    12 лет назад, скрыть # ^ |
    Rev. 3  
    Проголосовать: нравится 0 Проголосовать: не нравится

    For B, most probably the zig zag pattern made by (0,1) (n,m) (0,0) and (n,m-1) was the 4th one to be checked. The other 3 were only X-axis, only Y-axis and the 2 diagonal-one maximum side pattern. This passed pretests. Not sure though. System tests would tell us better. --- Nope, failed systests -- The method is right. Mine failed because of a typo :P

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

На чем ломали А, неужели кто-то читал эти странные длинные переборы?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Pretests were very weak again!
Lots of solutions on B, C, D will fail.........:SS

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Can somebody please explain D

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +53 Проголосовать: не нравится

Contest finished! But personally, I didn't like the idea of putting the arrays of names in problem A in sample test explanation place; because I think many people (including myself) do not check the explanation when they understand the statement. Maybe it was better if they were higher.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Cmon, place your bets! Who thinks this solution will pass the final tests? Hurry up!

7269849

»
12 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +6 Проголосовать: не нравится

I got a kind of stupid solution at B and got hacked. I passed the hack 3 seconds before end of constest. :)) I hope it passed.

Edit: It passed. :)) Thanks to the hacker.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I scared I will get down rating !

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

Как решать E без суффиксного дерева?

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +32 Проголосовать: не нравится

    Можно с суффиксным автоматом, например :)

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +13 Проголосовать: не нравится

    суффиксным автоматом :)

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +15 Проголосовать: не нравится

    Просто суффиксным автоматом. Строим суффиксный автомат для S1#S2$S3. В каждой вершине будем держать три числа a1, a2 и a3 — количество вхождений данного состояния в каждую из трёх строк. Прогоним S1, S2 и S3 по автомату, инкрементируя соответствующие счётчики.

    Но это ещё не всё: мы пока только инкрементировали в состояниях, соответствующих префиксам S1, S2 и S3, а подстрок у этих строк больше. Поэтому надо распихать эти добавки по суффиксным ссылкам. Суффиксные ссылки образуют дерево, обходим его DFS'ом, прибавляем к числам a1, a2, a3 в вершине числа из её сыновей.

    Теперь каждая вершина прибавляет к ответам на отрезке длин [suf->len + 1, len] произведение a1 * a2 * a3. Можно в оффлайне поприбавлять все ответы, получится решение за O(N).

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    У меня была идея использовать суфмасс, но не смог довести до ума, сдал суфавтомат. Потом мб додумаю и расскажу.

  • »
    »
    12 лет назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится +11 Проголосовать: не нравится

    Я суфф. массом решал.

    Как-то просто совсем получилось:

    1. Строим суфф. масс + ЛЦПшки.
    2. Далее понимаем, что при некотором фиксированном l нас интересуют некоторые подотрезки массива ЛЦПшек.
    3. Ну и победа, итерируемся по длине от большой к меньшей, мерджим эти отрезки в ДСУ, обновляем ответ.
»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is there any particularly tricky corner case for problem B?

I see many successful hacks, but I can't come up with any special case.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Running java programs with -Xmx512m and ML 256m is evil. I've spent most of the contest trying to make sure that my E fits in ML regardless of GC behavior :(

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Why not use "Off heap" memory? No GC, smaller memory footprint.

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +12 Проголосовать: не нравится

      I don't know much about off-heap memory, but I actually need GC functionality. The problem is as follows. With an implementation of suffix trees which I use (nice, readable and object-oriented, not the horror from e-maxx), total memory which is really used is pretty close to ML. Since there is Xmx512m option, theoretically nothing prevents java from growing it (by a constant factor) above ML (it thinks that it has 512m available, so it can decide to allocate a bit more in advance).

      So I decided to use an optimization: instead of Node[alphabetSize] store list of pairs (char, Node) until it grows to some constant, and then free it and use full-sized array. However, my calculations show that if GC does not reuse the memory which was freed, theoretically it is again possible to go dangerously close to ML (on logarithmic scale).

      Anyway experiments show that even my first submission passes all tests with "memory used" 188400 Kb. Maybe I'm overly paranoid, but I want my solution to be guaranteed to pass, not just pass by luck. And IMO setting "Xmx" to match actual ML would be a very good idea.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

contest really hard, hard and very hard (with me)

»
12 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Как D нужно было решать? Написал решение "в лоб", упадёт на тестировании скорее всего.

UPD: Упало на тестировании.

  • »
    »
    12 лет назад, скрыть # ^ |
    Rev. 3  
    Проголосовать: нравится +5 Проголосовать: не нравится

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

»
12 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится -77 Проголосовать: не нравится

Difficulty of problems, my impression:

A,B — div2 A

C,D — div1 B (I find D easier than C)

E,F — div1 D-E

Yet another situation (after Zepto Code Rush) where the problems are split into easy and hard ones, and time is the main tiebreaker on the easy ones. Although I don't know how many pretests there are, so I can fail on any of B,C,D during the systest.

I can write it in bold caps: MY IMPRESSION. Also, before systest.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Как решать F?

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +83 Проголосовать: не нравится

    Идём по числам слева направо, держим строку in длины N, где стоят единички в позициях, соответствующих значениям уже встреченных чисел.

    Что значит, что текущее число x является (a + b) / 2 для каких-то a и b по разные стороны от него? Это значит, что есть a и b на одинаковом расстоянии от x, такие, что in[a] != in[b]. А это значит, что строка максимальной длины с центром в x не является палиндромом. Значит, осталось идти слева направо и поддерживать, например, в дереве отрезков, хеши для прямой строки и обратной. В каждой позиции делаем запрос, проверяя, палиндром ли строка в текущей позиции.

    • »
      »
      »
      12 лет назад, скрыть # ^ |
      Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      Для примера
      5
      1 5 2 4 3
      Строками in будут являться следующие?
      10000
      10001
      11001
      11011
      11111

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +5 Проголосовать: не нравится

        Да.

        Соответственно, в момент, когда мы добавили двоечку (строка: 11001), подстрока с центром во второй позиции (110) не является палиндромом. Палиндромность ломается в первой и третьей позиции, это как раз и значит, что троечка и единичка находятся по разные стороны от двоечки, что и нужно.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Yeah ! I accepted only once problems A

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

why my solution for problem A skipped?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +23 Проголосовать: не нравится

very fast system testing! :)
thank you very much! :)

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

congratulations sevenkplus !

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Wow very fast systest (considering this is a special round with a lot of participants).

Anyway, why problem C has the same point as B? I think problem C is much harder....

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Will you be providing the editorial?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +68 Проголосовать: не нравится

Sorry, I didn't like any of problems from A to D at all, can't say anythig about E and F though. And seriously, how is D being D? It is much much easier than B and C!

»
12 лет назад, скрыть # |
Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

My answer is correct for problem B, pretest 1, submission #7269214

1 1
0 0
1 0
0 1

But verdict is

wrong output format Unexpected end of file &mdash; int32 expected
  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    A possible reason is that you output newline as '\n' rather than endl. Remember that test machines are running Windows, which uses "\r\n" as line separator.

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +26 Проголосовать: не нравится

    Your output is empty. And you've shown the right answer

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Ah, yes. How stupid of me! But the reason I got confused is because my compiler was producing correct output. I found the problem to be compiler specific, in my machine the code outputs different but correct answer:

      0 0
      1 1
      0 1
      1 0
      

      My compiler info:

      >>> g++ -v
      Using built-in specs.
      Target: x86_64-linux-gnu
      Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.4.7-8ubuntu1' --with-bugurl=file:///usr/share/doc/gcc-4.4/README.Bugs --enable-languages=c,c++,fortran --prefix=/usr --program-suffix=-4.4 --enable-shared --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.4 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --disable-libmudflap --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
      Thread model: posix
      gcc version 4.4.7 (Ubuntu/Linaro 4.4.7-8ubuntu1) 
      

      I used direct comparison between doubles (a == b), which failed in judge compiler.

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    I changed double in your solution to long double and it got AC

»
12 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

First of all , problems were awsome. B was harder than expected and D and E were interesting. C was maths , but I liked it.

On the other side , I think the pretests at C were weak. I put m instead of n in one place ( in a for ) and because of that it didn't passed. I think that pretests are made for this kind of situations.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Thank you for tasks E and F. Looking forward to reading the solutions to those.

I didn't like the rest of the tasks though. A and B were "let's see who forgets to code one if". Disliking C is my personal opinion — but I heavily dislike N <= 1000 when there is O(1) solution. As for D, I only have to say that I haven't even read the part "Moreover, after a piece of laundry is washed, it needs to be immediately moved into a drying machine, and after it is dried, it needs to be immediately moved into a folding machine", and my "solution" still was accepted.

  • »
    »
    12 лет назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится +7 Проголосовать: не нравится

    A: A is to guarantee that most contestants get at least one AC.

    B: Apparently B has a better solution than a bunch of if's.

    D: Perhaps the two problems have exactly the same answer. Who knows? Can you construct a counterexample?

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      about D: I think he meant that it was not reasonable to include it to the statement at all.

    • »
      »
      »
      12 лет назад, скрыть # ^ |
      Rev. 2  
      Проголосовать: нравится +1 Проголосовать: не нравится

      D: No, I can't. If there is an easier approach, which can be written by accident or in wrong belief that it's the correct one; then it's authors' job to differentiate two approaches. If they haven't foreseen this approach, well, it happens sometimes. Still doesn't make it a good task. If they have known about this solution (but just couldn't find a counter-example), then this task shouldn't even be given, or that extra text should have been removed and the task should be given with less points.

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +16 Проголосовать: не нравится

        The problems are equivalent I think. There is no difference between having a piece of laundry wait before it goes into the first dryer or having it wait in between consecutive dryers.

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +45 Проголосовать: не нравится

    In my honest opinion, not having the restrictions hint to the complexity of the solution adds to the difficulty of the problem. I couldn't figure out problem C for some reason. But I bet I would have had better chances if the author had written N <= 10^9. Then, my brain would have been focused on finding a formula, not all over the place thinking about DPs and such.

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Well, If you code ifs in A or B they solved their task to diferrentiate people who will write and debug tons of ifs and those who will write 5-lines solutions where one can't have bug.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -18 Проголосовать: не нравится

Самотроллинг=)

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

Похоже, что синдром задачи D снова разразился с новой силой. Абсолютно дебильная задача безо всякой идеи получает баллов больше, чем тервер и геома с частными случаями. Можно только порадоваться за тех, кто начинает читать с задачи D. Авторам рекомендую проверять как-нибудь, стоит ли задача своих баллов. Вот такой код 7267906 для задачи D — это просто смешно. Поймал багу в B — и пошел глубоко вниз, потому что задачу D даже собака сдать может.

А так, если расставить баллы за задачи по-другому, то вполне себе хороший набор задач. Спасибо авторам.

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +8 Проголосовать: не нравится

    Еще более простой код: 7271703 P.S. Я сам еще не умею писать динамики, но посмотрев твоё решение, разобрался, как тут можно было поступить =)

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Problems were very interesting...!! Thanks to authors... Nice contest...!!!

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

Мало кто знает, но боль выглядит именно так sqrt((double)n*n+(m-1)*m-1)

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +29 Проголосовать: не нравится

How to create a good test for problem F?

I accepted the following flawed solution consisting of two steps.

  1. A naive approach would be: for each number x in the permutation, for all possible deltas y, check whether x - y and x + y are on different sides of the x. A partial solution is to check only the MAX first and MAX last values of y in this approach. In my solution, MAX = 60.

  2. Another naive approach reduced to a partial solution is: for each position t in the permutation, look at values at positions s from t - MAX to t + MAX, check if p[t] is between p[s] and 2*p[t] - p[s]. Again, MAX = 60.

Looks like random test with only one valid pair (a, b) as an answer would make this solution fail with a good probability. So, is it possible to create such a test? If it is possible, how to do it?

  • »
    »
    12 лет назад, скрыть # ^ |
    Rev. 3  
    Проголосовать: нравится +13 Проголосовать: не нравится

    Test with only one valid pair can be constructed in this way. If you know a permutation p1...pn which has no valid pair then 2*p1-1,...,2*pn-1, 2*p1,...,2*pn will also have no valid pair for example 1 9 5 13 3 11 7 15 2 10 6 14 4 12 8 16 . Now if you will move for example leftmost even number to the left of the rightmost odd less than n/2 then you will have one valid pair in the example 1 9 5 13 3 11 2 7 15 10 6 14 4 12 8 16

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +5 Проголосовать: не нравится

      In general, if you take a permutation without valid pairs and swap two adjacent elements, you would get at most two such pairs. And with a good probability, you get only one.

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you, this construction seems to do the trick.

      By the way, the problem's test set catches me if I try using only the first part of the solution above, but lets me pass if I use only the second one.

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      While the test you provided is what I literally asked, it does not break the second partial solution. In your example, 2 and 7 end up being too close. If we move 2 further to the left, more valid pairs will appear, such as 2 4 with 3 between them. Similarly, moving 7 further to the right soon produces the pair 13 7 with 10 between them. The problem seems to persist if we build a larger example following the same procedure.

      So, how to break that partial solution, too? It would help to insert some "garbage" between 2 and 7 in the example, but we don't have any "garbage" left if we follow the procedure.

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
        Rev. 4  
        Проголосовать: нравится +3 Проголосовать: не нравится

        Look at this permutation a = { 1 5 2 6 3 8 7 4 }. For each pair (i,j) index of (a[i]+a[j])/2 is not i+1 and is not j-1. This means that in each valid triple no two are adjacent. Valid triples are 1 2 3 , 5 6 7, 2 3 4. Now consider we have the permutation [1 9][5 13][3 11][7 15][2 10][6 14][4 12][8 16] in each bracket the numbers give the same remainder when divided by 8. Now replace in permutation a[] whith this brackets according to their remainder. You will get [1 9][5 13][2 10][6 14][3 11][8 16][7 15][4 12] in this permutation the valid pairs can be only with the same remainders as in permutation a[]. i.e. from group [1 9]-[2 10]-[3 11] can be choosen respectively triples and each member of the triple can be from its respective group for example 9 10 11 are choosen from the first second and third brackets. Now imagine you have constructed a big permutation as before and replaced all brackets according to their place in a[] then in each valid triple members will be far from each other because in a[] in each triple the distance of each two is at least 2.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I enjoyed problem C very much as it has a very small and smart solution. And I am really eager to know how B can be solved without the use of more than 6 or 7 if. I can't solve B but any solution i see use more than 10 if !

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

In problem A I failed this test case 6 ......

but I assumed that there must be at least one letter in the input from the problem's statement "you already know some letters" and "fits the length and the letters given"

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -22 Проголосовать: не нравится

I had thought accepted problems F with randomize (YES or NO)

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -79 Проголосовать: не нравится

I now see why I failed B. One line that I forgot to remove from an older solution: if(N > M) swap(N,M);. I got AC after removing it. (submission during the contest: 7262088, after the contest: 7271312)

Therefore, my opinion that it's div2 A level holds.

My solution was: we either use the strategy from sample 1 (diagonal, vertical/horizontal line, diagonal) or the first obvious greedy (longest non-diagonal starting in a corner, diagonal, longest non-diagonal starting in the other corner). Special cases N = 0 or M = 0.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +25 Проголосовать: не нравится

When will the contest be rated usually in codeforces?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +29 Проголосовать: не нравится

Why is rating update taking so long?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +51 Проголосовать: не нравится

Country wise rankings for this contest has been updated. (link)

»
12 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

A: "кроме того, вам уже известны некоторые буквы"; "...строчная латинская буква (если соответствующая буква известна),". Правалиал на Теcте 9: "6 ......". Можно ли считать такой тест коректным......

  • »
    »
    12 лет назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    слово состоящее из шести букв есть только одно — espeon.

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится -8 Проголосовать: не нравится

      Я про то, что тест противоречит написаному в описании задачи.

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
        Rev. 2  
        Проголосовать: нравится 0 Проголосовать: не нравится

        Он ничему не противоречит. Некоторые можно понимать, как "некоторое множество". Множество может быть пустым.

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
         
        Проголосовать: нравится -11 Проголосовать: не нравится

        В кросворде неможет быть неразгадонного одного слова, у которого неизвесна ни одна буква. И кроссворд — это минимум одно пересечение, т.е. минимум два слова.

        • »
          »
          »
          »
          »
          12 лет назад, скрыть # ^ |
          Rev. 3  
          Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            12 лет назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится

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

            (условие)

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, скрыть # ^ |
               
              Проголосовать: нравится 0 Проголосовать: не нравится

              Из википедии: "Кроссворд, как и многие игры, не имеет строгих правил и жёстких ограничений". Что мешает тому, что весь кроссворд состоит из одного слова?. Или тому, что наше слово не имеет пересечений с остальными. Но да, прошлый комментарий я написал, не прочитав условие :)

              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, скрыть # ^ |
                 
                Проголосовать: нравится 0 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, скрыть # ^ |
                   
                  Проголосовать: нравится 0 Проголосовать: не нравится

                  "не имеет строгих правил и жёстких ограничений". Еще раз цитирую. А Вы пытаетесь их навязать. Библия не является кроссвордом, потому что она не является головоломкой, которую следует заполнять словами.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, скрыть # ^ |
                   
                  Проголосовать: нравится +8 Проголосовать: не нравится

                  "... не является кроссвордом, потому что ..." — С чего бы это? Прочитайте свою цитату: "не имеет строгих правил и жёстких ограничений"

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, скрыть # ^ |
                   
                  Проголосовать: нравится 0 Проголосовать: не нравится

                  Потому что то, что я написал выше -- это правила составления кроссворда, а не лексическое значение слова. В лексическом значении этого слова присутствует слово "головоломка"

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, скрыть # ^ |
               
              Проголосовать: нравится 0 Проголосовать: не нравится

              Может ли считатся, что я взял кросворд из 1 слова и почти его решил — неразгодал ни одного слова?

          • »
            »
            »
            »
            »
            »
            12 лет назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится

            Ну тут надо переписовать понятие слова "слово". А позже я согласен с тем, что кросворд может быть из 1 слова, если оно пересекаеться само с собой, например "espeon".

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +31 Проголосовать: не нравится

When will Ratings be updated ?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

waiting for the editorial :)

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Ratings are updated!

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Still Div1!

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

В задаче F проходил квадрат с отсечением по времени. Это из-за того, что нельзя создать анти-тест или это недочет авторов?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Let's go to next round!

»
12 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится +24 Проголосовать: не нравится

I solved F using pretty weird observation:

If answer is NO, then parities of elements in our sequence look sth like:

0000000000010001111111111111 / 1111111111100110000000000.

I mean, almost all odd numbers are before almost all even numbers or the other way around. Some inversion are possible, but only a small amount of them. Does anyone can provide appropriate bound for numer of those inversions? I bruteforced small cases and for n=10, there were at most 4 inversion, for n=13 at most 6, so I assumed that n + 10 is a safe bound and it passed. I checked manually whether those inversions are a part of a bad triple and later call recursively for odd and for even numbers which resulted in a O(n log n) solution. But I still don't know why it is correct :P.

Unfortunately I got one integer overflow in my solution and it wasn't accepted :(. After adding "1ll * " it passed ;/.

  • »
    »
    12 лет назад, скрыть # ^ |
    Rev. 4  
    Проголосовать: нравится +16 Проголосовать: не нравится

    During contest I found a paper that said that if n>11 then the parity of the first floor(n/2)-6 was the same and the parity of the last floor(n/2)-6 was also the same. However, I didn't come up with your solution; nice one!

    Edit: paper

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Why those papers are always so long :(? How have you managed to prove that observation? I don't feel like reading those 15 pages xd.

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        I actually just skimmed the paper to see if I could find ideas for a probabilistic algorithm. Without having read it in detail it seemed to me that a great part of those 15 pages were devoted to prove this, so I think it mustn't be easy to prove. One think that bothers me though is that if I understand the theorem correctly the correct structure would be more similar to: 00000000000/11111111111 or 1111111111/00000000000 since we can't have 0s at both sides (we would have 2*(n/2-6)>n/2) though this is not true for n<24

        Would your algorithm still work with this 'structure'?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится
»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

please anyone explain how to solve D?

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +2 Проголосовать: не нравится

    Straight forward implementation.

    We will simulate the process second by second.

    For each machine, keep a list of pieces inside the machine right now and for each piece save its entrance time.

    Every second, remove from machine(3) the pieces whose entrance_time + t3 == current_time. Do the same for machine(2) moving pieces to machine(3). Same for machine(1)

    Now at the end of each second, try to put as much new pieces in machine(1) as possible.

    You need to check that there is an empty place in machine(1) right now and that there will be an empty place in machine(2) after current_time+t1 and in machine(3) after current_time+t1+t2.

  • »
    »
    12 лет назад, скрыть # ^ |
    Rev. 3  
    Проголосовать: нравится 0 Проголосовать: не нравится

    Need to find a time when every thing is finished.

    Thing can start washing (drying or ironing) if the machine is free.

    That is if i - n[j] >= 0 then T[i] (beginning the process) = max( T[i - n[j]], T[i] ) else T[i], j is number process, i is number thing.

    End process is T[i] = max( T[i - n[j]], T[i] ) + t[j] or T[i] += t[j].

    Necessary to calculate the time after completion of each process. Answer is T[k].

    Source code: 7271703.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

I'm waiting for the editorial,it's so sad that I couldn't solve any problem last night TAT

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

I'm sorry to ask this, but when the editorial will be published? Since i'm a newbie in competitive programming i can't understand most of the problems. It would be very helpful for people like me if you publish an editorial on the contest. Thanks in advance :)

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

А разборы где?

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    Это официальные соревнования и, по-видимому, на них разбор задач появляется не сразу. Или же авторы просто забыли.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Contestant thank you for good contest.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Can we expect an editorial here?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

In problem C, Some of the tops I see have used something like a log table. Can someone explain what log array has to do with this?

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +25 Проголосовать: не нравится

    I had logs in my solution, just to prevent floating-point overflow. I was handling probabilities by counting the number of ways of choosing cards under certain conditions, and dividing at the end by ALL the possible ways. But these numbers (1000000! / 999000!) are far too large for doubles. So I worked with their logs instead. You don't lose too much precision.

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +14 Проголосовать: не нравится

      Since every binomial in the solution has k ≤ 1000, another trick is to multiply and divide at the same time at most k times:

      double r = 1;
      for(int j = 0; j < k; j++) {
          r *= n-j;
          r /= j+1;
      }
      
    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      I used the formula , and it worked in this task as well:

      double ncr[1111][1111] = {0};
      for (int j = 1; j <= n; j++) ncr[0][j] = 0;
      ncr[0][0] = 1;
      for (int i = 1; i <= n; i++) {
          ncr[i][0] = 1;
          for (int j = 1; j <= n; j++) {
              ncr[i][j] = ncr[i-1][j]+ncr[i-1][j-1];
          }
      }
      
      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        I'll take a look at your solution, it is something interesting) You need just C(n,n) — while naive combinatorical one uses C(n*m,n) (number of ways to generate deck and other stuff like that), which is too much for Pascal's triangle.

        Or could you please explain it by yourself? :)

        • »
          »
          »
          »
          »
          12 лет назад, скрыть # ^ |
           
          Проголосовать: нравится +8 Проголосовать: не нравится

          I calculate for k = 1, 2, ..., n the probability that the first chosen card appears exactly k times in the final deck and the first chosen card matches the second chosen card. The sum of these probabilities is the answer for the problem.

          Thanks for asking this, I didn't notice the other method that uses larger binomial coefficients. :)

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

@Mike Mirzayanov i have submitted my code for Problem A : Eevee during contest and it was accepted after the contest i saw in the Verdict tab writes skipped and my submisson have no score then i send again the same code after contest and it was accepted :( why this happens?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

can I expect editorials!

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится

http://main.edu.pl/pl/archive/ilocamp/2011/art — here you can submit F in a version when you have to count number of those pairs, not just state whether it's 0 or more :P.

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +16 Проголосовать: не нравится

    It is also said that you can assume that the result will never exceed 1,000,000. I think it is quite important.

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +3 Проголосовать: не нравится

      I was thinking about counting number of the pairs faster than in O(number number of them * log^2), but didn't manage to find a solution. Not sure if it is possible.

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        Hmm, I believe my solution can be extended to count them in O((N + #pairs) * log(N)), but it's quite tricky, I'm kind of "cheating" using polynomial hashing, and that's not much of an improvement. :)

        • »
          »
          »
          »
          »
          12 лет назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится

          Yes, my solution is also tricking around polynomial hashing (using binary search and information about previous differing characters positions to determine next one), but it has log^2 factor due to segment tree using.

          It's an interesting question how to avoid quadratic #pairs factor.

          • »
            »
            »
            »
            »
            »
            12 лет назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится

            It sounds like we have the same algorithm. But it looks like I was mistaken. I thought I could avoid a log factor using amortized constant-time segment tree queries, but that requires making O(N) queries, whereas we're only doing O(log N) queries. So the log^2 factor won't go away. D'oh!

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
         
        Проголосовать: нравится -10 Проголосовать: не нравится

        My solution ( http://mirror.codeforces.com/blog/entry/13095#comment-180008 ) clearly can be extended to counting by generating all inversion and checking them all, but I don't know how to properly estimate complexity. For F mentioned paper states sth which implies that if there are >36 inversions, then there is at least one good pair (a, b). Maybe there is a constant such that if there are > M * k inversion then there are at least k good pairs (a, b)? If this will be the case, then overall complexity will be O(n log n + result), but there's a large constant next to result. There also a possibility that such constant doesn't exist :D. But maybe it can be at least proven that we can replace M by something growing slower than log^2 k :D. That means that following statement will be true:

        if there are > M * f(k) * k inversion then there are at least k good pairs (a, b) (where f(k) / log^2 k -> 0)

        If so, we will get better solution : p. But until something here will be proven this is some kind of meaningless considerations :P. But on a contest I will give it a try :P.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +48 Проголосовать: не нравится

If not full editorial, please at least put the editorial for problem E and F. Editorials of other problems can be posted as comments of discussion in the blog.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -12 Проголосовать: не нравится

I think best solition for problem B is this . best means that code is easy to read

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Does this mean from now to 8.10 ,there won't be any other CF round ?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Can anybody explain the solution of problem E ?

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +8 Проголосовать: не нравится

    Problem is easily solvable with suffix automaton. We can use modification of algorithm from e-maxx for finding largest common substring of many strings. Firstly we concatenate strings like a#b&c%. Then we build automaton. For each state we should calculate number of paths from it ending with character '#', '$', '%' in variables f,s,t. It can be done with dfs. It will be amount of rightmost positions of current state in first, second and third string. Then we can simply iterate over the states and increase the answer by f[i]*s[i]*t[i] where i is a number of state for all different lengths of substrings that are compressed in the state. I.e. for the segment (len(link(i));len(i)]

    You can check my solution for better understanding: 7265940

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +15 Проголосовать: не нравится

Who's in?

yarrr, Igor_Kudryashov and Goofy57 definitely are.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

"MemSql round 2(online) нет возможности зарегистрироваться самостоятельно". Кто-нибудь зарегистрируйте меня!) И научите регистрировать других.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

I can't register to contest. When I click "Register now" I receive notification "The contest does not allow self registration"

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

I hope they give editorials this time.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

will people who not finished in the top 500 in Round 1 be rated ?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

It's been 2 months now since the contest...and the promised editorial has not come out. Are there still plans to release this?

If not, maybe we can compile all the relevant comments together to form what we already have.