magnified's blog

By magnified, history, 18 months ago, In English

It has been a wild ride the final 24 hours in the preparation of this contest! And we really hope you liked the problemset we gave today!

1737A - Ela Sorting Books

Author: low_

Tutorial
Solution snippet ( low_ C++)

1737B - Ela's Fitness and the Luxury Number

Author: low_

Tutorial
Solution snippet (low_, C++)

1737C - Ela and Crickets

Author: low_

Tutorial
Solution snippet (low_, C++)

1737D - Ela and the Wiring Wizard

Author: low_

Tutorial
Solution (magnified, C++)

1737E - Ela Goes Hiking

Author: ngfam_kongu

Tutorial
Solution snippet (low_, C++)

1737F - Ela and Prime GCD

Author: blobugh

Tutorial
Solution (C++)

1737G - Ela Takes Dancing Class

Author: magnified

Tutorial
Solution (C++)
Tutorial of Dytechlab Cup 2022
  • Vote: I like it
  • +38
  • Vote: I do not like it

| Write comment?
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you have the Proof for C, that 'somehow' they can reach point (x, y) ?

    How did you come to this conclusion ?

»
18 months ago, # |
  Vote: I like it -72 Vote: I do not like it

C is the worst competitive programming problem I've ever seen.

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

    Glad that you learn something new today!

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

      learnt what? casework? man, make better problems.

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

        You've not learned it enough if you cannot do it on your own. I can never stressed enough how caseworking is so so important, even for the simplest tasks!

        A word from a guy had multiple years of exp in the workforce ^_^

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

          you stressed enough today

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

          This task has purely no sense in case of competetive programming. One might say that corner cases have really important meaning in development of larger projects but its weird and utterly useless to make a cp task based only on corner cases. Every task should have at least some creative idea and should not be straight forward annoying paperwork. I find it really sad that instead of taking critique and trying to improve you just fixed your opinion on casework being cool.

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

            I want to add that I indeed consider how hard it is to come up with good and creative problems but it is no excuse to be closed to opinion of everyone else. I really hope that next time you will be able to come with amazing problemset to everyone's liking! (Today I really enjoyed problem D but problems up to D were honestly not to my taste)

          • »
            »
            »
            »
            »
            »
            18 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It's actually a task based on immutability properties in game theory & discrete math. The idea is based on a "Grasshopper" chess game on Chess.com, and I came up with the idea with my co-workers in the brainstorming sessions and had them head scratched for the whole afternoon!

            The only case working was with "corner" cases (which is pretty direct tbh). So obviously, it's not a task "based on" corner cases.

            I think you're upset about how the problem slows you down. But hey, ppl wonder what if they had done better all the time. =)

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
18 months ago, # |
  Vote: I like it +9 Vote: I do not like it

another day to be sad

»
18 months ago, # |
  Vote: I like it -116 Vote: I do not like it
And we really hope you liked the problemset we gave today!

No, we didn't. Please, don't make contests again.

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

why are all the critiquing comments removed?

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

    we aren't on web3 yet

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

    Someone removed the level 1 comment, and then brought the whole subthread down to the void :D

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

      The person who deleted the comment probably prevented long comments war thread XD so it might be for a good reason

»
18 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Is there any efficient way to count the number of [n] partitions with each part <k elements? What I am thinking for E is that:

Conditions for the i-th ant to win:

  1. For the i-th ant (not the last one), it must be going to the left initially. (heading right initially will always be eaten by some ants to the right)
  2. The i-th ant then must eat everything to its left, resulting in an ant with the weight i (because before it encounters any ants at position >i, it must encounter all ants at position < i)
  3. We need ants to the right all to have weight < i. Notice that every ant with an initial direction to the left will form a new ant, and its size is given by the number of ants going to the right on its left + 1. => count ways to partition n elements so that each part has <k elements. But I stuck on that for >1h.
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I was also thinking along these lines, but this misses a crucial point. We don't need the ant $$$i$$$ to be bigger than all of the ants going to the right on its left because ant $$$i$$$ will get bigger each time it eats a new one! For example, if the ant has size $$$3$$$ and it's facing a series of ants of sizes $$$2, 4, 5, 10$$$, it will end up surviving.

    So the relevant combinatorial question isn't the number of ordered partitions of $$$[n]$$$ with each part containing $$$\leq k$$$ elements, but rather something like "in $$$n-k$$$-bit binary string, what's the probability there's a run of length at least $$$r+k$$$ starting at position $$$r$$$"?

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

      OMG you are right... I missed that observation :-(

»
18 months ago, # |
Rev. 3   Vote: I like it -16 Vote: I do not like it

my head sucks :).

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is probably due to floating point inaccuracy for large numbers.

    From the tutorial: Also note that, since large numbers can cause inaccuracies in floating point computation, we should use binary search to find the floor-value of a square root, instead of using the sqrt function in any language.

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

      but the error is not happening in pc.

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

        Probably your Python environment or version or something is different from what Codeforces uses in the judge environment. It's possible that your PC would fail a test case that succeeds on Codeforces.

        In general, you need to be aware of such floating-point in accuracies for large numbers.

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

          yes i used integer sqrt.. it is accepted now.

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

        Accept the flaw and learn from it. Never repeat it.

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

