I_love_myself's blog

Codeforces Round #637 Editorial
By I_love_myself, 5 years ago, In English
Tutorial is loading...

Idea: I_love_myself
Solution: 77904333

Tutorial is loading...
Idea: alexX512
Solution: 77904408
Tutorial is loading...

Idea: Aleks5d
Solution: 77904455
Tutorial is loading...
Idea: I_love_myself
Solution: 77770331
Tutorial is loading...
Idea: Aleks5d
Solution: 77904646
Tutorial is loading...
Idea: Aleks5d
Solution: 77904714
Tutorial is loading...
It turned out that the author’s solution does not work correctly and so far no one, including participants, can prove that Nastya can be caught. This comments contain a lot of good thoughts. But if you can offer at least some solution to this problem, then I (and some participants) will be very happy!
Tutorial is loading...
Idea: I_love_myself
Solution: 77904971
Thanks to Holidin for help in preparing this problem.
  • Vote: I like it
  • -64
  • Vote: I do not like it

Comments Comments (137)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Video solution of Div2-D/Div1-B

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

    I couldn't understand what you said. Because my English is poor. This is a pity.

    → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

It seems that we cannot view the solution?

"You are not allowed to view the requested page"

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

Why does my submission for DIV2 D give memory limit exceeded? 77834554

Also I_love_myself can this be solved using memoisation somehow. Thanks.

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

    Yes it can be, but you need to track down the path after memoization. Storing the string while computing the recurrence will not help as that leads to TLE.

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

      I was also worried about this during the contest but could not figure out a way how to track the path and what to store in dp in recursion. Also, I have found that whenever an optimal solution of dp is to be printed there is no recursive way. Example print the longest common subsequence of two strings using recursion. I can find the length easily using recursion but cannot find a way to store the optimal path.

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

    Yes, here is my solution

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

    o(n) solution

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

Excellent round and excellent editorial. Just edit the submissions link please.

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

Can anyone explain Div2-C/Div1-A .please

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

    After taking example you can notice that you have to check that all element from 1 to end is in sequence (a[i+1]=a[i]+1). after take a[n]+1 as check again that form pos[a[n]+1] to pos[1] is in sequance and so on.

    example : 7(n=7) 6 7 5 4 1 2 3 first take position of 1 and check to the and if a[i+1]=a[i]+1 or not if not than ans is NO. after come to pos[lastnumber +1]. In our example it is 4 and here check that from this position to all right remaining is sorted or not here 4 is sort come again to 5 and than 6 and 7 is also sorted so this permutation can be Ganerated by Strange Generator and print YES

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Understanding the problem statement is the real problem, the solution is very easy once you see the pattern. The machine is the opposite of random. That is from position of 1 the array gets filled up to the end. Then select any position of next number and fill the array up to the position of 1. And so on. My submission.

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

      Don't you think this is better solution...! What i did is if v[i+1] is greater than v[i] then it has to be v[i]+1=v[i+1] else the permutation is wrong.

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

    I spent more than an hour understanding that problem statement and ended up unsolving due to poor skills in English.

    → Reply
»
5 years ago, # |
  Vote: I like it +52 Vote: I do not like it

In my opinion, solution of div1F with SQRT decomposition is significantly easier and faster to code. One can check out my code if interested.

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

    I tried to understand your solution during the round, but could not. Can you explain in more detail?

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

      It's the same on the idea level as the solution with treap.

      There are just 2 differences:

      1) Update operation is just rebuilding the pair (closed brackets vector, open brackets vector) for a segment of length $$$\sqrt{n}$$$ and also their prefix hashes (however, we need to reverse closed brackets vector).

      2) To find the answer, we need to merge information of several blocks. It's done exactly the same as with a treap, but we also need a stack, because there could be pieces of different blocks, but all of them are prefixes of aforementioned strings. If less than $$$2\sqrt{n}$$$ overall length is left, we just simulate. If it's more, we say the answer is No, because we can't eliminate all these symbols by the left and right remainder.

      So we get $$$O(n \sqrt{n})$$$ solution.

      → Reply
»
5 years ago, # |
  Vote: I like it +139 Vote: I do not like it

