Блог пользователя Sereja

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

Всем привет!

Совсем скоро, 13 февраля в 19:30 MSK состоится Codeforces Round #167, автором которого являюсь я. Это мой четверый раунд на Codeforces и я надеюсь, что не последний.

Спасибо Жене Соболеву и Диме Соболеву (Seyaua и sdya) за помощь в тестировании задач, а также Геральду Агапову (Gerald) за помощь в подготовке раунда. Отдельное спасибо Марии Беловой (Delinur) за перевод условий на английский.

Разбалловка стандартная в обоих дивизионах.

Настоятельно рекомендую прочитать условия ВСЕХ задач.

Gl & hf ! :)

Контест окончен, поздравляю победителей див1:

1). tmt514
2). tourist
3). scott_wu
4). rng_58
5). dreamoon_love_AA

И победителей див2:
1). yefllower
2). Harlos
3). pseudopodia

Разбор по ссылке.

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

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

Are you sure about this date : "Sunday, January 13th at 19:30 MSK"

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

Guys according to your date the contest has been completed... because your date Sunday, January 13th at 19:30 MSK is gone....

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

''Настоятельно рекомендую прочитать условия ВСЕХ задач'',- и так каждый контест от Sereja :)

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

    У него все задачи интересные. Лично я не могу успокоиться, пока не разберу все задачи второго дивизиона от Нагина.

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

Жалко, пропускаю вторые подряд соревнования из-за инста...

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

На прошлом его контесте шикарная дпшка была !!! Думаю и на этом тоже мы что-то похожее увидим

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

Взломаю любого кто окажется в моей комнате!!!

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

After 7 rounds, all the 3 digits of this round is strictly increasing :)

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

scoring??

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

в ОБЕИХ дивизионах??

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

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

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

daje teh kto ne reshil))) XD paca

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

    А. Даже так. Я ее помнил, с какого-то из прошлогодних этапов кубка.

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

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

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

        Все значительно проще. Берем любого у кого много. Переносим в другую часть. while (true). Сумма ребер внутри уменьшается, поэтому все закончится.

        Это получился квадрат. До линии или MlogN доводится просто очередью или сетом.

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

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

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

    Мне вот интересно — это специально? Автор матча мог и не видеть задачу, в это я еще поверю. Но ведь Seyaua и sdya Тимус решали. И кубок вроде бы тоже. Они решили, что такую задачу можно допускать на матч СF?

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

      Но ведь там ограничения другие, и можно решать за квадрат, так что даже если и знали, почему не дать?
      Мы вот давали Jedi Tournament в Петрозаводск со слегка другими ограничениями, и никто вроде не жаловался)

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

      Мне кажется, что главное — это чтобы Gerald ее раньше не видел)

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

    Более того, решение которое получило АС на тимусе, тут получило ВА 13, уже с дорешки отправил) Но оно явно багнутое, так что кроме слабых тестов тимуса обсжудать нечего)

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

Rishat_Ibrahimov used #define long unsigned long long and that costed me a wrong challenge, shouldn't that be considered code obfuscation?

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

