Автор Errichto, 8 лет назад, перевод, По-русски

В субботу, 7-го мая, в 18:05 начнётся Раунд 3 чемпионата по программированию VK Cup 2016! Не забудьте зарегистрировать вашу команду на раунд, регистрация закроется за пять минут до его старта.

В этом раунде могут принять участие все те команды, которые отобрались в Раунде 2 или в Уайлд-кард раунде 2. Участников ждет соревнование по правилам классических раундов Codeforces. Раунд 3 пройдёт в таком же формате, как и Раунд 2 — с онлайн-трансляциями (рейтинговыми, раздельно для див-1 и див-2 участников).

Раунд подготовлен силами гроссмейстерского коллектива: Radewoosh, Errichto и qwerty787788.

Напомним, что в Финал VK Cup пройдут все те команды, которые наберут положительный балл, не меньший, чем у команды на 20-м месте. Также обращаем ваше внимание, что участники всех команд, прошедших в Раунд 3 (независимо от их участия или неучастия в Раунде 3 или в его трансляции), получат фирменную футболку Чемпионата. Помимо этого, фирменной футболкой будут награждены топ-50 участников интернет-трансляции для первого дивизиона.

Желаем удачи и интересной борьбы!

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

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

Now my comment doesn't matter, just ignore it :3

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

G

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

Did you forget to mention AlexFetisov!?

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

" Maybe we will inform about the number of problems and scoring. "

Don't worry, that is not important :D

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

Hope to have some Small & Precise & Easy to Understand Problem Statements . And I like the Contest hosted by Errichto most . And I love Errichto as a person.

Hopefully this will be an interesting Contest .

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

Last time (on vk cup round 1) only "Bear and Chemistry" was mine and nobody was able to solve it. I hope that this time you will perform better. :P Good luck from Radewoosh!!! :D

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

What an original picture: http://codeforces.com/blog/entry/17690

UPD: (oh, looks like it's also visible only in Russian version of the post)

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

На всякий случай напишу еще и тут — не проходит регистрация команды на основной контест. Получаю оповещение, что я уже зарегистрирован на трансляцию для Див1 (это не соответствует действительности)

UPD. Не актуально

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

Can't wait to see the new points System hope this contest is even more fun than the last two :D

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

you said "extremely interesting"

That mean:

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

It will be rated ?

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

No more fogotten tree:)

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

"Top50 in the "Div1 Edition" contest will get t-shirts" .

So div2's are not human?!

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

    Why should strong div2 participants have better chances for a t-shirt than medium div1 participants? Also, t-shirts for div2 may cause cheating (div1 guys participating with other accounts).

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

      At least making a combined round makes more sense , bringing everyone to compete for t-shirts is a better choice.

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

        become div.1

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

        I agree that combined rounds are good when it comes to prizes. Though, there are other factors then. Two important ones are that (1) problems may not fit such a round at all, and (2) hacking is more random.

        Maybe div2 participants should treat usual rounds as a fight for t-shirts — good results will allow them to compete in div1 contests with prizes.

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

    Ehm, yes. The idea is the 50 best guys gaining T-shirts. If you are in div.2, you cannot be the best by definition.

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

      You can have 1899 rating, after a failed contest, where you got -250

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

        If you are good enough to get top 50 in div 1, it's extremely unlikely that you would ever drop to div 2.

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

          but a lot of strong div1 coders take part in official Round3:)

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

        Unlucky man. But it is your fault.

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

Just curious — if someone qualified for round 3, but decided to participate in div1 mirror instead of main round, in case of making into top50 there he'll get two VK Cup t-shirts?

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

bug or feature?

there is 88 teams and 168 participants...

UPD: for now 73 teams and 134 participants, looks real:)

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

    No, there are teams with a single participant.

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

      Or some participants are in many teams.

      EDIT. Maybe as an organizer I shouldn't make fun in comments. To make things clear: my comment isn't serious. #politicalcorrectness

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

    I already reported that "bug" (also seeable in unofficial contests). I once thought that the number in the "Contests" page also involves people that unregistered later, but I may be wrong.

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

i'm already registered in DIV2 round but my name doesn't appear in registrants list ?

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

Is there a problem with the registrants page? Cause on the contest page it says:

But on the actual page it says:

Hoping the 2500 number is accurate but would there be a problem with contestants that aren't on the registered page? Would they be able to submit in the contest?

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

I was outvoted to post the scoring. So, check out a new update (in the blog).

EDIT: someone is working on the registration issue.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится
  1. Зарегистрировался.
  2. Через несколько часов обнаружил, что мы больше не зарегистрированы.
  3. Зарегистрировался ещё раз.

