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

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
  • Проголосовать: не нравится

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

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

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

    Yes, thank you for bringing it up. Round one will actually be on Sunday, July 27th. Original post had a wrong date.

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

    Thank you for reminding me, that today will be TCO. If it weren't for you, I would probably forget :P (not that TopCoder should do that...)

»
10 лет назад, # |
  Проголосовать: нравится -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?

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

Deleted.

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

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

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

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

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

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

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

    As far as I know Codeforces allows one to participate unofficially in any round (same as division one contestant can participate in division two rounds). We will not intentionally disable this functionality.

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

      Why do you set such strange top-500 restriction for online version of second round? For example I can't participate in first round, so you force me skip both rounds. It is very easy to reach top-500, so it is only about could you participate in the round or not.

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

        It is very easy to reach top-500

        i think this is disrespectful to the people who won't make it to the top 500

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

          Sorry if I offended anyone. And I am sure they want officially participate in the second round too.

          P.S. I changed my flight, so I can participate, but still don't understand logic of organizers. It is not gcj with huge amount of participants, and it doesn't affect onsite at all.

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

          I'm sorry for whoever that stands in 501st place :/

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

            so sad for veecci and poopi. they missed out by just 4 and 6 points respectively. :(

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

              Oh, Thanks. I was very bad today, but really I prefer to be at 600th place or more instead of 502th :) It isn't nice but I'm hopeful that organizers find at least two cheater in places 1 to 501 :)

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

        I hope I will be able to say "It is very easy to reach top-500" in the future.

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

        I agree with the first statement of course. What's the point of the restriction of top 500? If the system can bear the load of 1st round then obviously it could bear the pressure if all are advanced so there is no point of top 500 thing from the point of system.

        But according to the 3rd sentence, if It is very easy to reach top-500, so it is only about could you participate in the round or not., then all the (1200 and counting) participants/registrants will reach top 500? Oh, but pigeonhole principle must disagree.

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

          then all the participants will reach top 500? Oh, but pigeonhole principle must disagree.

          what if 1000 participants all get same score, and all take the 500-th place? :D

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

          maybe two pig on one hole :/

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

      I guess main point of question was about rated participation (not like unofficial participation for div1 contestants in div2 rounds). For example, Croc Champ 2013 — Round 2 was rated event both for guys who qualified from round 1 and for those who did not; moreover, there was also Croc Champ 2013 — Round 2 (Div. 2 Edition) — rated event for div2 users.

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

      What happens to ratings when one participates unofficially though?

      I seem to recall that when VK-cup was on CF, unofficial participants still factored into the ratings pool. Will that be the case here?

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

        Last year it was a regular CF round for all participants in terms of rating.

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

where can i get the competition

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

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

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

Is it rated??

»
10 лет назад, # |
  Проголосовать: нравится +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.

»
10 лет назад, # |
  Проголосовать: нравится 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.

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

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

»
10 лет назад, # |
  Проголосовать: нравится +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!

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

    Are you kidding? It's summer now — who's studying in July?

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

      But according to my parents' opinion, if I want to grow taller, I should go to bed early... T_T

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

        you can go to bed 2 hours earlier than usual, that means your sleep time of a whole day is the same.

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

          And when I fall asleep the clock will wake me up... Anyway it is an acceptable idea:)

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

      Because I feel boring staying at home in summer holiday. And at home I must cook dinner for myself owing to my parents always not coming back home for dinner. After friends and classmates of middle school meeting, I have nothing to do but training coding skills. Home is not a good place to train. I think I would better go to school.

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

      I don't know about China, but it's not so unusual that we still have class in July in Japan. My friends in Japan are now taking the final exams! (In Japan, school starts in April, and the first semester often ends in July.)

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

    I catched math big god wow!

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

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

»
10 лет назад, # |
  Проголосовать: нравится -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");
}
  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Привет, напиши пожалуйста задание, и залей исходник например на ideone P.S. твоё сообщение не относится к теме статьи

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

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

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

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

»
10 лет назад, # |
  Проголосовать: нравится 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.

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

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

Regular Div1 or regular Div2?

»
10 лет назад, # |
  Проголосовать: нравится +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?

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

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

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

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

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

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

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

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

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

    Лол, я тут пытался спросить про ситуацию в мире -48:) Это сайт для прогеров а не для любителей футбола:)

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

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

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

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

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

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

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

Is this for DiV 1 or DiV 2 ?

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

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

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

    Yeah , this contest will start exactly at our iftar time in Syria. however , I still want to participate.

    BTW, happy feast tomorrow to you and all muslims!

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

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

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

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

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

    Нет, просто контакт перестал поддерживать КФ и теперь обречен на нестабильную работу...

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

Anyone can tell score of problems?

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

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

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

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

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

contest is not simple !

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      Какой ответ на этот тест?

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

        Конвертик, 2 диагонали и длинная сторона

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

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

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

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

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

How was problem C to be solved?

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

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

  • »
    »
    10 лет назад, # ^ |
    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

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

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

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

    6 ..p... или 8 ..p..... (в зависимости от решения).

    Некоторые не обращали внимания на длину имени.

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

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

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

