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

Автор 300iq, 6 лет назад, По-русски

Всем привет!

Сейчас проходит зимняя смена ЛКШ (Летней Компьютерной Школы), и мы в составе параллели А+ с ее преподавателями подготовили полноценный Codeforces Round.

Раунд состоится в 05.01.2019 19:35 (Московское время) и продлится 2.5 часа. В каждом дивизионе будет предложено по 6 задач.

Задачи раунда были придуманы и подготовлены 300iq, scanhex, cookiedoth, VeryLonelyRaccoon, ----------, kkarnauk, forestryks, TheWayISteppedOutTheCar, LordVoldebug, romanovsavelij, golub, ismagilov.code,alexey_kuldoshin, LadyPython, Jatana под руководством преподавателей izban, VArtem, meshanya, pashka.

Также спасибо за тестирование раунда isaf27, peltorator, Kurpilyansky.

И, конечно же, спасибо MikeMirzayanov за великолепные системы Codeforces и Polygon.

Всем удачи!

UPD: так как регистрация открывается раньше пересчета рейтинга Hello 2019, в случае изменения дивизона, участники будут перекинуты в другой дивизион.

UPD: Разбор.

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

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

Я горжусб тобой сынок

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

    Мне страшно за умственные способности деда...

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

      То есть за умственные способности отца не так страшно?

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

      А мне страшно за умственные способности сына 300iq

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

    Беру свои слова назад, задачи говно. Сын(?)очка, ты обосрался

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

I'd very much like to see rated rounds which are shorter than 2 hours, not longer.

For me, it's much easier to dedicate 1.5 consecutive hours to writing a contest than to have 2.5 or 3 hours available.

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

2 consecutive contests to start the year? bring me some of that

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

Cool! 300iq is now purple!

