Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

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

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

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

Представляю вашему вниманию Codeforces Round #539, который пройдет в эту субботу, 16 февраля 2019 г. в 19:35. Раунд будет рейтинговым для обоих дивизионов.

Авторы задач: markysha, xolm, aleex. Это наш первый раунд на Codeforces, и, надеюсь, не последний :)

Выражаем благодарность всем кто помог в подготовке задач:

В каждом дивизионе будет по 6 отборных задач и 2 часа 30 минут на их решение. Разбалловка будет объявлена ближе к началу раунда.

Быстрых вам идей и коротких решений!

Upd.
Div. 1: 500 — 1250 — 1750 — 1750 — 2250 — 3000
Div. 2: 500 — 1000 — 1500 — 2250 — 2750 — 2750

Разбор

Финальные результаты готовы!

Div 1:
1. Um_nik
2. jqdai0815 (это было очень близко...)
3. knightL
4. Swistakk
5. ToTLeS

Div 2:
1. schtamas
2. CheimaKH
3. revivedDevil
4. zhed
5. 1100011101

Наши поздравления победителям!

Возможно еще увидимся...

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

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

6 days wait is over. :)

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

hoping for a hell of a contest

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

    yeah it will be one atrocity of a contest. this guy has never made a contest before so we can expect the worst...they are just making fun of us at this point

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

How many shared problems between Div. 1 and Div. 2?

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

    I think 4, but it is not certain.

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

      So you think div1A will be div2E? No way.

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

        Oh, I mistook. The meaning of the previous comment is "Div1.A = Div2.C", but I momentarily mistook the meaning of shared problem as that of not shared problem.

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

        4 shared problems doesn't mean div1A = div2E. 6 problems for each division, with 4 shared problems i.e,

        Div2A
        Div2B
        Div2C = Div1A
        Div2D = Div1B
        Div2E = Div1C
        Div2F = Div1D
                Div1E
                Div1F
        
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +23 Проголосовать: не нравится

          I posted that before he edited his comment.

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

            Oops! Missed that.

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

              Yes. At first I mistook, and (through his comment) after knowing that I edited the commen. But I had to accept the downvote due to the mistake. Maybe it was and is a good experience...

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

                That's why people despise the 'codeforces community' , as they given 100's of down-vote(s) to guys who might have done a very small mistake even without knowing . You guys should not spread your frustration and negativity to others :-) (to the down-voters)

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

"(yeah, we approached testing thoroughly :))" This is important. I hope this is true.

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

congratulations on your first contest.

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

Is there a separate contest for both divisions or combined for both divisions?

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

do you even care about us anymore? the last few contests were like bad jokes full of math and other useless stuff. what happened? why did we stop getting good contests? are we not worthy anymore? do we not matter for you anymore? you just wanted us to make the statistics and now you shit on us?

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

    But why do you incur receiving negative vote by yourself? Your tone is the reason why there are a lot of negative vote on your comment. The same will be true of other comments. As I checked, 47 of your 60 comments received negative vote, 11 received zero sum of positive and negative vote, and only two received positive vote. And few people will think well of your comments though you may be going to post more comments in that tone.

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

      the truth hurts and that’s why people are downvoting. they know what i’m saying is true and are mad so they are downvoting me to make them feel better

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

make good contest or die

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

Hope this will be a fun and well-made round.

Good luck to all participants!

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

do you even care about us anymore? the last few contests were like bad jokes full of math and other useless stuff. what happened? why did we stop getting good contests? are we not worthy anymore? do we not matter for you anymore? you just wanted us to make the statistics and now you shit on us?

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

Finally I can have my chance to participate (I attempted to evade 2 previous rated contests to preserve the color formation) :D
Guess now would be my perfect chance to do good (or maybe do bad and reach purple, who knows :P)

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

Congratulations on your first contest! Will this round feature any interactive problem?

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

NO GreenGrape xD.

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

If the site does not collapse i think it will be a good round. I wish good luck to everyone!

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

Make good contest and hope no 404Error or sitedown issues.

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

Please ensure that the pretests are strong. There has been a spate of weak pretests in recent contests.

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

    Hacks are part of codeforces contests

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

    There has been a spate of weak pretests in recent contests.

    Hmm, no, have you been too obsessed with CodeCrafts?

    AFAIK two most recent contests are fine.

    jinlifu's round is a pretty good round ruined only by server issues.

    And about my contest, please research closer (all following data is calculated during contest time):

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

      I was talking mainly about round 537(codecraft). I apologize if it sounded accusatory or was worded badly.

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

        "recent contests" sounds like you're summing things up.
        Be specific, and optimistic. ;)

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

i am with a hope to cross rating 1200

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