Can somebody please explain D

»
10 лет назад, # |
  Проголосовать: нравится +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.

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

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

7269849

»
10 лет назад, # |
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.

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

I scared I will get down rating !

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

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

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

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

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

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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).

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

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

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

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

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

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

      А я делал наоборот. Итерировался от меньших к большим, разрезал отрезки и поддерживал ответ.

»
10 лет назад, # |
  Проголосовать: нравится 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.

»
10 лет назад, # |
  Проголосовать: нравится +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 :(

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

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +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.

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

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

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

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

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

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

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

»
10 лет назад, # |
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.

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

    What was the approach for problem B ?

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

      I can't believe it -.-

      I got AC after contest ended. Two lines of code and it was fixed!

      There is a little 'hack' that I like to use. Watch others submissions AC's and how much system resources they use... When I saw some solutions using a lot of memory then I figured out it MIGHT not be an easy one line solution.

      My approach: Fix two points (0,0) and (n,m). You can see that it must be included in the optimal solution. Then you have two points to select among 4000. It's not wise to choose a point inside the rectangle... So choose two distinct points that lies in the border (that's up to 4000 points!). So you can run O(4000^2) to pick those points. For each set of 4 points you still have to select the best order, that is, assing p1, p2, p3, and p4 and compute the length. Pick the best, and you are done! (m==0 || n==0 you can solve by hand)

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

    F is far from div1 E and... how to solve B -_-?

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

      I just tried all the possible 4-tuples of what I considered "important points". This passed pretests. I hope also system tests (((

      7262613

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

    saw a lot of hacks to B, so doubt it's div2 A level

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

    I find C easier than B.

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

      How did you solve C?

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

        Well, this formula 1/n + (n - 1)/n * (m - 1)/(mn-1) is a solution.

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

          I need explanation !

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

            Well, There two possibilities to get the same card. 1) One card was chosen twice. Probability here is 1/n 2) Different cards were choosen. Probability of that is (n — 1)/n. Let's see on all cards that was not chosen first time, All they ahve the same probability to be chosen. There are m — 1 out of mn — 1 cards that equal to first one.

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

          magic..

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

          Found the same formula but didn't check when n=m=1...and got a WA

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

    B = Div2 A? Nice joke :)

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

      First, I wrote this before systest. Second, it's B. Third, there were a LOT of passed pretests, and there are still a lot of passed systests.

      Right now, I'd say that B is div(-1) stupidproblemIdontwanttocompete.

      Your comment is just as biased as mine.

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

        Did I miss any announcement of some special prize that will be served if this guy (Xellos) gets a certain number of down vote? A man with +122 contribution to this community is getting down vote even without using slang, or native language! Come on, he just shared his feelings with you guys. Anyway I "donate" my +23 contribution to you,down voters . Please take it!

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

    For me, B and C were much harder than E.

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

      I didn't really try to solve them, and this was before systest. As I wrote, "my impression".

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

      Sorry, but stupid bruteforce + obvious combinatorics can't be harder for noone than some fancy algorithm on LCP xd.

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

        Obvious combinatorics is not that obvious for some people(like me =)). And no fancy algorithm on LCP is actually required in E, there is a well-known solution with suffix automaton for these type of string problems which is simple to understand and implement if you have seen it before.

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

        Did you say harder? If it's true I couldn't understand your reply.

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

        Just take a look at performance of kb.:)

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

    B can not be compared to any div2 A. You can see number of Submitted Solutions and number of Passed Solutions.

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

    You failed div2 A systest :)

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

      Nothing unusual for any problem with weak pretests, a lot of special cases, and considering I'm the one solving. Nearly everyone I see in my Friends tab failed B, even, so the last part can probably be extended.

      I can write it in bold caps for you, too: MY IMPRESSION.

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

Как решать F?

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

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

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

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

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

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

        Да.

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

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

          Для немного неочевидно, почему это работает.

          Для примера
          6
          1 5 2 6 4 3
          разве подстроки in не будут такими?
          ()
          (010)
          (110)
          ()
          (10111)
          (11111)
          Вроде получается, что палиндромность ломается, но прогрессии нет.

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

            1 5 2 6 4 3

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

              Спасибо, теперь понял!!! Мне почему-то показалось, что (a + b) / 2 должно лежать ровно посередине...

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

Yeah ! I accepted only once problems A

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

why my solution for problem A skipped?

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

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

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

congratulations sevenkplus !

»
10 лет назад, # |
  Проголосовать: нравится +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....

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

    It's just depend on the participant if it's harder or not. For those who likes such problems as me it was easier than B. So equal points is quite a good idea.

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

    Answer to C: (n = m = 1 is a special case). Doesn't look very hard.

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

      Ah I miss this simple solution. No wonder....

      Anyway, this euphoria is over. I think I will back to yellow :'(

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

      Can you explain how you obtained that expression?

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

        I considered two cases. The first case is when Alex chooses exactly the same card as you do. The probability of this is . Otherwise, you and Alex choose two different cards, and any pair of different cards is equiprobable (so, the fact that they are chosen from a random subset of size n is irrelevant). In this case, the total number of choices is , and the number of choices that result in the cards being of the same type is . By properly combining all these numbers, you get the answer.

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

      how do you reach this formula ?

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

