This is the preliminary version of editorial. Expect bugs. Some changes might happen!
Tutorial
Code
Tutorial
Code
1150C / 1149A. Prefix Sum Primes
Tutorial
Code
1150D / 1149B. Three Religions
Tutorial
Code
1150E / 1149C. Tree Generator™
Tutorial
Code
Tutorial
Code
Challenges
Tutorial
Code
Pretest for B were weak :(
a,b,c Div 2 pretests were weak(
for div1 C it was strong
for div 1 D it was strong
Thank you for a lightning fast editorial.
What was that sudden increase in difficulty curve from problem C to D (Div. 2)?
Please, add author solution too :(
I'll do it tomorrow, I'm too tired to even look at my screen now. :)
Have a good rest man
thanks for the problems you write,good job,man
Done!
I think that, at least, main tests 37 and 40 for Div2B should have been in the pretests.
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
I'm trying to figure out this myself :/
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$$$).
UPD: Deleted, sorry
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'. :p
Thanks for the super fast editorial.
Fixed! shame on me
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?
RobeZH Can you please example a bit more clearly what δ means and how it is used?
Keep 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.
Yup, absolutely correct!
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
Try this testcase: The Word of Universe is "abadadab", and there are two religions in that moment. Their descriptions are "abab" and "adad".
the long word "abcbdefe", and two subsequences "abef", "bcde"
I think it can be implemented properly with some backtracking, but not sure how that affects the complexity.
Div2 D is a nice problem,though i didn't solve it during contest.. (also got fst on C..nooo..)
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?
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?
Can somebody please explain the solution for Div2D? What exactly are we doing in the DP part? Thank You
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.
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.
The solution to div1 D is really beautiful
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.
As nobody published their proof, let's go with mine:
We'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.
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.
Could anyone recommend a good textbook about some advanced game theory (with all that ordinal nimbers, hackerbushes etc)?
Surreal Number? That's so difficult. :( Bad memory to me, I know little about it until now.
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 ).
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
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
emmmm.... I misunderstand the problem,sorry