Codeforces functionality may be limited from June 18, 19:00 (UTC) to June 19, 3:00 AM (UTC) due to technical maintenance. Polygon will work as usual. ×

### mnbvmar's blog

By mnbvmar, 5 years ago,

This is the preliminary version of editorial. Expect bugs. Some changes might happen!

1150A. Stock Arbitraging

Tutorial

1150B. Tiling Challenge

Tutorial

Tutorial

Tutorial

Tutorial

Tutorial
Challenges

1149E. Election Promises

Tutorial
• +258

| Write comment?
 » 5 years ago, # |   0 Pretest for B were weak :(
•  » » 5 years ago, # ^ | ← Rev. 2 →   -14 a,b,c Div 2 pretests were weak(
•  » » » 5 years ago, # ^ |   +11 for div1 C it was strong
•  » » » 5 years ago, # ^ |   +21 for div 1 D it was strong
 » 5 years ago, # |   +13 Thank you for a lightning fast editorial.What was that sudden increase in difficulty curve from problem C to D (Div. 2)?
 » 5 years ago, # |   +1 Please, add author solution too :(
•  » » 5 years ago, # ^ |   +68 I'll do it tomorrow, I'm too tired to even look at my screen now. :)
•  » » » 5 years ago, # ^ |   +19 Have a good rest man
•  » » » 5 years ago, # ^ |   +2 thanks for the problems you write,good job,man
•  » » 5 years ago, # ^ |   +6 Done!
 » 5 years ago, # |   -12 I think that, at least, main tests 37 and 40 for Div2B should have been in the pretests.
 » 5 years ago, # | ← Rev. 2 →   +8 Can someone help me find a counterexample to the following logic in div1 D: Find connected components if we use a-edges only Discard all b-edges with ends in the same component In the remaining graph, find shortest path from 0 to each p that uses minimum number of b-edges
•  » » 5 years ago, # ^ |   0 I'm trying to figure out this myself :/
•  » » 5 years ago, # ^ |   +35 If I understand you correctly, this should be a small counterexample for $a=2$, $b=3$. The dotted lines are heavier, solid lines are lighter:You can go from $1$ to $5$ using two heavy edges ($1 \to 2 \to 5$, cost $6$), which is more optimal than using one heavy edge ($1 \to 3 \to 4 \to 5$, cost $7$).
•  » » 5 years ago, # ^ | ← Rev. 3 →   +10 UPD: Deleted, sorry
 » 5 years ago, # |   +5 The contest had quite an interesting difficulty distribution. Problem B took quite a bit of time to implement (the solution was extremely simple, though) where C was absolute lolly and D had only 35+ solve in contest time (a little better in the Div 1 version, probably 50+).One other thing, there's a spelling mistake in the problem B name. You missed an 'l'. :pThanks for the super fast editorial.
•  » » 5 years ago, # ^ |   +4 One other thing, there's a spelling mistake in the problem B name. You missed an 'l'. :p Fixed! shame on me
 » 5 years ago, # |   0 In Div1.C, you wrote that $δ \text{ (the final depth, might be non-zero)}$. Maybe it is more clear to say that $δ$ is the total depth change in that block?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 RobeZH Can you please example a bit more clearly what δ means and how it is used?
 » 5 years ago, # |   +97 Challenge to D about 2^o(n) solutionKeep in state last $\sqrt{n}$ b-edges (or a-components of any size) used and mask of used components bigger than $\sqrt{n}$. That way we get $2^{O(\sqrt{n} \log{n})}$, which can even be slightly improved to $2^{O(\sqrt{n \log{n}})}$. Key insight here is that if we have small a-component (say 10) then we need to care only about possible forbidden connections using at most 8 b-edges between its endpoints.
