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

Очередной сезон крупнейшей российской олимпиады Russian Code Cup стартует в субботу. Впереди новые интересные и нетривиальные задания, бескомпромиссная борьба и самые крутые призы.

Но мы подготовили вам еще один сюрприз: 17 апреля у каждого из вас есть возможность оценить свои силы. В 19:30 по московскому времени на площадке http://codeforces.ru состоится тренировочный раунд олимпиады со свежей порцией задач от создателей RCC.

RCC 2014 Warmup – это тест, который даст возможность попробовать свои силы и понять, к чему готовиться в раундах чемпионата. А для «бывалых» участников это идеальная возможность потренироваться и разогреться перед первыми сражениями RCC 2014!

Автором большинства задач этого раунда является Aksenov239 — постоянный автор задач RCC. Конечно же ему помогали и другие члены жюри RCC-2014. Раунд пройдет как в div-1, так и в div-2, так что все найдут себе задачи по силам.

Ждем вас в четверг в 19:30 на площадке http://codeforces.ru

UPD: Итак, разбалловка раунда: Div1: 500-1000-1500-2500-2500, Div2: 500-1000-1500-2000-2500. Всем удачи!

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

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

Последняя ссылка на codeforces неверная из-за восклицательного знака.

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

Круто! А раунд будут рейтинговым?

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

Это стандартный раунд codeforces или по правилам ACM?

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

will the round be rated?

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

"Though Russian Code Cup is open only for those who speak Russian" will the problem be translated in English??... Can the one that can't speak Russian take part in it?

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

    The Russian Code Cup itself is in Russian, it will not be translated.

    RCC Warmup round will be like ordinary CodeForces round (just "sponsored" by Russian Code Cup), so it will have statements in both Russian and English. Sorry if there is any confusion.

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

Я правильно понял, что это будет обычный CFR, только называться он будет по-другому?

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

Вопрос про сам RCC. Верно ли, что участники до 18 лет могут участвовать, но в финал пройдут 50 сильнейших участников отборочного раунда среди тех, которым исполнилось на самом деле исполнилось 18?

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

are the problem's difficulties as usual rounds?

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

...

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

    на Codeforces будет только Warmup раунд. RCC будет на своем сайте

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

will the round be rated for every codeforces members or only for Russian participants??

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

Great start!

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

Good Luck everyone! Hope that the website wont be down again during the contest.

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

delay for ten minutes?

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

Немного не в тему: с большим трудом нашла на сайте RCC информацию о точном времени раундов. Может быть, стоит поместить ее на более видное место?

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

Those hacks in B! I did a bitmask dp with complexity O(N * 2^M) as did many, I believe. Is there some very tricky case or is the time limit strict?

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

For Div1 problem B, it was very tricky that INF=1e18 isn't enough. I resubmitted because of this, and made 4 successful hacks.

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

I think the problems were harder than usual.

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

а как решалась A div 2?
на чем ломали?

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

    Я не стал придумывать что-то особенное и сделал просто перебором количества раундов первого и второго типа. 6385830

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

Can't Div.2 Problem A give some explanation about sample tests?! Total inapprehension.

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

Не, ну это максимально подло: заводить в B маленькую константу inf, а в середине кода возводить ее в квадрат. -50 4 людям в комнате за полминуты

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

sorry, my mistake, yeputons find differ between tasks.

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

Неужели так трудно было в B уточнить, можно ли покупать два элемента с одинаковыми масками? Добавить хотя бы один сэмпл, где это видно? Или не игнорировать мои вопросы, а нормально пояснить (мне, допустим, из клара так и не стало ясно, что именно имеется в виду)?

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

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

    Даже если можно, это невыгодно, разве нет?

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

      Ой, я хотел сказать, элементы с пересекающимися масками.

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

Кто-то поток сдал в B div1?

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

    Какой поток, к ней элементано сводится Weighted Set Cover Problem, она NP-трудна.

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

Problems were very interesting...!!! Thanks for this Round.

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

Can anybode tell me, how could it get TL?!

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

For Div1 A: Outputting 10^6 numbers using cout with ios_base::sync_with_stdio(0) caused TLE :/ (also there was no large output warning).

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

Wow, so are time limit failures on problem A (div 1) something you were aiming for? While it's obviously good to remember that iostream is slow, you probably should have used different input bounds for that problem (or different time limit). There was enough room for hacking in that problem anyway, so TL-trick seems to be an overkill. Besides, in one of the previous D2 contests CF used to mention that "I/O size is too big for iostream, so don't use it".