div 2 D,can it be solved w/o chinese remainder theorem(CRT).

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

    Let's sort all pairs. There can be equal ones, which can be now easily recognized. If there aren't — the answer is (n+m)!, obviously. But if there are, we should divide our (n+m)! by number of equal pairs (since 2! = 2; if there were equal triples, we might have divided by 6). Division goes using Fermat's little theorem since we're using modulo.

    Edit: forget about the theorem, those 2's are from factorials, as MohallaBoy noticed.

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

      What do you mean by (n+m)! ?Can you show some details?

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

        I'm very sorry about misinformation — only yesterday before resubmitting D I realised that I wrote incorrect part of solution here. Please disregard it :) There's an editorial for now.

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

    basically you to find values like (n! / (2) ^ k) % m You can do this by removing 2's in the numbers which are used for calculating factorials. and taking then modulo m.

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

      first recognize all equal pairs, then for each repetition of the x term we calculate (length)!, omitting a 2 for each pair earlier. Although im 100% sure this is the solution i didnt implement it well enough for pretests :(.

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

    When we calculate factorial let's just divide each factor by 2, if there is any pairs left. Even if we use chinese remainder theorem, we can't calculate modInverse of 2 if 2 is divider of our modulo.

    long f(long n) {
    	long res = 1;
    	for (int i = 2; i <= n; i++) {
    		int k = i;
    		while (k % 2 == 0 && badCount > 0) {
    			badCount--;
    			k /= 2;
    		}
    		res = (res * k) % MOD;
    	}
    	return res;
    }
    

    The answer is integer so when we got our answer badCount == 0

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

Кто нибудь писал по D O(N^3 log^2 N) решение? На сколько быстро работает?

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

any ideas for solving C Div 1 ??

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

    Edited : I was wrong !

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

    Randomly distribute horses in 2 parties. Now if each horse has at most 1 enemy in its party, this distribution is correct. Otherwise, there exists horse A in party 0 that is enemy with horses B and C in the same party. Now move horse A to party #1 and it'll have at most 1 enemy in its new party. To prove this solution works, just define an invariant as count of enemy pairs in same party. Observe that after each move, this invariant decreases and hence our procedure is finite.

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

      How do you prove that if this method fails to find a partition, then a partition is impossible?

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

        Actually, when our invariant decreases at each step, it'll eventually reach 0 which means we are left with a correct distribution of horses in 2 parties. Possible partition always exists and it may not be unique but our algorithm guarantees to find one :-)

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

          Sorry for being picky but I think it's variant, not invariant.

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

            You're right. Thanks for pointing this out. Topic of this problem in Combinatorics is invariants and that's why I confused them :D

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

            I think it is called monovariant.

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

       Imagine, that all the horses are in part 0. According to your alrorithm, firstly we move horse 1 to part 1 (enemies 2,4,5). Then we move horse 2 to part 1 (enemies 3,5). Also we move horse 3 (enemies 4,6). Horse 2 now has 2 enemies (1,3) in its part. So, it doesn't work. Maybe I've misunderstood you, so please, can anybody explain me the correct solution of this problem?

      UPD: All right, I understood you. But it was not easy to push it through TL (3126714). Maybe it's because of Java. Is that an optimal solution?

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

        Complexity is O(m) and the idea behind this solution comes from a known graph problem. So I reckon this solution is optimal.

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

Угарный контест B — шку на последних 15 секундах сдал :D

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

    Везёт, я её вообще сдать не сумел. Кто-нибудь сталкивался с ошибкой на 14 претесте?

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

      Сам спросил — сам ответил, забыл, что в C++ (long long) надо использовать не только при объявлении, но и преобразовывать в него при операциях. Придётся ждать досдачи.

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

    Та же фигня. Искал в этой задаче тупую багу весь контест, в результате за 5 минут до конца нашел)

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

Sorry for tourist. How fast he was. But even this didn't help him to pass Pretest 0 ( Compilation ). 3123727 and 3123677 :)

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

заходил ли в С рандом? и как ее вообще решать?

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

:S DIV 2.B: Any one have an idea that why 3122613 has wrong answer on pretest #8?! I'm really sure that it should produce a correct answer. :S

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

DIV1 D is an original problem.

http://community.topcoder.com/stat?c=problem_solution&rd=14422&pm=11179&cr=10574855

TopCoder has its harder version.

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

one of the best contests ever..!!

well balanced on thinking and data structures...

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

wasn't anyone fool enough like me to use segment tree for div 2 C.

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

    well, i used BIT

    submission in queue...

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

    I used Fenwick Tree for that problem :)

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

      and fingers crossed.....:)

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

      I think you don't notice A[i] <= A[i+1] , I'm too) But I did it after writing void build(.... )))

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

        But even if it wasn't A[i]<=A[i+1] you can create sequence B such that B[1]=A[1] and B[i]=max(B[i-1], A[i]), so this assumption wasn't really necessary ; p.

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

    No, you weren't :/ Segment tree consumed all of my time — I should have read D first...

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

    lol, i wanted to code it, but then i saw a number of acceptions for this task.

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

    I use segment tree, too. I've got some MLE after some TLE and finally I forgot to use long long.

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

    same here :) I got it Accepted and also I apologize to Segment tree for using it in this easy problem

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

    I was fool too :(

    I didn't notice that the stairs are sorted

    I also didn't notice that boxes fall from the left until I coded it

    anyway I was fooler because my code was fail on test 45 because of overflow :(

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

It looks like the only difference in kissbuaa's and xiaodao's 2000s is the link in the beginning.. ..which is pointing to the same solution, yep. http://codeforces.net/contest/273/submission/3115085

http://codeforces.net/contest/273/submission/3114783

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

Как D решать? Так и не смог придумать состояние динамики -_-

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

Кстати, как по мне — нехорошо получается с этими напоминаниями по поводу 64битных чисел.

Так как их всегда ставят в задачах, где ответ не влезает в int — то это является неявной помощью участникам.

Вот сегодня я считаю свой результат по первой задаче — незаслуженным. Я бы сдал решение в интах (с переполнением), и тем более никого бы не ломал, если бы не было этого напоминания.

Надо или писать его вообще в каждой задаче, или где-то отдельно напоминать.

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

    Эх, а я не заметил. Хорошо, что поломали достаточно быстро.

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

    Да ладно, все равно было куча взломов по А на переполнении. Мои, например, все на этом.

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

      У меня тоже все 6 на переполнении:) Но все равно есть подозрение, что таких как я — которых спасло напоминание, — довольно много.

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

    Да я тоже об этом подумал. Наверное многие, как и я, дописали 64 перед тем как сделать сабмит)

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

