den2204's blog

By den2204, history, 6 years ago, translation, In English

Hi, Codeforces!

At Jan/13/2019 17:35 (Moscow time) will start Codeforces Round 532 (Div. 2). Round will be rated for second division (rating below 2100). As usual, participants from the first division can participate in a contest out of competition.

The round will consist of 6 problems and you will be given two hours to solve them.

Task prepared by me, den2204.

Thanks MikeMirzayanov for the platform Codeforces, KAN for round coordination and help with preparation. Thanks vintage_Vlad_Makeev, Andreikkaa, Flyrise, Um_nik, Aleks5d and ---------- for help with preparation and testing round, arsor for translating statements into English, arsijo for assistance in conducting the round. Thanks Andreikkaa for the idea of the problem E.

Good luck!

P.S. It is my first round on Codeforces, please, do not judge strictly :)

UPD: Added editorial. Thank you all for participating and for the feedback on the contest. I apologize for the leap in complexity between tasks and for weak pretests for some tasks, I’ll take this into account when further preparing contests.

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

| Write comment?
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Honestly, not bad for your first contest! I hope you had a great time creating the contest and all of us participants would like to thank you for spending your time on this! We all really appreciate it! Hope to see you again as a writer den2204!

And to all participants: Good luck and have fun at the contest tomorrow! <3

»
6 years ago, # |
Rev. 2   Vote: I like it +72 Vote: I do not like it

Thanks Andreiikka for the idea of the problem E.

Segment Tree in E???

»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Finally a contest without faked colors !

»
6 years ago, # |
Rev. 2   Vote: I like it -35 Vote: I do not like it

:D

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

    But isn't this an usual start time for codeforces rounds?

»
6 years ago, # |
Rev. 2   Vote: I like it +30 Vote: I do not like it

den2204, congratulations for your first contest as a problem-setter...

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is going to be my first contest of the new year. I am so excited. xD

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

    I didn't find you in the contest today. You got paralyzed with too much excitement or something?

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

      Couldn't give it because of some urgent work. Thanks for noticing though.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Obviously my classmate after all xD

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

Congratulate with your first contest, I think it will be greate :) Good luck all :D

»
6 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Please make strong test cases

»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

When there is a new problem setter its usually 2 condition : 1) the tasks are creative and fun to solve 2) the tasks are time taking and not fun to solve I hope for (1) :)

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

i hope your first contest will be great ^^

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Scoring distribution?

»
6 years ago, # |
  Vote: I like it -61 Vote: I do not like it