Edit: Not anymore :(

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

10 min delay :|

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

13 problem setters for 8 problems ...........

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

 Dear CF, is it very cold there?

Why are you freezing up?

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

The contest length is 2.5 hours in the blog but it shows 2 hours in the upcoming contests.

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

I think CODEFORCES hates me! Whatever comment(or reply) I make (I tried many kinds. Contributed, Made Memes, Helped people etc.), always get dozens of downvotes. I'm really sad about it. I don't want to contribute anymore! It's already -24 and going down.

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

Oh no, the magic has gone :( Now I can't play to the chameleon

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

очередной раунд от сине-фиолетовых ((

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

After a bad experience of acm icpc, finally I am going to start this year with a new way and this is the first contest for my new journey for this year..

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

the winter SIS (Summer Informatics School)

Hold up.

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

Well,some later to Chinese users :P.

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

Every JBer show me ur hands up

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

The registration page says the contest is two hours long--is it still intended to run for 2.5 hours?

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

Another contest with 300iq in problemsetters

Looking forward to good tasks

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

The time of the match is very unfriendly to Chinese players.

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

    Practically everybody in East Asia too

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

      Yah. But south-east Asins are having a good time I think >_<

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

        Nope :( I'm in the part of South-East Asia where the contest starts at 11:35 PM :(

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

          Yah, it will start at 10:35 PM in our country. I think we are almost at the same area . By the way, think about chinese people. they have to sit for contest at midnight :( Maybe we are a bit lucky :D

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

Oof.. Red and Orange problemsetters in disguise! XD

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

Seems like it’s going to be a good round

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

starts at 01:35 in South Korea... I'm willing to exchange tomorrows day time to a codeforce round XD

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

Score distribution?

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

Scoring Distribution?

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

lol what a contest :D

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

Wow!!! Problem F of div2 in not present in div1.
wonder!! why it is so??

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

Nice difficulty-balanced div2D and div2E/F

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

Is there a straight-forward solution for Div1B that's not a disgusting ton of mindless casework? That problem ruined the contest for me, so I hope there's something at least somewhat neat.

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

    I think its just two cases and then DP

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

    I don't think I have done any caseworking

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

    If my solution is correct:

    Good table is either

    1) Each row is XYXYXYXY

    So after you fix 2 symbols in the first row (just iterate over all possible combinations), symbols in all other rows are known. For each row you should check what is "cheaper" to make — XYXYXYXY... or YXYXYXYX...

    2) Same, but with rows instead of columns.

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

      Blah, you're right, I suck. Did the first part of that observation and then did the second still with the mindset of rows, which made stuff blurry.

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

    Either each row or each column consists of two alternating symbols.

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

A was a little difficult to understand.

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

what is test 6 in Div2 D ?

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

    n=7 p[i]={1 2 3 1 5 5} s[i]={1 -1 2 -1 -1 5 5} ans = 6 a[v]= {1,1,0,0,4,0,0};

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

    It's not optimal to make the value of node U as s[U]-s[parent of parent of U] if S[U]!=-1

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

    If your subtree's root is at an even depth, then making its value 0 is not optimal. Consider the tree with edges 1-2, 2-3 and 2-4. If the values are 0,-1,5,5 respectively, you want the node 2 to take 5 and not pass on the value to the nodes 3 and 4

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

      so what is the optimal answer ?

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

        The total optimal sum is 5, and not 10. Since node 2 is the root, it contributes to the sum for both 3 and 4, hence effectively reducing the total sum.

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

          yes I understood the test

          how to get the optimal answer in general

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

            Check minimum sv from even node's sons, substract sv from node's father and you get optimal av (and sv too) for this node. If node is even and hasn't sons, you set its av as 0. For odd nodes you just calculate svsfather.

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

              mj

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

                Suppose we calculated optimal sv and av values for every node on path 1 -> Parent of CurrNode. Let SumOnPath be sCurrNodesFather

                If CurrNode's depth is odd, we can unambiguously determine its av, the sv is given in input.

                Now move to the even depth case with 1+ sons Setting aCurrNode only affects contiguous sons ason value — the sson is constant. Since we can set aCurrNode to any value, we want to choose one that minimizes sum of ason.

                ason can be represented as

                ason = ssonaCurrNode — SumOnPath

                So

                is constant, so maximizing the value of aCurrNode will minimize a Also, av cannot be negative, so maximum value of aCurrNode is minimum of sson - SumOnPath

                Starting from root (where we have av and sv ) we can calculate all the values using dynamic programming.

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

    Try: 4 1 2 2 3 -1 8 5

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

    Consider the case : 4 1 2 2 3 -1 7 7

    Answer should be 7

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

    Try this: 3 1 2 2 -1 3 Answer is 3

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

Can someone give a hint for E Div2?

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

    Notice that either all the rows or all the columns must have only 2 letters each. Thus, iterate for all the possibilities.

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

      Why ? I get it, instincts, no one demonstrates it himself during the contest. But why is it so ?

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

        It is clear that no column/row has only 1 letter. Then, we need to show that if some row has 3 or 4 different letters, then all of the columns must have only 2 different letters (and the same switching rows and columns).

        Then, suppose that row i has 3 different symbols. As no two consecutive letters can be the same, we can guarantee that there is an index j such that si, j - 1, si, j and si, j + 1 are pairwise different. Also, as {si, j - 1,  si, j,  si + 1, j - 1, si + 1, j} = {si + 1, j - 1,  si + 1, j,  si + 2, j - 1, si + 2, j} (= {'A', 'C', 'G', 'T'}), it must happen that the letters in si, j - 1, si, j are the same as those in si + 2, j - 1, si + 2, j. Analogously, {si, j, si, j + 1} = {si + 2, j, si + 2, j + 1}. Since si, j - 1 ≠ si, j + 1, from our construction, in order to accomplish these two equalities si, j = si + 2, j, and thus, si, j - 1 = si + 2, j - 1 and si, j + 1 = si + 2, j + 1. You can continue this argument for the whole row, and discover that row i and row i + 2 are the same. Using induction, every row j such that i mod 2 = j mod 2 must be the same.

        But then, every column repeats characters every 2 steps, as we wanted to show.

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

The problems were very good! Fantastic! Thank you for great contest!!!

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

Can anyone share their approach to E? Also, for div 2 F, I think the solution would be dfs-based, at each step finding how many cookies can be eaten if Mitya ends the game at that point. Can someone confirm this?

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

    Yes that's right if we sort all cookies from root to node v, we want maximum x such that the first x cookies cost is smaller equal to T — 2 * (sum of all edge from root to v). We can do it with segment tree and after that in every move (except root) Mitya goes to the second child (by amount of its dp) and we can find the answer.

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

      Hey..could you elaborate further on how to find the maximum x using segment tree? The remaining solution is clear.. Thanks!

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

        For each node save number of cookie and sum of cookie and determine that go to left node or right node plus number of left node cookie.

        My code :48007201

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

Horrible, misleading problem statements!!

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

In problem Div1D, don't you have to dynamically keep the Huffman tree in order to answer the queries, or is there an easier approach?

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

    You can change it to just insertions and undoes with the dynamic connectivity trick. However I don't see how to do undoes without persistence, which would definitely TLE.

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

    Sort the numbers. Calculate the partial sum. At first, set ans = cnt-1. Then, for each i reduce ans by one if a[i] > partial_sum[i-1]*2. This can be done with a segment tree because the number of such cases is at most lg(1e9).

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

    I passed pretests with this idea:

    sort all numbers in ascending order, count how many numbers such that they are bigger than twice the sum of all previous numbers, let this count be K and N is total number of numbers, then the answer is N — K.

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

    There is an observation, that the result is #fishes - #(fishes which are more than 2 timesheavier than all fishes lighter than them (after sorting)).

    Next observation: is some fish can decrease the result by one, it is a result of a lower_bound operation for some power of 2. It helps easily find fishes which can decrease the result.

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

      Yeah, once you figure out the observation, it’s easy.

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

      How did you prove 1st observation ??

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

        I don't prove, I code :P

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

          Then, where did you come up with that from?

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

            I guessed/observed that they should eat themselves from the smallest ones. What happens when second smallest fish after eating the smallest fish becomes greater than the third smallest fish? The order is distorted, but the intuition is, that because of that the fishes became very close to each other, so now I will be able to do many dangerous fights (until the situation with much greater fish happens, because then for sure I won't be able to do the dangerous fight).

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

          what do you do when you get WA in this case? I mean how do you tell whether it's a bug or wrong observation? :P

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

went for overkill on DIV2D with hld and still WA

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

What a great contest!!

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

Was O(QlogQlog109) supposed to fail in D1D or only my implementation has a too big constant?

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

Why would Div1C be excluded and not being used for problem F of Div.2 version, instead there comes a new problem in place of this? :O

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

    I guess they just had too many problems (because they were doing this as a class work) and wanted to include all of them.

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

      It was no a classwork. We just thought that div2 is too easy for div1 and we didn't want to give our div1 for div1 because it can be too hard for them, and we wanted to give for div1 more problem there you need to write not very simple code, so we decided to put it there

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

Most contests are imbalanced these days :'(

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

problem D was very nice :DD , how to solve Div2E ?

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

HELP,

what is pretest 4 for the ACTG problem?

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

what is test 14 in Div2 D ?

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

Very great contest for non Div-1 coders like me. I particularly liked the gradient of submissions and the Div2-D problem. Ideal contest to increase rating for a graph lover like me.

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

what is test 4 in div2 F?

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

Does anyone know what was pretest 16 for Div2D?

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

    Answer needs to be long long. Explanation : s[i] <= 10^9. Sample case : 5 1 1 2 3 1 -1 -1 10^9 10^9

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

Isn't it a O(n) solution(Div2 B)? 48005949. If so, why did it pass a test n = 1e9?

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

is Div2 F binary search? I was trying to check whether it is possible to eat x cookies, but couldn't succeed.

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

That moment when you solve E 5 minutes before the end of the round but yiu cant submit it because you have the worst internet connection in the universe :( :( :(

I fucking hate my life :( :( :( Hope its not correct :( :( :(

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

The problem setter of Div1E should stop creating problems.

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

My screencast will be available here after it finishes processing: https://youtu.be/WR9rMvE-d9Y

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

C felt so empty :(

A how could initial height be 1 if we have two rocks.. and calling the second rock "second rock" doesn't that mean the first one is heigher but that wasn't mentioned.

sadly I'm not good in graphs to try D .

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

Is there a specific reason why integer overflow hacks didn't work on this contest? A person I tried to hack used int everywhere, but somehow his submission in C++11 managed to print 3000000000. Is the int limit bigger than 2^31-1? :O

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

i got the #victoryroyale on this contest

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

Let me ask. Is F just a HLD on a suffix tree with segment tree with operations like "do x[i]=x[i]+1 on the interval" and "get sum of x[i]*a[i] from the interval"? I think that I was close, I had tree and HLD already but the fact that we have to do queries in a middle of an edge defeated me and I run out of time.

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

    I don't know how to do it with 1D queries, our solution have sweep line at each heavy path...

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

cool picture in div2F

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

Is there anyone solve Problem C (div.2) with DP ?

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

How to solve Div2 F?

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

    We can solve this problem by using minimax + greedy and segmentation tree. Assume we are at some node u in the tree, then we have remaining time = T - 2 * sum_l, where sum_l is sum of l over all edges from root to current node u. Now we can use a segmentation tree to greedily eat as many cookies with our remaining time from min. time required per cookie to max. time required per cookie for cookies on path from root to u. This segment tree has a leaf for each possible value of ti (so 1...1000000), and stores per interval total cookies in the interval and total time required to eat all cookies in the interval. When we arrive at node u, we add x[u] cookies to all intervals t[u] lies in. When we backtrack from u, we remove the x[u] cookies. Vasya always cuts the edge that leads to the best result, but in the root Mitya can choose an edge before Vasya is allowed to cut. This solution is O(N log 1000000). Corresponding code: https://mirror.codeforces.com/contest/1099/submission/48030249 .

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

Just curious, why is div2 F not available in div1?

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

Was this round unrated?

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

My solution for the problem C was shown as "accepted" but then after the contest, they realised I had a wrong answer? Like.. How is that allowed!!?

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

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

    To give a serious answer:

    There are pretests for the contest, where you will be given a particular verdict (in your case, Accepted). Afterwards, the submissions are run on a more thorough set of test cases, where the real verdict is made.

    There are a few reasons for this – one is that it lightens the load on the servers to only run the submissions on <20 cases, as opposed to ~100. Another is that it allows for "hacking", where you can look at other people's submissions for a problem that were accepted on pretests but have a bug in them, and create a test case that exposes the bug. All the successful test cases created from hacking are added to the total test case suite that runs after the contest. This is pretty beneficial to problem setters, because it can be difficult to think about the wrong solutions that will be made, and the corner cases that must be created to expose the bugs in the wrong solutions. The hacking system essentially crowdsources the creation of thorough test cases, making a more accurate problem for everybody.

    Failing on system tests is, unfortunately, part of the game here. On the bright side, it could be worse: Some contests, like Topcoder and Facebook HackerCup don't run your code on any test cases until after the contest is over.

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

Новая ава 300iq как бы намекает...

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

Is it only me or somebody else also who was expecting a higher rating change? Rating Predictor is showing +162 but I got just +73 whereas my friends' ratings changed as per shown in rating predictor.

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

For me 2.5 hours are better !!

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

by the f**k, why it TL??? (help me please, I am just don`t understand what wrong???) https://mirror.codeforces.com/contest/1099/submission/48007197

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

    reeWorld We had a solution like yours. Ofcourse it gets to because real complexity of this solution is N^2logN. Look at test, it is a bambook of n/2 vertrexes and in deepest vertex of it there are n/2 vortexes connected with it. X and T are such as you should erase all elements when you can to these children, and when you return you put when again. So you do n^2 operations, and it multiplicates log because these are operations with multiset

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

      ah, realy... Thanks a lot! I even breafly did not have idea it is n^2*log(n) time complexity in worst case

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

For those who are afraid of precision errors.. Div2-B Solution

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

    Can you explain it,please

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

      We begin with a single square and then add more squares gradually. let a[0] and a[1] be the length and width(so both are 1 initially) Now, each time I'll pick the smaller of the two(which is a[0] since it is sorted) and increment it by 1(i.e. add one more segment to it)..with this extra segment drawn, I'll be able to complete a[1] more squares using this new segment as guide. Stop when at least n squares are drawn(i.e. while cur<n).

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

      always put a space after a comma.

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

    Or just notice that solution can only be 2*sqrt(n),sqrt(n)+sqrt(n)+1 or 2*(sqrt(n)+1).

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

How to solve Div2 D???

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

    Hint: the best S[i] for some unknown node is the minimum S[j] of its children, or the same of its parent if it has no children. After figuring out the optimal S[i] for every node, you can restore the original A[i] for each node.

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

когда выйдет разбор?

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

как решить E DIV2? суди по всему очень длинная решение но буду очень признателен если объясните)

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

Editorial?

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

editorial?

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

    It's here

    UPD: Oh... It's not translated yet.

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

      yeah you know what about writing it in English in the first place like a normal person not in your language that no one cares about

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

        Considering Codeforces owners, authors of this contest and a huge part of this community are russians, I think your trolling sucks.

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

I did'nt get the problem statement of div2-B, can anyone pls elaborate it.

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

Where is the editorial?

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

when editorial will come ??

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

Хочу выяснить причину незачета задач. Писал все сам никому не скидывал решения

include

using namespace std;

int main() { int wStone, hStone; cin >> wStone >> hStone; int w1, h1; cin >> w1 >> h1; int w2, h2; cin >> w2 >> h2; for(int i = hStone; i>-1; i--) { wStone += i; if(i == h1) wStone -= w1; else if(i == h2) wStone -= w2;

    if(wStone < 0) wStone = 0;
}
cout << wStone;
return 0;

}

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

damn man no editorial till now!!

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

As the editorial is not published till now can somebody tell how to solve div2E and div2F?

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

is it rated?

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

мэ нэ нраицца данный контекст

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

I love that contests are being held so often now :) I am learning a lot of things thanks to that , I have high hopes that it will keep going this way !!!!

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

    i don't think so lul

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

    you do not need to put a space between the last word in your question/sentence and the question mark/exclamation mark.

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

      Every sentence starts with capital letter.

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

      I appreciate your work, grammar.nazi. But I think you're in a wrong place. It's a community of Programming/Programmers. People type their comment here to express their idea. So, grammar doesn't matter here that much. People may learn many sides of grammar and be aware of grammatical mistakes but it's kinda disturbing. I think you'll get a bunch of downvotes every time you try to correct people's comments (I upvoted your reply). Don't mind.

      [Sorry that my reply may also have some grammatical mistakes. (I'm not a native speaker of English and I think many people aren't too.)]

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

is there a DP approach to solve C?

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

When is the editorial translation going to be here?

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

Is there some one know the link of this problem: given a string, and some query [l,r] find the maximum i such that s[l,i]==s[r-i,r]... I'm pretty sure it is in codeforces gym thanks

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

I have a sol to solve problem F:

first we can solve the lcp[i,l] l<=i<=r not consider the bound of r restriction.

then we can try the minus old and add new value of point i s[l,l+i]==s[r-i,r].

we can solve first question by sweepline the increasing order

of rank[l], and build 2D segment tree, it can be solved

by O(n*lg(n)^2)

then we consider to find point s[l,l+i]==s[r-i,i].

there is a problem in gym find the maximum i, if we

got maximum i, then we can got sec maximum j that

s[l,l+j]==s[r-j,r] so we can get it is a repetition of s[r-i,r-j-1]==s[r-j,r-j+i-j-1].....it is a arithmetic progression

we can find the next bound of this arithmetic progression by O(1) and this number of segment is not bigger than log(n) with small constant factor

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

What a great contest!!

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

Such shameless authors , nearly 25 people involved in the round and still no translation for the editorial. I think this affects not only the authors but also codeforces's reputation.

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

    We sincerely apologize for the delay with the English version of the editorial. It's now available (link).

    However, before writing offensive & demanding comments, please understand that yesterday was the last day of the camp, and all of us needed to travel really long way home. Quite obviously English is not a mother tongue for any of the high-school students who prepared the round, and it takes a lot of time to write something readable.

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

I AK IOI. I AK ACM World Final. I AK Universe OI. I hangbeat tourist. I'm txdy.

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

.