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

Автор josdas, история, 9 лет назад, По-русски

Доброго всем времени суток!

13 августа 2015 года в 19:30 MSK состоится очередной раунд Codeforces #316 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.

Это мой первый Codeforces раунд. Надеюсь, он вам понравится.

Хотелось бы сказать большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

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

UPD: Распределение баллов по задачам 500-1000-1500-2000-2500

Желаю всем участникам удачи!

UPD: Всем спасибо за участие!

Поздравляем победителей!

Разбор

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

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

great contest :))

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

    I'd prefer 11:30 pm than 9:30 am (my local time), when I need to be in the office working.

    No reason to complain, guys — this is Internet (i.e. INTERnational NETwork) and international site. Get used to it.

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

    In my city is 00:30 pm QAQ

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

i just want to don't see unrated Participants as firs & second & third ...

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

Is it rated?

please answer me for this important problem :))

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

i just don't want to see unrated paticipants as first & second & so on ...

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

get it

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

in my city is too late,it start at 00:30

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

What about the point distribution???

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

О, Стасян:D

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

Lets hope this round features a variety of problems with less math :P unlike the previous round

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

I think the good round should include problems from different topics ... because if you are not good at a topic you can find another problem with a topic you are good at .. and this will be fair:)... but also math is very important and any programmer should be good at it.

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

I haven't solved a single good question this week. How do you guys stay motivated? Please give me tips. I love coding, but sometimes, I just don't feel like it, but that won't do. Please help :)

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

    The key is to upsolve once the competition is finished. In other words — read the editorial and solve everything you weren't able to solve during the competition. This way you learn from your mistakes and get better.

    My main motivation is that I'm getting better with each competition. When I started Codeforces I struggled to solve A and B, now I'm consistently solving C and pushing towards Div1.

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

      2 hours is a very small amount of time to think about all the 5 problems. Then editorial comes within the next hour, so, 3 hours in all. Shouldn't you spend at least a day before jumping to editorials? Besides, looking at editorials suck out the joy of solving a difficult problem! I like to give the problem a fair shot before I open editorial. Why is your method more effective than mine, can you explain?

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

        I might have expressed myself wrong. I don't look at the editorial immediately after the competition, and if I manage to get some kind of an idea (or anything to work around) within an hour or two, I try to solve it without an editorial.

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

        Let's look at it in a different way: don't you think that wasting whole day on a problem is bad, because you might spend that day on learning much more things instead of reinventing the wheel?

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

          If I can re-invent wheel, who knows what else I can invent! In terms of ratings and contest performance, I can see my method is hardly efficient......but it is so much fun! I learned DP(whatever much I know about it) almost on my own... I learned LIS in n log n on my own.... and just a few others.....

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

            I heard similar ideas from people who are performing much better than me, so the fact that your method doesn't work for you (at least so far) doesn't mean that it is bad method in general. Maybe you need more time, maybe you simply aren't trying hard enough.

            From my point of view — it may make sense when you already know all basics and you are currently working on improving some "thinking skills" or stuff like that — but at the very beginning, when you simply need to learn a lot of different stuff, it doesn't make much sense for me.

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

      congrats you finally got into div1 !! Happy for you ! and i m experiencing the same too !

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

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

UPD. Теперь все в порядке.

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

О, ASСтас :D

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

Автокомментарий: текст был обновлен пользователем josdas (предыдущая версия, новая версия, сравнить).

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

This will be the best contest of this week

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

I think this is the last contest of August.

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

591 unrated users ... wow.

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

591 unrated users and counting.. ok.

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

Hi guys! This is my first contest and I hope not the last. I hope that one day we will take part in CF-International:D GL && HF!

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

Woke up in the middle of the night, and find out that I didn't register after finishing problem A...

Cheers!

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

Как по мне сложность задач оценена неправильно. По моему задачи скорее вот такие: B, A с подвохом, B, E, E.

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

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

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

      Я думаю, моё мнение, как участника раунда, будет интересовать проблемсеттера. Тем более это его первый раунд.

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

        Спасибо за отзыв, в следующий раз учту.

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

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

          Если будешь делать ещё контесты, то делай разбор наиболее подробным, так как на CF есть пользователи совершенно разного уровня знаний, а разбор, вроде как, делается для всех.

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

            На счет разбора я понимаю, мой косяк. Писать начал поздно и просто не умею подробно все оформлять. На будущих раундах отведу больше времени на это.

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

