### mnbvmar's blog

By mnbvmar, 3 weeks 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

•
• +250
•

 » 3 weeks ago, # |   0 Pretest for B were weak :(
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   -9 Yes, I didn't cater one case where we might have some dot lefts in grid.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   -14 a,b,c Div 2 pretests were weak(
•  » » » 3 weeks ago, # ^ |   +11 for div1 C it was strong
•  » » » 3 weeks ago, # ^ |   +21 for div 1 D it was strong
 » 3 weeks ago, # |   +13 Thank you for a lightning fast editorial.What was that sudden increase in difficulty curve from problem C to D (Div. 2)?
 » 3 weeks ago, # |   +1 Please, add author solution too :(
•  » » 3 weeks ago, # ^ |   +68 I'll do it tomorrow, I'm too tired to even look at my screen now. :)
•  » » » 3 weeks ago, # ^ |   +19 Have a good rest man
•  » » » 3 weeks ago, # ^ |   +2 thanks for the problems you write,good job,man
•  » » 3 weeks ago, # ^ |   +6 Done!
 » 3 weeks ago, # |   -12 I think that, at least, main tests 37 and 40 for Div2B should have been in the pretests.
 » 3 weeks 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
•  » » 3 weeks ago, # ^ |   0 I'm trying to figure out this myself :/
•  » » 3 weeks 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$).
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +10 UPD: Deleted, sorry
 » 3 weeks 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.
•  » » 3 weeks ago, # ^ |   +4 One other thing, there's a spelling mistake in the problem B name. You missed an 'l'. :p Fixed! shame on me
 » 3 weeks 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?
•  » » 7 days ago, # ^ | ← Rev. 2 →   0 RobeZH Can you please example a bit more clearly what δ means and how it is used?
 » 3 weeks 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.
•  » » 3 weeks ago, # ^ |   +6 Yup, absolutely correct!
 » 3 weeks 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
•  » » 3 weeks 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".
•  » » 3 weeks ago, # ^ |   0 the long word "abcbdefe", and two subsequences "abef", "bcde"
•  » » 3 weeks ago, # ^ |   0 I think it can be implemented properly with some backtracking, but not sure how that affects the complexity.
 » 3 weeks ago, # |   0 Div2 D is a nice problem,though i didn't solve it during contest.. (also got fst on C..nooo..)
 » 3 weeks 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?
 » 3 weeks 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?
 » 3 weeks ago, # |   +2 Can somebody please explain the solution for Div2D? What exactly are we doing in the DP part? Thank You
 » 3 weeks 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.
•  » » 3 weeks 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.
 » 3 weeks ago, # |   0 The solution to div1 D is really beautiful
 » 3 weeks 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.
•  » » 3 weeks 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.
 » 3 weeks 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.
 » 3 weeks ago, # |   0 Could anyone recommend a good textbook about some advanced game theory (with all that ordinal nimbers, hackerbushes etc)?
 » 4 days 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 ).