Just my opinion (of a person that got burned on this).

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

    Ya, CF gives large input/output warning in such scenarios : so I didn't bother using cout with ios_base::sync_with_stdio(0) (and got TLE!) which seems to be as fast as printf in many scenarios : it must be only 1.2-1.5 times slower than printf anyways.

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

Why no explanations to the sample cases? Some of the wording was more than a little confusing (not that I'm complaining with my hacks), and I suspect some people failed because of it.

Also Div2C/Div1A really should have the "large printing" warning — there's no point to having people who solved the problem TLE because printing is too computationally expensive. That makes it not a programming problem anymore but just semantics about syntax, which (at least in my opinion) does not a good problem make.

Also it seems like it is almost impossible to pass with Java — only one person managed it with Java 6 and not many more with later versions. Just a very bad problem.

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

    Also it seems like it is almost impossible to pass with Java — only one person managed it with Java 6 and not many more with later versions. Just a very bad problem.

    So, you've made a real application, and have sold it to a customer. The customer soon responds back: "On big inputs your program is too slow, while your competitors' solutions don't have a problem... Can you fix your program?"

    And you reply: "No, my program is fine, increase your time limits instead and ignore better solutions."

    Does this sound plausible? If you choose to write in language X, you have to know and accept its advantages and disadvantages. It is your choice to use this language, and so you can't complain if its disadvantages bite you back.

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

      I'm not sure which solution of mine accidentally became Java, but I was unaware that I still use this language for Codeforces. Thank you for correcting me. I will be sure to take Java's disadvantages into account when coding in C++.

      The issue with this problem stems not from the fact that a slow solution is not passing. The issue is that, despite the fact that the contestant is really solving the problem, different methods of printing result in wildly different verdicts. Besides the precedent of specifying not to use cin when this is a possibility, this is just a terrible problem from an algorithmic standpoint. What is the purpose of a problem that is all about choosing the correct printing method? Perhaps it's good as a homework problem, but it has no place whatsoever in a contest. Especially since some languages just can't do it (and Java is not exactly an obscure language...) under typical circumstances.

      Anyway, there is a profound difference between industry coding and recreational coding. Pick any nontrivial problem, and pick a random solution. Is this code you want to see in production? Of course not. With some exceptions, the formatting will likely be difficult, there is likely to be silly hacks to get around issues rather than writing clean code (as there should be with time constraints), but most importantly you probably need to take a long time to figure out what the code is doing. When was the last time you saw a solution with proper documentation, abundance of comments, and written for readability, accessibility, and evolvability? So the objection "this code wouldn't be good in industry" is a stupid one — no contest code would be good in industry (if it is, you're probably not doing contests right!).

      I'm not sure whether you work in the coding industry, but when was the last time you considered runtime as a serious factor? Besides not doing something insanely stupid like making a code O(N^8), there just isn't a great need to. Sure, several algorithms are useful, but implementing complicated things to avoid a logarithmic factor is silly. And anyway, code should not be elegant or clever — it should be readable and understandable. If you see

      // to convert prefix to postfix
      main() {
        char c = getchar();
        (c == '+' || c == '-' || c == '*' || c == '/') ? main(), main() : 0;
        putchar(c);
      }
      

      in somebody's code, even though this is some pretty damn cool code that person should be out of a job quickly. It's not worth the headache that someone else is going to have when trying to edit this code a few years down the road.

      I suppose we'll agree to disagree, but I think a good contest problem is one that provokes thought, has a nice solution, and gives that "aha!" moment when you solve it (perhaps because of my math background where an inelegant problem is considered a huge disappointment, not a good exercise). This particular problem satisfies exactly 0 of these criteria. Ok, maybe you have to think a moment to realize you can just connect a vertex to the k nearest clockwise ones, and maybe another moment to prove it if you're so inclined. But there's nothing interesting about the problem, and it's not one of those problems that you recognize a week later as "oh, I remember that problem! That was a nice one" (assuming you remember it at all, which this problem doesn't give much reason too). It's just not a good contest problem. A good homework exercise in the speed differences between output, but not a good contest problem.

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

        Did not want to edit such a long post. I want to clarify that I don't mean anything against the authors of the problems. Writing good contest problems is very hard, and ensuring they are more or less new (or at least not recently used) is just as hard (for example this problem from a month ago is extremely similar to this C). Anyone who goes through this self-inflicted pain is to be commended regardless of the end result. Bad problems happen, and when they do all we can do is give as constructive criticism as we can and move on.

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

    I had an interesting situation yesterday. I solved this problem in my favourite language — PERL. I sent submition and it passed pretests. Later I thought that Perl may be too slow to AC, and it was easy to translate Perl code to Pascal. So I did. And then I skipped my Perl submision, and sent Pascal's. At final tests I have TLE. But later I tried to send my Perl's program and it passed through 342 ms (6392774). So sad I was! But I was surprised, that Perl can do this!! My Pascal submision used up to 1000 * 499 iterations each having 2 "write", but later I joined to 1 "write" and passed in 826 ms. Why Perl hadn't TLE? I used array to push here my results, and later I asked to print whole array. Another succesfull variant was to make empty string, and add to it ("push back") answers, and later — ask to print this line (or so called "multiline") — 6395984 857 ms.

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

В div. 1 B предполагалось O(n * 2m)?..

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

    Да. По крайней мере, у меня такая сложность.

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

    Да: сортируем людей по числу мониторов, которые они требуют. Далее вычисляем в этом порядке динамику best[t][mask]: какую минимальную сумму можно потратить, решив задачи из mask с помощью первых t людей. Когда best[t][(1 << m) — 1] != inf, обновляем ответ числом best[t][(1 << m) — 1] + b * k[t].

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

      Блин, div.1 звери. Как-то совсем много народу порешало...

      P.S. A упала из-за кривой проверки на -1, B упала из-за отсутствия сорта. Победитель по жизни я, лол.

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

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

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

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

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

      Кстати, первое измерение в таком дп не нужно, всё можно обновлять в одном массиве (потому что два раза одного и того же чела не выгодно брать, и такое обновление не произойдёт).

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

Div.2: Why not 1000-1000-500-2000-2500 ? I joined to contest when less than an hour left, and solved only C. Statistics said to me to try to do so.

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

For D-Div1 I thought of 2 segment trees that you hold while you are decending in a rooted tree. Of course , I have to find the LCA in log(N) and the point that is at the middle distance between two nodes ( also log(N) ). It's quite complicated because is a lot to implement.

What would be a simpler way to solve D ?

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

Worst English statements Ever!

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

When can we see our new rates? When is the system test going to end? Anybody knows?

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

В задаче B подразумевалось N*2^M? Если да, то как-то не очень, при ТЛ 1 сек...

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

Div.2C I used cout instead of printf, and it turned out to be TLE. So sad!

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

What a weird contest it was. So many WAs on A and B (Div 2).

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

Hundreds of solutions failed because of one fucking endl.

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

    And hopefully hundreds of authors learned to use '\n' or "\n" instead of endl next time.

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

    Fortunately I passed Pro.C(Div.2) by a fluke with 997ms using endl.

    6390244

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

    I don't understand why my solution passed 1000 499 and failed on 999 499. http://codeforces.com/contest/418/submission/6386127

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

      On 1000 499 your program took 966 ms. Not surprising that another similar case would take over a second, it's just random variance.

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

        But it should be strictly less, shouldn't it? The latter case will have less iterations. If this is random variance, then this problem was a mistake on the part of problem setters.

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

          Suppose that with probability 95% the 999 case will execute in time from 949 to 1049 milliseconds, and the 1000 case — in time from 950 to 1050 milliseconds. Still this doesn't forbid the first case from executing in 1040 ms and failing, and the second case in 980 ms and succeeding.

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

      I don't know. But maybe division by 999 is slower than by 1000?

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

The problem http://vn.spoj.com/problems/VMQTREE/ was similar to the Div. 1 D problem today, except the 50000-limit and the multiple-tests. Sorry, because I don't have the English statement.

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

    We haven't known that.

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

      Can you explain why in problem E you used pashka solution as reference one, but only set TL about 16% over its runtime? What wrong solution you tried to fail with such tiny margin?

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

        Sorry for late answer.

        Because there is normal solution, which is passing in the half tl, and for this one we haven't normal proof about asymptotics. Because of that we have added special test at which pashka's solution isn't working well. This is the same test at which you have failed. But it have passed because of the buben-constant and I wanted to make my solution to pass half tl.

        And it was so pity, that your solution haven't passed, because this contest could have been the "best" contest.

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

          But you had not answered second part of my question — what solution had you tried to fail? Also you either want approach to pass — and that means setting tl at least 2x of the approach runtime — or you want it to fail — and that means setting tl several times under this approach. You did neither here

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

            I wanted that the solution, that you have sent, could pass only with some buben-optimization. I can fail pashka solution too, if I manage against some constant. Really, pashka's solution don't pass. I don't know, why you know background information.

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

              Well, I can prove my solution's runtime. It is worse than yours by factor sqrt of log. But now lets look at c++. Do you think my solution rewritten in c++ would not pass?

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

                Probably it can, you can check it. I don't think, that it can be much faster because of memory.

                And sqrt(logn) gives you x4 slower solution. And it's big difference.

                I think, that this is my fault that tl isn't so clear, but as a result the solution with wrong asymptotics haven't passed. I think, you can agree with my last statement, that wrong asymptotics shouldn't pass. And here you have written solution on your own risk.

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

                  I do not believe anyone within one's mind would try to differentiate solutions with factor of 4 because just so much depends on implementation. I do not believe you wanted to and I do not believe you are sincere when you say that you are glad you did. I do believe whole contest has poorly set time limits

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

                  Maybe you are right, maybe I'm wrong. But we haven't asymptotics for this solution. That's why we aren't consider this solution to easily pass tl.

                  My sincere apologize, but your solution has wrong asymptotics, and really I can't see the problem. If somebody have solved this problem with the same solution, we could have considered to change tl.

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

                  Because I believe given existence of solution with runtime of 3 s one need to either set tl at least 6 s or at most 1.5 s (and while we are at it I do not like tls of less than 2 s at all — if you do not want to clog judge queue use multitest)

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

    I was tester of that problem. I'm so sad that I forgot about this match and skipped it :(

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

Too weak pretests. TopCoder level weakness, except there we at least see those tests.

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

Обрубать решение по C(div2)/A(div1) использующее потоки, мне кажется не особо правильным.

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

    использовал cin/cout. Зашло: 6393221

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

    Поменял в cout выводе, endl на "\n" и получил accepted.

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

      Еще лучше

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

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

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

    причем у одних заходит, у других нет, хотя код практически идентичный

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

I can't believe I got 3 'Failed System Test'! My experience in contest: Always use printf :(

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

dont you think its unfair? For Problem C Div 2* half of the people who get pretest passed got time limit for not using something like printf!!!! please for next times mention that we should use! (sorry for bad English)

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

Задача А(див1) была хорошая, интересная, но разве ее главной фишкой было повалить решения на выводе ответа?

Так или иначе, спасибо, узнал много нового про <<endl )

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

Is there anyone else, who got AC on Div1 C using random :P? http://codeforces.com/contest/418/submission/6394595 (corrected link) So bad, that I couldn't make it during a contest, because my solution got TLE on case 2 1 ; / (but not on 1 2 :P).

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

    I used random in Div1 C to generate two rows of length n and m.

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

      But if you got that it suffices to generate two rows of that length you have already solved 90% of problem :P. So it doesn't count :D. I tried to find solution of form

      aaaaaaab

      cccccccd

      eeeeeeef

      ... and fortunately solution of that form always exists :P (at least for n, m <= 100 :D)

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

        Yeah I checked that too during the contest but was not able to continue XD. how do you use that fact?

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

          Just generate some rows of that form which fit, start from any initial position and change one randomly chosen row from actual candidate to solution into another randomly chosen one from all generated rows till you got a solution. Also you can look at my code.

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

    Can you explain a bit your idea , please ?

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

    I took 4 random numbers in range from 1 to 100 and put them like this:

    x x x x x y
    x x x x x y
    x x x x x y
    z z z z z t
    

    202 ms

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

      Wow, solution without any deeper thoughts and it works :D! Great!

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

      but why does that work?! i tried to prove but couldn't, please explain a little more.

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

      Actually it does not work :D. "50 68" is a counterexample. Even if solution exists my computer says that it will get TLE :P.

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

        Oops =)

        However, such a solution does not exist for this test and some others:

        { 50, 68 }, { 50, 72 }, { 50, 83 }, { 50, 84 }, { 50, 87 }, { 50, 90 } 
        { 82, 68 }, { 82, 72 }, { 82, 80 }, { 82, 83 }, { 82, 84 }, { 82, 87 }
        

        But if change the upper limit to 120, it will be for any input.

        In fact, we can just iterate over these 4 numbers. With the limit of 120 it gets AC in 15 ms

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

          I iterate over all 4 numbers and got Accepted
          First I think testcases are too weak but I don't now is that fair or not.
          Second why if the limit is 120 this solution is valid for any input ?
          cout<<"Thanks"<<endl;

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

            I don't know if solution of that form exists for any input, but I'm pretty sure that setting limit to some constant won't be sufficient for arbitrarily large input. And why 120 works for n,m<=100? Because you can simply check it for all valid inputs :P. I doubt that there is a nice proof of that fact.

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

just cout<<endl nd cout<<"\n" being the reason for AC nd Tle is not justified. Not at all.

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

TLE in Div 2 problem C with cout , AC after the contest with printf -_-

UPD : sorry , i clicked russian by mistake

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

Название контеста warmup подобрано неспроста — оно характеризует состояние многих участников после написания этого контеста :)

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

