include

5 years ago, # ^ |

Fixed

→ Reply

Mikemirzyanov1

5 years ago, # |

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

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

→ Reply

striver_79

5 years ago, # ^ |

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

→ Reply

Mikemirzyanov1

5 years ago, # ^ |

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

→ Reply

striver_79

5 years ago, # ^ |

← Rev. 3 →

-13

I have made a video on the same, checkout the first comment, might help you.

→ Reply

guimafelipe

5 years ago, # ^ |

It is possible. I did it recursively. You can check out my submission if it helps :)

→ Reply

epsilon_573

5 years ago, # ^ |

← Rev. 2 →

My solution using recursion and memorization.

→ Reply

ScaryTerry

5 years ago, # ^ |

Yes, here is my solution

→ Reply

5 years ago, # ^ |

o(n) solution

→ Reply

PRESS_F_2_PAY_RESPECT

5 years ago, # |

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

→ Reply

RollBack

5 years ago, # |

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

→ Reply

LazyPrime

5 years ago, # ^ |

← Rev. 3 →

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

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

→ Reply

TimeTraveler

5 years ago, # ^ |

← Rev. 3 →

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

→ Reply

Pallove

5 years ago, # ^ |

← Rev. 2 →

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

→ Reply

YPK

5 years ago, # ^ |

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

→ Reply

Kostroma

5 years 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.

→ Reply

5 years ago, # ^ |

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

→ Reply

Kostroma

5 years 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.

→ Reply

5 years 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.

→ Reply

5 years ago, # ^ |

-153

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

→ Reply

5 years 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.

→ Reply

5 years 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 locally

judge: 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)

→ Reply

5 years 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$$$).

→ Reply

5 years 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:

→ Reply

5 years ago, # ^ |

-27

Oh... I will try to solve this problem too...

→ Reply

Radewoosh

5 years ago, # ^ |

+53

→ Reply

5 years ago, # ^ |

+89

→ Reply

Radewoosh

5 years ago, # ^ |

+268

Hey, don't worry, shit happens. For sure it'll be better next time ;)

→ Reply

5 years ago, # ^ |

+32

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

→ Reply

5 years 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)

→ Reply

5 years 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.

→ Reply

5 years 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$$$.

→ Reply

5 years 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.

→ Reply

5 years 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.)

→ Reply

5 years 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!)

→ Reply

Philae

5 years 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://mirror.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.

→ Reply

TimonKnigge

5 years 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.

→ Reply

Errichto

5 years 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.

→ Reply

5 years ago, # ^ |

-33

We made standard 3TL from author's solution.

→ Reply

Errichto

5 years 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})$$$

→ Reply

gagannagpal68

5 years ago, # ^ |

Why geometric ?

→ Reply

Errichto

5 years ago, # ^ |

+44

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

→ Reply

5 years ago, # ^ |

+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

→ Reply

falconlover

5 years 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

→ Reply

Vintarel

5 years ago, # ^ |

← Rev. 2 →

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

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

