markysha's blog

By markysha, 5 weeks ago, translation, In English,

Good day to you, Codeforces!

Let me introduce you Codeforces Round #539, that will take place at Saturday, February 16, 2019 at 19:35. The round will be rated for both divisions.

The problems of this round were developed by markysha, xolm, aleex. That is our first round on Codeforces, and I hope not the last one :)

Thanks everyone who helped with tasks preparation:

There will be 6 tasks and 2 hours 30 minutes to solve them. As usual, the score distribution will be revealed shortly before the contest.

Wish you quick ideas and short solutions!

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

Editorial

Final results are ready!

Div 1:
1. Um_nik
2. wxhtxdy (was so close...)
3. knightL
4. Swistakk
5. ToTLeS

Div 2:
1. schtomi97
2. Dev0302
3. revivedDevil
4. miseri
5. fragusbot

Congratulations to the winners!

Maybe see you later...

 
 
 
 
  • Vote: I like it  
  • +584
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it +69 Vote: I do not like it

6 days wait is over. :)

»
5 weeks ago, # |
  Vote: I like it -22 Vote: I do not like it

hoping for a hell of a contest

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

    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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What hell

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -52 Vote: I do not like it

    I think 4, but it is not certain.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      So you think div1A will be div2E? No way.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 4   Vote: I like it -15 Vote: I do not like it

        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 weeks ago, # ^ |
        Rev. 3   Vote: I like it +9 Vote: I do not like it

        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 weeks ago, # ^ |
            Vote: I like it +23 Vote: I do not like it

          I posted that before he edited his comment.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Oops! Missed that.

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
              Rev. 3   Vote: I like it +44 Vote: I do not like it

              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...

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                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 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

congratulations on your first contest.

»
5 weeks ago, # |
Rev. 2   Vote: I like it -29 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Separate

    There is actually a link in the post.

»
5 weeks ago, # |
  Vote: I like it -59 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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 weeks ago, # |
  Vote: I like it -156 Vote: I do not like it

make good contest or die

»
5 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

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

Good luck to all participants!

»
5 weeks ago, # |
  Vote: I like it -36 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Good luck!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am really sorry, that your preserved color is gonna fade away :|

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Somehow I predicted this to be happening... :<

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -58 Vote: I do not like it

Score: 500-750-1000-1500-1750-2000

P.S. It is just my opinion, and what about you?

»
5 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

NO GreenGrape xD.

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Hacks are part of codeforces contests

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -32 Vote: I do not like it

      it will be rigged as always

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        be more optimistic :)

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it -31 Vote: I do not like it

          about what? all odds are against us. newbie contest maker (it’s his first ever) so we can expect the worst and they are treating us miserably. there really isn’t anything to be optimistic about.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +14 Vote: I do not like it

            All the authors have a great life experience in making contests, so please think twice before saying something.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

i am with a hope to cross rating 1200

»
5 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

wow~ any interact problem?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    No, we would say if there was an interactive problem

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

Kindly make time period 2 hours and make problems accordingly tough. 2:30 is much longer. (At least for Div 2).

»
5 weeks ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

Good luck to everyone.

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I wish everyone high rates!

»
5 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    It is better to refrain from containing "Is it rated?" in the comment.

»
5 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