In D1E, I think it is incorrect that Nastya will go to meet some bee. If graph is big cycle of squares ("cycled ladder"), than, if all bees will start in one half of cycle and will use your algorithm, than Nastya can escape forever. Read also this comment.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -153 Vote: I do not like it

    Nastya will go to meet the bee relative to the path of the bee 1. And we have this test.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +138 Vote: I do not like it 
      -----------------1-----------n--N-----------------
  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
-----------------2--3-----------------------------

      Let's assume that this cycle is 1000 vertexes long and Nastya moves from n to N. Than, according to your algorithm, all bees will move one step right. It will continue forever.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 4   Vote: I like it +128 Vote: I do not like it

        Consider this interactor: 77912680 (can be run e.g. together with GCJ's interactive_runner.py). It implements your test -- a graph with 14 vertices.

        I ran this interactor together with your model solution locally

        I'm not sure the randomness on CF is exactly the same, but just in case you can hardcode v[0]=0, v[1]=2, v[2]=8.

        (I_love_myself for visibility)

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

          Yes, we know about this (huge) problem. Expect further announcements.

          It's my mistake. Short explanation on task E: graph will be planar or it will be $$$K_{3, 3}$$$ (boring case). If the graph is planar, then there is a solution that uses $$$3$$$ bees and $$$2n$$$ moves in the general case (perhaps in ours graph it can be reduced to $$$n$$$).

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

            graph will be planar or it will be $$$K_{3,3}$$$

            No, it may also contain a subdivision of $$$K_{3,3}$$$ as a subgraph, which is definitely not boring:

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

            Philae also has a construction with K5: https://codeforces.net/blog/entry/76348?#comment-609622

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

            I think that in general this problem cannot be solved in $$$O(n)$$$ queries.

            There are my thoughts:

            Consider 6-dimensional hypercube.

            $$$1$$$. On 6-dimensional hypercube with edges of same length, if there are 3 bees which fly with 1 unit per second speed, and there is Nastya who moves also with 1 unit per second speed, bees can't catch Nastya.

            Proof: Assume Nastya is in vertex $$$v$$$. To catch her, one bee (let's call it $$$k$$$) needs to fly straight to her. When it reaches middle of edge that leads to $$$v$$$, Nastya starts escaping. She has 6-1=5 vertexes to escape. But each other vertex is connected to at most 2 of these 5 vertexes (if you don't believe, look at hypercube attentively). Consider vertexes $$$i$$$, $$$j$$$ which are the nearest to two other bees. As mentioned above, these vertexes are connected with at most 4 of 5 vertexes in which Nastya can escape. Then, Nastya escapes in last 6th vertex and she is again at least half an edge away from nearest bee! So we can continue this escaping forever.

            $$$2$$$. 6-dimensional hypercube can be converted to graph that satisfies problem statement almost without losing structure.

            Proof: we need to replace each edge of hypercube with long ladder (assume it has length $$$L$$$), then each edge will be contained in some cycle. But there is a problem with vertexes: they all have degree 6. So, let's replace each vertex with this construction:

            Then, our graph will satisfy all necessary conditions and our chase is very similar to mentioned above. So, does Nastya have a way to escape forever?

            I think that maybe not forever, but very long time. I'll explain: only "losts" of speed occur in vertexes (described on picture), because moving to the opposite edge takes 10 turns, while moving to adjacent takes only 4 turns. So, in each vertex, theoretically, Nastya can lost up to $$$10-4=6=O(1)$$$ moves. So, as in my proof for continuous version, without these losses she can stay half edge away of nearest bee. So, only way to be catched is to lose $$$O(L)$$$ moves. But Nastya goes through vertex only every $$$O(L)$$$ moves, and, as I said, can lose only $$$O(1)$$$ moves each time. So, to have theoretical chances of losing, she needs to make $$$O(L)$$$ transitions from vertex to vertex. But it will take $$$O(L^2)$$$ moves!

            Finally, $$$n=64*48 + 192*(2*(L-1))$$$ (first part is vertexes of hypercube, second is edges-ladders), then $$$L=O(n)$$$. So, Nastya can escape at least $$$O(n^2)$$$ moves! (as constant is huge, it is hard to implemet in constraints $$$n<5000$$$, but it is just for asymptothics)

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

              That looks great! Also, I think it's possible to upgrade this structure so that the distances between all ladders are equal.

              At both ends of each edge of the hypercube, put the following gadget:

              (We need $$$2^6 \cdot 6 = 384$$$ such gadgets.)

              The edge of the hypercube comes from top. Notice that I replaced each face in the ladder by a pentagon to make the ants and bees to travel through the left part of this ladder.

              Now, notice that the distance between the green vertex (the end of the ladder) and each of five red vertices is exactly $$$10$$$.

              Now, here comes the trick: take all six edges incident to a single vertex of the hypercube. For each pair of edges $$$e$$$, $$$f$$$, we want to connect them by taking any pink edge at the end of $$$e$$$ and any pink edge at the end of $$$f$$$, and create a connection by merging these two pink edges into a single edge. For example:

              After all $$${6 \choose 2} = 15$$$ connections in the vertex, it's easy to see that the distance between any two green vertices is exactly $$$20$$$. Therefore, passing through each vertex takes always $$$20$$$ moves.

              With these gadgets, I believe it can be shown Nastya could escape forever -- not 100% sure as there are still some caveats about this (e.g. the bees could perhaps make up some time if they go to some vertex $$$v$$$ through some edge $$$e$$$ and then immediately retreat through this edge?). If someone wants to pick up the proof from here, it'd be great.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                ← Rev. 4   Vote: I like it +18 Vote: I do not like it

                Wow, what a beautiful gadget!) And idea of pentagons is also very good.

                I don't think that instant retreat is helpful for bees (I even assume that my version of vertexes can guarantee infinite escape). We can maintain as invariant that the shortest distance between Nastya and bees is, for example, at least $$$L/2-100$$$. (assume that L is very big number)

                So, again, to catch her, one bee (let's call it $$$k$$$) needs to fly straight to her. When it reaches distance of $$$L/2-100$$$, (that's near middle of edge that leads to $$$v$$$), Nastya starts escaping. She has 1 vertex to escape and distances between this vertex to other bees ($$$i$$$ and $$$j$$$) are at least $$$3*L/2$$$. So even if Nastya spends 100 moves on moving through vertex (and L moves on moving through edge), while $$$i$$$ and $$$j$$$ spend 0 (and L respectively) moves, they are still at least $$$3*L/2-L-100=L/2-100$$$ moves away. And if Nastya will go with shortest way, bee $$$k$$$ also cannot be closer than $$$L/2-100$$$.

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

                  Now that I thought about this even more, it could probably be possible to produce a small enough graph (that is, with $$$\le 5\,000$$$ vertices) in which Nastya can escape indefinitely.

                  Instead of the hypercube graph, we could take Robertson graph ($$$19$$$ vertices, $$$38$$$ edges) which is the smallest $$$4$$$-regular graph in which the shortest cycle has length $$$5$$$. I believe that your reasoning about the hypercube can be rewritten in terms of this graph, only that now each bee can block at most one neighbor of any vertex. If that's true, we only need four edges incident to each vertex.

                  Also, our gadgets used to join vertices would be significantly smaller now that each end of any edge has to connect with only two other vertices:

                  (Same color coding as above. Green vertex is now in distance $$$5$$$ from each red vertex.)

                  Using this construction, I believe we could create a test with only a couple thousand vertices. This is however a bit tedious (and then we would have to somehow encode the strategy programmatically), so I'll probably pass on it.

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

                  Yeah, I think $$$5000$$$ vertexes is enough to implement this much simpler counterexample. So, if we're not mistken, problem has no solution. But, despite this, problem is interesting and I would like to say thanks to I_love_myself for it.)

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

                  Yep. I implemented Robertson graph (even with my, very simple gadgets) and every solution that I tried fails not later than on test with $$$L=8$$$ (and that's only $$$608$$$ vertices!)

                  → Reply
»
5 years ago, # |
← Rev. 7   Vote: I like it +58 Vote: I do not like it

If I understand the proof for E correctly, there are some gaps in the proof:

So suppose Nastya (N) starts at vertex V with neighbours A,B,C. Also suppose that bees 1,2,3 have paths to A,B,C respectively.

Q1: What are the properties of a path? Can they self-intersect? Can they go through V? Must they be shortest paths in some sense?

Assume that N moves to A and that the cycle through V-A also goes through B.

The proof as written does:

  • The 1->A' path decreases length by 1, where A' is the vertex on 1->A before A.
  • The 3->C' path increases length by 1, because C'=V.(Assuming that the 2nd last vertex on 3->C wasn't V already.) This assumes that A' != V, i.e. the 1->A path doesn't go through V, or else we'd have A'=C'.
  • We reroute the 2->V path to 2->B', where B' is the 3rd neighbour of N=A (the one not equal to A' and V). This increases the length by at most 3-1=2. This assumes that the cycle through AV (and VB) doesn't go through A', or else we'd have A'=B'.

I don't think the proof can easily be fixed. Also, the counter example of a cyclic ladder graph (as explained in https://codeforces.net/blog/entry/76348?#comment-609545) still holds I think. The only way to potentially fix that would be to change the paths to be completely disjoint, but that might not be easy.

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

    So to summarize: the 5 cycle containing B->V->A might not be disjoint with the path for bee 1 to vertex A. Therefore the invariant that the bees are matched to three different adjacent edges of N's vertex is not maintained.

    Anyway, your questions can be answered by just looking at the model solution: 77904900. Judging by the fact that the distance array is reset for each call to find_next, disjointness of the paths is not required.

    → Reply
»
5 years ago, # |
← Rev. 6   Vote: I like it +47 Vote: I do not like it

I tried to find three disjoint paths (if possible) in E and kept getting TLE. Why were limits so tight? Most of accepted solutions exceed half of TL. Did you try to fail some slightly-too-slow solution? $$$n \leq 5000$$$ is quite a lot for $$$O(n^2)$$$ intended solution in a graph problem, especially if one might need like $$$3 \cdot n$$$ BFS's.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -33 Vote: I do not like it

    We made standard 3TL from author's solution.

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

      It's lazy to have some constant multiplier. If author's solution takes 300ms and next too slow solution takes 1 hour, don't you think TL=5s is quite reasonable? It's bad to use a formula but if you really want one, please use the geometric average of intended and slow solution, capped at 10*intended if you want.

      $$$min(10 \cdot good, \sqrt{good \cdot slow})$$$
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Why geometric ?

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

          Because we care about two ratios: good/TL and TL/slow. The geometric average makes those two equal, which is good enough.

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

      I'd like to be able to read the authors' responses to these types of questions without it being hidden due to downvotes haha

      → Reply
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Help needed in Div2D/Div1B!
My solution for Div2D/Div1B gives the correct answer for the 5th test case locally but fails when I submit the same code.
77871440
I've already commented the use of each variable in the code. In case of any doubt in the code please ask.

Does anyone know the reason why the code shows such strange behaviour?

Test case on which the code fails
10 10
0101111
0000000
1111011
1011011
1011011
1111011
0010010
1010010
1101111
0000000

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

    It happened to me when I went too far while travelling through the arrays. My computer gave me good answer while it was wrong on codeforce.

    I guess your problem is in your fonction calc : you go through strings of length 7, s and t, with :

    repn(i,10){
        if(s[i]=='1' and t[i]=='0'){
    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    You can use valgrind to double check your code. I ran your code on sample 1 with valgrind valgrind ./b-other < b1.in. It gives some error, and the root of the problem turns out to be what Vintarel said above. 

    ==52205== Conditional jump or move depends on uninitialised value(s)
==52205==    at 0x40143E: calc(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, long long) (b-other.cpp:24)
==52205==    by 0x400E52: main (b-other.cpp:47)
    → Reply
»
5 years ago, # |
  Vote: I like it +56 Vote: I do not like it

This test/hack seems to break the validator for problem Div 1B. I've submitted it as a hack for a few different solutions now and they all give 'Unexpected Verdict':

2 2
1110111
1011101

(nb: this is an anti-greedy case; the input is 02 and k=2, so the correct solution is 08.)

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

    Figured it out. The statement says:

    It is allowed that the number includes leading zeros.

    Despite this fact, none of the tests (pre or sys) include such a case, and cases that do have leading zeros (such as the hacks I submitted) crash the validator.

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

      It is surprising how none of the pretests, and even the system tests, include an anti-greedy case. No wonder so many greedy solutions passed all system tests. If greedy ain't the intended solution, shouldn't it be failed in the pretests itself? Does this also imply that the checker is wrong in any sense?

      → Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I had a shorter solution for Div2C

It checks for each element a[i], if there is no number smaller than it, for all indices < i.

https://codeforces.net/contest/1341/submission/77830430

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +28 Vote: I do not like it

A shorter simplified solution for problem 1341C - Nastya and Strange Generator: 77840978

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

    Can you explain the solution and the proof of correctness if possible?

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

      Let's say you put your 1 at some position. You can observe that all the positions after that must be 2,3,4,... till the last block. Then you need to start again with your new lowest number and all the blocks on the left. So, the final permutation will contain blocks of consecutive numbers.

      So you just need to check if the next number is +1 the current number, then you are continuing the block, or it can be smaller than the current number, which means it was already filled by some previous block.

      In simple terms, whenever you put a number somewhere, you need to put consecutive numbers starting from this position till the last empty position. So, if you put 5 somewhere, the next number must be 6 or the position must be already filled by some smaller number.

      For Eg. 5, 6, 7, 3, 4, 1, 2 => [5, 6, 7], [3, 4], [1,2] is a valid permutation. 5, 7, 6, 3, 4, 1, 2 is not.

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

      I'm not intending to prove rigorously. But here is how you can do it.

      • initially count is 1 1 1 1 1 1 ...
      • prove that next step is 1 1 1 1 ... 1 0 2 1 1 1 ...
      • prove that next steps is: 0 2 1 1 1 becomes 0 0 3 1 1, then 0 0 0 4 1 and so on.
      • until it become 1 1 1 1 1 1 ... 0 0 0 0 0 ... which is essentially same as initial count.

      (notice all of this is completely deterministic)

      Now, prove that one iteration of: from single 0 in the middle to tail of 0 and head of 1 — is actually: i, i+1, i+2, i+3, i+4 ... i+k. so general form of permutation is:

      $$$ k_m + 1, k_m+2\;\;\dots \;n-1, n \\ \dots \\ k_2+1,\; k_2+2\; \dots \;k_3 \\ k_1+1,\; k_1+2\; \dots \;k_2 \\ 1, 2, 3, 4, \dots \;k_1 $$$

      All is left is prove that code above is enough to check that permutation is in this form.

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

I have a slightly different solution for Div2-E, Div1-C.

First, lets assume we find matrix $$$G$$$ where $$$G_{ij}$$$ is set if we can start from i-th island at green light and stop at j-th at red light. We can fill this matrix in $$$m$$$ dfs over matrix $$$m*g$$$, each dfs is $$$O(mg)$$$ so in total $$$O(gm^2)$$$, and then, find how many cycles (green & red light) we need to reach each island using bfs over matrix $$$G$$$ in $$$O(m*m)$$$ time.

Key insight: if we were able to reach island $$$i$$$ in time $$$t$$$ from starting island $$$s$$$, and then during next dfs from $$$s'$$$ we also were able to reach island $$$i$$$ from $$$s'$$$ it means, that we have some common subset of G for $$$s$$$ and $$$s'$$$ that is reachable from island $$$i$$$ and time $$$t$$$. This means, if we run bfs over G and fill rows of G in order of queue of bfs and disable clearing of visit matrix of dfs, we will find solution in $$$O(mg)$$$. Why? Well, if dfs from $$$i$$$ has reached some island $$$j$$$ from island $$$i$$$ it will set $$$G_{ij}$$$, and thus we push $$$j$$$ in queue. Also, we know that it's shortest path to island $$$j$$$, because it's how bfs works. If during some of next dfs we reach already visited island $$$i$$$ at time $$$t$$$ because we didn't clear visit flags — this means that we already pushed into queue all islands reachable from current one, and all of them already has shortest cycles (green & red light) determined.

Source: 77903961

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

    I have a similar approach 77853210 but idk why it is getting WA.

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

      It doesn't look similar to neither mine solution or editorial solution.

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

Another solution for Div2-D/Div1-B 77915468

→ Reply
»
5 years ago, # |
  Vote: I like it -60 Vote: I do not like it

include

include

include<math.h>

using namespace std;

int main(){ int t; cin>>t; while(t--){ long n,a,b,c,d; cin>>n>>a>>b>>c>>d;

long p=a-b; long q=a+b; long x=c-d; long y=c+d; long flag=0;

for(int i=p;i<=q;i++){
 if(n*i<=y&&n*i>=x){
  cout<<"YES\n";
  flag=1;
  break;
 }
}

if(flag==0) cout<<"NO\n"; } return 0; }

what's wrong in this, it's giving error on 2nd testcase please answer.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    you've considered that all the grains are always having the same value of weight, which isnt correct, different grains can have different value of weights in range (a-b) to (a+b).

    PS: From next time try posting formatted code and mentioning the problem youre talking about, had to go through your code to even know what problem you were talking about.

    → Reply
»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

For Div2 C, My solution was

For any i, from 0 to n-1,

if a[i+1] — a[i] > 1 then "No"

If there is no such i, answer will be "Yes"

Can anyone prove why this is correct?

I could only think that If after number "I" we put "I+2" or more, means that we had already put "I+1", but the vacant place with max count after putting "I" must be the place next to it (which is vacant as we put "I+2" later) So, we can't have a permutation with a[i+1] — a[i] > 1.

→ Reply
»
5 years ago, # |
  Vote: I like it +49 Vote: I do not like it

Actually, in Div.1 F the persistent treap is not needed. It's enough for us to query the prefix part if we only maintain the length and hash value. See this code.

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

Can anyone explain Div 2E/1C nastya and unexpected guest?

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

    I can describe my solution, which is actually based on the same idea as above described one, just mine has additional log factor , because I use Dijkstra instead of 0-1 BFS. Limits of n and g give us opportunity to make a graph with n * g nodes, where each node describes a situation where we reached node N , currently having Gth minute of the current green light. So simply run Dijkstra on that graph, every moment we can go either previous safety island or the next safety island (of course if we can manage to do it during current green light), which are ( N -1, rem1) and ( N + 1, rem2) nodes respectively , where rem1 and rem2 are the green light current situations after doing that move. After calculating minimum time we need for each node to reach it, just check from which island you gonna do your last step to gain minimum overall time.
    Check my implementation here.

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

      Thanks, got it!

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

      How is your Dijkstra passing the test cases? I used it and getting TLE. My code is here Did you use any optimization for Dijkstra?

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

        Try not to use pairs, make your own class/struct , and define an operator for it

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

          I copied your first line "#pragma GCC optimize "-O3" to my implementation and that got it to pass (tho barely under time limit — 967 ms / 1000).

          Adding it to my template for sure! :D

          → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You traverse between a current node to the next and the previous node. Why does this occur more naturally to you than traversing from the current node to the node that can be reached from the current node in those g no. of minutes. Can you kindly explain?

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

        Well, imagine you have a standard graph. At each moment you choose one of the adjacent nodes to go. In our case, adjacent nodes are the previous and the next safety islands (with their particular modulo of g). All others can be reached through those two (in other words, you have to pass them , to reach other nodes).

        → Reply
»
5 years ago, # |
  Vote: I like it -16 Vote: I do not like it

what is testcase 7 for div 2 D problem

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

Could anyone give me a proof of the correction of 0/1BFS? I learned to use that just now but cannot understand :)

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

The questions were good. But I personally think that some problem statements were too big.

→ Reply
»
5 years ago, # |
  Vote: I like it +97 Vote: I do not like it

Problem Div1D Nastya and Time Machine is very beautiful!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Could someone kindly explain the $$$O(n\log^2n)$$$ solution for d1F? I neither understood the definition of "exactly not CBS" nor what the segment tree is storing in the editorial.

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

    If you have (] somewhere in the sequence you can never succeed. Otherwise, if you take any fully reduced string (reduce all []s) that can be a subsegment of a correct sequence, it must look something like )]]}) [<(.

    The segment tree stores for every interval in the segtree the reduced string in two parts, a prefix of ] and suffix of [. However, if it has (], no segment containing it can be reduced and we don't store anything.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Can anyone help me for finding error in my code for problem DIV2Chere. It is giving WA at tc 10. Thanks in advance.

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

    Try this case

    1
4
4 2 1 3

    The answer should be "No" instead of "Yes".

    → Reply
»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

In DIV-2 B i m not getting where my code in not working, please tell me which test case is missing??

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

O(n) solution for div2-D : solution

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

    In spite of this submission to be hacked I think the idea is correct, I implemented the same. 77847086

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      now that my idea has been hacked, I think it needs some changes..but the main idea isn't all that bad=]]

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

      I think I have an idea to solve the problem 100% correctly but rn i am too tired to implement it.. if you want, I'll let u know if i succeeded

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

      nevermind..got TLE

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

Could someone explain why the tutorial's method for div2 D is O(10nd)? For my understanding, it should be O(10nk).

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

    It is $$$O(nk)$$$, caused by

    this loop

    The greedy runs in $$$O(n)$$$ with 10 or 70 as a constant factor.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      Actually I made a test on which it's $$$O\left(\binom{n}{n/2}\right)$$$. Nice try.

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

        Finally I think I understood why my solution does not work. I used those min and max prefix sums, but actually these are not min/max values. Because there are values in between which cannot be created. Thanks for teaching me this!

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

        As proof that I understood I implemented a working version ;) 78055034

        But it is not so greedy any more, actually it looks like the dp solutions, and runs in $$$O(nk)$$$ :/

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

My code for Div 2 B works on my vs code but is showing wrong answer on cf. Can someone please help? Link to code https://codeforces.net/contest/1341/submission/77953400

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

    It is off by one error, the $$$-1$$$ is to much, just delete it: for(int i=x+1;i<x+k-1;i++)

    → Reply
»
5 years ago, # |
  Vote: I like it -28 Vote: I do not like it

for 1341C — Nastya and Strange Generator, I have a better approach. https://codeforces.net/contest/1341/submission/77968416

#include<bits/stdc++.h>
#define DEBUG(x) cout << '>' << #x << ':' << x << endl
#define f(i,n) for(int i=0;i<(n);i++)
#define fa(i,a,b) for(int i=(a);i<(b);i++)
#define far(i,a,b) for(int i=(a);i>(b);i--)
#define vect_i vector <int>
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define T int t; cin>>t; while(t--)
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define mod 1000000007
using namespace std;
int main()
{
    FIO;
    T{
        int n;
        cin>>n;
        int a[n];
        f(i,n){cin>>a[i];}
        bool possi = true;
        f(i,n-1){
            if(a[i+1]-a[i]>1){
                possi = false;
                break;
            }
        }
        cout<<(possi? "YES\n": "NO\n");
    }
    return 0;
}
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2 D is such a beautiful problem to sharp your backtracking skills.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I am just learning DFS, BFS... Tried to solve Div2 D by using DFS and got a TLE verdict. Can anyone please tell me why? 77981220

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I couldn't understand what problem C meant. the language felt complicated and twisted

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

A compact version of Div2D: https://codeforces.net/contest/1341/submission/77998256

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

Can someone tell why solution with Dijkstra doesn't work in Div2E: 77912522?

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

    Because you don't need to wait the last red light. So you should minus $$$r$$$ from your answer in this case.

    → Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Hi, can you reopen the original Editorial for Problem E? It is still make sense since there are lots of dicussion about it.

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

Can someone tell me why my code is giving tle on test case 7... in spite of using dp with memoization.

Code for D div 2 #637

https://codeforces.net/contest/1341/submission/78051371

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

Would anyone like to talk about how to maintain each prefix in a treap? Thanks!

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Help needed in Div2D/Div1B!

My submission is exceeding time limit on test case 22 although it has passed all other tests having n=2000 and k=2000.

I have used recursion with same logic as per tutorial to get O(10*n*k) time complexity. Can anyone please help me understand why is it still exceeding time limit?

This is my submission. I have already commented the use of necessary variables and functions used.

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

    It's not a $$$O(10nk)$$$ solution. In your solution, you try to find answer by recurrsion method, not dp.

    Actually for specific numbers lptr and k, the answer is unique and we only need to consider it once. But in your solution, for specific numbers lptr, there may be plenty of ways to reach the number k, and for each way you recalculate trav(lptr, k), which causes TLE.

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

    Here is my solution 78450668, you can check it out.

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

      Thank you so much for the help!!

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hi. I appreciate your help. But if you look, I used recursion with memoization which is nothing but dp. The only difference I found out between my solution compared to others is that I am using a recursion with memoization(top down approach) while other solutions are using iteration with memoization(bottom up approach) and logic being same. And after some research I found out that recursive solutions take more time than iterative, because the function calls are being done repeatedly many times, and each time some new memory is allotted for respective variables used in function which will consume some time. That is why I think my solution was not being accepted.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        You are right. What's more, recursion with memoization, which is usually called memory search, is also a technique to solve problem. It's an idea based on dfs and different from dp. You should check it out. However, it doesn't work for this task.

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

I am only able to understand editorial for 1341F — Nastya and Time Machine partially. Can anyone explain it in more detail..

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Hi, can someone tag problems that have a similar DP approach as that of D. Nastya and Scoreboard problem of this contest. I am facing a hard time with such DP problems. So for practice, if anyone has some similar problems, please tag or mention them. I came across one such on CodeChef XORSUB — XOR with Subset. Thanks!

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

1341A — Nastya and Rice solution failing attest 2 but working at test 1 ,please help

include <stdio.h>

int main() { int t; scanf("%d",&t); for(int i=1;i<=t;i++) { int n=0,a=0,b=0,c=0,d=0,total=0,flag=0; scanf("%d%d%d%d%d",&n,&a,&b,&c,&d); for(int j=a-b;j<=a+b;j++) {

total=n*j;
        if(total<=(c+d) && total>=(c-d))
        {
        flag++;
        break;
        }

    }
    if(flag==1)
        printf("Yes\n");
    else
        printf("No\n");
}
return 0;

}

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

    your logic is incorrect. You are NOT covering all possible sum_value of all the grain weights. In your case, possible sum_values are only (2 * b) by iterating it through a-b to a+b. But in fact, all possible values are (n * 2 * b) which one can get by iterating from (n * (a — b)) to (n * (a + b)). Sample example where your code will fail:

    n = 2
a = 2
b = 1
c = 5
d = 0
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please explain why in Div2 question D answer to test case 5 is is 8993391761 instead of 8999991760 which is greater and also feasible.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nastya and Time Machine

For case 2: If u has been in states (u, t+1), (u, t+2)......(u,T). How can u be in (u, t+k) in the end? Also how to calculate t'?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[Deleted] because I am stupid.

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Editorial of Div2D is bad. Next time just don't write anything.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I thought Problem D is really Tough.

Until I saw its editorial.

And realized the editorial is tougher than the problem itself! :/ xD

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

EASY EDITORIAL OF D AND PERSONAL THOUGHTS AS WHY THIS EDITORIAL SUCKS!

Personal Thoughts as Why This Editorial Sucks!

Approach for Problem D:

  1. Create dist[n][10] , where dist[i][j] represents the distance/sticks so that ith string/digit could be converted into jth digit.(0<=j<=9)

  2. Create dp[n][k] , where dp[i][j] means if its possible to use all i...n strings by using exactly k sticks. Here,

    dp[i][k]=-1 , means already explored from here, cant go further, ith string and above don't have a solution using exactly k sticks , so Go Back!

    dp[i][k]=0, means Not Yet explored this option. Go Ahead, and mark this =1 if you found answer or -1 if not.

    dp[i][k]=1 Means found ans. Keep returning back, You just need the maximum digit(0-9) from all strings, so no need to check further!

3 Now here we use Dp in Recursion, To avoid Repetition. Ex. Firstly For the 0th string we check if we can use the digit d=9 and use up all k sticks. But How we did That ? By passing the next in recursion i.e. Pass along (i+1,k-dist[0][9]) which means that now we are 1st string, and we have k-dist[0][9] units remaining. Again we start checking for d=9...1 for our 1st string.

And so the recursion keeps going...

Now , Observe that without dp we would be re-calculating these values, that weather it is possible or not to form ith string (and ahead) using exactly (whatever k value was at that point).

If at any point the Recursion gave you -1, mark it , dp[i][whatever k value was at that point)]=-1,means that its impossible to go further from here. So that if you ever happen to reach here again, Simply Say "NO" because you already have visited here once.

Also , when we find the answer (i.e. we reached nth string index and k==0) , we start adding that digit(0-9) in our answer, and return 1.

Then simply reverse the String and Print!

My Simple Yet Not So Simple Code

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried Dijkstra on DIV2E/DIV1C and get TLE on test 76

→ Reply