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

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

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

Приглашаю Вас поучаствовать в 313 Codeforces раунде, над которыми для вас работали я и tunyash. У каждого из нас за плечами по четыре раунда, так что это наш пятый или девятый раунд, как хотите. Я придумал почти все задачи (кроме D div.1), написал условия и разбор всех задач, а tunyash занимался разработкой всех задач.

Gerald уже не является координатором, так что, возможно, Вы по нему соскучились. В этом раунде вы снова с ним встретитесь и поможете ему разобраться в его повседневных жизненных проблемах.

Спасибо координатору Zlobober, нашей переводчице Марии Беловой (Delinur), а так же MikeMirzayanov и всей команде Codeforces за эту платформу.

Этот раунд состоится в необычное время — 17:00 по Московскому времени.

Соревнование закончилось, добро пожаловать в разбор!
Краткий разбор.
Подробный разбор.

Разбалловка в первом дивизионе будет следующая:

500 — 1000 — 1500 — 2250 — 2250

А во втором дивизионе — стандартная:

500 — 1000 — 1500 — 2000 — 2500

Желаю всем получить удовольствие от решения задач!

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

Div. 1:
1. jqdai0815
2. qwerty787788
3. SirShokoladina
4. ainu7
5. Endagorion

Div. 2:
1. goons_will_rule
2. lbn187
3. crawling
4. loveannie
5. Jagabee

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

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

This is always my first thought when I see 313 anywhere:

:)

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

Wow!I'm looking forward to the coming contest!

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

>mfw there's finally a round after a long time

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

Another unusual time! I'm happy because I'll be able to sleep before 02:00... though it might collide with others' schedules.

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

it is so funny

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

    Really Don Rosa drew it like this :o? It's like a profanation made by a saint ;__;

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

Классно что разбор написали заранее

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

17:00 ? Srsly? Every normal people work in this time (in Russia) -_-

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

    Normal people earn money from home :P

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

    Are programmers normal people? :D

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

    It is only people in our time zone, who works without flexible schedule. It is very few people. Every contest time not comfortable for someone.

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

    We take 'usual time' CF rounds at 01:30, and it takes two hours, so if you are a student or have a schedule and you REALLY want to participate, you should spare your sleep.

    I'm not saying that the time CF rounds start should iterate over and over. I just want you to know that there are many people around the globe who cannot(or wouldn't) participate because of the time zone. Give us some chance, please.

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

Ребята!!! а за это соревнование можно получить футболку? http://mirror.codeforces.com/blog/entry/19327

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

    Именно за это — нет.

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

      А почему???(( Чем оно хуже остальных?? Былобы интереснее участовать если можно было бы за это получить футболку подумайте над предложенеим пока еще не время контекста!!))))

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

        Футболки почти никогда не дают. Чем это соревнование лучше остальных?

        За 24 часа до соревнования уже поздно думать о таких вещах. Это же куча денег и организационных проблем.

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

Thanks guys for taking the time doing all this work!

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

313 is a holy number for Muslims :)

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

i think it's a good time for china coders

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

Izi problem, izi life

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

уф волнуюсь это мое первый в жизни раунд=)

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

which rounds did you prepare?

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

3.13 is my birthday! Hope there be a rating harvest!

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

tagged "codefores" :p if its a mistake, surprisingly it was done before :p

UPD: tag was removed :p

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

" Scoring distribution will be known closer to the beginning of round ," this time there is new sentence ;) !!!!!!!!!!!!!!!!!!!!!!!

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

tnx for usual time

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

Прошу прощения за наивный вопрос, но чем разработка задачи отличается от придумывания задачи?

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

Anybody know at what time the practice problems will be unavailable for judging because of this round! It's very important for me to know... thanks!

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

My last contest before IOI!

I hope I can practice with this round.

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

Good luck to IOIers. (Not everyone, hence it is possible :P)

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

Good luck for your round Sammarize :D

I'm very excited to take part in it!

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

My previous dorm room no. was 313 . Loved that room :P hope this contest is some kind of good luck charm for me!

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

Привет из ЛКШ.

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

wow...scoring distribution occurred so soon :D, really unusual round

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

it seems that 313 has lots of significance :/

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

У меня одного лагает и жутко тормозит? Ещё и "We are upgrading some infrastructure, we expect to finish in at most 1 hour." вывалилось один раз..

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

