I_love_myself's blog

By I_love_myself, 4 months 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

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

Video solution of Div2-D/Div1-B

  • »
    »
    4 months 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.

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

    "Let dp[i][j]=true, if at the suffix i…n you can turn on exactly j sticks and get the correct sequence of digits and false otherwise. It is easy to recalculate this dynamics: we will make transitions to all possible digits (the mask at position i should be a submask of the digit)".

    Can you explain what does this mean ? striver_79

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

    Bro, I went through your solution of DIV-2 D (Nastya and Scoreboard) and using your idea i arrived at my own recursive solution without memorization, and it gives all the correct output, obviously for smaller test cases. I did try to memoize my solution but couldn't do it effectively. I have attached the link to both my recursive and recursive with memoization (again not working for reasons unknown to me), Please help me out bro.

    P.S: I did try to contact personally using codeforces messages option. Again, help out it would certainly move me a step closer to interpreting dynamic programming models.

    link to recursive solution: https://codeforces.com/contest/1341/submission/81055670

    link to recursive with memoization solution but fails to solve the purpose: https://codeforces.com/contest/1341/submission/81057944

    P.S 2: I observe your channel continuously, great explanation of BIT.

»
4 months 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"

»
4 months 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.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

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

      striver_79 I am getting a MLE on test 1, can someone please tell my what's wrong here?

      UPD : I change long long int to int and MLE disappeared, but now i am getting TLE on test 22

      My Solution

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

      Hey I used bottom up DP solution even then I am getting MLE on test case 7. Any Idea what could the reason be? 89512080

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

    Yes, here is my solution

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

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

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

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

  • »
    »
    4 months 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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

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

    According to me, during the generation process, the generator described in the question works in a way which forces a[i+1] to be x+1 if a[i]=x, unless position i+1 is already filled.

    Which leads us to the conclusion that the given array should contain several decreasing sequences (as seen from right to left).

    One way to check for the same is to start iterating from the last element and check if a[i]=a[i-1]+1, while subsequently inserting a[i] in a set and also calculating max( mx ) element till the current element.

    If at any i, a[i]!=a[i-1]+1, then the current size of the set must be equal to the value of mx (because the set must contain all natural numbers till the current element, which makes its size equal to the value of mx) otherwise the answer is NO.

    My solution: sol

  • »
    »
    2 months 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.

»
4 months 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.

  • »
    »
    4 months 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?

    • »
      »
      »
      4 months 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.

»
4 months 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.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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)

        • »
          »
          »
          »
          »
          4 months 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$$$).

          • »
            »
            »
            »
            »
            »
            4 months 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:

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

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

          • »
            »
            »
            »
            »
            »
            4 months 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)

            • »
              »
              »
              »
              »
              »
              »
              4 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months 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$$$.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months 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.)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months 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!)

»
4 months 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.com/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.

  • »
    »
    4 months 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.

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

Waited for this editorial Eagerly!

»
4 months 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.

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

    We made standard 3TL from author's solution.

    • »
      »
      »
      4 months 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})$$$
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Why geometric ?

        • »
          »
          »
          »
          »
          4 months 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.

    • »
      »
      »
      4 months 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

»
4 months 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

  • »
    »
    4 months 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'){
    
  • »
    »
    4 months 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)
    
»
4 months 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.)

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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?

»
4 months 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.com/contest/1341/submission/77830430

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

A shorter simplified solution for problem 1341C - Настя и странный генератор: 77840978

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

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

    • »
      »
      »
      4 months 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.

    • »
      »
      »
      4 months 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.

»
4 months 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

  • »
    »
    4 months 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.

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

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

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

Another solution for Div2-D/Div1-B 77915468

»
4 months 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.

  • »
    »
    4 months 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.

»
4 months 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.

»
4 months 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.

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

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

  • »
    »
    4 months 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.

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

      Thanks, got it!

    • »
      »
      »
      4 months 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?

      • »
        »
        »
        »
        4 months 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

        • »
          »
          »
          »
          »
          4 months 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

    • »
      »
      »
      4 months 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?

      • »
        »
        »
        »
        4 months 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).

»
4 months ago, # |
  Vote: I like it -16 Vote: I do not like it

what is testcase 7 for div 2 D problem

»
4 months 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 :)

»
4 months 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.

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

Problem Div1D Nastya and Time Machine is very beautiful!

»
4 months 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.

  • »
    »
    4 months 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.

»
4 months 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.

  • »
    »
    4 months 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".

»
4 months 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??

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

O(n) solution for div2-D : solution

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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=]]

    • »
      »
      »
      4 months 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

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

      nevermind..got TLE

»
4 months 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).

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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!

      • »
        »
        »
        »
        4 months 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)$$$ :/

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

    https://codeforces.com/contest/1341/submission/78243717

    can you please tell me why my solution gives TLE.

»
4 months 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.com/contest/1341/submission/77953400

  • »
    »
    4 months 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++)

»
4 months 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.com/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;
}
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Isn't Div2C supposed to be several 'ascending' sequences?

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

Can anyone please tell me why my code fails:

import java.io.*; import java.util.*; import java.lang.*;