repn(i,10){
        if(s[i]=='1' and t[i]=='0'){

→ Reply

gouravraj

5 years ago, # ^ |

Help required in this solution Solution

→ Reply

Vintarel

5 years ago, # ^ |

→ Reply

https://mirror.codeforces.com/contest/1341/submission/77830430

5 years ago, # ^ |

← Rev. 2 →

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

==52205== Conditional jump or move depends on uninitialised value(s)
==52205==    at 0x40143E: calc(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, long long) (b-other.cpp:24)
==52205==    by 0x400E52: main (b-other.cpp:47)

→ Reply

TimonKnigge

5 years 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.)

→ Reply

TimonKnigge

5 years 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.

→ Reply

cuber_coder

5 years 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?

→ Reply

i_64

5 years ago, # |

+11

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.

→ Reply

sodic

5 years ago, # |

← Rev. 3 →

+28

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

→ Reply

aditya314

5 years ago, # ^ |

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

→ Reply

doubleux

5 years ago, # ^ |

← Rev. 2 →

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

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

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

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

→ Reply

r57shell

5 years ago, # ^ |

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

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

(notice all of this is completely deterministic)

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

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

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

→ Reply

r57shell

5 years ago, # |

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

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

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

Source: 77903961

→ Reply

Bhj2001

5 years ago, # ^ |

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

→ Reply

r57shell

5 years ago, # ^ |

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

→ Reply

sthfaceless

5 years ago, # |

Another solution for Div2-D/Div1-B 77915468

→ Reply

dikki99

5 years ago, # |

-60

include

include<math.h>

using namespace std;

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

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

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

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

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

→ Reply

anshuman.singh

5 years ago, # ^ |

← Rev. 2 →

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

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

→ Reply

Harirai

5 years ago, # |

+17

For Div2 C, My solution was

For any i, from 0 to n-1,

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

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

Can anyone prove why this is correct?

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

→ Reply

doubleux

5 years ago, # ^ |

You can check Here

→ Reply

Elegia

5 years 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.

→ Reply

supriyanta

5 years ago, # |

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

→ Reply

JOF

5 years ago, # ^ |

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

→ Reply

supriyanta

5 years ago, # ^ |

Thanks, got it!

→ Reply

aviral0807

5 years ago, # ^ |

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

→ Reply

JOF

5 years ago, # ^ |

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

→ Reply

Ahmed_Salama

5 years ago, # ^ |

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

Adding it to my template for sure! :D

→ Reply

ajayNegi

5 years ago, # ^ |

← Rev. 2 →

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

→ Reply

JOF

5 years ago, # ^ |

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

→ Reply

_pastor_

5 years ago, # |

-16

what is testcase 7 for div 2 D problem

→ Reply

rain_star

5 years ago, # |

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

→ Reply

fishlicker

5 years ago, # ^ |

← Rev. 2 →

This is a better explanation: https://mirror.codeforces.com/blog/entry/22276

→ Reply

rain_star

5 years ago, # ^ |

It's a nice tutorial.Thank you!

→ Reply

Ankur1999

5 years ago, # |

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

→ Reply

PinkRabbitAFO

5 years ago, # |

+97

Problem Div1D Nastya and Time Machine is very beautiful!

→ Reply

5 years 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.

→ Reply

ksun48

5 years 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.

→ Reply

5 years ago, # ^ |

makes sense, thanks!

→ Reply

Mcayitel

5 years 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.

→ Reply

5 years ago, # ^ |

Try this case

1
4
4 2 1 3

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

→ Reply

utsavparakhiya

5 years ago, # |

-11

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

→ Reply

5 years ago, # |

← Rev. 3 →

O(n) solution for div2-D : solution

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

← Rev. 2 →

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

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

nevermind..got TLE

→ Reply

5 years ago, # ^ |

I made one, see 78055034

→ Reply

5 years ago, # ^ |

well done, but now you have O(nk) ..basically the solution from the editorial :))

→ Reply

5 years ago, # ^ |

this is my attempt

→ Reply

shashack

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

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.

→ Reply

dorijanlendvaj

5 years ago, # ^ |

← Rev. 2 →

+11

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

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

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

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

→ Reply

ayonsen

5 years ago, # |

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://mirror.codeforces.com/contest/1341/submission/77953400

→ Reply

5 years ago, # ^ |

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

→ Reply

Kritagya_khandelwal

5 years ago, # |

-28

for 1341C — Nastya and Strange Generator, I have a better approach. https://mirror.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;
}

→ Reply

yogi

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

what is backtracking skill...i am new to programming can you please tell

→ Reply

yogi

5 years ago, # ^ |

Here you go

→ Reply

https://mirror.codeforces.com/contest/1341/submission/78051371

5 years ago, # ^ |

thank you so much

→ Reply

__RaiyaN__

5 years ago, # |

← Rev. 2 →

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

→ Reply

gaurav1903

5 years ago, # |

+14

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

→ Reply

anvexior

5 years ago, # |

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

→ Reply

Vladosiya

5 years ago, # |

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

→ Reply

Little_Sheep_Yawn

15 months ago, # ^ |

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

→ Reply

MinakoKojima

5 years 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.

→ Reply

R-d-G

5 years ago, # |

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

→ Reply

RobeZH

5 years ago, # |

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

→ Reply

prajwlr

5 years ago, # |

← Rev. 3 →

Help needed in Div2D/Div1B!

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

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

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

→ Reply

5 years ago, # ^ |

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

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

→ Reply

5 years ago, # ^ |

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

→ Reply

prajwlr

5 years ago, # ^ |

Thank you so much for the help!!

→ Reply

prajwlr

5 years ago, # ^ |

← Rev. 2 →

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

→ Reply

5 years ago, # ^ |

← Rev. 3 →

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

→ Reply

failed_coder

5 years ago, # |

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

→ Reply

tarunlahrod

5 years ago, # |

← Rev. 2 →

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

→ Reply

Rahul_Negi

5 years ago, # |

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

include <stdio.h>

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

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

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

}

→ Reply

thesoulreaper

5 years ago, # ^ |

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

n = 2
a = 2
b = 1
c = 5
d = 0

→ Reply

stellea

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

is it your phone number

→ Reply

stellea

5 years ago, # ^ |

No, that's my query

→ Reply