Can't hack... Codes don't open...

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

I didn't have brave to submit something, but problem set is very nice ! I like first four problem ( in div 2).

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

Ну тут однозначно надо было увеличить время раунда. Лагало жуть.

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

geometry geometry and geometry :P

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

А вы тоже заметили, что Е — это задача-бигмак?

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

UNSUCCESSFUL HACKING ATTEMPT AT 19:00:00

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

geometry geometry and geometry :P

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

Div1 B has already been given for training to the Junior National Team in our country and the teacher who gave us the problem said that she took it from some Russian site... And announcing the thing for odd length wasn't fair, I needed to resubmit. And it wasn't even added to the statement...

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

    The statement clearly said "If we split string a into two halves of the same size". You can't do that if it has odd length. If anything, it's unfair that the announcement caters to people who can't read.

    EDIT: Ok, I reread the statement more carefully, and I see why the clarification was necessary. "If we split a into two equal halves, then some things are equal" can also be understood as "For every possible way to split a into two equal halves, some things are equal". In this case, if a has even length, there is of course exactly 1 way to split it. But if it has odd length, there are 0 ways, so indeed the things are equal for every way. However, this would imply that the answer is always "YES", which is inconsistent with the sample tests, so you should notice that something is wrong before submitting.

    So, clarification is indeed necessary, I retract my slightly rude comment above, but I stand by my claim that it's impossible to read it in a wrong but consistent way.

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

    "If we split string a into two halves of the same size..."

    If size is odd you can't divide it into two halves of the same size, do you ?

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

    It's a formal consequence of the statement: string of odd length cannot be divided into two halves of equal lengths, therefore strings of odd length are equivalent iff they are equal

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

      Okay, my bad, however it would be better if there was such sample. And still, the problem is known and I guess a lot of people just coded it with no thinking :)

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

Мне кажется, или задача С div 1 где-то в тренировках была? Может не с такой легендой, но смысл тот же.

UPD: нашел, задача 100589F - Count Ways, даже editorial есть http://mirror.codeforces.com/blog/entry/16099.

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

Can someone please help me catch the mistake in this code? It never gives correct answer but I think the reasoning behind it is corect.12182932

Essentially I am trying to sort the strings(swapping the halves of the blocks), first in blocks of length 2, then blocks of length 8 and so on. sorting for all blocks of powers of 2 that divide the length of the strings.

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

    Blocks can have odd length (e.g. string of 6 letters has 2 blocks of length 3).

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

      Oh yeah, so I had to make d the greatest odd factor of the string length and then the blocks should be of length 2d, 4d, 8d... right? thank you.

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

Problem C (div 1) is an old problem.

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