как решить С?

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

    Например так: http://pastebin.com/Wg9BUS1v

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

    Ответом на запрос является количество точек в строке минус количество групп, образованных подрядидущими точками.После изменения i го символа нужно обратить внимание на i+1 ый и i-1 ый символ строки, Если i ый сивол точка '.', то он может дополнить одну из групп(в который входит i-1 ый символ или i+1), объединть две в одну(i-1 ый и i+1 равны '.') или образовать новую группу из одного элемента; теже мысли также обощаются на разъединие групп.

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

How to solve D?

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

E was almost exactly http://www.usaco.org/index.php?page=viewproblem2&cpid=553

Only difference was it was a rectangle, not a square...same constraints, modulo, and all.

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

too many hacks on problem B

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

The contest was really nice, especially C and E.

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

Hacking Contest!! it's very nice :D

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

Thank you josdas. Nice problem statements, and not strong pretests -> posibility to hack :)

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

This round was very interesting thanks to the 'Hacks'. I've never seen Div. 2 this passionate about hacking.

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

Did anyone solve E with hashes??

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

    How would you do it? There is too many possible paths = too many strings to hash.

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

    I tried hashing, but my solution exceeded the memory limit. In hindsight, it obviously wasn't going to work as there could be (500 * 500 / 2) ^ 2 pairs of positions, which is well over 256MB when hashed into longs.

    Did your solution work?

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

      Isn't it something like 2^500? How could you achieve (500*500/2)^2?

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

        My submission

        I kept track of two positions while running a DFS, with one starting at (0, 0) and the other at (N — 1, M — 1) and continuing until either the two positions met up in the middle or passed each other. To take care of overlapping paths, I hashed each pair of locations. There are (500 * 500 / 2) possible locations for each the first and second positions, giving a total of (500 * 500 / 2) ^ 2 possible pairs.

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

          ok, it makes sense. Though I don't see a way to improve this solution (cutting memore consumption for example).

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

Wasn't E too basic/known? At least, I have thought of the same problem a few times when I don't have what to do :D However, it was a nice contest, I liked D :)

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

How to solve C?

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

    With segment tree. If at i-th and (i+1) positions there are points then we have 1 at our segment tree. Answer for query is sum on whole tree.

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

    With string. For every query you look into substring with wide of 3 chars: at query position and +-1 positions. Then you remove from counter the number of possible '..', change query letter, and then add the new number of possible '..'.(12518363)

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

For D, how to make projection of arbitrary point to arbitrary depth?

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

D has offline solution, right?

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

Вот это по-настоящему эмоциональный контест! Спасибо за него! Респект таким пацанам!

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

great contest ! thanks ":))

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

This contest had a really good difficulty curve.

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

    A,B,C easy, D,E very tough (if you never solved something similar)

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

      It's a lot better than the usual CF contests, which have ~3000, ~2000, and then ~500 solutions, because it let's beginners solve more problems than usual. Although I do agree that D and E were very tough relative to A,B, and C, moreso than usual.

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

Контест взломов!! Всегда мечтал!

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

problem D strict time limit :/

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

Room topper for the first time :D

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