wow~ any interact problem?

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

    No, we would say if there was an interactive problem

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

      Any clue when this will stop? I hope we eventually get to a point where interactive problems are just treated like normal problems.

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

Good luck to everyone.

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

Congratulations on your first contest..love to see div2 contest

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

I wish everyone high rates!

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

Is it rated?xD.. hopefully so because my first contest.. wish you all good luck

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

Why the downvote on me comment? I say good luck to all.. !!

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

A bad time for Chinese players :(

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

Best of luck every one.

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

It's my first div1 contest...A bit nervous...

Anyway,good luck to you all.

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

    I had that feeling too in my first Div. 1 round, luckly things ended up great and I solved 2 problems earning +76 :D

    Good luck

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

    I'm in the same boat (@1904). I'm both nervous and excited! Good Luck!

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

is it rateed?

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

The problem:A in Div.1 will be which problem in Div.2 ?C or D

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

Hope short and clear statements...

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

Best Of luck everyone

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

So far there are no registrants with rating 2019...???

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

yay — a contest that california people can take! good luck everyone!

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

bad timing for chinese... im sleeping during that time...

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

Finally! Indians can have their dinner and give the test

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

Good luck!

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

Finally contest comes after 6 days

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

Good Luck

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

I can't submit. When I click submit the "You have submitted exactly the same code before" notification appears, also I can't ask questions :/

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

Wtf is wrong with pretest 7 on Div2.B?????

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

Я, конечно, ни на что не намекаю...
bogyatstekskoykachalki
l-vkcom-stupidjokesproga

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

a xor b xor c means ((a xor b) xor c) ?

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

8073a83dcd32198a9781a5be97ceb3f773f794c7

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

In Problem C Div2 what are l and r?

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

Very nice contest, was eagerly waiting for it...

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

Was there at all a successful hack today?

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

whats wrong with protest 7 (problem B)

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

how to solve c? my code TLE testcase #9 T^T

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

    tle in 11 worst case takes around 3 seconds tried every optimization :(

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

    Though I didn't participated but I think dividing prefix xors for even and odd indexes should work

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

      my idea is xor(l~r) = xor(xor(mid~r),xor(l~mid)), but i didnt optimize to find this for every array..

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

    This might help:

    Let's say you have numbers A and B. C = A XOR B Then C XOR B will be A. You can use this in ranges too

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

    Let's consider segment (l, r] where r-l is odd, then
    p[r] xor p[(l+r)/2] = p[(l + r)/2] xor p[l]
    p[r] = p[l]
    Now it's simple thing to calc.

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

How to solve div2 Problem C?

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

    Maintain prefix XOR. Partition the indices with two of them in the same set if their prefix XORs are same. Maintain separate count for odd and even indices in each of the partitions. Answer will be the sum over all partitions of (odd choose 2) + (even choose 2).

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

    First, note that the problem can be reduced to count number of subarrays given xor by noticing that

    a[i] ^ a[i+1] == a[i+2] ^ a[i+3] equals to a[i]^a[i+1]^a[i+2]^a[i+3] with zero as a result.

    Hence, given xor will be 0.

    Since the problem limits to even-size array only, we need to modify the array a bit. We can try to merge every index i and i+1 (i.e. a[1]..a[n] becomes {a[1]^a[2], a[3]^a[4], ... } Then the problem simply becomes count number of subarrays given xor.

    But, another caveat is that we only handle even indices. We also need to create an array consisting of {a[2]^a[3], a[4]^a[5], ... } to handle odd indices.

    P.S. You can simply google how to count number of subarray given xor

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

      I think there is a problem with finding number of sub arrays with xor 0.

      a[i] ^ a[i+1] == a[i+2] ^ a[i+3] equals to a[i]^a[i+1]^a[i+2]^a[i+3] with zero as a result The converse isn't true for this statement, i.e., if xor from range [l, r] is 0, that doesn't mean we can partition it such that xor from range [l, mid] = xor from range [mid + 1, r]

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

How to solve div2 D ? sashan and one more name ? Any idea .

btw good contest , div2 a was also a little bit thinking .

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

how to solve Div 2 C

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

How to solve Div2 D?

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

    Hint : Answer belongs to {1, 2, Impossible}

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

    Assuming my solution works:

    You can split the problem into two cases, a palindrome of odd length and even length. For both cases, you can notice that the answer will either be 1 or two. That's a major hint.

    For odd cases: Checking for the "Impossible" case isn't too difficult so I won't explain that. The answer will always be 2 for this case otherwise (we can cut a prefix and a suffix of the string a "swap").

    For even cases: If both halves aren't palindromes, the answer is 1. Else, we can check if we can cut some prefix and append it to the back to form a palindrome that is different from the original one (if yes, the answer is 1). Otherwise, the answer is 2 by the same reasoning as the odd case.

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

    Div2D: Solutions fall into 3 cases: {1,2,impossible}.

    Let's think of a palindrome as consisting of "mirrored" part and a possible "center" character. For example, "abcxcba" has "x" center and "abc" mirrored part.

    Impossible case: input where the mirrored part consists of only 1 character. For example, "qq" or "qqqxqqq". If the mirrored part consists of more than 1 character, for example, "abcxcba", then we can always solve with 2 cuts (cut the outermost 2 characters from both sides in the example).

    So if the answer is not impossible we just need to check if a 1-cut solution is possible. If it's not, the answer is 2. Since input length is only 5000, we can try all possible places for 1 cut, check that we get a palindrome, and that the palindrome is different than the original palindrome.

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

What is so specific to test 9 in div1C? It's killed me...Also I really don't get why C. The other problems seemed decent, but this one is just coding. D was nice, E was very DSish (I'd personally rather find its place in an educational round). Didn't have time to read F. I absolutely loved B.

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

    Can you explain D?

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

      It's pretty mathy: you have to know prufer codes. Basically you can infer the following thing: the number of trees on N nodes with given degrees d1, d2, .., dN is the multinomial coefficient on the array d(i)-1, that is: (N-2)!/product of (d(i)-1)!. That comes from the number of arrays of length N — 2 where i appears exactly d(i)-1 times. It's easy to prove that once you know the bijection between the prufer codes and the labelled trees. Now, assume you've fixed the distance between the 2 nodes to be K (note the actual 2 nodes don't matter and you can ignore them, I for one, haven't read them). That implies you should have K — 1 ordered nodes on the path between them. There are (N-2)(N-3)...(N-(K-1)+1) ways of doing so. Then, let's assign their weights: the number of ways of writing M as sum of K numbers: C(M-1, K-1). Then the rest of the weights are free to take any value: M^(N-2-K). Now we're interested in the actual number of trees. Let's contract the K+1 nodes on the path into one big node. The thing is that you now care about the degree of that big node. Assuming it is d, you have to multiply the answer by (K+1)^d because for every node that has chosen it to be a neighbor, you need to assign an actual concrete node out of the K+1 small nodes that make up the big node. So if you iterate d, then you can choose the d-1 spots where the id of the big node will be placed and complete the rest of them with anything. This is N^2. The inner loop (the one that iterates d) can be algebraically manipulated to look like a constant times a sum of C3*C(C1, i)*C2^i which gives C3*(C2+1)^C1 where C1 and C2 are some constants that you can find by grouping together things that are dependent on d and things that are not. You then get NlogVmax because of some raisings to power (that I think you can skip if you really want to, but there's no need for that).

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

        Thanx a lot!!

        Can you please suggest any tutorial for prufer codes and some related problems?

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

    You should not take into consideration events that appeared before l. In other words, the initial s on the interval should be 0, not the last speed that was set before l. Such a fix changed my score from "Wrong Answer on test 9" to "Pretests Passed".

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

Very good and balanced contest! Thanks to writers.

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

How to solve div1 D?

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

Nice problemset, especially 1B and 1D ;) (though I failed both miserably :D)

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

    how u solved div1 b ?

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

      A little bit intuitive (I didn't make it to prove just yet), but the answer can only be either 1, 2 or Impossible. Thus, this can be solved by some bruteforce.

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

        Well, I think you can prove it by showing that if you swap a prefix of s with a suffix of s such that the prefix/suffix is not a palindrome, then it will be sufficient. Because of this, as long as the n/2 prefix and n/2 suffix are not all the same letter, it is possible in 2 moves or less. Then you can brute force to check 1 move solutions.

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

Problems were very interesting to solve. Thanks for your first contest! :)

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

It took me nearly an hour to realize that if a_l ^ a_l+1 ^ ... ^ a_r = 0 then a_l ^ a_l+1 ^ ... ^ a_x alway equals a_x+1 ^ a_x+2 ^ ... ^ a_r

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

thinking in C dp gave me headache but it was a nice problem

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

Can someone pls tell what is wrong with this code? https://codeforces.com/contest/1113/submission/50033374

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

    i dont know if this is helpful, but testing your code against: 2 1 100. gives me 100 instead of 20.probably you're missing the fact that your meant to perform the increase & decrease at most once.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    forn(i,0,n)
        {
          cin>>a[i];
    ...
    
     forn(i,1,n)
           {
    ...
    

    second for is from 1

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

Is Div2E/Div1C solved by doing minimum-prefix-sum query with segment tree?

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

Nice problems! The round was quite hard but it isn't a bad thing, I guess.

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

div1C на тупую реализацию. Раунду был присвоен статус "мусорка".

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

Can anyone please tell me what's wrong with this code: https://codeforces.com/contest/1113/submission/50029202

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

In 1B, I completely missed that the initial string was a palindrome, I was trying to solve for general string(as constraints were bit low), after struggling for 30 mins I re-read the problem.

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

-

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

Can anyone tell me why this DIV2B code is WA? `

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

    answer is 22, your program is giving 23

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

    Next time you want to put some code in comments, I suggest you using pastebin, ideone, link to your submission or even the thing called "spoiler", because it's not very nice to put your long code in the comments section)

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

    Use a spoiler tag. A long code comment makes it difficult to read all the blog comments. Especially on mobile.

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

Blackness & dragn78 .. 1 user, 1 room, 2 accounts.

room : https://codeforces.com/contest/1113/room/216

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

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

Why the system testing hasn't started yet?

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

Oh I almost got Div.1 D, I was just having some bugs and didn't get it on time.

Amazing problem-set, enjoyed every minute in the round

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

Damnnn!!! Completely missed that initial string is palindrome in Div2-D. fml.

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

For more contests on the weekends : )

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

куча читерских взломов

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

MikeMirzayanov I think this should be considered as cheating. look here

The person who has done this 6-vkcom-stupidjokesproga

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

The contest with least Hacks and System Test Fails !

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

По смыслу задачи нормальные, спасибо за раунд и за работу! Но позанудствую :)

на Востоке поступают следующим образом: записывают исходное имя как строку, из которой хотят получить новое имя на лист бумаги.

Что такое «получить новое имя на лист бумаги»? А, это пропущенная запятая!

В данной задаче деревом называется взвешенный связный граф, состоящий из n вершин и n−1-го ребра

Это просто фейл. У вас дерево состоит из эн вершин и эн минус первого ребра. Видимо одного. Добавив «-го» вы специально даёте читателю понять, что это именно порядковое числительное.

две свои любимые врешины

Пожалуйста, давайте кому-нибудь вычитывать русские условия, чтобы было меньше врешин!

Удачи, спасибо и не обижайтесь на занудство :)

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

    У вас зоркий глаз! Может вам стоит попробовать себя специалистом по вычитыванию условий? :)

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

      В тех олимпиадах, к подготовке которых имею отношение (NEERC, ВКОШП, олимпиады ЛКШ), беру на себя эту работу регулярно и с радостью, ага!

      На КФ, наверное, можно тоже меня просить о такой работе, но тут уж должно совпасть настроение, время, готовность не писать этот раунд (это проще всего :)) и т. д.

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

div2-C I think the question is ambiguous.

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

good contest. :)

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

Умер мужик

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

road to yellow

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

Быстрых вам идей и коротких решений!

Адское ДД с миллионом характеристик в вершине, не менее адское ДО, которое еще в ТЛ надо запихать, и линк-кат

Хороший раунд (нет)

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

Такое ощущение, будто вам хороших задач на полноценный раунд не хватило :)

d2C — возьмем баянистую задачу про количество подотрезков с нулевым ксором и потребуем, чтобы отрезок был четным, получили новую задачу (нет)

d1D — задачка на посмотреть вики про теорему кэли, даже без комментариев

d1E — возьмем легкую задачу при простом модуле и устроим карнавал, превратив модуль в составное число

Зато d2ABD очень классные, мне даже понравилось!

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

    Тайна раскрыта! Ну правда от части.
    С d1E не согласен, так как случай с простым модулем это малая часть решения текущей задачи.
    d1D есть другие решения. Не зная теоремы Кэли можно было решить тоже, может потратив чуть больше времени.
    d2C идея все же есть, хоть и почти очевидная для div1 участников.

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

It seems that systests for problem Div1C don't contain test with query similar to

3 1 1 0

I resubmitted my solution, because found that my first version printed '-1' on this test, but it should print '1'. After contest I submitted first version and it got AC too.

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

Can anybody tell me why my 1st solution for div2D is giving wa on 8 but when I changed the code a little bit with even less memory it is giving MLE on test case 1. MLE solution

WA on 8 solution

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

    It seems you did more than one change. Inside main there are two nested loops and an unused variable g in the WA8 code. Then you used it in the MLE solution. I've taken your MLE code without using said g variable and it uses less memory but still WA8. I guess you did some logic corrections wich ended in MLE, maybe you didn't set properly the values in P matrix, what do you think?

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

Did div D in N(log N).Here is the solution : https://codeforces.com/contest/1113/submission/50054538

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

Очень идейный (хороший) раунд побольше таких бы.