why geometry??

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

    why not?

    Rather than complaining about it, maybe it would be more beneficial to get better at the topic, because it's not going away.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -107 Vote: I do not like it

      why not?
      because it is completely pointless and rather than wasting time "getting good at it" for no reason, they might as well give us better and more useful problems overall.

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

        Do you have any reason why other problems are “better” and “more useful” besides just your opinion?

        It’s not pointless if your goal is to get better at cp. You’ll end up doing better in contests because you’ll know the topic.

        And if you don’t want to learn geometry either, that’s perfectly fine. Just don’t start complaining about the questions when you can’t do it, since you made the choice not to learn. There’s 5 other questions for you to try.

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

          I'm neither with any sides nor saying geometry is bad, but you know, memorizing( or even searching ) a formula and coding an O(1) program is not really fun.

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

            All you need to memorize is the definition of sin function. If you can't memorize 8-th grade math, then I have bad news for you.

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

              How does the definition of sin function help in solving this problem?

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

                You have to connect center of inner circle, center of outer circle and point of tangency between two outer circles, In this triangle we know two sides, one acute angle, and also we know that angle between tangent and radius is right.

                I'm not saying that this problem is innovative or interesting, but in no way that's because it is geometry or math in general.

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it -14 Vote: I do not like it

              OK, I'm too stupid, and I know it!!!

              BTW in our country they teach it in 11th grade, and I haven't reached there yet.

              And again; BTW I know what sin func is.( But still stupid )

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it -51 Vote: I do not like it

            exactly, it isn't fun nor useful.

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

            It can be boring if you can instantly come up with the correct formula and code it up (but it's also good, since it will give you more time to work on other problems).

            If you don't know the formula, you can spend some time deriving the solution using what geometry knowledge that you know.

            And isn't going through the process to reach a solution the fun in cp?

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it -66 Vote: I do not like it

              so in conclusion, it is pointless. period. glad we could all agree.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it -11 Vote: I do not like it

                Sorry if you didn’t see it before.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it -67 Vote: I do not like it

                  i saw it but because you have anime profile picture i have automatically skipped it so i didn't count it.

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

        What is useful?

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

        So geometry is useless, but wasting time to create fake accounts is useful?

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it -19 Vote: I do not like it

          how can an account be fake?

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

            You didn't have the balls to post that comment with your actual account because you feared downvotes, so you created this one. Do you honestly think we don't know that?

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it -12 Vote: I do not like it

              THIS is my main account. you can ask the codeforces administration about this.
              your downvotes don't affect me, they are worthless because i know what i say is true.

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

                You yet to do a contest in your "main account" and you are complaining about problemset. WOW!!!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it -11 Vote: I do not like it

                  ? what are you talking about?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                  Rev. 3   Vote: I like it +10 Vote: I do not like it

                  Before trying to make the community fool, you may not notice your color is still black now :P :P And you may be forget people can go to your profile and see the number of contest you attend till now.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it -25 Vote: I do not like it

                  you imbecile just because it glitched for you doesn't mean that's how it is for everyone.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Illuminati wants to know your location.

»
6 years ago, # |
  Vote: I like it +131 Vote: I do not like it

There is a drastic difference between A-C and D-F, so the contest turned into speed coding.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope you not to repeat it

»
6 years ago, # |
  Vote: I like it +53 Vote: I do not like it

Worst Problem statement with worst Explanation. Wasted 10 min in just understanding the problem Statements

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why D, E, F so hard? Massive AC-gap between C & D :(

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

    For me E is easier than C.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's right.But D is too hard to put in a Div.2 D I think.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      C was pretty straight forward. If you know Trigonometry, It is easier than A , else you wouldn't be able to do it :( How about E ? Didn't read that. Was it a data structure problem ? Or something else ?

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

A, B, C = A and D, E, F != DIV 2.

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

In problem F, are we supposed to answer the queries for maximum subarray xor? Probably somehow offline?

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

    No, we have to choose some numbers from l to r s.t. their xor is maximum ... It's a problem similar to https://www.spoj.com/problems/XMAX/.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I am aware of that, let me reformulate my question. Is that problem equivalent to finding maximum subarray xor on segments of the given array?

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, it's related to finding independent basis vectors of l to r. It can be done using gaussian elimination. But my solution was N*logN*20^2 which is not enough to pass t.l.

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

        In general, maximum subset xor and maximum subarray xor aren't going to be the same — subarray is a fairly restrictive condition when you need to pick things.

        For example, take a = [5, 6, 2]

        Maximum subset xor is 7, maximum subarray xor is 6.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Isn't subarray a subset of an array?

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

            If that's the definition you're going with, then yes, the answer is maximum subarray xor.

            I'm going with the more commonly used definition for competitive coding, where a subset is your usual subset and a subarray is a contiguous segment of the array. Similar to how a substring is a contiguous segment of a string.

            Something like this, basically.

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

              Can it be done without Gaussian elimination?

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

                Maximum subarray xor can be done with a trie — see here for a tutorial.

                Maximum subset xor, I don't think so. I'm not aware of any other method at the very least.

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve D?

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

    Bring the king to the center. Then count the number of rooks in each quadrant, and go diagonally in the direction opposite to the quadrant with the least number of rooks.

    Verify as an exercise that this works.

»
6 years ago, # |
  Vote: I like it +26 Vote: I do not like it

How to solve F?

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

    Take yesterday's G -> TLE with seg tree -> use divide and conquer that you can use just prefix/suffix -> done

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

      Yeah I got TLE with segment tree, very nice solution, thanks!

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

      Is it possible to merge two independent vector sets in better than 20^2 time?

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

        I don't think so. My solution computes suffix/prefix when dividing [l, mid) [mid, r) (to add a number to a prefix/suffix is O(bits) time) and then solves the queries with l < mid and r >= mid in O(bits^2).

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your Gauss struct is black box for me.
      If you can provide some intuition how those max and min are working?
      First time I have seen inserting an element in O(bits).
      My implementation in O(bits^2) was giving tle.

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

        You can add number by number. So instead of thinking of a N*BITS matrix when you have N numbers, think of a BITS*BITS matrix where you insert one value at a time. Also, don't use vectors in code like this that uses a ton of memory, it'll use a lot more memory and it'll have more cache misses. For max, you have the basis so just go from the number with highest bit to lowest bit and activate the bit whenever you can.

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

          Got it. Thank You.

          What I have understood is that each no in your table has a bit (the most significant bit) associated with it. Similar to the basis vector which has at least one dimension with them.

          And that no is responsible for activating(max)/ deactivating(min) that particular bit.

          P.S. After reading I got core idea of your implementation. But was bit confused with just go from the number with highest bit to lowest bit So, I added prt function in your implementation. And then I came up with the above explanation.
          Thank you. :)

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

          In your submission (linked below), the Gauss::add() function confuses me.

          I think that the invariant for the Gauss class is that if table[i] > 0 then the $i$th bit of that needs to be set. But if you don't make that check in your add(), this invariant could be violated.

          Your submission did get AC, so what am I missing here?

          48339644

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            Edit: True, let me think how that worked rofl. So... I got careless and think that code shouldn't work, systests were weak?

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

    You can split your array in chunks of size 20 and use sparse table on array of size n/20. Query can now be answered online in 20*20 time by sparse table query + adding elements partially belonging to a chunk one by one.

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

      Nice! I thought of sparse table but I didn't think of dividing into blocks, that's a cool idea.

»
6 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Does E have the following solution?

Sort all the edges according to c. Binary search over this to find the edge so that no cycle is present. Compute the topological order of this graph without cycle and add reverse remaining edges which violate the order.

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

    Sorry if I understand your idea wrong, but don't you mean to reverse all the edges that have a lower cost than the middle in your binary search ? I thought the same but there might be some edges that you can reverse that should not be reversed which made it so much harder

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

      You cannot reverse all the edges which have lower weight because you might end up getting cycles in new graph. Instead what you do is reverse those edges which violate the topological order as a directed graph has no cycles iff it has a topological order.

»
6 years ago, # |
  Vote: I like it +33 Vote: I do not like it

The problems were actually pretty good, but the difficulty gap was pretty bad. Hope you can balance the problems in the future!

»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

How we were supposed to locally test D?

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

    Write your own local judge, or don't write with mistakes.

    Anyways, if you submitted and get a wrong answer on the first test, it will tell you what went wrong, for example "invalid move for king", which is still helpful.

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

    I scaled down the problem by a factor of 111, i.e. 9x9 board and 6 rooks in play.

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

      That's a really clever line of thought.

      I can see that 1 dimensional properties and 2 dimensional properties of the problem will remain the same. But maybe, just maybe, the properties of the problem that require an interaction of a 1D vs 2D would not hold.

      I'm sorry that I'm very vague, but I'm not very clear about it myself. I also can't think of an example of such a property.

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

How to solve E? I thought of using finding a maximum spanning tree and every not used edge would be a flipped edge, but I didn't know how to implement a dsu for directed graphs.

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

    binary search the answer, then the problem becomes to check whether it has cycle.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, one quick question, would we reverse all the edges whose c is less than or equal to mid?

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

        No, find a valid topological ordering for the graph with > mid. Now, just orient the edges <= mid according to this order.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't see why I can ignore edges to check of cycles just because I can choose the orientation of them on the directed graph.

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

            Given that you ignore them, you have a topological ordering. Now, you can direct them using the topological order (from the vertex that comes first in the order to the one that comes second).

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain what u mean by bs over the answer? what answer

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        When a problem is asking for the minimum k satisfies a condition T, and k satisfies T => any k' > k satisfies T, and for a number k' you can check whether k' satisfies T.

        You can binary search k. If k satisfies T try k smaller, else try k larger.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ok skylinebaby i understand .

          regarding this question everytime we should choose a k using binary search.

          then we can build a new graph with edges > k , if this graph forms a cycle , then answer will obviously will > k , and if not then answer will be <=k.

          this way we can get the best k .

          now , how to proceed further . which edges to revert so that graph becomes acyclic .

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            You can topological sort the graph with edge  > k, because the problem don't need to minimize the number of edge which should be reversed, you can simply reverse every edge which has the wrong direction against the topological sort.

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              so is it reduced to can we make topological order of edges > mid, because if we can do so we can ALWAYS adjust remaining edges? . please help, i m not finding the way that how remaining edges can cause problem to topological order for why we need to orient remaining edges to topological order

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                Rev. 3   Vote: I like it +3 Vote: I do not like it

                Yes, if we can make the topological order of edges  > k, we can always adjust remaining edges  <  = k, because we can just follow the topological order. On the other hand, if we can't make the topological order of edges  > k, that means there is a cycle with edge all  > k, and we can't satisfy the original condition by reversing those edge  <  = k.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  oh thanks bro, just got it accepted :D

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wasted the whole time on C. Dunno why got WA on D. Coded E just after the contest ended. Gonna kill myself if it passes.

»
6 years ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

Honestly speaking, the gap between C and D is very large. C is the normal Div.2 B and B is the normal Div.2 A.

Surely you didn't send problems to the problem pool like what Arkady did on the problem B. I mean it was like, n=6, m = 6 and 112556 then the answer is 000001

Need solution on D too. It really looks like pigeonhole, but I don't know how to do it.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    D and E were easier than C

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

      Well, depends on perspective IMO.

      For me, I think C is easier than D and E. You just need to write some geometric formula and derive it.

      Well, actually I can't tell much because I didn't finish D and E.

»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Geometry problem ---> T̶r̶y̶ ̶t̶o̶ ̶s̶o̶l̶v̶e̶ ̶i̶t̶ google it.

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

What were the hacks for B and A? I managed to hack someone on B because his implementation had a time complexity of O((m — n) * n). Are there any other hacks for B?

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

    I passed pretests on A but failed system tests by thinking that you could opt to not remove any tabs. The case 3 2 1 1 1 will break this

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C guys? I could not come with a solution during the contest :(

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

    Solve your homework on triangular formulas. If you did not take them yet, well you are rekt.

  • »
    »
    6 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    The centers of the n outer circles make a regular polygon with n sides. Now focus on the centers of 2 adjacent outer circles and the middle circle. You have a triangle with side lengths (r+R), (r+R) and (R+R). You can also find all the angles in the triangle. Finally, you can use cosine theorem to get a formula: (2*R)^2 = 2*(R+r)^2 — 2*(R+r)^2*cos(A) [A is the center angle, actually A = 360/n]. Then, you can simplify and use the quadratic formula, or use binary search.

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

    What I did was visualized that the centers of the outer circles when connected formed a regular polygon with n sides. That polygon has its center coinciding with the center of the inner circle. We can calculate the length from the vertex of the polygon to the center of the inner circle using trigonometry and hence there is only one variable i.e R (here side of the polygon will be 2R). I am almost sure of my solution, I didn't take time to prove what I conjectured, so will come to know exactly if my hypothesis is right when final results are out.

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

    This is my idea,may be inefficient.

    draw some cases,we can find:

    The center of inner circle can make a Isosceles triangle with two conterminous outer circles' center,and two angles will be ,difine this as θ

    then we have (R + r)2 = R2 + (R·tan(θ))2

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

    If you connect the centers of two adjacent little circles and the center of the big one, you'll get a triangle. The sides of this triangle have lengths r+R,r+R and 2r

    . A little trigonometry will get you that the top angle is

    θ=2arcsin(r/r+R).

    Since you want the small circles to form a closed ring around the big circle, this angle should enter an integer amount of times in 360° (or 2π

    if you work in radians). Thus,

    θ=360°/n.

    From this, you can compute that

    r=Rsin(180°/n)/1−sin(180°/n).

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All you gotta realize is that centers of outside circles must be 2R away from each other. How to get centers? Well just do x = (r+R)cos(t) and y = (r+R)sin(t), where t = (2pi/n)*i. If you want to visualize draw two circles tangent to each other with radius r and R. They will be r+R away from each other, and assuming one of them is at 0,0 the other's coordinates can be gotten from sin and cos.

    Binary search: if distance < 2R the circles are too big otherwise they are too small.

»
6 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

Please tell me how to debug intractive problem or what is pretets 2 for D. Idea for D: Place king in 500,500. Divide chessboard in 4 pieces. Each piece has one corner as king position and one corner as chessboard corner. Find which of this 4 pieces has smallest number of rooks. Go to opposite corner with king moving only diagonally. Convince yourself it always works.

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

    This is correct and actually needs at most 1000, not 2000 steps! Really cool problem.

    I debugged on 9 x 9 grid with 6 pieces.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Unfortunately, one must check that the king doesn't move to a space already occupied by a rook (which I failed to do). This is probably where the factor of two comes from.

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

        If we try to move to a cell with a rook, it means we are trying to move diagonally! Otherwise the king was already hit. Therefore, we can just move either horizontally or vertically to a cell adjacent to this rook. And then we are hit and the game ends. So the number of moves will really be at most 1000.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I did it as well. Can anyone take a look and tell me what is wrong with this? Even passed pre1. 48356184

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same with WA6. I think what matters is how you get to the corner. You have to try to move diagonally as much as possible. After considering this, got AC!

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for reply but, already found mistake it was checking if(x!=500 and y!=500) instead of (x!=500 or y!=500) ;)

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

I'm surely misinterpreting the problem/making some really silly mistake, but I think the king can't guarantee having a check ?

Define Si to be the configuration where the black rooks are at the cells {(1, 1), (1, 2), ..., (1, i - 1), (1, i + 334), (1, i + 335), ..., (1, 999)}. Initially start with S1 and the white king at (1, 1). Now at some step, if the king's x coordinate changes from x to y (with |x - y| ≤ 1) then it's easy to see we can move some rook so that the rooks configuration become , so the king can never guarantee a check ?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But in your example all the pieces share the row, so the king is already hit by all the rooks.

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

      Ooops thanks, it was embrassing.

»
6 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Just curious to know, why does this submission on problem B doesn't get runttime error when he declares array of size exactly 100000.
My hack test

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why would it get runtime error? n, m <= 100000 so it seems fine.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      array size has been declared as 100000. hence, array element range is between 0-99999. but he does arr[aa]++;
      hence it should get runtime when aa = 100000. Sorry, correct me if I am wrong.

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

        Ah, so he is accessing an element outside of the array. If he'd used std::vector instead of a plain array he would have gotten a Runtime Error. However, since he's using a plain array, his solution is doing undefined behaviour, which is bad, but most often it won't be a problem because he's accessing memory right next to the array.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        When you declare an array.Usually you will get an array a little bigger than you declare.That works in most computers.Include my computer,Codeforces computer and our school computer.And even a[-1] won't get Runtime Error in some computers.

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

OMG! I had a clean solution for D, but didn't consider the case of eating a rook. Didn't look at the CF error message :(( It was saying king ate rook

»
6 years ago, # |
Rev. 2   Vote: I like it +76 Vote: I do not like it

Trash contest...
1500 point problem solved by 3.5k and D problem solved by only 125 people. Also E problem is just classic know problem added binary search(here is the solution). I think F also range version of the XOR max problem(here is solution).
If you want to do such contest, better to not do. Educational Rounds much better than this kind of contests...

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem D was not actually that difficult. The entire contest was consistently simple IMO, which is fair.

    I do agree that this contest is more like an Educational round, tho. Because it's very easy to google solutions to some problems.

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I do not want to judge you strictly. But What the hell.

»
6 years ago, # |
  Vote: I like it +40 Vote: I do not like it

I understand that it is not easy to make a well balanced contest, but the big jumps in difficulty of problems are really obvious in most of recent codeforces contests.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve B?? Can anyone please explain??

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got pretest pass by maintaining a set {1...N} and erase element x when I see x. If I saw x after I erased it, store that information. When set is empty, re-construct the set, without the elements I stored information about before.

    For example, 3 9 1 1 2 3 3 3 2 1 3

    Set : 1 2 3 (initial)-> 2 3 -> 2 3, (1 seen once more) , 3 (1 seen once more) -> X (first Round), Reconstruct only 2, 3 -> 2 -> 2, (3 seen once more) .....

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

    It was clear that whenever i get all type of elements atleast multiple of n times then i can create a contest. What I did was maintained a frequency array freq for each type of element. As soon as i get element of type X i increased it's frequency say new frequency is z. Also i maintained an array for keeping count of how many elements i have of particular frequency z. If i have n such elements that means i can create a contest so i incremented answer by one.

»
6 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Is it possible to hack someone's solution after the contest? Or how can I practice hacking (besides educational rounds)?

recurze, your B solution will probably run out of time on a test like:

100000 100000
1 2 3 4 ... 99999 1

I tried to hack it during the last 2 minutes of the contest but forgot to put an endl after the 1st line, so it wasn't accepted.

My the very first hack :D

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was more concerned about the inner loop but figured it'll only run (m/n) * n times so all good but didn't realize the if condition would run O(n). I tried to port my old solution using sets to using frequency array and didn't think much.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      My own solution got TLE on test 41, lmao.

      I guess, using std::set was the best thing to do.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Any structure with support for key-value pair (i, frequency[i]) would do the trick I suppose.

»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Codeforces turning into Codechef :P

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

Here's my idea: Run a DFS from any node, let onstack[i] denote if the ith node is currently being processed, also intime[i] denote the scan time of ith node(similar to topological sort algo). Now maintain a segtree for onstack nodes only, and use RMQ query where index is the intime of nodes. Whenever we find a backedge we calculate the minimum weight edge in the cycle using the segtree. Is this idea correct? Is there an easier way?

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

    I'm not sure if this is easier, but this was my solution.

    Task E Statement:

    Given a weighted directed graph, convert it into a DAG by reversing edges. You have to minimize the maximum weight of the edges that you reverse.

    If the given graph G = (V, E) is already a DAG, then the answer is 0.

    Let us choose a value k arbitarily. Let us call an edge heavy if it's weight is greater than k, else it is light.

    If Gheavy = (V, Eheavy) forms a DAG, then we can find a topological sorting of V in Gheavy. We can then arrange edges in Elight to be consistent with the topological sort.

    We can find the minimum value of k so that Gheavy doesn't have cycles using binary search.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Are you reversing the direction of all the light edges? If so, then there might be a case where the original direction of a light edge might be a part of one cycle and after reversing it, it becomes part of other cycle.

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

        No, not all the light edges. We find a topological sort of Gheavy. Then we can ensure that all the light edges are oriented so that they are consistent with that order.

        We will only reverse those edges that are inconsistent with the order.

        This is my submission, but I'm not sure how readable it is. I don't use the terms heavy and light in the code. It also hasn't passed system tests yet.

        48354300

        EDIT: Passed system tests.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          what if the selected edges created 2 graphs, now we have 2 topological sorts what if we need to connect node from the first graph to another node from the second graph. example

          graph 1 with the visiting order
          A->B->C->D
          4  3  2  1
          graph 2 with the visiting order
          E->F->G->H
          8  7  6  5
          

          now we need to connect nodes (D, E) but order[D]<order[E] so we reverse it and we add it to the answer, but if we didn't reverse it the graph is still DAG. how we handle this case, it seems I'm missing something.

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            what if the selected edges created 2 graphs

            You mean a disjoint DAG? That's a DAG as well, and it has a topological sort as well.

            In your example, there are many valid topological orders. Let us choose any one, say "EFGHABCD".

            If we have edge between D to E, then we must have the direction as E--->D (because that is what the topological order tell us).

            If the given edge is D--->E, then we will reverse it, else we won't.

            Hope it is clear now.

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

              Thanks for your respond, yea I understand that. but my question is, In the example, we can generate 2 topological sort

              ABCD->EFGH and EFGH->ABCD
              

              let's say we have edge E->D if we selected the first topological sort then we need to reverse the edge if we selected the second topological sort then we don't need to reverse the edge. so I see that selecting the topological sort actually affect the results, but it's not clear for me why selecting arbitrary topological sort is ok, did you got what I mean?! :D

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I think I understand your question.

                The observation is correct that choosing a specific topological sort affects the final resulting Graph (after reversing edges).

                The claim is that we could use any of it. But once we choose a topological sort, we can't change that.

                I think the best way for you to get this intuition but by generating examples.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry if this is obvious but how is minimizing the maximum weight of reversed edges the same as minimizing the sum of the weights of the edges we reverse.

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        We aren't minimizing the sum.

        the same as minimizing the sum of the weights of the edges we reverse.

        I can't find this quote in my comment.

»
6 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Trash. Again.

»
6 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Pretests of E are weak. I did not get TLE for the following DFS routine:

void dfs(int u) {
  visited[u] = 1;
  for (int v : g[u]) {
    if (visited[v] == 1) { // cycle and hence do not continue }
    dfs(v); // missing visited[v] == 2 check
  }
  visited[u] = 2;
}
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Good round! Thanks for problem D!

»
6 years ago, # |
  Vote: I like it +114 Vote: I do not like it

2o50s2

contestant.

»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

If I submitted two solution for same problem and both are right then which will be judged first or second one?

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

    second. first will be skipped.

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

    I think only the last solution you've submitted that passes the pretests will be taken into account.

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

    The last solution that passed pretests will be judged.

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

    second, you got skipped verdict on first

»
6 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Yeah yeah contest was slightly unbalanced but I still think it was a good contest, especially if it's his first one. Tbh we've seen much worse here and I actually hope that den2204 will be the problemsetter for some later contests too. I mean, problemsetters also have to learn how to do it properly and I believe this contest was actually pretty good for his first one. Gratz man !

»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I'm so regretful to spend 14 minutes to think for a solution in C.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Worse. I spend around 15 min think that error between 1.0000000 and 0.9999999 is greater than 1e-6. I have to actually put these values in formula to check the error.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't have to set constant value PI that much long

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, I took it from my partner's template. Still I have a few things in my life that requires such a number.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Better than spending 19 minutes using tan instead of sin and don't know what's wrong :\

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I somehow made the same mistake lol

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    which ide u used

»
6 years ago, # |
  Vote: I like it +113 Vote: I do not like it

Solution for D (if anyone is interested)

Move the king to cell (500, 500) in less than 1000 moves. Now board is divided into 4 squares by king's column and row. At least one of these squares contains no more than 166 cells. Then move king to the corner opposite to that square by diagonal. We will get to the corner in 499 moves, but the other player will have to move all >=(666-166)=500 rooks to avoid checks. So he will not have enough moves to avoid checks.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thought I was close to getting it during the contest but your solution seems much simpler than mine :()

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh... you can move diagonally...

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

    I don't like these type of tasks, where every number needs to be so precise.

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

      In fact, it is possible to solve this problem in 998 steps with efficient implementation using the same logic, hence the number of moves is not as precise as you think.

      Moreover, 166 is not just an arbitrary number, it is rather an integer part of 666/4. Therefore you could have write 666/4 everywhere instead of 166 and get the same result without having to care about all the precise numbers.

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

        If n = num_rooks and m = board_size (m is odd), then the condition for this to be a winning strategy was that

        In the current example, it boiled down to $500 > 499$, which is just enough for this equality to hold. This is what he means by too precise.

        But almost all pigeonhole problems seem to have this property of just managing to work. So, I really enjoying this problem despite not being able to solve this.

        Open Question: Is there any winning strategy if this inequality doesn't hold?

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Maybe you could generalize it, by checking the "quadrants" of every single position, not just the center. And then choose the closest one, instead of the center.

          To me this looks like it's optimal, but still doesn't always win.

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it
»
6 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Is there no hacking for this contest? I want to hack!!

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How much time after the contest can we submit solutions again?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anybody came up with a good solution for E ?

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

    Binary search the answer, then check if there exist a cycle with all costs > mid?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Let's solve it with a binary search. We want to check that the answer is at least k. Let's remove all edges with weight less than k (we can choose any direction on this edges). Notice that if our graph contains any cycles then the answer is more than k, otherwise the answer isn't greater than k.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      and how restore answer? if we change all edges with cost lower or equal to k its not create another cycle?

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We know that there are no cycles, so we can find a topological ordering. After that we can direct our edges, which were removed, the right way

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you please explain the use of topological ordering in more detail.

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            If we rearrange our vertexes in topological order then every edge will be directed from left to right. Some edges before removal were directed from left to right, we won't change their direction, but if an edge was directed from right to left we'll change its direction.

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Honestly, task C is nothing to do with coding competition. Very hard to understand problem statements.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Devic, Can I know why?

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

      Yes, you can.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Not only because it can be googled. It's a pure geometric task which takes one line to solve in terms of code. There is no place for optimization, algorithmization, choosing the right data structure and so on.

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

    Basically it is more like D, E, F is too hard for most of Div.2 coders (including me. I ran into E for 80 min and I couldn't solve it). For them(from submission record, I think this includes both you and me), only meaningful problem was A, B, and C and one of them (C) were something like an basic geometric question for mathematics textbook or so. I agree with you — many people could write less than 5 lines to get it write after working on paper, especially when you write in python and don't really care about real number precision stuff. I think it would have been nicer if D was easier, so that more people could actually enjoy programming more.

»
6 years ago, # |
  Vote: I like it -21 Vote: I do not like it

It was impossible to hack! pretests are stronger than they suppose to be!

»
6 years ago, # |
  Vote: I like it -6 Vote: I do not like it

system testing started yes!!!

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D can be solved without being able to move the king diagonally.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Works up until test #6 :)

    Sorry this is not quite right. You have to move diagonally to the corner from the center. If you can't move diagonally, then you take one step either vertically or horizontally and terminate.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got TLE on problem B :https://codeforces.me/contest/1100/submission/48351000

How do I speed this up?

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

    Sorry, you just have wrong approach... Your works in O(nm) only

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks. I will try to get a better approach. Also, can you point out which part of the approach is wrong?

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

        You seem checking every time if he can make contest. This is waste of information. Think about the case, when he knows that he needs 1, 2, 3, 4, 5 and he got 4. He don't have to re-check everything again. Right after seeing 4, it is already known that 1, 2, 3, 5 is missing without checking again.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hi. I have modified the solution a little bit : https://codeforces.me/contest/1100/submission/48360651

          Now getting a Runtime error. How do I test this?

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Not quite sure because I'm not currently able to run or read carefully on your solution. Though I suppose the problem is that your vector val and group is both size m+1. Shouldn't one of them be size of n+1? Seems index out of range is being accessed.

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              Goddammit! Thanks. Got it. I guess this is why people allocate an array of size 10e5 and keep iterating over the fixed range. Miles to go.

              :)

»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +52 Vote: I do not like it

D is a very nice problem. Thanks.

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

Pretest for E wast too weak

»
6 years ago, # |
  Vote: I like it -32 Vote: I do not like it

The worst contest in my life

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D got WA on test 40. Is there any way to know what that test was? Here is my submission.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same problem as you. Has there been some modifications on codeforces which don't let you see the test you got wrong answer on ?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      One difficulty is that this problem is interactive, so the input kind of depends on what you program prints. So you would need initial positions + the algorithm that moves the rooks.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Never mind, I found my bug: I have

    while (kx != 500 && ky != 500)
    

    but it should be

    while (kx != 500 || ky != 500)
    

    Argh!

»
6 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Even the system tests are weak for E. (Attaching previous comment below)

Pretests of E are weak. I did not get TLE for the following DFS routine:

void dfs(int u) {
  visited[u] = 1;
  for (int v : g[u]) {
    if (visited[v] == 1) { // cycle and hence do not continue }
    dfs(v); // missing visited[v] == 2 check
  }
  visited[u] = 2;
}
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Good contest , just +1 shift was needed i.e D = E , E = F, questions were very good ! den2204

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

Now i have to wait 9 days for comeback (-_-)

»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it

My friend GreenGrape should teach den2204 how to prepare the pretests. Dear den2204, can you imagine that someone can use map to store the edges and write in the statement, that there are can be absolutely same edges, or at least include it in the pretests.

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

    I agree, my solution failed exactly because of this issue, which is a shame because the problem was pretty nice. :/

»
6 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Excuse me, I used C++17 to submit my solution during the competition, but I got Wrong answer. After I tried to use C++11 and C++14, I got Runtime error, so I want to ask this. Why? (My solution involves dividing by zero error)

int vx = (tx - x) / abs(tx - x);
int vy = (ty - y) / abs(ty - y);

C++11 Runtime error on test 6: 48359273

C++14 Runtime error on test 6: 48359354

C++17 Wrong answer on test 6: 48360585

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

    Division by zero is undefined behavior in C++

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      That is to say, the error of dividing by zero in Online Judge may get uncertain results. Is that true? I always thought that if the pointer is out of bounds or divided by zero, it will return Runtime error, thank you.

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

        Indeed, undefined behavior means at that point the program could do anything completely unexpected (i.e., "undefined"), and it usually varies depending on the computer and the compiler it's being ran on. So it doesn't make much sense to analyze WA, RE, TLE or whatever veredict whenever you're doing undefined operations. Another common one: accessing an array over its defined bounds.

        Sometimes it might be Runtime Error because that sector of memory doesn't belong to you, sometimes it actually does and it's initialized with zeros, some others it belongs to you as well but it hasn't been initialized at all (contains a random value). All of these three cases could happen running exactly the same code.

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

          Thank you for your help. I'll be more careful in programming and make fewer similar mistakes in the future. Another point is that I may not choose to use C++17 to submit the solution in the future. QAQ

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve E if to reverse each edge different controllers are used i.e. minimize the sum of cost all edges we have to reverse?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If we can solve this then same procedure can be used to solve it for directed graph with weights 1. The latter problem is minimum feedback arc set problem. This problem is known to be NP-hard.

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

    I misread the problem during the contest but I think the problem might be reduced to minimum cost Hamilton path and thus NP complete(I don’t have a proof though).

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Same thing happened with me also. I thought different controllers are required for different edges. :(

»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Here's my idea with proof for D: Greedy: Take the king to the centre. Then consider the number of rooks in each of the 4 squares formed by lines passing through the king. Look at the square with least amount of rooks. Walk the opposite way.

Proof: From the center, you can reach each corner in less than 500 moves. The square with least rooks must have number of rooks <= 666/4 by pigeon hole principle. So, there are atleast 500 rooks in the other 3 squares, combined. Now, Dasha has to move >= 500 rooks within < 500 moves, which is not possible. Hence, we are done.

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

    Ah, so that's why those numbers were chosen. Very nice.

»
6 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

DELETED

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a general question that is kind of related to this contest.

In today's contest there was a solution in my room that solved Problem B using brute force solution with complexity O(n2). The solution was supposed to give TLE on a test that has (n = m = 105) and all the numbers appearing starting from 1 and ending with 105.

I wasn't able to hack this solution due to test case size which was about 512 KB, while codeforces seems to have the upper limit for a test case on hacking set to about 265 KB. Is there a reason for this low limit? Shouldn't it be a little higher? Specially since lately most problems seem to have bounds about 2.105 rather than 105 like before, wouldn't this limit make it harder to hack solutions that fail due to TLE on large test cases?

MikeMirzayanov, perhaps you could kindly provide an answer?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For hacks with test case size greater than the limit you can send the generator for your hack.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You mean sending the generator code rather than the test case itself?

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

        Yeah, you can send the generator code instead

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

          Aha! I asked a similar question to the authors during the contest and they replied "No Comments" to it. :(

»
6 years ago, # |
  Vote: I like it +37 Vote: I do not like it

It's a shame C and E were well known. I liked those problems. (and I didn't know them, so I couldn't figure out E in time 0w0)

But nevertheless I think it is a good contest! Good job den2204

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    E well known.where? how to solve e

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Binary search on the operators and then do this

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        but the above link describes the way in which we have to add edges , how can it be applied here

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Imagine you want to check whether you can make the graph with C amount of operators.

          Well notice that every edge > C is fixed and every edge <= C can be adjusted to fit the resulting graph.

          If you can make a graph of edges with edge.c > C and find a topological sorting of the graph, then C works because you can adjust the other edges to fit the graph.

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            ok , so suppose we choose the best k .

            then how to proceed further using topolozical sorting , how to revert edges so that graph becomes acyclic , since no. of reversions need not be minimum , so we can choose any edge .

            but how ?

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              let us say we have the topological sort (I would suggest bfs based): {a,b,c,d,e}

              And then we have this edge (b,d). We would not reverse that.

              But we have another edge (c,a). It violates our toposort, so we would reverse that.

              As for implementation you can store the positions of every element in the topological sort.

»
6 years ago, # |
Rev. 3   Vote: I like it -68 Vote: I do not like it

Problem D. Correct submission: 48360170 My contest submission: 48346037 This 1 character cost me 150 rating points (-65 instead of about +90). The worst part in it, that it passed pretests when it is wrong 1 out of 4 times. This should have failed on pretests. But now I am in the same position as people who couldn't solve D. I know that I made a terrible mistake with that x instead of y, but I still have the question: Why does Codfeforces judging system is so unfair? EVERYONE who gets wrong answer on pretest have the chance to correct it, while EVERYONE who passed pretests with a wrong submission will lose ALL of the points for that problem. This is just a game of luck. In My opinion there would be 2 fair way to judge with a similar system. A: There are no pretests, only maintests. That would be much harder to make a good solution, but it would be fair. B: pretests=maintests. This would make a little easier to make a good solution, and it would be fair as well.

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

My wrong submission for D that I skipped during the competition passed system test. Paradoxically I would be first if I didn't come up with correct solution.

Wrong submission: https://codeforces.me/contest/1100/submission/48362464

»
6 years ago, # |
  Vote: I like it -19 Vote: I do not like it

I can only handle A,B,C after contest.Bt during contest time I was a great looser

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a problem that harder than F and I revise it wrong :( Actually if I make the array in size 1e6 then I can get Happy New Year :(

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wanna ask sth about E, i use the dfn[], get the time when i into a node, but others get the time they leave the node, as a result i get WA, i hope someone can explain it. Thank you so much.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i use dfs to solve,bfs get in or out can solve it,so i wanna konw why use dfs to get the into time cannot solve it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I know it's an accident but problem F really coincides with a problem in a training contest proposed by whzzt called "异或"(XOR, in English).

In that problem, you will be given a sequence of n integers a[] and m queries {li, ri, di}. For each query, you need to choose a subset of a[li, ri], compute the XOR-sum of all numbers in this subset and XOR the result by di so that the final result is maximized. You need to output the final result. Constraints: n, m <= 10^6 and 0 <= ai, di < 2^30.

Anyway, D is awesome.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, is there someone like me that easily get a binary search and Topological sorting solution to the answer of worker but failed on the construction of answer of edge?

»
6 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem A

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve e. my idea was do a dfs from a certain node. keep trace of the minimum weight . if a cycle is formed. we will reverse the edge with minimum weight and then again start dfs from the reversed node.

will it work?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No because reversing the minimum weighted edge doesn't work because reversing the wrong edge might create a new cycle for which reversing cost can be much higher.

»
6 years ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

I think there is a critical test case which was not given in the dataset of problem C. I found a user’s two accepted solution with different output. If I am not wrong then some user may not be able to pass the dataset if this test case is valid. I am giving the test case and the two solutions link below-
Test case: 3 100
First accepted solution
Output of first solution: 646.4101614984
Second accepted solution
Output for second solution: 499.9999999418
Please check den2204

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

    Thanks, added the test into testset for practice. Also I wrote to the writer about it.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Our coach 2778 (rank 448) Rating +24 1876->1900 became Candidate Master ???

»
6 years ago, # |
  Vote: I like it -31 Vote: I do not like it

Regarding tasks A-D:

A — easy, but you have to state in bold, that i can be any number. Because usually, it is 0/positive.

B — ok, but usually the number of problems would be described as n and would go first.

C — this task is the worst. As I stated in my older comment, it's pure geometry task which takes one line to resolve. There is no algorithm, no space for optimization, just geometry. I believe, that some people just googled it and I'm mad at myself, that I haven't done it also and spent the time to solve this task.

D — OK

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

    I think you did the right thing.

    I could have searched up both C and E and instantly solved them. But I didn't. I don't think you should be mad for putting an earnest effort in a contest; looking for solutions on google will never help you develop problem-solving skills. The people who just googled it are doing themselves a disservice, and I question why they even do codeforces.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -17 Vote: I do not like it

      Yeah. I wouldn't google E or any coding task during the contest. But solving C didn't help me in terms of my coding problem-solving skills. The problem is interesting because you need to see, that if you connect centers of external circles, you've got regular polygon. But it's nothing to do with programming(((. Maybe I'm more disappointed, that I've spent time on this task instead of solving D faster.

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

        Many hard CP problems are based entirely on observations instead of hard algorithms. Programming is only one part of CP.

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

.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain me how is Idleness limit calculated?

»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

den2204 will there be an editorial?

»
6 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Someone can explain me how to solve B with a time complexity of O(m) and not O(m*n) ?

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

    If you loop the O(m) elements and keep track of a frequency array you can realize at each point you can either

    1) hit a contest — O(n) update

    2) not hit a contest — O(1) update

    Seems like O(n*m) right? Nope!

    Observation: you can hit a new contest up to O(m/n) times. In total hitting a contest can only contribute (m/n)*(n) = O(m) to your complexity. So actually the overall complexity is O(m), regardless of n. This is the basic idea behind amortized analysis: looking at worst case of how much each operation contributes instead of the whole algorithm. It is very likely you already thought of this solution in contest!

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain more, how exactly can I identify these types of problems?

      And if you don't mind can you explain why my solution gives a TLE, I thought of a very similar approach.

      https://codeforces.me/contest/1100/submission/48354732

      Thanks a lot for asking, I am just getting started with CP!

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your code is O(nm) because your loop O(n) everytime you check a new element. You want to only loop O(n) when you hit a contest, which would make overall code O(m).

        for (int i = 1; i <= n; ++i) {
            if (ar[i] == 0)
                return false;
        }

        Instead of this you want to keep track of "how many cnt[i] > 0" which can be done by updating every time you add or subtract.

        My code

        How to identify these problems?. Intuitively, you know you should analyze complexity more carefully when the algorithm does a heavy operation rarely. Here is works out nicely, because the O(n) update is infrequent enough so that it is linear overall.

»
6 years ago, # |
  Vote: I like it -30 Vote: I do not like it

i am sorry if this comes across hateful, but this isn't an interdisciplinary contest. why did we get maths in this contest? i think there was a misunderstanding somewhere. can we get a rating compensation for this? doesn't seem fair ..

  • »
    »
    6 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Geometry problems are not endemic to codeforces.

    As a side note: The idea of certain math concepts as "unrelated" is actually harmful to your learning. I learned this the hard way.

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

    Some math and geometry questions fall under the umbrella of competitive programming.

    Notable math topics: Number Theory, Combinatorics, Probability.

    Notable geometry algorithms: Convex Hull, Line Sweep.

    These topics are well known, and a competitor shouldn't be surprised if they appear in a contest.

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

      sorry but i can't understand this. what has math to do with programming? they are two completely different things. why mix them together?

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

        CS is literally Math 2.0

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it -23 Vote: I do not like it

          yeah exactly and it shouldn't be this way

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it -11 Vote: I do not like it

            Speaking about rating, I'm still a beginner so I don't have a word about this but have a look at my contests result for this year:

            If I used google, I would've ended up with (3) solved instead of just 1 :P

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

            Then you aren't doing CS

            I agree with you though, pure math should stay OUT of codeforces.

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

              If you're going to complain about the problems laid out to you voluntarily and for free, perhaps it is you who should stay out of codeforces.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Things only get better with feedback. My feedback is that we should stop having rounds filled with pure math. Utilizing X obscure theorem that shows up in 2 problems in the entire history of the universe is not cool. Putting a round with 100% NT, combinatorics, is straight up bad. "Solve some IMO problems and then write them in code" is not what I'm looking for.

                If cf turned into "implement 400 lines of this lame problem statement involving checking for double checkmates in chess or something" would you still be around? If people just went around saying "if you don't like it then leave", the site would be dead instantly, because the problem authors wouldn't change a thing. In contrast, the quality of things can only improve when you provide critiques for them.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Why problem Div2 C has "Binary Search" in tags?