•  » » 5 years ago, # ^ |   +6 Yup, absolutely correct!
 » 5 years ago, # | ← Rev. 2 →   +3 Can't div2 D be solved searching by searching subsequence (using precalculated positions for each symbol) and marking them as used? We have 6 order varinats to search subsequences: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). It goes into $O(q \cdot 250 \cdot 6)$, but algorithm looks like not work :(my try
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Try this testcase: The Word of Universe is "abadadab", and there are two religions in that moment. Their descriptions are "abab" and "adad".
•  » » 5 years ago, # ^ |   0 the long word "abcbdefe", and two subsequences "abef", "bcde"
•  » » 5 years ago, # ^ |   0 I think it can be implemented properly with some backtracking, but not sure how that affects the complexity.
 » 5 years ago, # |   0 Div2 D is a nice problem,though i didn't solve it during contest.. (also got fst on C..nooo..)
 » 5 years ago, # | ← Rev. 2 →   +22 For D, during contest I didn't realize we can ignore components of size $3$, so I had a higher complexity and with no optimizations my solution would get TLE. With the following heuristic I was able to pass main tests: in Dijkstra, if the shortest path from $1$ to $i$ is $2$(I used $4$ in contest but $2$ also passes main tests, interesingly $1.99$ doesn't pass) times shorter than the shortest path from $1$ to $i$ with some $mask$, ignore this $(i, mask)$ state. Can someone prove that this works or find a countercase?
 » 5 years ago, # |   0 I don't understand why in B div1 you obtain the shortest prefix in that way. Why can't you choose a character from the same prefix? Why is it always making the prefix bigger, what if there is a character that we can use in the current prefix?
 » 5 years ago, # |   +2 Can somebody please explain the solution for Div2D? What exactly are we doing in the DP part? Thank You
 » 5 years ago, # |   +1 Just a little request to all the coders who conduct the rounds try to please explain the editorial with the help of examples. I know this will take little bit of your extra time but it will help us how you approach the given problem. Example there are lot of people who are not able to understand the editorial of question D but if you try to explain us with the help of an example they will understand better. It's up to you guys but please think this once. It will help us to learn more and save our time. Thankyou Happy coding.
•  » » 5 years ago, # ^ |   +10 If I find some free time this week, I'll try to rewrite this editorial, e.g. to include some examples or write the explicit DP transitions.I even thought about writing some interactive app where you could fiddle with the inputs and see how DP states change, but it's imho quite time-consuming. No promises for this one, then.
 » 5 years ago, # |   0 The solution to div1 D is really beautiful
 » 5 years ago, # |   +18 Can anyone prove that Div1D is NP-hard ? I might learn some way to deal with that type of problem to avoid some unnecessary ideas.
•  » » 5 years ago, # ^ |   +27 As nobody published their proof, let's go with mine: ReductionWe're reducing from Hamiltonian-Path. We're given a directed graph $G$ consisting of $n$ vertices: $1, 2, \dots, n$. We want to test if there's a Hamiltonian path in $G$.Let $a=2$, $b=3$, and construct an instance of our problem consisting of $n(2n-1) + 2$ vertices: $s$ (source), $t$ (sink), and $n$ paths $P_1, \dots, P_n$, each having $2n-1$ vertices: $P_{i,1}, P_{i,2}, \dots, P_{i,2n-1}$. Each of the path is constructed using light edges only.For each edge $u \to v$ in the original graph, add $n-1$ heavy edges to our instance: $P_{u,1} \leftrightarrow P_{v,3}$, $P_{u,3} \leftrightarrow P_{v,5}$, $\dots$, $P_{u,2n-3} \leftrightarrow P_{v,2n-1}$. Add also some heavy edges connecting source and sink with the path: connect the source $s$ with first vertices $P_{i, 1}$ of each path, and the sink $t$ with final vertices $P_{i,2n-1}$ of each path.Now, one can prove that the minimum distance from $s$ to $t$ in our instance is equal to $b(n+1)$ if and only if $G$ contains a Hamiltonian path. (It's an easy exercise for the reader.)On that note, I think probably nobody solving the problem actually proved that the problem is NP-complete — I guess they had some sort of intuition that they shouldn't be able to solve it in polynomial time.
 » 5 years ago, # |   0 Could someone elaborate more on the solution to Div2 D/Div 1 B. I don't quite understand how we can use the helper array to check for a valid construction without keeping an index to the Words Of Universe string in our dp.
 » 5 years ago, # |   0 Could anyone recommend a good textbook about some advanced game theory (with all that ordinal nimbers, hackerbushes etc)?
•  » » 5 years ago, # ^ |   0 Surreal Number? That's so difficult. :( Bad memory to me, I know little about it until now.
 » 5 years ago, # |   0 For div1-D I implemented this code using a priority queue. This is tutorials logic. And took 639ms.But when I implemented same logic using a single normal queue it took 280ms. ( My code ).Can any one tell me why without priority queue Dijkstra working much faster. Please help me to understand the complexity for 2nd code ( without priority queue ) . I understood the complexity of the 1st code ( with priority queue ).
 » 5 years ago, # |   0 I think the transition has problem:when string is : "abdabc" , and then the s[0] is "ad", the s[1] is"b",s[2] is empty,the dp[2][1][0] should be 4 but the program show the dp[2][1][0] is 2,and the problem is caused by the wrong transition:dp[1][1][0] can not update the dp[2][1][0] by just using the helper arry
 » 5 years ago, # |   0 I can hack you with the following data:the origin string is "abd",3 operations + 1 a + 1 d + 2 b the answer should be YES YES NO but yours is YES YES YES
 » 5 years ago, # |   0 emmmm.... I misunderstand the problem,sorry