I have seen Div 1 C problem in Soviet math olympiad in 1979. This problem is "Proof that there always exists answers."

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

теперь если меня спросят, что значит "упороться" я скину им этот код: http://codeforces.net/contest/272/submission/3122354

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

I've accepted problem C Div 2 at 1:29:22 ( Only 30 seconds untill the end of contest) ! I wonder if it was a record!?

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

How to get test case data on which our program has failed.

Since test input is large so It is showing only part of it.

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

    i was about to ask the same question !!!!

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

    An untidy way.. but if u really really need it you can make a hack.. Just print say 20 tokens once (or whatever size fits in the screen), then next 20 and so on..

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

Хороший проблемсет, мне понравился) не смотря на то, что баг на задаче Б немного бошку поморочил и на нервах поиграл, я рад) спасибо организаторам за то, сделали эти 2 часа самыми захватывающими для меня за этот день)

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

Почему не завершается тестирование Див.2? 10 минут уже стоит на статусе "Системное Тестирование, 100%".

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

Обалдеть!.. Оказывается, из фиолетовой полосы выход существует!;)

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

Господи, да почему же я такой неудачник?! Я никогда не стану красным! После прошлого раунда у меня было 2145 рейтинга. Через некоторое время что-то изменилось (хотя место в раунде осталось неизменным) и 1 рейтинга у меня отняли. Как результат, после этого раунда у меня этой единицы и не хватило до красного цвета. Когда граница красного была равна 2000 я уже устанавливал 1999. Теперь 2199, при границе в 2200. Надеюсь, что в этот раз пересчет будет на моей стороне.

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

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

    Что за странные мысли? Отбрось пессимизм.

    Вот у меня было 2199 здесь, так же было 2198 на ТопКодере.

    Красным я не был ни здесь, ни на ТС. Да и по жизни я конкретный неудачник:)

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

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

    Вот видишь, какой несправедливой бывает жизнь.. Там чувак взял решение из ТК (такой молодец, решил D за 9 минут!), и стал красным. А вот не сделай он этого, он, скорее всего, оказался бы ниже тебя, и, кто знает, может, это дало бы тебе недостающее очко рейтинга.

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

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

      Привет, Саш. Спасибо за поддержку. Теперь мы оба в клубе "2199" :) Да скорее всего никто ничего снимать не будет. Здесь такое не практикуется.

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

      Prewritten code на Codeforces разрешен.

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

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

        Спасибо за критику. Но как предвидеть, что задача уже не была?

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

          Никак.

          Если конкретный автор не видел конкретную задачу — его редко можно в этом винить. Все задачи в мире ведь перерешать не так уж и просто. И просто перечитать — тоже задача не из легких)

          В данном случае меня интересует другое. Те, кто помогал в подготовке этого раунда, и точно видели боянистую задачу (Соболевы, к примеру, которые точно видели задачу С) — как они отреагировали на такое? Это было что-то вроде "ну ладно, ты ведь ограничения поднял, теперь надо не просто взять тупой код к старой задаче, а зайти на форум в поисках умного, или дописать несколько строчек"? Или "Тимус? кто же его решает в наше время в русскоязычной среде... Все нормально, никто ничего не заметит"?

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

            Так вышло, что это единственная задача, которою они не читали.

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

              Неудачное совпадение, бывает:)

              Ладно, хватит о плохом.

              Спасибо за раунд, ведь в общем все было очень даже неплохо — условия хорошо написаны, обошлось без лишних кларов, тесты тоже вроде бы в порядке.

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

        Ну это не совсем pre-written code. В Codeforces FAQ так и написано, что не нужно вставлять в решение чужой код. Если бы люди копировали собственное решение той задачи, то его можно было бы назвать pre-written code и тогда уже претензии было бы сложно предъявить.

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

          Фактически оно так. И понятно, что это не очень "честно" со стороны участника. Но формально ведь никто ничего не нарушил. Допустим, я могу за несколько свободных вечеров перепечатать вручную по одному работающему решению к каждой из задач ТС SRM. И сохранить их у себя в папке с алгоритмами. Для наблюдателя со стороны разницы между этой ситуацией и ситуацией, которая описана в теме выше — никакой. Разве что пользователь сам попросит "забаньте меня, меня совесть замучила".

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

        Prewritten code (чтение, макросы и т.д.) разрешён. Prewritten solutions — вряд ли. Prewritten solutions, написанные кем-то другим — точно нет.

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

        Это, в конце концов, просто неспортивно.

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

          А ещё неспортивно давать бояны, притом настолько очевидные.
          Кстати, а не правда, что solution состоит из code и, соответственно, множество solutions является подмножеством code?

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

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

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

    Мне бы твои проблемы :)

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