Give this comment '+' if you want the contest be unrated. Give this comment '-' if you want the contest be rated.

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

Спасибо, конечно. Раньше не обращал внимания на сброс буфера из-за endl и последствия этого. Теперь буду знать.

Но все же, что это такое?

Test: #34, время: 935 мс., память: 0 КБ, код возврата: 0, код возврата чекера: 0, вердикт: OK
Ввод
999 499
Test: #41, время: 1000 мс., память: 0 КБ, код возврата: 0, код возврата чекера: 0, вердикт: TIME_LIMIT_EXCEEDED
Ввод
999 499

С какой радости? Там после 41 этот тест еще несколько раз встречается, или больше нету?

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

TLE in Div 2 problem C with cout , AC after the contest with printf -_-

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

    Me too :(

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

    cout's normal behavior is to sync with C's stdout stream. Put this as main()'s first instruction: ios_base::sync_with_stdio(false); You should expect a major io improvement.

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

B div 2 had a very vague problem statement.Half of my friends interpreted it differently and most of them failed.In my room too only 2 solutions passed for B.

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

при системном тестировании выдал тл. после раунда переотправил то же самое решение и полное решение. как это? http://codeforces.com/contest/417/submission/6395189 http://codeforces.com/contest/417/submission/6389180

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

    во время систестов нагрузка больше => решение которое еле влезает в 1с (982 мс) на дорешивании вряд ли влезет в 1с на систестах.

    p.s. flush всех неплохо потроллил на контесте :)

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

    Время выполнения программы зависит от состояния кешей процессора и памяти перед её запуском, от прерывания программы другими процессами и/или перевода программы на другой процессор (хотя Codeforces наверняка это минимизирует), и от других факторов. Так что время на разных запусках может немного различаться.

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

    печаль...

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

