### I_love_myself's blog

By I_love_myself, 15 months ago,

Idea: I_love_myself
Solution: 77904333

Idea: alexX512
Solution: 77904408

Idea: Aleks5d
Solution: 77904455
Idea: I_love_myself
Solution: 77770331
Idea: Aleks5d
Solution: 77904646
Idea: Aleks5d
Solution: 77904714
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!
Idea: I_love_myself
Solution: 77904971
Thanks to Holidin for help in preparing this problem.

• -64

 » 15 months ago, # |   0 Video solution of Div2-D/Div1-B
•  » » 15 months ago, # ^ |   0 I couldn't understand what you said. Because my English is poor. This is a pity.
•  » » 15 months ago, # ^ |   0 "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
•  » » 14 months ago, # ^ |   0 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/81055670link to recursive with memoization solution but fails to solve the purpose: https://codeforces.com/contest/1341/submission/81057944P.S 2: I observe your channel continuously, great explanation of BIT.
 » 15 months ago, # |   +4 It seems that we cannot view the solution?"You are not allowed to view the requested page"
•  » » 15 months ago, # ^ |   0 yep same error is being faced by me
•  » » 15 months ago, # ^ |   +8 Fixed
 » 15 months ago, # |   0 Why does my submission for DIV2 D give memory limit exceeded? 77834554Also I_love_myself can this be solved using memoisation somehow. Thanks.
•  » » 15 months ago, # ^ |   +4 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.
•  » » » 15 months ago, # ^ |   0 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.
•  » » » » 15 months ago, # ^ | ← Rev. 3 →   -13 I have made a video on the same, checkout the first comment, might help you.
•  » » » » 15 months ago, # ^ |   +1 It is possible. I did it recursively. You can check out my submission if it helps :)
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   0 My solution using recursion and memorization.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 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 22My Solution
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 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
•  » » 15 months ago, # ^ |   0 Yes, here is my solution
•  » » » 15 months ago, # ^ |   0 Yash on fire.
•  » » 15 months ago, # ^ |   0 o(n) solution
 » 15 months ago, # |   0 Excellent round and excellent editorial. Just edit the submissions link please.
 » 15 months ago, # |   0 Can anyone explain Div2-C/Div1-A .please
•  » » 15 months ago, # ^ | ← Rev. 3 →   +7 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
•  » » 15 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » 15 months ago, # ^ |   0 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
•  » » 14 months ago, # ^ |   0 I spent more than an hour understanding that problem statement and ended up unsolving due to poor skills in English.
 » 15 months ago, # |   +52 In my opinion, solution of div1F with SQRT decomposition is significantly easier and faster to code. One can check out my code if interested.
•  » » 15 months ago, # ^ |   +4 I tried to understand your solution during the round, but could not. Can you explain in more detail?
•  » » » 15 months ago, # ^ | ← Rev. 3 →   +64 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.
 » 15 months ago, # |   +139 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.
•  » » 15 months ago, # ^ |   -153 Nastya will go to meet the bee relative to the path of the bee 1. And we have this test.
•  » » » 15 months ago, # ^ |   +138 -----------------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.
•  » » » » 15 months ago, # ^ | ← Rev. 4 →   +128 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 locallyjudge: Judge init: 1 3 9 judge: Me init: 4 judge: Judge turn 1: 6 10 8 judge: Me turn 1: 12 judge: Judge turn 2: 10 3 4 judge: Me turn 2: 13 judge: Judge turn 3: 3 2 12 judge: Me turn 3: 11 judge: Judge turn 4: 2 7 13 judge: Me turn 4: 5 judge: Judge turn 5: 7 14 11 judge: Me turn 5: 9 judge: Judge turn 6: 14 1 5 judge: Me turn 6: 8 judge: Judge turn 7: 1 6 9 judge: Me turn 7: 4 judge: Judge turn 8: 6 10 8 judge: Me turn 8: 12 judge: Judge turn 9: 10 3 4 judge: Me turn 9: 13 judge: Judge turn 10: 3 2 12 judge: Me turn 10: 11 judge: Judge turn 11: 2 7 13 judge: Me turn 11: 5 judge: Judge turn 12: 7 14 11 judge: Me turn 12: 9 judge: Judge turn 13: 14 1 5 judge: Me turn 13: 8 judge: Judge turn 14: 1 6 9 judge: Me turn 14: 4 judge: Judge turn 15: 6 10 8 judge: Me turn 15: 12 judge: interact2: interact2.cpp:90: int main(int, char**): Assertion turn <= V' failed. 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)
•  » » » » » 15 months ago, # ^ |   +27 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$).
•  » » » » » » 15 months ago, # ^ |   +51 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:
•  » » » » » » » 15 months ago, # ^ |   -27 Oh... I will try to solve this problem too...
•  » » » » » » » » 15 months ago, # ^ |   +53 XD
•  » » » » » » » » » 15 months ago, # ^ |   +89 :(
•  » » » » » » » » » 15 months ago, # ^ |   +268 Hey, don't worry, shit happens. For sure it'll be better next time ;)
•  » » » » » » 15 months ago, # ^ |   +32 Philae also has a construction with K5: https://codeforces.com/blog/entry/76348?#comment-609622
•  » » » » » » 15 months ago, # ^ |   +114 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)
•  » » » » » » » 15 months ago, # ^ |   +83 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.
•  » » » » » » » » 15 months ago, # ^ | ← Rev. 4 →   +18 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$.
•  » » » » » » » » » 15 months ago, # ^ |   +16 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.
•  » » » » » » » » » 15 months ago, # ^ |   +56 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.)
•  » » » » » » » » » 15 months ago, # ^ |   +28 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!)
 » 15 months ago, # | ← Rev. 7 →   +58 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.