Will you be providing the editorial?

»
10 лет назад, # |
  Проголосовать: нравится +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!

»
10 лет назад, # |
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
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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.

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

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 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.

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

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

»
10 лет назад, # |
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.

»
10 лет назад, # |
  Проголосовать: нравится 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.

  • »
    »
    10 лет назад, # ^ |
    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?

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

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

    • »
      »
      »
      10 лет назад, # ^ |
      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.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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.

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

      I did it with DP in O(N^2), so I think it whould have been harder with a formula. ( maybe worth more points )

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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.

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

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

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

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

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

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

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

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

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

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

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

»
10 лет назад, # |
  Проголосовать: нравится +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?

  • »
    »
    10 лет назад, # ^ |
    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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        10 лет назад, # ^ |
        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.

»
10 лет назад, # |
  Проголосовать: нравится 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 !

»
10 лет назад, # |
  Проголосовать: нравится +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"

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

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

»
10 лет назад, # |
  Проголосовать: нравится -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.

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

    Pretests on B were very weak.

            x=make_pair(0,0);
            y=make_pair(N,M);
            z=make_pair(0,0);
            t=make_pair(N,M-1);
    

    I failed B because I mistyped the points for one "case", yet I still passed the pretests.

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

When will the contest be rated usually in codeforces?

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

Why is rating update taking so long?

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

    I always wonder why system test is faster than rating update!

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

      Generally the rating the updated with in half an hour of the system testing, but today i don't know what is it that they are taking so much time.

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

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

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

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

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

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

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

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

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

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

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

            Из того же источника "некоторый"="какой-то, точно не определённый". Если брать вторую трактовку, то все верно. А про квантор. То, что квантор читается, как эти слова, не означает, что эти слова читаются, как этот квантор. Стоит учитывать, что у слов может быть несколько значений.

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              1. ...либо неверно :) , 2. а где "некоторый" употребляеться другим, т.е. N\0 значением? ссылку на словарь
              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                вот ссылка. http://ru.wiktionary.org/wiki/%D0%BD%D0%B5%D0%BA%D0%BE%D1%82%D0%BE%D1%80%D1%8B%D0%B9 Я не совсем понял вопрос "а где "некоторый" употребляеться другим, т.е. N\0 значением?". Можете перефразировать?

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

                  Имел в виду множество {0,1,2,...}

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

                  Тогда вы неверно выразились, сказав N \ {0}, потому что ваша запись обозначает разность множеств, а не их объединение

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

                  Согласен. Имел в виду символ \ , как субскрипт знака 0. эмм..

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

                  А пример я сейчас, с ходу привести не могу, но, в любом случае, трактовка "некоторый"="точно не определенный" корректна для данной задачи. А в случае двоякого понимания условий стоит задавать вопрос.

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

                  "не определенный" говорит о том, что неизвесно какой именно элемент (1-ый?, 4-ый?, ...) множества, а "какой-то, " — квантифицирует. Если кванифицирует иначе, чем написано в статейке "Квантор существования", было бы интересно посмотреть источник.

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

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

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

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

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

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

            (условие)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

When will Ratings be updated ?

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

waiting for the editorial :)

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

Ratings are updated!

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

    Oh! At last having the test of being purple for the first time! Alhamdulillah. :)

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

Still Div1!

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

    I'm surprised that I added rating. I decided two tasks are not particularly slowly. (Google Translate).

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

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

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

Let's go to next round!

»
10 лет назад, # |
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 ;/.

  • »
    »
    10 лет назад, # ^ |
    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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 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'?

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

          Um, sorry, I somehow understood that you proved that observation, but you wrote that you found it on a paper :P.

          And that sign "/" was meant to be "or". Those were 2 separate sequences :P.

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

            We both read each other's comment wrong then!

            It all makes sense now :)

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

please anyone explain how to solve D?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    10 лет назад, # ^ |
    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.

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

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

»
10 лет назад, # |
  Проголосовать: нравится +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 :)

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

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

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

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

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

Contestant thank you for good contest.

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

Can we expect an editorial here?

»
10 лет назад, # |
  Проголосовать: нравится 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?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +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;
      }
      
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 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];
          }
      }
      
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 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? :)

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится +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. :)

»
10 лет назад, # |
  Проголосовать: нравится 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?

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

can I expect editorials!

»
10 лет назад, # |
  Проголосовать: нравится +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.

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

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 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. :)

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 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.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 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!

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

        My solution ( http://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.

»
10 лет назад, # |
  Проголосовать: нравится +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.

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

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

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

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

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

Can anybody explain the solution of problem E ?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +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

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

Who's in?

yarrr, Igor_Kudryashov and Goofy57 definitely are.

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

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

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

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

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

I hope they give editorials this time.

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

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

»
10 лет назад, # |
  Проголосовать: нравится +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.