A bad time for Chinese players :(

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    It's always a bad time for someone, quit whining.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of luck every one.

»
5 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

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

Anyway,good luck to you all.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -47 Vote: I do not like it

is it rateed?

»
5 weeks ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope short and clear statements...

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Best Of luck everyone

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello and Good Luck all of them

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Finally! Indians can have their dinner and give the test

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Good luck!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally contest comes after 6 days

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same shit

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try: 2 100 1. should give you 20.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Atmost 1 operation can be performed by the farmer. Trying to perform more than one operation results in failure in this test.

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    There's no matter in how you place the brackets

»
5 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

8073a83dcd32198a9781a5be97ceb3f773f794c7

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C Div2 what are l and r?

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Was there at all a successful hack today?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I saw a person with +3:-2.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh okay thanks.
      But all I could find was -1 or -2 hack counts.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    You can always go to the contest->status and use status filter to see all successful hacks in the contest.

    Image
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, thanks alot. This is something I never knew that it existed even after 2 yrs of cf.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

whats wrong with protest 7 (problem B)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Your solution might have a bug.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it -6 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve div2 Problem C?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you give an example?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes you are right. I made a mistake. If the xors of left range and right range were a and b, where a not equal to b, then a xor b can never be zero.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it -8 Vote: I do not like it

        Ignore my original comment, I was stupid :<

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Are you sure? Can you provide contrary instance for second?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It is always true. Do you have an example when it's not?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oops, I was going full mad. Sorry guys :<

»
5 weeks ago, # |
Rev. 3   Vote: I like it +7 Vote: I do not like it

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

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve Div 2 C

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve Div2 D?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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 weeks ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain D?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanx a lot!!

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      Fuck...Thanks for telling me. Now I can die peacefully

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Very good and balanced contest! Thanks to writers.

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve div1 D?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +35 Vote: I do not like it

    https://en.wikipedia.org/wiki/Cayley%27s_formula #generalizations

    Then you just enumerate the number of points between A and B

    Knowing how to google properly gives 1750 in div1! How motivational

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      do we need to know the above theorem to solve it . if yes , it must be pretty hard for them who have no idea abt. cayles theroem

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      There is a very interesting question still remains: how to find a number of different paths with length i and sum m?

      UPD: sorry for the stupid question, it was just Cnk :)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Found the formula, thought it was useless, skipped XD

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Also, there is no such a generalization in the russian version of the wiki page.
      I'll take a note about always reading English version.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Sadly, I didn't give too much attention to the generalization section due to the round pressure.

      So, in the end, I spent some upsolving hours creating my own generalization based on the specific Cayley's formula proof by double counting (https://en.wikipedia.org/wiki/Double_counting_(proof_technique))

      But, afterwards, it was rewarding for me to see that it was a relevant result.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use cayley's and basic combinatorics to find the number of trees in which we have k edges in simple path from a to b. (a, b doesn't actually matter)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    let's renumerate vertices a = n — 1, b = n. Than think about Prufer Code. You'll have path between n — 1 to n with number of edges >= e if Prufer code ends with (e — 1) sequence of distinct numbers that are less than n — 1. Than you can find formulas for dp[e] (it's just what is written above) to make number of edges == e just subtract from dp[e] , dp[e + 1] and dp[e + 2] ... Implementation for details 50017868

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Sad thing is I looked at that page but skipped past the formula. Sad face!

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how u solved div1 b ?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        in the recent cf rounds , i m solving problems upto c but i have very little of no proof for it . just a gut feeling and implement it . it passes .

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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 weeks ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's giving 20. Can u pls check again?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        sorry my mistake. try 2 100 1. should give 20. but gives 101.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    forn(i,0,n)
        {
          cin>>a[i];
    ...
    
     forn(i,1,n)
           {
    ...
    

    second for is from 1

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +64 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    #define read(a,n) upto(i,0,n-1,1) cin>>a[i];
    ...
    for (int i = n-1;i>=1;i--)
    ...
    

    for to 1 instead of 0

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      its sorted so you don't have to consider first element...because i am multiplying factor with arr[0] every time.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        #define MAX ((int)1e4 + 1) 
        

        should be 5e4 + 1 :/

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          silly mistake:( thanks for pointing it out...

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

-

»
5 weeks ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

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

Spoiler
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check for: 2 1 100 Answer should be 20

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    4
    7 5 8 3 
    

    answer is 22, your program is giving 23

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
5 weeks ago, # |
  Vote: I like it +54 Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Why the system testing hasn't started yet?

»
5 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

For more contests on the weekends : )

»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

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

The person who has done this 6-vkcom-stupidjokesproga

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is hilarious. What are the odds that his alt account and him were assigned to the same room.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think that he has many alts, so it is more likely to get in the same room as one of his alts.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +21 Vote: I do not like it

        Birthday paradox at work.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          Only if he's willing to get rating on any of the accounts. It's much more likely that he has one main account and multiple helpers and then birthday paradox doesn't apply.

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

The contest with least Hacks and System Test Fails !

»
5 weeks ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

div2-C I think the question is ambiguous.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

good contest. :)

»
5 weeks ago, # |
  Vote: I like it +104 Vote: I do not like it

road to yellow

»
5 weeks ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?