•  » » 15 months ago, # ^ |   +34 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.
 » 15 months ago, # |   0 Waited for this editorial Eagerly!
 » 15 months ago, # | ← Rev. 6 →   +47 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.
•  » » 15 months ago, # ^ |   -33 We made standard 3TL from author's solution.
•  » » » 15 months ago, # ^ |   +86 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})$
•  » » » » 15 months ago, # ^ |   +8 Why geometric ?
•  » » » » » 15 months ago, # ^ |   +44 Because we care about two ratios: good/TL and TL/slow. The geometric average makes those two equal, which is good enough.
•  » » » 15 months ago, # ^ |   +33 I'd like to be able to read the authors' responses to these types of questions without it being hidden due to downvotes haha
 » 15 months ago, # |   -10 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
•  » » 15 months ago, # ^ | ← Rev. 2 →   +3 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'){ 
•  » » » 15 months ago, # ^ |   0 Help required in this solution Solution
•  » » » » 15 months ago, # ^ |   0 No
•  » » 15 months ago, # ^ | ← Rev. 2 →   +8 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, std::allocator >&, long long) (b-other.cpp:24) ==52205== by 0x400E52: main (b-other.cpp:47) 
 » 15 months ago, # |   +56 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.)
•  » » 15 months ago, # ^ |   +83 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.
•  » » » 15 months ago, # ^ |   +10 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?
 » 15 months ago, # |   +11 I had a shorter solution for Div2CIt 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
 » 15 months ago, # | ← Rev. 3 →   +28 A shorter simplified solution for problem 1341C - Nastya and Strange Generator: 77840978
•  » » 15 months ago, # ^ |   0 Can you explain the solution and the proof of correctness if possible?
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 15 months ago, # ^ |   0 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.
 » 15 months ago, # |   0 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
•  » » 15 months ago, # ^ |   0 I have a similar approach 77853210 but idk why it is getting WA.
•  » » » 15 months ago, # ^ |   0 It doesn't look similar to neither mine solution or editorial solution.
 » 15 months ago, # |   0 Another solution for Div2-D/Div1-B 77915468
»
15 months ago, # |
-60

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

•  » » 15 months ago, # ^ | ← Rev. 2 →   +9 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.
 » 15 months ago, # |   +17 For Div2 C, My solution wasFor 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.
•  » » 15 months ago, # ^ |   0 You can check Here
•  » » 15 months ago, # ^ |   -16 Lol, seriously? You made a solution, without knowing the correct logic? Seems fishy!
•  » » 15 months ago, # ^ |   0 I have a different approach with n*log(n) time solution
 » 15 months ago, # |   +49 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.
 » 15 months ago, # |   0 Can anyone explain Div 2E/1C nastya and unexpected guest?
•  » » 15 months ago, # ^ |   +6 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.
•  » » » 15 months ago, # ^ |   0 Thanks, got it!
•  » » » 15 months ago, # ^ |   0 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?
•  » » » » 15 months ago, # ^ |   0 Try not to use pairs, make your own class/struct , and define an operator for it
•  » » » » » 15 months ago, # ^ |   0 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
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 15 months ago, # ^ |   0 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).
 » 15 months ago, # |   -16 what is testcase 7 for div 2 D problem
 » 15 months ago, # |   0 Could anyone give me a proof of the correction of 0/1BFS? I learned to use that just now but cannot understand :)