problem D strict time limit :/

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

    No. For D there is a O(N + Q*logN) algo. Your code is O(Q*26*logN) which should be TLE.

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

      Can you describe the basic idea of the solution? Thanks

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

        Key steps:

        • For each height, store all the nodes of that height.
        • For each query, use binary search to find the range of the nodes that is in subtree of v at height h. If you don't know how to do this, you should probably read some code (maybe FatalEagle), it is not very easy to explain this step.
        • When you know the range of nodes, you have several choices. One is to use a cummulative array, which leads to either Q*26*log or Q*(26 + log), depending on how you implement it. You can also read my code using bitmask trick for Q*log.
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          FatalEagle got AC with Q*26*logn complexity. See 12502770
          My code with same complexity got TLE'ed. :(

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

            My solution is the same U_U , but i got TLE.

            Submission

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

            I figured that the constant is low enough so fast input should make it work (input can be very huge).

            Your solution with fast input works too: 12517730

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

              I have seen that using the upper and lower bound of C++STL directly in the main , is faster than make a function calling upper and lower bound.

              TLE

              AC

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

              I got AC by defining my array as 5*10^5 * 26 rather than 26 * 5*10^5. But for similar situation on Codechef defining like the latter one had less overhead than first one. My AC'ed submission after making these changes. 12517583
              This was the codechef ques where we had to do the opposite to get 100 points. Codechef Ques
              Not sure what is happening here. o.O

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

                You get more cache hits in the first way, since you want each letter of each level instead of each level of each letter (in which case 26 * 5*10^5 would be the better way of declaring the array).

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

              is using lower_bound/upper_bound STL faster than implementing binary search? because with the same complexity as yours, mine get TLE.. my submission

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

      mine O(Q*26*logN) solution got TLE What is correct approach though?

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

        Time Limit was weird. My code with the same O(26QlogN) complexity passes in 1980 ms . This seems unfair towards many participants .

        Link : 12513092

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

          yeah, I had same implementation with vectors and STL lower/upper_bound functions. I got TL when submitted it, and decided that it should work fine if I remove vectors and STL lower/upper_bound functions, but this did not help either. :( I do not really understand why my solution has bigger constant though :( I'd like to understand it.

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

      Very nice idea with bitwise xor's!

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

      Unnecessary strict constraint i think , a improve of a 26 constant is not a big improve in my opinion . BTW the problem was very interesting.

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

        I think you misunderstood my comment. It was NOT 26 --> log, it was 26*log --> log, which makes the program 26 time faster.

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

          oh, I think I got it. We have to use bitmasks. thanks for the hint.

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

          I mean a 26 constant improve is not a big improve in my opinion , i think a nice improve is taking for example improving n^3 to n^2 , and if someone really like improving some kind of things of contasts , there is a lot of problems in SPOJ that you can solve , i know that my algo is 26 n log n and it past pretest , but fail in system test.

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

        It's improvement big enough to distinguish solutions by time. So it is a big improvement.

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

      my O(Q*26*logN) got AC :)

      how to optimize it to O(N + Q*logN)?

      UPD: sorry my code is O( Q*( 26+ log(n) ) ), but it took about 1800 , strange!

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

        Unfortunately mine not.. To take away 26 you make xor sum on BIT,and every character is represented as a bit.

        If the answer on interval has more than two 1 bits in its binary configuration the answer is no.

        Xor helps you for parity,because 2 bits of the same (two 1's) make each other disappear.

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

        Really strange. I have the same idea. 12517064 — 967 ms.

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

    i upsolved D using this thing: "if there r no letters X in subtree of vertex V -> continue;" passed in 1300 ms

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

    Changing 26 * N array to N * 26 array gave changed TLE to AC :/

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

Haven't read B statement to the end. I can't understand what the importance to the player of which number he chooses — bigger or lesser if it gives the same probability to win...

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

Хнык хнык(3 таски слетели)

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

Are future contests going to be scheduled on weekends? I know many of us have school starting soon.

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

    Agree x100000. These contests are in the middle of school for me at 11:00 or 11:30 AM. Would be really nice to have them on the weekends.

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

The only thing I've thought about in D was to cache the parity of all descendants of a node on all child layers in that node. This could occupy a single int per node per layer, if encoded as a bit string. However, this wouldn't be enough, since it's obviously an O(n^2) solution in terms of both memory and time, so it is definitely not feasible when n=500 000. How did you solve it?

UPD: The shortest submission 12506489 is also quite clear. I guess using a DFS clock and then binary searching on each layer is a standard technique.

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

one of my friends :

here

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

    I think i can relate to it.

    Not reading whole problem, or reading it incorrectly is a major issue for me. I don't know what happens during a contest, so i got three WA in problem A.

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

Weak pretests in problem B :'( I can't believe I missed the "minimum" part ._.

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

Codeforces Round #Hack (Div. 2)

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

What were the states and transitions for the problem E dp?

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

    dp[x_first][y_first][x_second][y_second], but this will TLE and ML.
    So we can convert the state into dp[x_first][x_second][len] witch is O(N ^ 3) Memory and Time.

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

Thank you for such a wonderful contest!

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

How did someone hack 24 solutions? can we hack people's solution from other rooms ?

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

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

    You can easily open a room and see that there are more than 24 users in a room

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

      There are 26 contestants (at least submit once) in our room, including myself, and only 23 of them pass at least a problem's pretest :)

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

    you can hack a person more than once and you can hack more than one problem .

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

    Also, it's possible to hack someone's solution twice. Submit, hack, resubmit, hack. Of course, the hacks must be distinct cases because resubmitting requires the submission to pass previous hacks.

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

Why this code http://codeforces.me/contest/570/submission/12498380 passed system test ???

It should be wrong answer. For 11 6 test it will be generate garbage value.

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

    try 5 3 , it should generate garbage but it gives 4 !! can anyone explain why this happens ?

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

    I think compiler removed "if(l>r)" since "a" wasn't initialized anyway.

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

http://codeforces.me/contest/570/submission/12515787
Code works fine on my pc as well as [on ideone].
However, same code gives tle on codeforces for same test case of n=5. What is the reason? (http://ideone.com/G1AApF)

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

    I guess you have some bug (like checking array[-1]) and it causes undefined behaviour. Then everything could happen.

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

      I can't find it! :(

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

        E.g. here is checking s[n] — "while(s[i]=='.' && i<s.size())". Use custom invocation to debut 5th test. You can comment part of your solution and check if you still have TLE.

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

This may be a dumb question but .. is the 'problem set' page temporarily blocked during a contest ?

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

josdas Thank you for this contest , keep going :)

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

Добрый!

Я новичок, недавно зарегистрирован. Вердикт по задаче "Решение взломано" http://codeforces.me/contest/570/submission/12506136

Можете пояснить, как считается что "Решение взломано"? или ссылку на правило где про это написано!

Спасибо!

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

    сылку?

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

    Переходим: Главная страница -> Помощь -> "По каким правилам проводятся соревнования?"

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

Автокомментарий: текст был обновлен пользователем josdas (предыдущая версия, новая версия, сравнить).

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

Got five successful hacks on B using the "1 1" test case.

After system tests: WA on "1 1" case.

Dammit.

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

Problem C = KISS

Keep It Simple, Stupid!

:( I never learn

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

Auto comment: topic has been updated by josdas (previous revision, new revision, compare).

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

That moment when you make 3 problems in one hour and you realise that you did the first problem wrong because you did not analised the simple case ..... So disappointing. But still my rating raised. A positive note though.

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

thank you for contest!:)) we want Editorial fast :((

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

By the way, the second problem from here is pretty cool: http://codeforces.me/blog/entry/17291?#comment-221267 :D Seems like this was the source of my thoughts about such problem.

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

How to solve E?

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

    You will start travelling in both directions (from the upper-left to the lower-right and from the lower-right to the upper-left). For making it simpler, we can make a copy of the input matrix and rotate it on 180 degrees so we move in the same direction in both of the matrices. The dp state will be dp[row1][col1][row2] (the number of ways to reach those cells and have the same strings so far) since from this we can get col2=row1+col1-row2. We can notice that if a[row1][col1]!=b[row2][col2], then dp[row1][col1][row2]=0. Otherwise dp[row1][col1][row2]=dp[row1-1][col1][row2]+dp[row1-1][col1][row2-1]+dp[row1][col1-1][row2]+dp[row1][col1-1][row2-1] so we need the information only for row2-1 so we can store only the last two tables. You can take a look at my submission for more details, although it looks really crappy.

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

Firs 3 problems so eeeeasy! NOOOOOOOOO! Why did I miss this contest, I am such a looser, guys!

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

У меня одного архив не доступен?

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

Although this may seem stupid, but can anyone explain how to solve Div2 Problem B?

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

    There are two main cases we can check:

    Either there will be more numbers between N and M, or there will be more numbers between 1 and M

    Take this set of numbers, for N = 10, M = 3

    1, 2, 3, 4, 5, 6, 7, 8, 9, 10

    M is 3^

    Notice that choosing 2 will mean you win on 1 or 2 Now look at what happens if you choose 4: You will win on any choice from 4 to 10.

    In this way, you want to choose either (m+1) or (m-1), based on what would give more winning numbers Some code might look like

    if (n — m > m — 1) print m + 1 else print m — 1

    .... and don't forget to print 1 when n = 1

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

Auto comment: topic has been updated by josdas (previous revision, new revision, compare).

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

D had a very simple offline solution too in O ( N + Q * 26 ) !! here is the link to it http://codeforces.me/contest/570/submission/12505776

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

Hi,

I can't figure out what's wrong with my solution for D... Here it is: http://codeforces.me/contest/570/submission/12521712 Please help!

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

Не мог бы кто-нибудь, пожалуйста, объяснить, а то никак сам понять не могу. Мое решение на задачу В было взломано тестом (5,3), оно вывело ответ 4. Почему он не является верным? Спасибо.

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

    Ответ 2. Там вероятности выигрышей и у 4 и у 2 одинаковые (так как m — центр, в данном случае), но в условии сказано: Если таких значений несколько, выведите минимальное из них.

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

Жалко, что на задачу D такие жесткие ограничения — она очень похожа на задачу 208E - Братья по крови, однако я не смог запихать такое решение по памяти :(