Does solution for DIV 1-B is just simply write a recursion function that check what the problem statement said?!?

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

    I think NO. It will be TL. I've used something like merge-sort in O(NlogN).

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

    Let's define the following operation on string S: We can split it into two halves and if we want we can swap them. Then we can recursively apply the operation to both of its halves.

    Now we need to make the observation that if after applying the operation for some string X, we can obtain Y, then after applying the operation for Y we can obtain X.

    And for the given two strings, we can recursively find the least lexicographically string that can be obtained from them. Let's say that those strings are A' and B'. If A'==B' then the answer is YES, otherwise it's NO.

    But it seems like almost nobody made those observations since the problem is known and most of the Russian-speaking contestants may have seen it before :)

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

    By the master theorem, your solution would have O(n^2) complexity.

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

    I wrote this recursion and it didn't got TL. I think that it is because I used random to choose the order in which I call recursive function.

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

      No. I removed this randomization, but it still works.

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

      I wrote a naive recursive implementation and got AC 124ms here: 12177962

      I still don't get how my solution ran so fast.

      No random, no optimizing, no anything.

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

        It is probably the order of the recursion call. Check 12187196 and 12187385.

        There is something called luck related to this problem. And seriously, letting us pass O(n^2) solution is not good at all.

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

          It has nothing to do with luck. Look at this C++ code:

          int main()
          {
              int x, y;
              cin >> x >> y;
              cout << ((y == 1) && ((1 / x) == 5)) << endl;
              return 0;
          }
          
          

          What will be the output when you input x = 0 and y != 1?

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

            Yep, but the thing is that you already know this test case and you are sure that first of these equalities will be true. Imagine that y != 1 in all of the test cases and pretests wouldn't contain case x = 0, but final tests would. That's where you are more lucky than someone, who sent cout << (((1 / x) == 5) && (y == 1)) << endl; and got RE (if I'm not mistaken) after final testing.

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

              I agree with you, order matters in this example. But my point was that C++ optimizes bool operations. If first operand of && evaluated to false, then other operand does not compute. Applying this reasoning to solutions with 4 recursive calls in a (A&&B)||(C&&D) manner, we can conclude that there are maximum of 3 calls actually made. Let's look:

              -If A == true and B == true, then neither C nor D are computed, because || already evaluates to true

              -If A == false, then B does not compute, because A&&B is false for sure

              -If C == false, then D does not compute

              -At last, if A == false, C == true, D == true, we get 3 recursive calls, which is maximum.

              So, basically, solutions written in C++ in this manner are not O(n2), but rather .

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

                Maybe i'm missing something, but what about A=true, B=false, C=true, D=true? Then we will get 4 calls. Why isn't it possible?

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

                  Let's use  =  sign for equivalence. Then we have:

                  a1 = b1

                  a2 ≠ b2

                  a2 = b1

                  a1 = b2

                  We know that equivalence relation is transitive, so:

                  a2 = b1 = a1 = b2

                  But we suggested that a2 ≠ b2. It means that such situation is impossible.

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

                Looks like A=true, B=false, C=true and D=false is still possible, for example, when s=XX and t=XY, and that's 4 computations.

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

                  If we take the meaning of A, B, C and D from the statement, then:
                  A = 'X is equal to X' = true
                  B = 'X is equal to Y' = false
                  C = 'X is equal to Y' = true
                  That's contradiction.

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

                  Right you are, my bad!

                  But: another example, checked by writing a program this time.

                  s=XY, t=XX

                  A = (X==X) = true
                  B = (Y==X) = false
                  C = (X==X) = true
                  D = (Y==X) = false
                  

                  A byproduct of checking is that this example is unique (if we don't consider symmetrical cases).

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

                  That is brilliant! My apologies for claiming that 3 calls are sufficient.

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

    Wow, it passed the final test. I'm surprised...

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

What the the possible end configurations in C? I got a point, an equilateral triangle, a trapezoid, a rhombus. What did I miss?

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

Can anybody please see my Div2 E code, and tell me if it is TLE because of python, or my algorithm needs optimizing? :( Wasted 4 submissions on this.

http://paste.ubuntu.com/11920717/

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

    No, a O(H*W*log(N) ) algorithm wont pass with H,W=10^5 and N=1000. The proper solution is O(max(H,W)*N). I couldnt get it correct in time, though...

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

      No the correct algorithm is O((W+H) + N^2). The W+H comes from precomputing binomial coefficients.

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

I feel like problem C(Div1) is famous. I couldn't solve it but I'm pretty sure I've seen it around more than once.

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

How to hack Div1B, those who just recursively check equivalence?

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

    It passed the systest, so the correct question is, how to prove its runtime is better than O(N^2).

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

      I coded my B as a recursive function satisfying T(n) = 3T(n / 2) + O(n), which is n1.5 approximately. This is much less likely to fail than a O(n2). You can check my code for details on how you do the reduction on number of checks needed.

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

        Clever. But that doesn't explain why some people passed without using this trick, for example 12178491

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

          I don't think there is a test case for this solution which will run N^2. ANDs would eventually cancel two extra recursion calls.

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

        Really good observation

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

        Didn't actually check your code, but I guess you wrote A?B:(C&&D) instead of (A&&B)||(C&&D) while B, C, D is compute only when needed.

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

        Can you explain why you can go directly to the return statement in your if without checking the else?

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

          If you're asking about my solution, what it does is:

          Use ~ to denote equivalence. Note that it is transitive.

          Say A splits in a_1, a_2. B splits into b_1, b_2. If a_1 ~ b_1, it suffices to check that a_2 ~ b_2. Indeed, if the other case holds (a_1 ~ b_2 and a_2 ~ b_1), then b_2 ~ a_1 ~ b_1 ~ a_2, so we would get that a_2 ~ b_2 anyways.

          Otherwise, a_1 is not equivalent to b_1, so just check a_1 ~ b_2 and a_2 ~ b_1.

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

      Why did mine fail then? High constant?:/

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

        I think so. Copying substring is way too slow to pass this problem. A char* solution can pass it easily and unexpectedly. 12182556

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

      I know recursion enough good, because I couldn't invent something smarter for half hour and some guys solve it in 5 minutes :)

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

Anyone got accepted problem C(Div.1) using O(n^2*log(10^9)) time ? :\

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

    No... But I got accepted in O(N^3)...

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

      O(N^3) how? I did it in O(N^2).

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

        Well my solution is pretty stupid, it calculated useless values. My dynamic programming is F[A][B] = number of paths from black cell A to black cell B without passing any other black cells along the path. Computing every state takes linear time so O(N^3) in total. The question is — why doesn't it time limit? I'd bet on weak tests.

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

    I promise to always precalculate modulo inverse from now! Rank 64 to Rank 213 :(

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

When can we use the training problems again? Now it seems blocked...

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

Ok, so problem B was in an ACM training around a year ago, and C was in a Slovak OI nationals around 6 years ago. Naturally, I knew the solutions of both by heart.

D: Pick's theorem was obvious, but I couldn't figure out how to cut down the boundary part to better than in contest. Oh well, time to keep going with those 480.6 pushups.

UPD: Just did E, it was much easier for me than D. I've got to be more daring...

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

why still not rated?

I may increse rating 50 around~~~

finished system test yet?

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

Div.1 pC let me recall this problem : ICPC 2009 Asia Phuket Regional — Your ways

When I practiced it, I misread it as problem of today.

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

Is there anyone else who saw "Judge protocol is inaccessible" error during challenge process? I saw that error and submitted the same wrong hack submission again. Several minutes later, all the submissions which gave that error were rejudged and considered "unsuccessful hacking attempt", so I got plenty of minus scores :p

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

I particularly didn't like this round considering problems B and C were old problems and problem A was just simply googlable.

Plus, then you read comments about how simple brute force passed in B and O(N^3) passed in C.

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

    A was googlable. ? oh damn. I could have been purple .

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

    "A+B problem" is also googlable xd. Funny how people can think of googling such adhoc and simple things.

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

      It all depends on how you are approaching the problem. Most people, I think, thought of finding the area of the special polygon.

      Its a formula which you can a) derive for hexagons in the contest, or b) google and get answer in a minute.

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

      Come on, don't make so categorical judgements :)

      Open standings of div2 and you'll see that 70% of contestants there wasn't able to solve this problem. One which is simple for you — isn't that simple for someone else.

      Moreover, it took me 3 attempts to solve this "adhoc and simple" one :) At least I didn't google it...

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

        Maybe I didn't express it clearly, but mainly I wondered who even bothers of writing such things in Internet out so that they can be easily googlable :P.

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

Did anyone get Accepted in Div1-B using hashing? My solution 12181985 failed and not sure why.

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

    Yes 12179329, Time Complexity O(nlog^2n)

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

    Equality check using only the hash may give you a false positive. You should do the actual string comparison in case of matching hashes, to be sure. But then you risk getting a TLE on something like test 89, like I did: 12185730 :)

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

      Yep, also tried using hashing and got TLE on 89 12171361

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

      it turned out that the reason of the TL isn't the actual string comparison of matching hashes but the fact that the branching factor for each recursive step is 4 then, in the worst case, the overall complexity is O(n2).

      If you try to choose randomly the order of recursive calls you make for each recursive step I guess it is hard to create a test case that requires 4 calls for each recursive step.

      This is the AC solution using hashing (and just using the equality check of hashes to determine equivalence) with random order of recursive calls: 12187657

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

    Hashed successfully, using several primes: 12176236

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

    I got it accepted using hashing after changing the order of recursive function calls. (http://mirror.codeforces.com/contest/560/submission/12188786)

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

Кто-то может объяснить почему рейтинг обновляется не сразу после окончания соревнония?

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

Here is an O(nlgn) solution of div1 B: Let the input strings be S and T, find the lexicographically smallest strings which are equivalent to S and T respectively, and check if they are equal. code : 12173245

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

Why does 12166408 fail? Precision problems? It seems to do the same thing as everyone else.

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

    (int)(ans + 0.5)?

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

      I think this is to print closest integer to ans. So, if ans is something like 0.9999 due to precision errors, we want to print 1.

      Edit: I didn't see the solution actually and thought you were asking why is that being done. Of course, you are right, that is the mistake.

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

        It should say (int)(ans+0.5) but it says (int)ans+0.5.

        Operator precedence strikes once again.

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

      Oh wow, he's gotta be mad.

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

    Yeah, (int) ans + 0.5 should be (int) (ans + 0.5) (12185888).

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

      Is there any reason behind writing "(int) n", but not "int(n)"? Is latter variant considered something like bad style? It always seemed ok and even more logical for me, but you, W4yneb0t and ainu7 wrote it another way.

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

        As far as I understand it, (int)n is called a typecast, while int(n) is called a constructor, with the difference being that one of them causes stupid bugs like this and the other doesn't. I write int(n) in my own code.

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

          Multiple sources (cplusplus.com, wikibooks.org) state that both are called type casts. Perhaps it doesn't hurt to think of the latter one as a constructor though.

          The reasons to use (int)n notation are perhaps tradition and/or C portability: this was the only notation available in C.

          Anyway, I just used whatever was in the source, trying to make the edit minimally intrusive.

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

        Personally, I prefer to write casts as (int) (n) in C++, since this notation is extendable to (long double) (n + 1) without change of form.

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

Could someone tell me why this code got TLE? DIV 2D Code

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

    Doesn't substring() makes a new array and copy the exact string? It may take a lot of time.

    Instead, save the string in global variable, and give only the index (of left and right bound for both string) to the recursive function.

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

    In your code for the return value instead of t1||t2 try t2||t1 Make "equivalen(a1,b1)&&equivalen(a2,b2))||(equivalen(a1,b2) && equivalen(a2,b1)" this "(equivalen(a1,b2) && equivalen(a2,b1)||equivalen(a1,b1)&&equivalen(a2,b2))"

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

For problem Div1 B I used divide and conquer but for the case when strings size is odd I called another function, this was the only reason I got TLE for test 91, I wrote code for this case in caller function and AC now. I checked "status" page and some of you have TLE for 91, so keep in mind my sad story.

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

Anyone else experiencing this problem for div 2 problem D?

In the question for operation 2, we have to recursively check for condition a or b and if either one if them is true. In the recursion code, if we check for condition b first then a, then I got an AC, if I check for condition a first then b I got a TLE (test 89)

TLE solution: http://mirror.codeforces.com/contest/560/submission/12186384 AC solution: http://mirror.codeforces.com/contest/560/submission/12186179

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

    If first condition is true then your function won't run for second condition. So order affects running time.

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

      But that means the test cases are weak right? If at all bruteforce recursion was to fail, then both codes should have got a TLE

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

        Test cases weren't strong but it's hard for problem setters to fail all possible brute-forces. Though here we have two naive solutions and both should get TLE.

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

          Yes, I can understand that its hard for problem setters, it would be nice if a few more test cases are added now (maybe reverse strings from original cases).

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

            They could just set higher constraints. 200k is not enough sometimes.

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

I'm doing a farewell party for some of my rating. They were supposed to leave around now, is the plane delayed?

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

Good contest! But... It seems that the testcase for div1 Problem B is not strong enough. My first submission failded a case that I wrote(It prints YES but the answer should be NO). So I resubmitted it after revising. And then I used this testcase to hack someone's program. Though the hacking attempt is unsuccessful(because this program can pass my testcase), it shows that the testcase is feasible. But now I find that my first submission can also pass this problem...... I am not very happy because this resubmission made my goal -400. :( By the way. How can I show this testcase that I wrote? Maybe many of you want to check your program with this. Thank you.

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

I can't understand why my solution of div2 problem D gives WA on test 8: 12186517. It tries to make the smallest string (from both given) using the operation: swap partitions if the first is greater than the second. Than checks if the two strings are equal.

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

Can someone explain why My Div2D got tle?? 12186568 latest submission 12188078 Thanks in advance

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

Got TL in D div2 with python3, but the same code was accepted with PyPy. How to figure out how to send?

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

    exactly the same thing! %) Sometimes Python is faster, sometimes Pypy (( I should have used C++

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

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

Div1 C used in this contest is simply the copy of this problem. https://www.codechef.com/CDCRF15R/problems/CWAYS/ Author didn't even change the logic and used the same problem.

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

    I'm pretty sure the authors didn't see this problem (you see there are not many participants in the contest you gave link at). Sometimes it happens — same natural ideas come to mind of different people.

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

Thanks for the problemset I really enjoyed it. But wasn't problem B Div. 2 Easier than problem A?

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

Finally became an IGM! Donald Duck and Taylor Swift gave me power :D!

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

А "эквивалентные строки" должны решаться банальной рекурсивной проверкой эквивалентности или нет? А то мое решение на питоне, провалившееся по времени на системных тестах внезапно зашло после контеста с использованием компилятора PyPy. Как-то очень обидно.

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

I think test cases for div1 b should be revised and solutions should be rejudged

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

    Why? Did correct solutions not get AC? If not then there won't be any rejudge.

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

      Yes. Depending on which case you handled first, you could TLE. See http://mirror.codeforces.com/blog/entry/19374.

      12188567 vs. 12188586. The only difference is in the commented/uncommented line.

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

        Both solutions are wrong, all correct solutions got AC.

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

          Good. But why many incorrect solutions can get AC?

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

          So if I thought about the complexity before writing the solution I don't solve it, and if I write the solution without thinking I solve it? is that fair?

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

            It's bad that some wrong solutions get AC but it's impossible for setters and testers to prevent it for 100%. Is it fair? It's not cool that some people have more points than they should but well, we all had the same possibilities to use this situation — so it's fair for some definition of "fair".

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

              we all had the same possibilities to use this situation

              I can't imagine a yellow/red coder writing an O(n^2) solution for a problem where n<=2*10^5

              But you are right, it's impossible to prevent it 100%

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

                I can imagine a yellow/red coder writing an solution or properly optimising something to make his solution pass.

                And statistically, such lucky situations are negligible when the problems are tested properly. People who don't have the skill will just drop down again eventually.

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

                I wrote optimized O(N^2) solution for N = 2*10^5 in contest before (and it passed).

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

            You're not the first to think of this problem. If you solve it, tell us. Adding tests after the contest has its downsides.

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

          Actually,someone i know proves that the complexity is O(n^1.57)

          If A and B are equivalent, it will only recurse at most three subtasks so complexity is T(n) = 3T(n/2) that is approximately O(n^1.57)

          If A and B are not equivalent, it will recurse four subtasks only if two subtasks are equivalent so complexity is T(n) = 2T(n/2)+O(n^1.57) it's also O(n^1.57)

          EDIT1: I made a mistake to let T(n) = 3T(n/2) in the first case since the subtasks might not be equivalent ! But after further calculations i still believe the complexity should be O(n^1.57) Plus, i wrote a program to calculate the times of recurses and it's about 10^9 which Codeforces is still able to run in 1s

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

      And mine too 12188078 I have no clue why I am getting TLE.

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

Помогите пожалуйста разобраться с D(Div2) или же B(Div1). Решение на хэшах, WA-92. Этот тест маленький и на моей системе проходит (правда у меня GCC-5.2). При изменении простого числа на очень большое (я надеюсь, что система и компилятор 64-битные), вовсе выдаёт WA-2.

Изначальное решение: http://mirror.codeforces.com/contest/560/submission/12183108

Если изменить простое: http://mirror.codeforces.com/contest/560/submission/12182854

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

    1000000000039 — слишком большой модуль, так как его квадрат не влазит в int64.

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

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

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

can anyone explain div2 c. My approcah is dividing the hexagon into four triangles and calculate the area of the individual triangles and then summing them up gives area of hexagon and later divide the area of hexagon by area of the equilateral triangle .is it correct or am i going wrong somewhere ?? please tell the other methods to solve this :)

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

Div2/C can any body tell me what's wrong with my code , i used these theory :

area of a triangle abc = 0.5 * b *c * sin(A)

area of a triangle abc = sqrt((a+b-c)*(a-b+c)*(b+c-a)*(a+b+c))

this the code :

#define sin120 0,86602540378443864676372317075294
    vector<double> v;
    double air,air1,air2,air3,air4;
    int x,y;
    cin >> x >> y ;
    v.pb( sqrt(x*x+y*y+x*y) );
    air1=sin120*x*y*0.5;
    
    cin >> x >> y ;
    v.pb( sqrt(x*x+y*y+x*y) );
    air2=sin120*x*y*0.5;

    cin >> x >> y ;
    v.pb( sqrt(x*x+y*y+x*y) );
    air3=sin120*x*y*0.5;

    double a=v[0],b=v[1],c=v[2];
    air4=sqrt((a+b-c)*(a-b+c)*(b+c-a)*(a+b+c));
    
    air=air1+air2+air3+air4;

    cout << (air * 4)/sqrt(3);

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

    First, decimal representation of C++ is "." not ","

    You defined sin120 as 0,86602540378443864676372317075294 but you should change , to .

    Second, you calculated variable air4 with wrong formula.

    Heron's formula is sqrt(s(s-a)(s-b)(s-c)) where s = (a+b+c)/2

    If you rewrite the formula and fix it right, code should be

    air4 = sqrt((a+b-c)*(a-b+c)*(b+c-a)*(a+b+c))/4.;

    Third, you used cout and printed double , without any setprecision, converting to integer or something. Answer can be large, and cout will use scientific notation such as 6e+006

    Your code should be fixed as

    cout << (int)( (air * 4)/sqrt(3)); (?)

    However, this might not correct.

    If you fix all the things, you might not get accepted because of real number error. To prevent this, rounding answer to nearest integer is preferred.

    cout << (int)( (air * 4)/sqrt(3) + 0.5 ); adding 0.5 can be used rounding answer to nearest integer, if answer is positive.

    and the code got accepted. 12190712

    Using real number is dangerous, so you should be noted.

    By the way, this problem can be solved with simple method, not using real number or any complicated method.

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

      Thanks a lot , i really appreciate it . btw i already solve it , i was just trying this methode :)

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