•  » » 15 months ago, # ^ | ← Rev. 2 →   +3 This is a better explanation: https://codeforces.com/blog/entry/22276
•  » » » 15 months ago, # ^ |   0 It's a nice tutorial.Thank you!
 » 15 months ago, # |   +2 The questions were good. But I personally think that some problem statements were too big.
 » 15 months ago, # |   +97 Problem Div1D Nastya and Time Machine is very beautiful!
 » 15 months ago, # | ← Rev. 2 →   +16 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.
•  » » 15 months ago, # ^ |   +16 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.
•  » » » 15 months ago, # ^ |   0 makes sense, thanks!
 » 15 months ago, # | ← Rev. 2 →   -8 Can anyone help me for finding error in my code for problem DIV2Chere. It is giving WA at tc 10. Thanks in advance.
•  » » 15 months ago, # ^ |   +9 Try this case 1 4 4 2 1 3 The answer should be "No" instead of "Yes".
 » 15 months ago, # |   -11 In DIV-2 B i m not getting where my code in not working, please tell me which test case is missing??
 » 15 months ago, # | ← Rev. 3 →   0 O(n) solution for div2-D : solution
•  » » 15 months ago, # ^ |   0 In spite of this submission to be hacked I think the idea is correct, I implemented the same. 77847086
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 now that my idea has been hacked, I think it needs some changes..but the main idea isn't all that bad=]]
•  » » » 15 months ago, # ^ |   0 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
•  » » » 15 months ago, # ^ |   0 nevermind..got TLE
•  » » » » 15 months ago, # ^ |   0 I made one, see 78055034
•  » » » » » 15 months ago, # ^ |   0 well done, but now you have O(nk) ..basically the solution from the editorial :))
•  » » » » » 15 months ago, # ^ |   0 this is my attempt
 » 15 months ago, # |   0 Could someone explain why the tutorial's method for div2 D is O(10nd)? For my understanding, it should be O(10nk).
•  » » 15 months ago, # ^ |   0 It is $O(nk)$, caused by this loop 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; } } } } } The greedy runs in $O(n)$ with 10 or 70 as a constant factor.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +11 Actually I made a test on which it's $O\left(\binom{n}{n/2}\right)$. Nice try.
•  » » » » 15 months ago, # ^ |   0 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!
•  » » » » 15 months ago, # ^ |   0 As proof that I understood I implemented a working version ;) 78055034But it is not so greedy any more, actually it looks like the dp solutions, and runs in $O(nk)$ :/
•  » » 15 months ago, # ^ |   0 https://codeforces.com/contest/1341/submission/78243717can you please tell me why my solution gives TLE.
 » 15 months ago, # |   0 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
•  » » 15 months ago, # ^ |   0 It is off by one error, the $-1$ is to much, just delete it: for(int i=x+1;i
 » 15 months ago, # |   -28 for 1341C — Nastya and Strange Generator, I have a better approach. https://codeforces.com/contest/1341/submission/77968416 #include #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 #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; } 
 » 15 months ago, # |   0 Div2 D is such a beautiful problem to sharp your backtracking skills.
•  » » 15 months ago, # ^ |   0 what is backtracking skill...i am new to programming can you please tell
•  » » » 15 months ago, # ^ |   0
•  » » » » 15 months ago, # ^ |   0 thank you so much
 » 15 months ago, # |   0 Isn't Div2C supposed to be several 'ascending' sequences?
 » 15 months ago, # |   -40 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;iarr[j-2] && arr[j]
 » 15 months ago, # | ← Rev. 2 →   0 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
 » 15 months ago, # |   +14 I couldn't understand what problem C meant. the language felt complicated and twisted
 » 15 months ago, # |   0 A compact version of Div2D: https://codeforces.com/contest/1341/submission/77998256
 » 15 months ago, # |   0 Can someone tell why solution with Dijkstra doesn't work in Div2E: 77912522?
 » 15 months ago, # |   +13 Hi, can you reopen the original Editorial for Problem E? It is still make sense since there are lots of dicussion about it.
 » 15 months ago, # |   0 Can someone suggest alternative non-analytical solution for DIV2, problem A?
 » 15 months ago, # |   0 Can anyone explain the solution of div2 E, any a way to tackle such kind of questions
 » 15 months ago, # |   0 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 #637https://codeforces.com/contest/1341/submission/78051371
 » 15 months ago, # |   0 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
 » 15 months ago, # |   0 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??
 » 15 months ago, # |   0 Would anyone like to talk about how to maintain each prefix in a treap? Thanks!
 » 15 months ago, # |   0 Can anyone explain why dp[n + 1][0] = 0; is done in the code /** * author: tourist * created: 23.04.2020 17:45:43 **/ #include using namespace std; vector 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 s(n); vector> dist(n, vector(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> dp(n + 1, vector(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; } 
 » 15 months ago, # |   0 lol, really.... solution of tourist and poor text description for Div2D have nothing in common.. except both are dp
 » 15 months ago, # | ← Rev. 3 →   0 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.