А как решалась C(div1)? Времени было полно, но всё равно не смог придумать..

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

76 contests and 18 months of ups and downs and finally I get to taste Division 1 in Codeforces, the place where I started online programming.. May be small thing for others but it means a lot lot to me because this is where I started from.. Sometimes getting close and then falling back and sometimes no where near to the horizon..Yes... Now I can proudly say that I am Div 1 in codeforces and topcoder together .. I dont know how long I am going to stay here but just being here is a great feeling... :) I hope I will never see Div 2 again.. Thanks to the author Sereja and Egor as always for CHelper

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

Gotta thank Sereja for the best contest in my whole life. Couldn't be better than this for me! :D

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

    It's because You became candidate master and solve five problems?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится
      • A contest that was based on Combinatorics and problem solving skills and didn't need hard and famous algorithms to be implemented. A brain challenging one.
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Well if You can solve C segment tree with updating on segments, it doesn't seem so simple. And if You solve D in few minutes to the end, it doesn't seem so simple too.

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

Просьба помочь найти ошибку в решении, задача Д див2, WA на 44, идея решения — факториал с учетом точек в одной координате (с замечанием, что в одной точке пространства не более двух точек) http://www.codeforces.ru/contest/272/submission/3120115

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

    Проблема в том, что ты делишь по модулю. А так нельзя. Пример: Рассмотрим взятие по модулю 6. По модулю 6 числа 4 и 22 равны, но (4 / 2) % 6 = 2 ,(22 / 2) % 6 = 5.

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

      Спасибо, забыл найти обратный элемент.

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

        Его может не быть, так как модуль задается каждый раз разный. Я делал так: заметим, что деление на два необходимо только для вычисления С из n по 2, то есть в формуле (n * (n — 1)) / 2. Это можно посчитать точно в int64, а потом уже взять по модулю.

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

          На самом деле можно было разложить факториалы на множители: 2 и все остальное. Тогда просто выходит.

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

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

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

I did problem D in div2 carelessly and WA for 4 times in the contest. At last I only got 880 for this problem... But my rank seems OK...

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

what happened to your tutorial link?

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

    The tutorial is written in Russian, it hasn't been translated now. Only Russian vision is visible... So just wait them to translate...

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

в первой задаче чекер был не правилным в примечании было написано что 1 1 ответ будет 1 либо 3 либо 5 я выводил 1 и у меня Wrong answer

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

http://www.codeforces.com/contest/272/submission/3128898

i don't understand the fail of my solution ?

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

Не заходил пол-года, а Гена все еще первый в рейтинге

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

By python, I can not solve C in Div I! If anyone know, please post it!

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

    The input is n<=3*10^5, m <= 9*10^5, about 10^7. It's just too large for python. My C++ solution cost 375ms and my python solutions are always 10 times slower. So I guess python need about 4 seconds for each test case.

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

      yes, I think so. I also meet this issue. I implement C++ and python with the same algorithm. The C++ code is accepted in 500ms, but the python one is not.

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

        can you explain about the second argument in your change function? Your solution is recursive. I can convert it to non-recursive version if I understand the trick.