NORTH KOREA DOES IT AGAIN!

I got strong suspicions against black_horse2014. First reason being of course that he's from North Korea :P.

"00:17:22 A Accepted [main tests] 00:30:36 B Accepted [main tests] 00:35:09 C Accepted [main tests] 01:16:57 D Accepted [main tests]"

His times for A, B, C were 17, 13 and 5 minutes which seems unnatural, but doesn't sound impossible. However in his previous contest we can find this:

"00:13:12 A Accepted [main tests] 00:39:13 A has been locked 00:49:40 B Wrong answer on pretest 5 [pretests] 00:53:46 B Accepted [main tests] 00:54:38 C Wrong answer on pretest 8 [pretests]"

That B and C looks highly suspicious.

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

    I dunno, there are a lot of things missing that lead to suspicions towards other Best Koreans.

    • a relatively similar template and coding style

    • I took 35 minutes to solve A+B+C as well (10 minutes on reading A,B,C,D and solving A; 9 on solving B, 16 on solving C), that doesn't mean I cheated; he could've tried to solve C first, had a bug or missing idea and found it after doing A+B

    • the minimum gap between submits in this round is 5 minutes, not seconds; in the previous one, there's a huge gap between solving and locking A that could've been spent on C, it looks like typical behaviour of someone who's unsure if the solution is correct even if it passes samples and getting AC on B boosts that confidence enough to submit; and there's still a minute gap; compare with 0 seconds and 14 seconds

    The templates in B and C are different, but they have something in similar at least (chkmin and chkmax). It's not as clear as RNS's conduct in Looksery Cup. Still, your suspicion isn't unreasonable and CF should look into it.

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

      Yes, some people might prefer submitting a few solutions at once.

      Also, I hope you don't use the word 'Korean'; many people mistake North Korea(Democratic People's Republic of, communist, nuclear, ...) as South Korea(Republic of, `88 olympics, Seoul, ...). There's even a joke about South Korean people scaring foreigners, saying something like 'I’m from North Korea!'.

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

In problem D, I got TLE in system test 91 due to my habit of using long long every-time. After the contest, I converted all the long long to int and same solution was accepted :(

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

Мне очень понравилась идея с кратким разбором.Хотелось бы почаще такие разборы!

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

Just curious. Why there's no "Congratulations to the winners!" since Round #312?

Anyway, congratulations for winning the round and good luck for your IOI jqdai0815!

UPD: it's been added.

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

For Div2 E, is there any notation as to how the points are placed? For example, is (1, 1) the top left of the board or the bottom?

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

No Euler circuits, so an easy win for jqdai0815 :P

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

Спасибо за раунд =)