•  » » 15 months ago, # ^ |   0 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.
•  » » 15 months ago, # ^ |   0 Here is my solution 78450668, you can check it out.
•  » » » 15 months ago, # ^ |   0 Thank you so much for the help!!
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 15 months ago, # ^ | ← Rev. 3 →   0 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.
 » 15 months ago, # |   0 I am only able to understand editorial for 1341F — Nastya and Time Machine partially. Can anyone explain it in more detail..
 » 15 months ago, # | ← Rev. 2 →   +3 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!
»
15 months ago, # |
0

# 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;

}

•  » » 15 months ago, # ^ |   0 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 
•  » » » 14 months ago, # ^ |   0 can u explain how can i get any weight of all grains from n(a−b) to n(a+b) ?
 » 15 months ago, # |   0 could someone be helpful and point out where i have made mistake in Div 2 D Thanks in advance https://ideone.com/qBBfH5
 » 15 months ago, # |   0 Couldn't understand the editorial for Div2-D. Can someone explain?
 » 15 months ago, # |   0 Can anyone explain Div 2E ?
 » 15 months ago, # |   0 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.
•  » » 15 months ago, # ^ |   0 is it your phone number
•  » » » 15 months ago, # ^ |   0 No, that's my query
•  » » » » 15 months ago, # ^ |   0 off course i know it was just a joke
•  » » » » » 15 months ago, # ^ |   0 Can you answer the query?
 » 15 months ago, # |   0 Nastya and Time MachineFor 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'?
 » 14 months ago, # | ← Rev. 2 →   0 [Deleted] because I am stupid.
 » 14 months ago, # |   -8 Editorial of Div2D is bad. Next time just don't write anything.
»
14 months ago, # |
Rev. 3   0

//B.Natsya and Door

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

 » 13 months ago, # |   0 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?
 » 13 months ago, # |   0 I thought Problem D is really Tough.Until I saw its editorial.And realized the editorial is tougher than the problem itself! :/ xD
 » 13 months ago, # | ← Rev. 3 →   0 EASY EDITORIAL OF D AND PERSONAL THOUGHTS AS WHY THIS EDITORIAL SUCKS! Personal Thoughts as Why This Editorial Sucks!My thoughts are Limited to Problem D.(and a bit far...)As I've spent pretty much my last 8 hours on Problem D (And I still couldn't come up the bottom up dp solution like Editorial's aka Tourist's.) Editorial lacks proofs and explanation of Problem D. What dp[i][j] isn't clearly specified. How can you expect a beginner to make a dp[][] table when he doesn't know what dp[i][j] Represents? The code for D is just Tourist's Solution. Now, as a beginner it's impossible (Personal Experience) to understand what a Leg. GrandMaster coded during a Live Contest. The code: It's just too complex and messy. No proper Explanation. But that's Okay because you can't expect anyone to write an explainable code during a contest. It's just not Editorial Material. 5.What I saw, was that Div1-E was incorrect in some ways. But thats Okay here, I guess, since we're far from Div-1 E. C'mon it just sucks and you know it! (Also editorial blogs rarely have -ve votes!) Approach for Problem D: 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) 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
•  » » 9 months ago, # ^ |   0 Nice Solution!
 » 13 months ago, # |   0 I tried Dijkstra on DIV2E/DIV1C and get TLE on test 76
 » 11 months ago, # |   0 In problem Div1-A or Div2-C we can check if p[i+1]-p[i]>1 then print No otherwise print Yes. https://codeforces.com/contest/1340/submission/91719645
 » 7 months ago, # |   0 I have a query about the problem 1341A.(natsya and rice)if the two ranges of the weights intersect, only then the answer can be a YES. If any of the two weight bounds of the grain i.e. n*(a-b) or n*(a+b) lie in between the range of the package weight, it's enough for the intersection. But the solution that I implemented shows up an error on test case#2.for i in range(int(input())): n,a,b,c,d= map(int,input().split()) if (n*(a-b) >=(c-d) and n*(a-b) <= (c+d)) or (n*(a+b) >=(c-d) and n*(a+b) <= (c+d)): print("YES") else: print("NO")`this was the code that I submitted, i simply checked if either of the grain weights lie in between.I need help in understanding what went wrong with logic that i used to solve it..
 » 4 months ago, # |   0 Unusual,Boring,Quite lengthy statement in problem "C".I have read it for more than 5 times but still I couldn't understand the statement.