А как посмотреть протокол по взлому? Во вкладке "взломы" написано — "Нет данных".

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

I don't know it was good or a bad contest/ typical or harder set but I must say, the feelings is different this time. Couldn't understand A (replica of april fool contest! what is given and what they demand!!! ). Learned an excellent DP from problem D. it was a nice trick to sort the input. And about E, i will definitely like to learn to solve this problem. by the way I found a solution for N*N and if it were a square matrix then it would be at most C in div 2. :p . Overall , I enjoyed this contest.

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

6389193 на локальной машине тест 2 0 1 1 1 даёт ответ YES, на сервере же NO

gcc версия 4.8.2 20140206 (prerelease) (GCC)

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

    Если вместо base a[n]; написать static base a[100005];, то ничего не меняется?

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

      нет

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

        Если функция-компаратор для qsort() для каких-то двух элементов возвращает 0, то тогда их взаимное положение в отсортированном массиве не определено. В этом тесте как раз оба k равны.

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

А на java вообще реально A в Div 1 сдать было? http://codeforces.com/contest/418/submission/6387067

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

In problem C of div 1, we only want to find two matrices: A[m..1], B[1..n] and the result will be A x B and matrices A, B such that sum of square of all its elements are also a square. But we know that: 169 can be express as sum of k square number with 1 <= k <= 155, so the given problem can be solved straight forward. This is my code:

http://codeforces.com/contest/417/submission/6395366

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

Для чего в D(div2) требуется сортировка по мониторам?

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

Div1 A / Div2 C can be used to compare time taken by different print statements.

Time taken on my solution —
1. Using cout and endl 998ms :)
2. Using cout and "\n" 265ms
3. Using cout and '\n' 202ms
4. Using printf 296ms (strange?)

Can anyone explain why 3 is faster than 2?

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

    Because printf("%d", x); has to parse the format string each time, and cout << x; already knows at compile time what should it print, cout in theory should be faster than printf. And it seems that in this case it is not only in theory, but also in practice.

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

    I think 3 is faster because interpretation of one sign takes less operations, than interpretation of string, contains one sign.

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

My solution for Problem C got TLE on Test Case 40(solution id: 6392630) during system testing and after the contest I submitted the same code, it passed Test Case 40(solution id: 6395155). After some time, I submitted it again and it got TLE on test case 34 (solution id:6395832) which it had passed on previous two submissions. Don't know what's wrong??

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

C div 2.

cout<<endl; — TL >1000ms

cout<<"\n"; — AC — 500ms

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

Объясните, пожалуйста, что не так с этим генератором http://pastebin.com/kHiDe0qg для B Div 1 ? Говорит, некорректный взлом: FAIL Expected EOLN (stdin) [validator validator.exe returns exit code 3] Уже раз двадцать код пересмотрел и так и не понял в чем проблема.

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

    Пробел в конце строки?

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

    printf("%d ", j+1); выводит один лишний пробел в конце строки.

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

      Без пробела тоже отсылал. http://pastebin.com/MaV2PF2k

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

        А теперь отсутствует перевод строки в конце теста.

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

        Возможно, в этом дело?

            if (i != n - 1)
                cout << endl;
        

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

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