Sad to use sqrt instead of sqrtl in problem b ಥ⁠‿⁠ಥ

»
18 months ago, # |
  Vote: I like it +26 Vote: I do not like it

huge gap between C and D

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B: How come ((ll)sqrt(x) * (ll)sqrt(x)) be greater than x?
AC: 175053872 WA: 175045921

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

    Floating number precision loss.

    Maybe you could use sqrtl(x) to get $$$\lfloor\sqrt x\rfloor$$$

»
18 months ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

we can prove that there is always a way to line up 2 pieces on the same-colored squares with the target square diagonally.

[but we won't]

If you can prove it, do it...

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't understand the equation of problem B how did we get it ? , can any one explain?

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (1 2 3) (4 6 8)(9 12 15)(16,20,24) and so on, if x=15, sqrt(15)=3 ans = 3*3 =9 =>(1,2,3,,4,6,8,,9,12,15)

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This just an example what I mean is how we did conclude it

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

        Let's say that $$$\left \lfloor{\sqrt{x}}\right \rfloor=y.$$$ That means that $$$y \leq \sqrt{x}<y+1$$$ so $$$y^2 \leq x < (y+1)^2 = y^2+2y+1$$$. Obviously the smallest valid value of $$$x$$$ divisible by $$$y$$$ is $$$y^2$$$, the next one is is $$$y \cdot (y+1)$$$, then the next one is $$$y \cdot (y+2)$$$, and $$$y \cdot (y+3)$$$ is too large.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain D test case 1? Why after change, time cost from Machine 1 to 8 is 6?

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

    Disconnects $$$(2, 3)$$$ and connects $$$(2, 8)$$$.

    graph

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is this &mdash in solution code of E ?

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably, after reading the editorial, it means minus"-". I don't know what's wrong but in some places "-" might be changed into "&mdash".

»
18 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Difficult Round

»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone please explain the 2nd case in the editorial of D Ela and the Wiring Wizard

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

    If you try to find the answer for the sample test case #3 in the D, you will find that the 1st case in the solution is not able to find the correct solution.

    In this test case, the correct solution would be to -> take the edge connecting vertex 2, 5 -> connect it to 2, 6 take the now edge connecting vertex 2, 6 -> connect it to 2, 4 take the now edge connecting vertex 2, 4 -> connect it to 4, 4 take the now self loop edge connecting vertex 4, 4 -> connect it to 4, 7 take the now edge connecting 4,7 -> connect it to 4, 1 take the now edge connecting 4, 1 -> connect it to 1, 8

    The answer -> (22 * 6 + 22) = 154

    So what happened is we saw that the edge connecting the vertex 2, 5 might just be what we need for the best possible path but if we try the case 1 that we thought of then the total time won't be the shortest possible we could get. We could instead just take one of the vertex and connect it an intermediate vertex ( a vertex that is present in the shortest path from 1 to n). After this, we create a self loop on this intermediate vertex. (Total time up till now -> dist[u][x] + 1

    Now we can just expand this self loop on both sides -> dist[x][1] + dist[x][n]

    Now one last time of actually travelling this edge -> 1

    total time => (dist[u][x] + 1 + dist[x][1] + dist[x][n] + 1 ) * w

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I get that by applying the formula for case 1, the answer would be suboptimal. But how do you apply the case 1 to sample test case 3 in the graph? How to connect both 1 to u and v to n for the edge between (2,5)?

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

        1 to u will be — (1,7,6,5) and v to n will be (2,5,6,4,8) The total time become (3+4+1)*22 equal 176

        Which is suboptimal so we go for the case 2 and get better answer

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

          That's fine what I want to know is how you break the edge. If you break it the way you mentioned above, that would cost 65 each time (since the edge between 1 and 7 costs 65). Do you get what I want to convey?

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

            We break the edge between u and v. In the case I described, we break the edge b/w 2,5 and connect it to 2,6, then 2,7, then 2,1. Its cost becomes — dist[1][5] * 22

            Then we take the edge of 2,1 break it to join it to 1,5 then 1,6 then 1,4 then 1,8 Cost becomes dist[2][8] * 22

            This is.for case 1, for case 2 also we start by breaking the edge between 2,5 but once the u reaches an intermediate vertex we like we create self loop and expand both sides

            • »
              »
              »
              »
              »
              »
              »
              18 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Firstly, you broke the edge between (2,5) so 2 and 5 are no longer connected. Then later on you connected 1 to 5 directly by breaking the edge between (2,1). How is it possible since 5 is not connected to 2 anymore?

              • »
                »
                »
                »
                »
                »
                »
                »
                18 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Yeah, you are right. It is not possible like this Good find.

                Though it is still possible to achieve the same results, I will first break (2,5) to make self loop on (2,2) than expand one side to 1 and the other to 8

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  18 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I think this isn't possible as well. That's because the self loop on (2,2) can't be expanded as there is no edge connecting to 2 other than the (2,5) which we broke.

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

                  oh sorry,. i didnt see the graph again before replying. it should be self loop on (5,5) .i misremembered the graph

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help clarify what the second and third cases for problem C are talking about and why they work? Thanks in advance.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does the solution say that $$$[1,2 * i - 1]$$$ and $$$[2 * i,n]$$$ are independent in problem E?

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why __int128 CE in C++14 and AC on C++ 20?

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

    GNU G++14 on codeforces generates 32 bit executables, apparently. I don't think __int128 is available on 32 bit targets yet.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How did the author write such an obscure topic?

»
18 months ago, # |
  Vote: I like it +16 Vote: I do not like it

In D how do you show the following things? 1. It's never optimal to touch any edge apart from the one that we are trying to put on 1-n spot? 2. Lower bounds provided are always feasible? Even the simplest case where you never 'merge' ends of the edge that is being moved. How to prove that the path "will not break" or something along the process? This doesn't seem very hard but I have some trouble finding clean proof.

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

    maybe i have an answer to Q1.

    suppose shortest path a->c is a->b->c, WLOG, let dist(a,b) < dist(b,c) (cases with more edges are similar). so cost is dist(a,b)+dist(b,c)

    however we can rewire a->b to get a->c, then total cost is 2*dist(a,b) which is less than previous one. base on this, we can alway reduce the optimal answer to only one edge.

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, that's clear. I'm rather asking about cases like we rewire other edge(s) to deliver "our" edge to 1 — n faster (than we have only one edge from 1 to n in the end).

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

        oh, sorry for misunderstanding

        so in general the answer is (number of rewiring/movement) * (edge weight), and now you are concerning about reducing the first term instead of simply use floyd shortest path, right?

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

          Roughly yes. And i can see some "sketch" of the proof of that, but there are so many (nested) cases etc. that it doesn't convince me at all. I assume there should exist something concise.

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

    If its optimal to use any other edge then this is not the edge which will us give us optimal answer and this only happens when there is an edge with weight smaller than current one in this path. I wrote a proof to a similar question by my friend so I am copy pasting it here.

    Question
    Proof
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      I don't think you answered my question. Have you seen discussion above? I'm not concerning about the fact that optimal solution consists of exactly one edge, but rather whether fixed edge could possibly be delivered to 1-n faster using other rewires.

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I guess only you read the "Question" part. My proof did contain it even tho he didn't ask for it. I will be more specific this time.

        Lets say if there was a segment $$${a} - {b} - {c}$$$ (possibly $$${a} = {c}$$$) in some path after one operation we can "contract" it and make it $$${a} - {c}$$$. It doesn't induce any new paths but rather contract already existing ones. So we can say final edge is just a contraction of one of initial paths from $$${1}$$$ to $$${n}$$$. Note this is true for any path not necessary shortest.

        But what's the Optimal way to contract a path? that's what I did in my proof. You only need one edge that has minimum weight in that particular path.


        Details of the first paragraph of previous comment.

        I was asleep, this reply is a bit late.

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

        If I understood correcty,

        You say that if we can wire our current edge from 1 to n faster by using another smaller weighted edge, why don't we use that edge to speed up our "rewiring"

        And badlad says that if we can use some another smaller weighted edge to speed up our "rewiring" process, there is no point to use our current edge to wire 1 and n

        Because if we can use some edge to speed up our rewiring, that means this edge is in the same path as our current edge and its weight is smaller than our current edge

        And if we have another smaller weighted edge in a path that contains our current edge, there is no point trying to rewire our current edge (proof is given by badlad in the first reply)

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

    For the final edge $$$f$$$ which will be between $$$1-n$$$ at the end, I think we can prove that using it only is optimal as follows:

    When we re-wire we have $$$2$$$ options:

    1. Create a self loop, this does not shorten any existing path or add any new path in the equivalent unweighted graph (in fact it can disconnect existing paths). So, it does not make sense to use that except with $$$f$$$ to transport it from a place to place.
    2. Make edge $$$e_1$$$ with terminal nodes $$$u$$$ and $$$v$$$ bypass edge $$$e_2$$$ with terminals $$$v$$$ and $$$w$$$ (so that $$$e_1$$$ now has terminals $$$u$$$ and $$$w$$$). If $$$f$$$ was not connected to node $$$1$$$ from the beginning, then at least one bypass is needed to connect it to node $$$1$$$, same with node $$$n$$$. For any edge $$$e$$$ that is bypassed by $$$f$$$, if $$$e$$$ already made $$$x$$$ bypasses earlier, then we could have not done these $$$x$$$ bypasses and make $$$f$$$ do $$$x+1$$$ bypasses instead. The same logic can be followed to prove the same for any edge bypassed by $$$e$$$ and made some bypasses earlier.

    Conclusion of point $$$2$$$:

    We can always achieve a bypasses count by $$$f$$$ alone no greater than when there are other edges as well contributing in the bypasses count.

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      More elaboration on why we can use only $$$1$$$ edge in all the re-wires:

      Observe that re-wiring works bidirectionally, e.g., for $$$e_1(u-v)$$$ and $$$e_2(v-w)$$$, we can either use $$$e_1$$$ or $$$e_2$$$ to achieve the same new end points $$$u-w$$$. This means that whenever we make $$$2$$$ rewires with different edges sharing an end-point, e.g., for $$$e_1(u-v)$$$, $$$e_2(v-w)$$$, and $$$e_3(w-x)$$$:

      1. $$$1^{st}$$$ re-wire: $$$e_1(u-w)$$$, $$$e_3(w-x)$$$
      2. $$$2^{nd}$$$ re-wire: $$$e_3(u-x)$$$

      then we could have always chosen the cheapest edge to perform both the re-wires while achieving the same new end points. e.g., if the cheapest is $$$e_2$$$, the sequence of re-wires could be:

      1. $$$1^{st}$$$ re-wire: $$$e_2(u-w)$$$, $$$e_3(w-x)$$$
      2. $$$2^{nd}$$$ re-wire: $$$e_2(u-x)$$$
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I don't have an answer for you but I agree that these are points that should be addressed more carefully. For example, it is not true that for an arbitrary edge $$$e$$$, the cheapest way to move this edge to go between $$$1$$$ and $$$n$$$ involves operations with $$$e$$$ only, Intuitively, the problem might be okay still because for these cases, any helper edges which are moved just end up being better choices as the final edge. (That is not a proof, of course.)

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

      The point is, if the rewiring could be sped up by using some other edgeto speed it up, our choice of the optimal edge to place between 1 and n is wrong, which is why this method works since it takes the minimum of all possible edges.

      To state it more mathematically, if an edge e can be placed faster between 1 and n by using an intermediate edge f to speed up the process, edge f is a bettee choice to place between 1 and n

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

      isn't it a true for a path though? If its initial length was k no matter how you reduce it to "the final one edge" its cost will always be sum of k terms. So the best you can do is just pick one edge that has minimum weight.

      Or am I assuming something wrong here?

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        why downvotes? if you can why explain why I am wrong then please do I want to know.

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A bit late but you can prove it like this:

    Consider

    $$$\min(\min_x(dist(1, x) + dist(n, x) + dist(x, edge) + 1), dist(1, edge) + dist(n, edge))$$$

    for a fixed edge. You can prove that with any operation it decreases by at most 1 with a small case work.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hi low_ sorry for the ping.

Can u pls exaplin how u came up with the idea of problem c.Though the observaton was quite simple but it took me a long time to observe it.So want to know how u thought it in the first place.So that from next time I could try that way too.

Sorry for bad english.

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I put 3 pawns on the chessboard and move around like crickets and see the pattern.

    The idea I got from grasshopper chess variants, which you can find on chess.com

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the reply.Really enjoyed the contest.

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And after finding some pattern on a chessboard, you thought, oh cool, this will make a nice competitive programming problem? It has absolutely nothing related with competitive programming.

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What do you know abt competitive programming? XD

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

          I don't know much, but I know you're not a good problem setter.

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

            well if C isn't related to competitive programming, then I don't know what is.

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

            Well I can't ever argue with unranked ppl, can I? XD

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

in problem D, "We can prove that it is always better to make an edge directly connect 1 and N."

Here is the proof if anyone’s not getting the hang of it.

  • Assume the shortest path between $$$1$$$ to $$$N$$$ after rewiring has more than one edge.
  • Let's say the length of the path is $$$L$$$.
  • Now take the lightest edge (with weight $$$W$$$) among all the edges on this path and rewire the whole path using this edge only. It will have the cost $$$(L-1) * W$$$.
  • Which will be less or equal sum of all L weights on the original path.
  • By contradiction We can say our assumption is false.
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1737/submission/175080288 same code gets ac when I used isqrt when sqrt used gives a wa on test 4 dont know why https://codeforces.com/contest/1737/submission/175044806

»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

We can prove that it is always better to make an edge directly connect 1 and n.

Can someone give proof of that? (Problem D)

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

    Imagine if you have a sequence of edges in the path, lets say it is $$${1}, {2}, {3}... {k}$$$ for simplicity if the minimum weight among $$$w_{1}, w_{2}, w_{3}... w_{k}$$$ is $$$x$$$ then $$$w_{1} + w_{2} + w_{3}... + w_{k} >= x * k$$$ and cost of rewiring everything such that 1 and n are connect by edge with weight $$$x$$$ is $$$x * (k - 1)$$$ so you can always achieve $$$x * k$$$ by rewiring so it never hurts. Note this is true for any path, since we are checking all the edges the path which gives optimal answer will also be included.

»
18 months ago, # |
  Vote: I like it -40 Vote: I do not like it

Trash problem. Coordinators should survey authors better. We've reached new peaks of stupidity.

Marinush

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

    little boy crying how cute

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

      Thank you for floppily bullying me. I will speedrun the days until you correct your paths, stop feeling so superior. Apologies if this does not fit your view.

      Marinush

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In B you should not write a new sqrt if you use c++ you can use

int r2 = sqrtl(r)

then r2 will be the floor of sqrt r

be careful to use sqrtl, not sqrt because the input is long long not int

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

    didnot understood why should we use sqrtl

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sqrt is more accurate for int because its return double

      but sqrtl returns a long double and it's better to use this for accuracy and don't get overflow

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when i used sqrt i got wa , but when i used sqrtl i got correct . why i got wrong with sqrt. submission :- 175144961

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

Proof for $$$C$$$:

Assuming that the central cell is labeled $$$X$$$ and the other two cells are labeled $$$O$$$, for the following initial configuration (and equivalently for the other three valid configurations as well):

We can cover the following cells (A similar pattern can be achieved vertically as well):

After analyzing this pattern we can see that all white diagonals (equivalently all white cells) can be covered, and all black cells which are in column similar in parity as $$$X$$$'s initial column (and equivalently rows similar in parity to $$$X$$$'s initial row) can be covered. Since each time we move 2 rows or 2 columns, black cells in columns (and equivalently rows) with different parity are already unreachable by definition.

However, the previous pattern requires that at least one of $$$X$$$'s initial row and column to be neither $$$1$$$ nor $$$n$$$ (for the initial $$$X$$$ to not be in a corner), otherwise the previous pattern cannot be achieved and only the initial row and column of $$$X$$$ can be covered.

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

Can anyone please explain test case 3 of problem D? ok nvm found it above

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell why it is optimal to directly connect 1 to n and how we thought of using 1 weight shortest path .please help

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the need of creating the self look in problem D

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

Can anyone tell me how to solve C[1400-1600 rated Problems] faster? What I have observed is

Spoiler
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone explain 3rd sample test case for problem D