public class codeforces_1341B { static class FastReader { BufferedReader br; StringTokenizer st;

public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
public static void main(String[] args) {
    FastReader ob = new FastReader();
    int t = ob.nextInt();
    for(int i=0;i<t;i++){
        int n =ob.nextInt(),k=ob.nextInt();
        int arr[] = new int[n];
        for (int j = 0; j <n ; j++) {
            arr[j]=ob.nextInt();
        }
        int p[] = new int[n];
        p[0]=0;
        p[1]=0;
        for (int j = 2; j <n ; j++) {
            if(arr[j-1]>arr[j-2] && arr[j]<arr[j-1]){
                p[j]=p[j-1]+1;
                //System.out.println();
            }
            else{
                p[j]=p[j-1];
            }
        }
        //p[n-1]=p[n-2];


        int max_p=Integer.MIN_VALUE;
        int start=0;
        for (int j = 0; j <=n-k ; j++) {
            if(max_p< p[j+k-1]-p[j]){
                start=j;
                max_p=p[j+k-1]-p[j];

            }
            //System.out.println(max_p+"--"+(p[j+k-1]-p[j]));
        }
        System.out.println((max_p+1)+" "+(start+1));


    }
}

}

»
4 months 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

»
4 months 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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 months 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?

»
4 months 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.

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

Can someone suggest alternative non-analytical solution for DIV2, problem A?

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

Can anyone explain the solution of div2 E, any a way to tackle such kind of questions

»
4 months 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.com/contest/1341/submission/78051371

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

Can someone help me getting the test case for which my code does not work for problem Div 2 Problem E (Natsya and Unexpected Guest) Code link https://codeforces.com/contest/1341/submission/77992324

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

why can't i apply dp in problem DIv2E, my approach is here, Can anyone please explain why Dp won't work in this problem??

»
4 months 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!

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

Can anyone explain why dp[n + 1][0] = 0; is done in the code

/**
 *    author:  tourist
 *    created: 23.04.2020 17:45:43       
**/
#include <bits/stdc++.h>

using namespace std;

vector<string> digits = {"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<string> s(n);
  vector<vector<int>> dist(n, vector<int>(10));
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    for (int d = 0; d < 10; d++) {
      for (int j = 0; j < 7; j++) {
        char x = s[i][j];
        char y = digits[d][j];
        if (x == '1' && y == '0') {
          dist[i][d] = -1;
          break;
        }
        if (x == '0' && y == '1') {
          ++dist[i][d];
        }
      }
    }
  }
  vector<vector<int>> dp(n + 1, vector<int>(k + 1));
  dp[n][0] = 1;
  for (int i = n; i > 0; i--) {
    for (int j = 0; j <= k; j++) {
      if (dp[i][j]) {
        for (int d = 0; d < 10; d++) {
          if (dist[i - 1][d] != -1 && j + dist[i - 1][d] <= k) {
            dp[i - 1][j + dist[i - 1][d]] = 1;
          }
        }
      }
    }
  }
  if (dp[0][k] == 0) {
    cout << -1 << '\n';
    return 0;
  }
  for (int i = 0; i < n; i++) {
    int now = -1;
    for (int d = 9; d >= 0; d--) {
      if (dist[i][d] != -1 && k >= dist[i][d] && dp[i + 1][k - dist[i][d]]) {
        now = d;
        k -= dist[i][d];
        break;
      }
    }
    assert(now != -1);
    cout << now;
  }
  cout << '\n';
  return 0;
}
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

lol, really.... solution of tourist and poor text description for Div2D have nothing in common.. except both are dp

»
4 months 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.

  • »
    »
    4 months 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.

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

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

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

      Thank you so much for the help!!

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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.

»
4 months 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..

»
4 months 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!

»
3 months 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;

}

  • »
    »
    3 months 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
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can u explain how can i get any weight of all grains from n(a−b) to n(a+b) ?

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

could someone be helpful and point out where i have made mistake in Div 2 D Thanks in advance https://ideone.com/qBBfH5

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

Couldn't understand the editorial for Div2-D. Can someone explain?

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

Can anyone explain Div 2E ?

»
3 months 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.

»
3 months 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'?

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

[Deleted] because I am stupid.

»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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

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

//B.Natsya and Door

include <bits/stdc++.h>

define ll long long

using namespace std; int main(){ ll t,n,k; cin>>t; while(t--){ vector v(200001,0); cin>>n>>k; vector a(n+1); for(ll i=1;i<=n;i++){ cin>>a[i]; } for(ll i=2;i<=n-1;i++){ if(a[i]>a[i-1] && a[i]>a[i+1]){ v[i]++; } } ll m=0; for(ll i=2;i<=k-1;i++){ if(v[i]==1){ m++; } } ll j=3; ll l=m,li=1; for(ll i=k;i<=n-1;i++){ if(v[j-1]==1){ m--; } if(v[i]==1){ m++; } if(m>l){ l=m,li=j-1; } j++;

          //cout<<m<<" "<<li<<endl;
      }
        cout<<l+1<<" "<<li<<endl;
}

} //Can anyone tell why there is coming TLE in my code in test case 2.

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

For Div2 E, can we use the dp (dp[i] stores the minimum time to reach ith island including the waiting time at ith island) :-

dp[i] = min(dp[i] , (dp[m]+r+g)) --> for all m before ith island(i.e. from [i-g,i], such that we can reach ith island (either directly or by going to some other island and returning back to i). Once this is calculated, we just need to loop for the last island from which we can reach our destination directly i.e. for all islands in the range [n-g,n] and choose the overall minimum. Is this approach wrong?

»
5 weeks 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

»
5 weeks 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

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

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