can anybody plz explain how to do div2 problem D.

thnx for help .

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

plz explain how to solve problem D of div 2 .

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

    The number of problems were only 20, so we can ask what is the min cost for a given subset of problems. To do so, sort the persons offering services in decreasing order of monitors demanded and for each one of them run a subset-sum type loop update for each subset 0 ... 1<<m -1. This ensures that subsequent updates to a set from a subset has fewer monitors and hence does not include the cost of monitors, only the extra cost x. Include the base case of monitors cost + x for subsets covered by single persons and you are done. Time Complexity : O(n * 2^m)

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

Sad situation in problem C div2. This shouldn't happen again. -_-

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

was it only me or did anyone else have difficulty understanding the very first question? I thought the no of problems was 2 for this case

1 10

7 2

1

because 1 problem for main round and another problem for additional round.

for this

2 2

2 1

2

no need of problems, all the past finals winners will proceed.

So, my assumption was there can be three cases 0, 1 or 2. Can anyone explain what the question is really asking? I appreciate it.

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

    think like this:

    • the number of winners from rounds is at least equal n*m-k, and

    • if he decide to have i main rounds and j additional rounds, then total problems is c*i+d*j and total winners from rounds is n*i+j, and

    • the question asks you to print the smallest value of (c*i+d*j) that satisfies n*i+j>=n*m-k :)

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

Почему не сделать тайм на Див2 Д 2 секунды? На джаве дп по маске и номеру друга не заходит, на ++ заходит. Решение со сложностью из разбора.. обидно как-то (или я не умею писать на джаве?)

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

А так, спасибо за раунд — отличный!

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

    Все решения написаны на Java.

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

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

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

tourist had so much luck in this contest :P! Egor on 2nd place got TLE on E, because TL was very tight and flashmt on also 2nd place got TLE on A, because of endl's instead of \n and they will easily win if it weren't for those unlucky TLEs!

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

Horrible problem statement. Could not understand A and B of Div2.

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

Problem A,B and C is too week in data

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

The problems is nice,I find many bugs in my code,although I have passed the pretest

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

Getting WA in case 11 in DIV2 number B problem :( :( Can any one provide me a small test case for which i will get WA? Here is my code.6398585

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

А это нормально, что в Div1-B заходит следующее решение: динамика, состояние описывается двумя параметрами: маска решённых задач и количество мониторов, которые имеем. А меморизация происходит через map<pii, LL> ?

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

Could someone explain to me the Div2 C problem ?

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

Я, наверное, один такой, у кого возникли проблемы с пониманием условий в этом раунде.

Задача B\Div2

"... каждое отправленное решение A характеризуется двумя числами: x — числом различных решений, отправленных до первого решения, идентичного решению A, и k — идентификатором участника, который является автором решения."

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

"... каждое отправленное решение A характеризуется двумя числами: k — идентификатор участника, который является автором решения и x — число различных решений, отправленных участником k до первого решения, идентичного решению A"

Задача D\Div2. Стоило, наверное, отдельно прописать, что каждый друг может решать уже решенную задачу. А то в итоге непонятно, стоит ли использовать xor или or.

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

Пишу сейчас виртуально этот контест для Div. 1 и стабильно получаю "Отказ тестирования" по В. В чём проблема?