Только у меня так ?

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

    Нет. Точно помню, что регистрировался с утра. Но пришлось зарегистрироваться заново сейчас.

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

There is a bug with showing participants list, and may be it's something legated with teams

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

Я понимаю, что участники не читают соглашение об участии, но почему его не читают те, кто его пишут?

Текст

Во-первых, адреса всё ещё ведут на codeforces.ru, с которым мы попрощались уже почти год назад. Во-вторых, какое отношение ко мне имеет первый пункт, если я регистрируюсь на интернет-трансляцию? И вообще, когда это "соглашение" наконец сделают нормальным шрифтом и с кликабельными ссылками?

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

The difficulty jump from Div2 D to E and F seems huge... Kinda sad that speed and hacking is going to determine most of the Div2 results, even if it seems like I'll be at the top of the 4-task-solvers.

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

Complete problem D and thinking about sleep :)) :))

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

I made someone angry and then...

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

    Yup we were in the same room.... I don't know what was on his mind....he tried to hack mine too a lot of times!

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

      Likely one of those guys like .o..

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

      I think it's clear he wasn't happy with his perfomance and he "hacked himselft out of the contest". If you have negative score, the contest is unrated for you, or at least it used to be that way.

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

        It's not true. I've checked it today? Effect? -120 :)

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

          Yes, it seems they changed that. I think this a much more reasonable policy. But there should have been a notification about this (I searched and didn't find it anywhere).

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

            It never was like you describe. Even having an ultra-negative score always affected your rating.

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

              Okay. Sorry for mixing things up. I was definitely mistaken. Don't know how I came up with that, I was sure I had read it somewhere.

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

                I've also heard about it. Maybe there was such a bug (feature :D) a long time ago. We should probably ask Mike whether it's just a social myth

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

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

Time: 1981

Memory: 2465792

Переписываешь его решение, запускаешь в "запуске", а там стабильно 2100 мс =(((((

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

What is the hack for Div2D?

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

What was the hacks for Div2A and Div2B?

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

    Some guy in my room was outputting 2^(max — min — 1) and that passed pretests.

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

I didn't even submit a single problem and there it was the lock button for problem B. Must be a bug.

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

"Простые задачи? Зачем!"

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

What's the idea for div1 C?How to calculate the expected value on a interval?

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

    P.S. didn't get AC on C, but I think the cost function is correct

    cost(L, R) = cost(1, R) — cost(1, L — 1) — sum_of_1/a(L, R) * sum_of_a(1, L — 1)

    idea: cost(L, R) = t_L / t_L + (t_L + t_(L+1)) / (t_(L+1))... =t_L * (1 / t_L + 1 / t_(L+1) + ..) + t_(L+1) + ...

    which then becomes much easier to see

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

    let :

    S1[k] be sum of T[i] for i = 1:k

    S2[k] be sum of 1/T[i] for i = 1:k

    S3[k] be sum of S1[i]/T[i] for i = 1:k

    then the expected time to finish the interval s->e is S3[e] — S3[s — 1] — S1[s — 1]*(S2[e] — S2[s — 1])

    from that we can turn it to a dp + convex hull optimization problem ...

    PS : my code fails test 14 — I should practice convex hull optimization more :'(

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

How do you avoid floating point errors with 1C/2E?

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

На мой взгляд, очень не хватало подзадачи DIV1 C, в которой бы проходил k*n*n.

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

Please allow practice.

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

    After the system testing.

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

      Please start system testing =)

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

        Mike and/or Gleb must work a bit after each round, to manage hacks and any issues. I'm sure they don't try to be slow to annoy all participants. You must wait a bit. In the meantime, you can check the editorial.

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

The B,div 2 is maximum bipartite matching?

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

    Nope, it's much simpler! The lower problem in each pair must be the div 2 problem. You just need to find the maximum div 2 problem and the minimum div 1 problem, then take the difference.

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

In div2 D, input :

7 11
2 4 7 3
output
2 7 1 3 5 6 4
7 1 2 4 6 5 3

Why is this output incorrect ?

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

After one hour and solving the first four tasks, next two hours were like a fishing. I was trying to catch some wrong submission and I didn't manage in it :)

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

I'm sure you are all wait for the system testing. So maybe you have time to give the feedback. Which problems were good/bad and what could be better? Something too easy or hard? Too mathy? Too not-mathy?

Someone already said that there was a big gap between div2D and div2E. It may be true. Do you agree? Other opinions?

Seriously, your feedback will make future contests better.

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

    I think B problem shall be C and C shall be B in div 2 contest .. thx at all

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

    yeah , there was a big gap ... but I liked the div2 E problem :D

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

    Yeah, it seems as though there was a ginormous gap between the two. I didn't really think much about the E problem though because I've never been able to solve an E problem during a contest. I went straight to try hacking :P (although I wasn't very successful).

    In general, I liked all the other problems though!

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

    Duplicating my russian comment in english: it would be nice to have a DIV1 C subproblem, which could be solved in O(nnk).
    There were a huge difficulty jump between AB and the others.
    UPD: so, if you are not red, then after solving AB problems in 30-60 min, there is nothing to do in remaining 2 hours, except reading other problem statements and trying to hack someone :)

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

    it would be great if you lower the accuracy of DIV2E/DIV1C and rejudge all submissions :'D

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

    I was stuck at Div1 C so I didn't read Div1 D, however it seems that Div1 D was seriously underestimated. Before system test, judging by successful submissions amount — it seems to be the hardest problem.

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

      I was also thinking that Div1 D is simpler that C, and started it, but only 10 persons solved it so far in all 3 contests >.<

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

    [TL;DR] => too many queries / expected value ;)

    [Div 1] Two first problems were like a warmup, almost everyone solved them.

    But then? [A, B, . . . . . . . . . . . . . E, C, F, G, D(wtf) ]

    Looking at the problems :

    *easy problems *

    -Shieet, expected value.

    -Oh god, queries.

    -Expected value!!!11

    -Hidden queries.

    -Even more queries!!!

    My opinion: Too many queries and expected value :) And almost every one of the C — G problems required DP (maybe with maths) , it is always nice to see a varying problemset with flows / graphs / strings (or even geometry ^^).

    This is only my opinion, please don't dovnvote just because you don't agree with it ;)

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

      The number of upvotes you got means that many agree with your comment. I see that there was too much DP, and maybe too much expected value. But I don't understand one thing — what is wrong with queries? Is it that they make a problem less elegant and nice? Because not all problems with queries are about the same topic.

      Would the following version of 643E - Bear and Destroying Subtrees be better? It has no queries (does it make the problem nicer?). The tree is given and there are no queries at all. We consider removing each edge with prob. 1/2. What is the expected value of the height after the process, modulo 109 + 7.

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

    Yeah,there was huge gap between these problems.In addition C was too easy , I think it would be better if it was problem B.

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

      Imo C is harder than B. Only problem with B was a bit overcomplicated statement :)

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

    In my opinion, the pretests for problems which greatly affect standings (for today's contest, it's all problems after div1B) should be nearly identical to final tests, that is to say all corner cases should be present. It's definitely a frustrating bug to drop 70+ places because

    for(int j=1; j<i; j++)

    should be

    for(int j=i-1; j<i; j++)

    Before you say "but what about hacks", I'd like to point out pretty much nobody is going to hack a problem with more than a few lines of code. Indeed, there were no hacks on C, D, E, F, or G of div1 contest.

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

      I think that we tried to make pretests strong in hard problems. I think that the only exception was a problem about the expected height of partly-destroyed subtree. (There, I thought there would be hacks requiring big value of MAX_H.) About which problem are you talking?

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

        I failed Div1 C because my DP formulation considered splitting n levels into more than n parts, which obviously causes bad things to happen. Any test where n = k and n >= 3 will cause my program to output a value smaller than n. Adding two characters would fix this :(

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

          It's hard to be so careful about pretests. Still, I see your point and I'll try to consider it in the future. Thank you.

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

    In division 2 C, why was index written in brackets. All the while I thought only about index of the lowest tied color :| Rank dropped by at least 200. :(

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

    This isn't that important, but I would prefer if the problem statements seemed more "natural" in some sense, maybe something that I would naturally be interested in, not too contrived statements, etc.

    I thought A was OK in this respect. B was ehh, the condition that ab, cd aren't edges is slightly unnatural. C was pretty unnatural, in the statement of the game, etc. I didn't try D, E, G so no comments here.

    F is a decently natural statement I thought, if you think about the problem mathematically.

    Tell me if I confused you...

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

      It's a very important thing in my opinion. Statements are a huge part of the contest. Initially, in B there was something like "Limak wanted to get from a to b. Unfortunately, there was no direct connection. So, he will be late anyway for some event and at least he will take a long nice walk. He then went to b, visiting all cities during his walk. On the other day, ...". It's easier to understand the story but the cost is that the statement is (much) longer. The current version is much shorter than the previous one, with some background. I was advised not to write long statements for this contest and I think it's better. For example because some people aren't fluent in English. So, maybe shorter precise statement is better than longer natural one. But still, I left some story. I will gladly hear more opinions about it.

      But generally, it's hard to invent only natural problems. I can do nothing about the fact that C was unnatural for you. I thought it's still better that only definitions ("split sequence to maximize the score defined as ..."). But some problems are just artificial. I know I will never be able to produce only non-artificial stories and problems (enough of them to make contests).

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

    I was expecting to solve more of the problems and it just feels bad to solve 2 and one of them didn't pass system tests, so I got a beautiful 1 problem accepted. I think that is because the difficulty gap between first 2 and all others was too high, if there are going to be 7 problems, I would expect the average to solve 3-4, if there are going to be 5, then 2 or 3 is nice, I just think that a minor mistake shouldn't move you more than 100 places, or 170 in my case, around half of the people that participated in div1.

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

    It would be interesting to know: is "34 accepted solutions for D-G problems" near with expected estimation of AC ratio for this problems before contest?
    What is ideal AC ratio in your opinion? (e.g. A 50%+, B 25%+, C 12%+, ...)

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

      It's hard to estimate these numbers before the contest. I'm only sure that we considered div1C (CHT) and div1D (Fanpages) to be easier than they turned out to be. I think that the number of AC's in other problems is fine.

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

Please enable upsolving immediately after systests...

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

How to solve div 2, C ?

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

Can anyone explain the idea of recalculating all of the probabilities in Div1 E? Thanks

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

Impressive performance of .o. in Div2! My NBHEXT expects +401 for him >_<

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

round was rated or unrated ??

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

My solution in Div1C adds each of n lines in CHT after calculating DP for some k.
How to prove that the best line for i (when I calculate dp[i][k + 1]) will not have some index j > i?
It is not obviously for me but it passed systests. I even tried to change the order of addings but it didn't pass pretests :D. Or maybe weak testcases are the reason of my Accepted :D? 17793170

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

    We have dp[i][k + 1] < dp[i][k], and . I'm not sure this is sufficient to show more rigorously that adding further indices will not affect the answer, but it seems to make it intuitively clear.

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

    For your CHT you need to put lines in increasing by angle of line order.

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

А знает ли кто-нибудь, почему так долго пересчитывается рейтинг?(уже после компиляции)

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

My Div1-C timed out since I was using cin for input. Changed it to scanf and passed. :(

cin : http://codeforces.com/contest/674/submission/17792111

scanf: http://codeforces.com/contest/674/submission/17797745

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

Its happened first time with me this is my Div2 D soln which was hacked — > http://codeforces.com/contest/673/submission/17796235 after contest i submitted this code again — > http://codeforces.com/contest/673/submission/17798097 ( which got accepted ! and the test case on which my code was hacked seems to give correct result ) Am i missing some thing or is it just my hard — luck ??? → Reply

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

Waiting for Rating Changes.....

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

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

Доброго времени суток. Сравните посылки 17798554 и 17797966. Прошу перетестить все решения на задачу 673C - Медвежонок и цвета, так как при отправке идентичного кода каждый раз сервер дает разный вердикт

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

    Меняй vi a(n); на vi a(n+1); у тебя не существует a[n] и поэтому должно выдать ошибку но выдаёт не знаю почему TLE.

    C

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

      Та это не важно, само поведение сервера доставляет: то на 4 ТЛ, то на 10, то на 26...

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

        Засылаем программу с undefined behaviour, его же и получаем на сервере. Чему удивляться?

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

        Важно. У тебя undefined behavior.

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

Кф такой тролль(

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

My todo list before todays contest.

Facepalm the point "Convex hull trick" is in my todo list for a several months and I failed today to solve C although I come up with a right DP.

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

    Do you imply that you didn't yet learn CHT? sorry if I'm acting stupid

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

Доброго времени суток. Сравните решения 17787696 и 17803831 разница лишь в комментарии. Прошу перетестировать все решения по задаче 673C - Медвежонок и цвета, так как при меньшей загруженности сервера или просто другом сервере решение отлично успевает в 2 секунды, undefined behaviour вроде нету.

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

    решение отлично успевает в 2 секунды.
    1794 ms.
    P.S. Самое быстрое решение по этой задаче : 46 ms.

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

      Я знаю, что моё не идеальное и впритык, но всё же успело потом так почему на контестик её не засчитать?

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

    Мне кажется, здесь просто не совсем точные органичения: по-хорошему лишний логарифм должен давать ТЛ.

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

Так что там с футболками ? Нашей команде так никто и не написал, это у всех так или конкретно у нас так?

UPD: Ребят, кому — то пришла? Потому что нам ничего так и не пришло.

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

Lol

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

А футболки ещё не всем разослали? Просто нам до сих пор ничего не пришло :(

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

    мне кажется принтануть и разослать 250 футболок это не пол года. поправьте меня если я ошибаюсь плиз)

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

    Мне тоже до сих пор не пришла футболка. Яндекс — молодцы в этом плане, прислали примерно через месяц после конца Яндекс.Алгоритма.